Security Protocols (Advanced Topics in Cryptology)

Spring 2008

General Information

Instructor

Sorin Iftene

Office: C301

E-mail: siftene@info.uaic.ro

Tel: (0232) 201538

Class Time and Location

Monday, from 16:00 to 18:00, in C309

Announcements

The seminar from May 2 is rescheduled on May 19 (C309, 16:00 – 18:00)

The seminar from April 25 is rescheduled on April 23 (C112, 18:00 – 20:00)

Course Objectives

This course will cover some of the latest cryptographic techniques for security protocols. This course intends to stimulate

students in their own research - improve their ability of extracting, presenting, and discussing results from recent papers

on a certain topic and try to extend/improve them.

Course Outline

Basics in cryptology - cryptosystems, digital signatures, (keyed) hash functions

Secret sharing

Threshold cryptography

Lattice-based cryptography

Elliptic curve cryptography

Oblivious transfer

Private information retrieval. Secure keyword search

Zero-knowledge proofs

Secure multiparty computations (case studies: set intersection, e-auction, e-voting)

E-voting based on mix-nets

Pairing-based cryptography. Identity based encryption

Seminar Content

Efficient arithmetic for cryptography

Discrete logarithm algorithms

More secret sharing - weighted, compartmented, hierarchical

Additional capabilities in secret sharing (dealer-free, composability, changeability)

Student Presentation Topics (tentative list)

Cryptosystems based on theory of formal languages

Signcryption

Broadcast encryption. Tracing traitors

Digital signatures with additional capabilities

on-line/off-line signatures

undeniable signatures

designated confirmer signatures

fail-stop signatures

one-time signatures

forward-secure digital signatures

group signatures

ring signatures

proxy signatures

delegateable signatures

list signatures

aggregate signatures

chameleon signatures

Credential systems

Exposure resilient cryptography

Key escrow

Commitment schemes

Fair exchange

Coin flipping

Deniable encryption

Computation with encrypted inputs

Conditional oblivious transfer

Distributed oblivious transfer

Oblivious polynomial evaluation

Oblivious transfer with adaptive queries

Search on encrypted data

Password management

Incremental cryptography

Visual cryptography

Micropayments

E-lotteries

Lectures

1. Basics in cryptology – symmetric cryptosystems, public-key cryptosystems, digital signatures, (keyed) hash functions (February 18)

References

· Chapter 1 of Handbook of Applied Cryptography (by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone)

· Seminar - Efficient arithmetic for cryptography- Chapter 14 of Handbook of Applied Cryptography

2. Secret sharing – access structures, models for secret sharing, threshold secret sharing schemes (Shamir’s scheme, Asmuth-Bloom scheme), general secret sharing schemes (schemes based on cumulative maps, schemes based on formula templates) (February 25)

References

· A. Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979

· C. A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208–210, 1983

· H. Ghodosi, J. Pieprzyk, R. Safavi-Naini, and H. Wang. On construction of cumulative secret sharing schemes.

In C. Boyd and E. Dawson, editors, ACISP ’98: Proceedings of the Third Australasian Conference on Information Security and Privacy, volume 1438 of Lecture Notes in Computer Science, pages 379–390. Springer-Verlag, 1998

· J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In S. Goldwasser, editor, Advanced in Cryptology-CRYPTO’ 88, volume 403 of Lecture Notes in Computer Science, pages 27–35. Springer-Verlag, 1989

· Seminar - Discrete logarithm problem - A. M. Odlyzko. Discrete logarithms: The past and the future. Designs, Codes, and Cryptography 19 (2000), pp. 129-145. Reprinted in Towards a Quarter-Century of Public Key Cryptography, N. Koblitz, ed., Kluwer, 2000, pp. 59-75

3. Verifiable secret sharing. Threshold cryptography (March 3)

References

· P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, pages 427–437. IEEE Press, 1987

· T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology - CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 129–140. Springer-Verlag, 1992

· Y. Desmedt and Y. Frankel. Threshold cryptosystems. In G. Brassard, editor, Advances in Cryptology - CRYPTO ’89, volume 435 of Lecture Notes in Computer Science, pages 307–315. Springer-Verlag, 1990

· V. Shoup. Practical threshold signatures. In B. Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 207–220. Springer-Verlag, 2000

· K. M. Martin, R. Safavi-Naini, H. Wang, and P. R. Wild. Distributing the encryption and decryption of a block cipher. Designs, Codes and Cryptography, 36(3):263–287, 2005

· Seminar - Secret sharing based on information dispersal. More secret sharing - weighted, compartmented, hierarchical.

4. Lattice-based cryptography. Elliptic curve cryptography (March 10)

References

· P. Q. Nguyen and J. Stern. The Two Faces of Lattices in Cryptology. In Revised Papers From the international Conference on Cryptography and Lattices (March 29 - 30, 2001). J. H. Silverman, Ed. Lecture Notes In Computer Science, vol. 2146. Springer-Verlag, 146-180

· N. Koblitz, A. Menezes, and S. Vanstone. The State of Elliptic Curve Cryptography. Designs, Codes and Cryptography Volume 19 , Issue 2-3 (March 2000), 173-193

· Seminar - Additional capabilities in secret sharing (dealer-free, composability, changeability, multi-secret sharing)

5. Oblivious transfer (March 17)

References

· M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981

· S. Even, O. Goldreich, and A. Lempel. A Randomized Protocol for Signing Contracts. Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985

· C. Crépeau. Equivalence between two flavours of oblivious transfer. In Advances in Cryptology: CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 350-354. Springer-Verlag, 1988

· M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. In Advances in Cryptology: CRYPTO '89, volume 435 of Lecture Notes in Computer Science, pages 547-557. Springer-Verlag, 1990

· F. Bao, R. H. Deng, and P. Feng. An Efficient and Practical Scheme for Privacy Protection in the E-Commerce of Digital Goods. In Proceedings of ICISC 2000, volume 2015 of Lecture Notes in Computer Science, pages 162-170. Springer-Verlag, 2001

· Seminar - student presentations (Cryptosystems based on theory of formal languages, Signcryption, One-time digital signatures)

6. Private information retrieval (March 24)

References

· E. Kushilevitz and R. Ostrovsky. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In Proceedings of 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), pages 364-373, 1997

· R. Ostrovsky and W. E. Skeith III. A Survey of Single-Database Private Information Retrieval: Techniques and Applications. In Proceedings of Public Key Cryptography 2007, Lecture Notes in Computer Science 4450, pages 393-411, 2007

· Seminar - student presentations (Broadcast encryption, Tracing traitors, Fail-stop digital signatures, Undeniable digital signatures)

Midterm Exam (Friday, April 4, 18.00-20.00, in C112)

7. Zero-knowledge proofs (April 7)

References

· O. Goldreich. Zero-knowledge twenty years after its invention. Electronic Colloquium on Computational Complexity, Report No. 63, 2002 (a revised version )

· Seminar - student presentations (Conditional oblivious transfer, Distributed oblivious transfer, Secure keyword search)

8. ∑-Protocols (April 14)

- Identification protocols – Fiat-Shamir, Guillou-Quisquater, Schnorr

- Proofs of equality of (double) discrete logarithms with applications in verifiable encryption and publicly verifiable secret sharing

References

· A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology–CRYPTO ’86 (LNCS 263), 186–194, 1987

· U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1 (1988), 77–94

· L. C. Guillou, J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. Advances in Cryptology–EUROCRYPT ’88 (LNCS 330), 123–128, 1988

· C. P. Schnorr. Efficient identification and signatures for smart cards. Advances in Cryptology–CRYPTO ’89 (LNCS 435), 239–252, 1990

· R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In W. Fumy, editor, Advances in Cryptology - EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 103–118. Springer-Verlag, 1997

· M. Stadler. Publicly verifiable secret sharing. In U. M. Maurer, editor, Advances in Cryptology - EUROCRYPT ’96, volume 1070 of Lecture Notes in Computer Science, pages 190–199. Springer-Verlag, 1996

· B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In M. J. Wiener, editor, Advances in Cryptology - CRYPTO ’99, volume 1666 of Lecture Notes in Computer Science, pages 148–164. Springer-Verlag, 1999

· Seminar - student presentations (Search on encrypted data, Incremental cryptography, Ring signatures)

9. Secure Multiparty Computation (April 21)

- Yao’s garbled circuit technique

- Techniques based on secret sharing

- Private Set Intersection

References

· A. C. Yao. Protocols for secure computations (extended abstract). In Proceedings of Twenty-third IEEE Symposium on Foundations of Computer Science, Chicago, Illinois, November 1982, pages 160–164, 1982

· A. C. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 162-167, 1986

· D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay - A Secure Two-Party Computation System. Proceedings of Usenix Security '2004, pp. 287–302, August 9-13, 2004

· M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the Twentieth ACM Symposium on Theory of Computing, STOC ’88, pages 1–10, 1988

· R. Gennaro, M. O. Rabin, and T. Rabin. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In PODC ’98: Proceedings of the seventeenth ACM symposium on Principles of distributed computing, pages 101–111. ACM Press, 1998

· M. Freedman, K. Nissim and B. Pinkas. Efficient Private Matching and Set Intersection. Advances in Cryptology - Eurocrypt '2004 Proceedings, LNCS 3027, Springer-Verlag, pp. 1-19, May 2004

· Seminar - student presentations (Fair exchange, Visual cryptography, Biometrics identification)

Eastern holiday (April 28 – May 2)

10. E-voting protocols (May 5)

References

· R. Cramer, M. K. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In U.Maurer, editor, Advances in Cryptology - EUROCRYPT ’96, volume 1070 of Lecture Notes in Computer Science, pages 72–83. Springer-Verlag, 1996

· A. Fujioka., T. Okamoto, and K. Ohta. A Practical Secret Voting Scheme for Large Scale Elections. In Proceedings of the Workshop on the theory and Application of Cryptographic Techniques: Advances in Cryptology (December 13 - 16, 1992). J. Seberry and Y. Zheng, Eds. Lecture Notes In Computer Science, vol. 718. Springer-Verlag, London, 244-251

· M. Jakobsson and A. Juels. Millimix: Mixing in Small Batches. DIMACS Technical Report 99-33, 1999

· D. Boneh and P. Golle. Almost Entirely Correct Mixing With Applications to Voting. In Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 68-77, 2002

· Seminar - student presentations (Password management, Computation with encrypted inputs)

11. Pairing-based cryptography (May 12)

References

· A. Joux. A one-round protocol for tripartite Diffie-Hellman. Algorithm Number Theory Symposium (ANTS-IV), Lecture Notes on Computer Science 1838, Springer-Verlag (2000), pp. 385-394

· D. Boneh, M. Franklin. Identity-based encryption from the Weil pairing. Advances in Cryptology -Crypto'2001, Lecture Notes on Computer Science 2139, Springer-Verlag (2001), pp. 213-229

· D. Boneh, B. Lynn, H. Shacham. Short signatures from the Weil pairing. Advances in Cryptology -Asiacrypt'2001, Lecture Notes on Computer Science 2248, Springer-Verlag (2001), pp. 514-532

· D. Boneh, C. Gentry, B. Lynn, H. Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. Advances in Cryptology - Eurocrypt'2003, Lecture Notes on Computer Science 2656, Springer-Verlag (2003), pp. 416-432

· D. Boneh, G. Di Crescenzo, R. Ostrovsky, G. Persiano. Public key encryption with keyword search. Advances in Cryptology -Eurocrypt'2004, Lecture Notes on Computer Science 3027, Springer-Verlag (2004), pp. 506-522

· Seminar - student presentations (E-auctions, E-payments)

Student Presentations

Cryptosystems based on theory of formal languages (Besliu Larisa Elena (MSD), Fodor Gabi Razvan (MISS))

Signcryption (Acasandrei Anca Liliana (MSD), Herghelegiu Ioana (MISS))

One-time digital signatures (Costea George Alin (MSD), Cotoi Cristian (MISS))

(March 17, March 21)

Broadcast encryption. Tracing traitors (Onica Emanuel (MSD), Diaconu Adrian (MISS), Mirza Lesan Ion (MISS))

Fail-stop digital signatures (Cracana Roxana (MISS))

Undeniable digital signatures (Cristea Marius (MSD), Dobrincu Dan Ionel (MISS))

(March 24, March 28)

Conditional oblivious transfer (Mardari Laura (MLC), Gheorghita Irina Ioana (MISS), Munteanu Anca Stefana (MISS))

Distributed oblivious transfer (Dima Emanuel (MSD))

Secure keyword search (Amariei Ciprian (MSD), Matcovici Ioan (MISS))

(April 7, April 11)

Search on encrypted data (Botea Bogdan (MISS), Postudor Vlad (MISS), Pantilimon Narcisa Maria (MISS))

Incremental cryptography (Mihaila Andrei (MSD), Rotaru Adrian (MISS))

Ring signatures (Popa Tudor (MISS))

(April 14, April 18)

Fair exchange (Caltais Georgiana (MISS), Goriac Eugen Ioan (MISS), Dabija Constantin Alexandru (MISS))

Visual cryptography (Rustioru Raluca (MSD), Valica Ecaterina (MISS))

Biometrics identification (Turcu Paul (MISS))

(April 21, April 23)

Password management (Deliu Constantin Gabriel (MISS), Matei Irinel (MISS), Rusu Anda Ramona (MISS), Sandu Roxana (MISS))

Computation with encrypted inputs (Goldan Elena Amalia (MISS), Tabara Iulian (MISS))

(May 5, May 9)

E-auctions (Pantescu Andreea (MSD), Morosan Raluca Melania (MISS), Soldanescu Alina Dana (MISS), Ungureanu Radu Andrei (MISS))

E-payments (Sardariu Costel Cristinel (MISS), Perietanu Elena (MISS), Sarghie Costel Cristinel (MISS))

E-lotteries and E-casinos (Luca Bogdan Lucian (MISS), Vlad Silviu Adrian (MISS))

(May 12, May 16, May 19)

Required Text and Materials

Most of the course and seminar material will be based on conference or journal articles which will be announced in advance.

Class Requirements

Class participation: Students are expected to come prepared and actively participate in the courses and seminars.

Class presentation: Every student is required to give a class presentation (roughly 25 minutes) on a selected topic (see the above list)

The course grade will be determined as follows:

presentation of a report on a selected topic (during seminars): 40%

midterm exam: 30%

final exam: 30%

(You have to collect at least 50% points from the presentation, and at least 50% points from each exam)

Exams

- midterm exam (Friday, April 4, 18.00-20.00, in C112)

- final exam (Friday, May 23, 18.00-20.00, in C112)

- re-evaluation exam (Tuesday, June 17, 18.00-20.30, in C112)