Plan du cours IFT6180: Cryptologie: théorie et application

Claude Crépeau 14 septembre 1992

Mes coordonnées:

bureau Y-219, DIRO téléphone: 343-6804 adresse électronqiue: crepeau@iro.umontreal.ca

Plan de cours

Voici un aperçu des prochains cours de cryptographie: semaine du:

• 14 septembre: Introduction, théorie de l’information, distance d’unicité, Systèmes cryptographiques à clef secrète; exemples: one-time pad, DES et autres.

• 21 septembre: théorie de la complexité, théorie des nombres, Systèmes cryptographiques à clef publique; exemples: Diffie-Helmann, RSA et autres.

• 28 septembre: Encryption probabiliste et générateurs pseudo-aléatoires.

• 5 octobre: Bits difficiles de RSA, log discret et en général.

• 12 octobre: preuves et arguments interactifs et à divulgation nulle (zero-knowledge): définitions et exemples, preuves à divulgation nulle pour N P et MA.

• 19 octobre: preuves à divulgation nulles non-interactive et systèmes cryptographiques résistant aux attaques “message chiffré choisit”, partage de secrets et systèmes cryptographiques “justes”.

• 26 octobre: signature numérique, NIST et signatures indéniables.

• 2 novembre: partage de secret vérifiable et calcul de fonction multipartie.

• 9-16 novembre: transfer équivoque et ses applications.

• 23 novembre: cryptographie quantique (échange de clefs secrètes, mise en gage d’un bit et transfer équivoque).

• semaines restantes: débordement des sujets précédents et présentations des étudiants.

Livres utiles au début du cours:

1. Cryptography and Data Security, de Dorothy Denning

2. Modern Cryptology/ Cryptologie Comtemporaine, de Gilles Brassard

Liste d’articles

Voici une liste d’articles qui vous sera utile afin de choisir un sujet à presenter en classe.

References

[ACGS88] W. B. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr. RSA and Rabin functions: certain parts are as hard as the whole. SIAM J. Computing, 17(2):194–209, April 1988.

[Bab85] L. Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 421–429, May 1985.

[Bac88] Eric Bach. How to generate factored random numbers. SIAM J. Computing, 17(2):179–193, April 1988.

[BBR88] C. H. Bennett, G. Brassard, and J.–M. Robert. Privacy amplification by public discussion. SIAM J. Computing, 17(2):210– 229, April 1988.

[BM84] M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Computing, 13(4):850–863, November 1984.

[BM88] Mihir Bellare and Silvio Micali. How to sign given any trapdoor function. In Proc. 20th ACM Symposium on Theory of Computing, pages 32–42, Chicago, 1988. ACM.

[BOGKW88] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multiprover interactiev proofs: How to remove intractability assumptions. In Proceedings of 20th Annual AMC Symposium on Theory of Computing 1988, pages 113–122, 1988.

[BOGW88] M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for fault-tolerant distributed computing. In Proc. 20th ACM Symposium on Theory of Computing, pages 1–10, Chicago, 1988. ACM.

[CCD88] D. Chaum, C. Crépeau, and I. Damgård. Multi-party unconditionally secure protocols. In Proc. 20th ACM Symposium on Theory of Computing, Chicago, 1988. ACM.

[Cha81] D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communcations of the ACM, 24:84–88, February 1981.

[Cré88] C. Crépeau. Equivalence between two flavours of oblivious transfers (abstract). In C. Pomerance, editor, Advances in Cryptology: Proceedings of Crypto ’87, volume 293 of Lecture Notes in Computer Science, pages 350–354. Springer-Verlag, 1988.

[FM85] P. Feldman and S. Micali. Byzantine agreement in constant expected time (and trusting no one). In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pages 267–276, Portland, 1985. IEEE.

[FS87] A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In A. M. Odlyzko, editor, Proceedings CRYPTO 86, pages 186–194. Springer, 1987. Lecture Notes in Computer Science No. 263.

[GGM84] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, pages 464–479, Singer Island, 1984. IEEE.

[GL89] O. Goldreich and L. Levin. A hard-core predicate for all oneway functions. To appear in STOC ’89, 1989.

[GMR89] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM. J. Computing, 18(1):186–208, February 1989.

[GMW86] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 174–187, Toronto, 1986. IEEE.

[GMW87] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game, or: A completeness theorem for protocols with honest majority. In Proc. 19th ACM Symposium on Theory of Computing, pages 218–229, New York City, 1987. ACM.

[LMR83] M. Luby, S. Micali, and C. Rackoff. How to simultaneously exchange a secret bit by flipping a symmetrically biased coin. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 11–22, Tucson, 1983. IEEE.

[LR88] M. Luby and C. Rackoff. How to construct pseudorandom permutations and pseudorandom functions. SIAM J. Computing, 17(2):373–386, April 1988.

[MBM88] P. Feldman M. Blum and S. Micali. Non-interactive zeroknowledge and its applications. In Proceedings of the 24th Symposium on Theory of Computing, pages 103–112, May 1988. Has been accepted and to appear.

[RIL89] L.A. Levin R. Impagliazzo and M. Luby. Pseudo-random generation from any one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989.

[Sha79] A. Shamir. How to share a secret. Communcations of the ACM, 22:612–613, November 1979.

[SV84] M. Santha and U. V. Vazirani. Generating quasi-random sequences from slightly-random sources. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, pages 434–440, Singer Island, 1984. IEEE.