מדעי המחשב
אוניברסיטת תל אביב
Computer Science
Tel-Aviv University

הוכחות אפס מידע

Zero knowledge proofs

0368-4152-01.

Lectures:

Meetings:

Amnon Ta-Shma

Sunday, 12:10-15:00.

אמנון תא-שמע

יום ראשון בשעות 12:10-15

תוכנה 1, אלגוריתמים, סיבוכיות.

פתוח לתלמידי תואר ראשון

לפי בחינה.

תהיה אפשרות בסוף הקורס להציג מאמר במקום בחינה

תרגילים (ללא חובת הגשה).

תרגיל מס. 1

תרגיל מס 2

Salil Vadhan, A study of statistical zero knowledge.

Papers:

1. O. Goldreich, Candidate One-Way Functions Based on Expander Graphs, 2000.

2. O. Goldreich and S. Goldwasser, On the possibility of basing Cryptography on the assumption that P neq NP, Feb. 1998.

3. Rafail Ostrovsky. One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs. STRUCTURES 1991, pp. 51-59.

4. O. Goldreich, E Kushilevitz, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm Journal of cryptology 6:22, 97-116, 1993.

5. O. Goldreich and H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM journal on Computing, 25 (1): 169-192, Feb 1996.

6. Shien Jin Ong, Salil Vadhan, Zero Knowledge and Soundness are Symmetric. ECCC TR06-139

7. O. Goldreich, The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.

8. M. Nguyen, S. Vadhan. Zero Knowledge with Efficient Provers.
   STOC `06.

9. S. Vadhan. An Unconditional Study of Computational Zero Knowledge.
   FOCS `04. ECCC `06.  SICOMP `06.

10. S. Sanghvi, S. Vadhan. The Round Complexity of Two-Party Random Selection. STOC `05. ECCC `05. SICOMP `06

11. O. Goldreich, and S. Goldwasser, On the Limits of Non-Approximability of Lattice Problems. STOC 1998.

12. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP-hardness. STOC 2006, pages 701-710.

13. R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali. Resettable Zero Knowledge. STOC 2000, pages 235-244.

14. Chapter on NISZK from Salil's thesis.

תאריך

אין פגישה.

22.12.06

הוכחות אינטראקטיביות. המחלקה HV-SZK. הוכחות אפס מידע ל GISO ו GNISO.

29.10.06

SD היא ב HV-SZK כל עוד a^2>b.

5.11.06

אנטרופיה. בניה של אקסטרקטורים מ2-universal hash functions. הבעיה FED היא ב HVSZK.

12.11.06

הבעיה ED היא ב HVSZK. הבעיה coSD היא public-coin-HVSZK קשה.

19.11.06

Relative entropy. הבעיה ED היא בעיה HVSZK שלמה.הדגמה עם שוויון של DLOG. המחלקה HVSZK סגורה תחת משלים.

26.11.06

המחלקה HVSZK מוכלת ב promise(AM intersect coAM .על בעיות הבטחה ושפות. אםNP מוכל ב coAM אז ההרכיה מתמוטטת. דוגמא לרדוקצית Turing מ SAT לבעיה ב promise(NP intersec coNP .

HVSZK סגורה תחת נוסחאות בוליאניות

3.12.06

מטבעות פומביים וסודיים - המקרה של התפלגות שאלות שטוחה

10.12.06

אין פגישה. חנוכה. לא יתקיים שיעור.

17.12.06

מטבעות פומביים וסודיים - המקרה של התפלגות שאלות לא שטוחה. The pushing game.

24.12.06

מטבעות פומביים וסודיים - המקרה של התפלגות שאלות לא שטוחה.

OWF, distributional OWF, SZK hard on average implies OWF.

31.12.06

הוכחות אפס מידע מול בודקים לא הוגנים. הגדרות. Random selection

7.01.07

Random selection מספיק כדי להתמודד עם בודקים לא הוכנים. מדוע לא ניתן להטיל מטבע הוגן בין שני שחקנים. פרוטוקול הRandom selectio. הוכחת תת-הפרוטוקול של שלושת הסיבןבים הראשונים. (DGW). בנית גרף מתאים עבור DGW.

14.01.07

לא התקיים שיעור בגלל השביתה

21.01.07

הוכחת הסימולטור עבור פרוטוקול ה Random selection.

28.01.07

Zero knowledge proofs allow proving theorems without revealing any information beyond the theorem correctness. The study of such proofs has relationship both to complexity and cryptography.

We will be mostly following Salil Vadhan's P.hD. thesis, "A study of statistical zero knowledge proofs". Among the results we will see are:

- Natural complete problems for the class.
- SZK is in PH .
- SZK is closed under complement.

- Public vs. private coins
- Honest verifier vs. dishonest verifier proofs.
- The relationship between SZK and one way functions.

and more. We will encounter and use useful tools like hash techniques, extractors, dispersers, piar-wise indepndencr, t-wise independence, information theory results, and others.