Master’s Thesis Presentation • Algorithms and Complexity — Privately Constrained Testable Pseudorandom FunctionExport this event to calendar

Thursday, September 13, 2018 — 12:33 PM EDT

Filip Pawlega, Master’s candidate
David R. Cheriton School of Computer Science

Privately Constrained Pseudorandom Functions allow a PRF key to be delegated to some evaluator in a constrained manner, such that the key's functionality is restricted with respect to some secret predicate. Variants of Privately Constrained Pseudorandom Functions have been applied to rich applications such as Broadcast Encryption, and Secret-key Functional Encryption. Recently, this primitive has also been instantiated from standard assumptions. We extend its functionality to a new tool we call Privately Constrained Testable Pseudorandom functions.

For any predicate C, the holder of a secret key sk can produce a delegatable key constrained on C denoted as sk[C]. Evaluations on inputs x produced using the constrained key differ from unconstrained evaluations with respect to the result of C(x). Given an output y evaluated using sk[C], the holder of the unconstrained key sk can verify whether the input x used to produce y satisfied the predicate C. That is, given y, they learn whether C(x) = 1 without needing to evaluate the predicate themselves, and without requiring the original input x.

We define two inequivalent security models for this new primitive, a stronger indistinguishability-based definition, and a weaker simulation-based definition. Under the indistinguishability-based definition, we show the new primitive implies Designated-Verifier Non-Interactive Zero-Knowledge Arguments for NP in a black-box manner. Under the simulation-based definition, we construct a provably secure instantiation of the primitive from lattice assumptions. We leave the study of the gap between definitions, and discovering techniques to reconcile it as future work.

Location 
DC - William G. Davis Computer Research Centre
2585
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (212)
    1. December (1)
    2. November (4)
    3. October (14)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  2. 2018 (220)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (22)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  3. 2017 (36)
  4. 2016 (21)
  5. 2015 (36)
  6. 2014 (33)
  7. 2013 (23)
  8. 2012 (4)
  9. 2011 (1)
  10. 2010 (1)
  11. 2009 (1)
  12. 2008 (1)