Loading...
Please wait, while we are loading the content...
Similar Documents
CSE 599 b : Cryptography ( Winter 2006 ) Lecture 6 : Collections of One-way Functions ; Candidates 20 January 2006
| Content Provider | Semantic Scholar |
|---|---|
| Author | Beame, Paul |
| Copyright Year | 2006 |
| Abstract | (0) Sampling: – There is a PPT CI that on input 1 produces an element of I ∩ {0, 1}. – There is a PPT CD that on input i ∈ I produces an element of Di. Note that neither CI nor CD is required to be uniform (or even have support that is all of I ∩ {0, 1} or Di respectively) so all we need is that CI and CD choose elements from the appropriate sets. (1) Easy to Compute: There is a deterministic polynomial-time algorithm F that on input i ∈ I and x ∈ Di computes fi(x). (2) Hard to Invert: For all PPT A the function is negligible for (n) = Pr[A(fi(x), i) ∈ f−1 i (fi(x)) | i← CI(1); x← CD(i)]. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://courses.cs.washington.edu/courses/cse599b/06wi/lecture6.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
