Seminario de Criptografía: Computación Multipartita y Aplicaciones (2008/02)

Profesor: Alejandro Hevia

Propósito: El propósito del seminario es discutir conceptos y resultados detrás de recientes trabajos en el área de protocolos criptográficos multipartitos. Se pondrá énfasis en protocolos para comunicación anónima, votación electrónica, y estructuras de datos distribuídas seguras.

Aspectos administrativos:

Horario reunión: Miércoles 2:30pm-4:00pm, sala reuniones 3er piso DCC
Auxiliar: No hay.
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 5 UD,
Requisitos: (CC40A/CC62W), o Autorización
Carácter del curso: electivo Cs. de la Computación

Novedades

• Importante: Escoger al menos dos artículos para presentar y dos fechas distintas disponibles. Luego, por favor comunicarselo al profesor antes del Viernes 22 de Agosto. Ver listado de artículos y fechas disponibles.

Temas

1. Conceptos y Nociones de Seguridad de Protocolos Criptográficos: Modelos básicos, Universal Composability
2. Mecanismos para compartir secretos (Secret Sharing)
3. Protocolos Genéricos: 2 participantes y múltiples participantes.
4. Mix networks: conceptos y construcciones
5. Votación Electrónica, conceptos y construcciones
6. Acumuladores, Zero-Knowledge Sets y Oblivious Data Structures

• Definiciones Básicas:
  • [1] "Security and Composition of Multiparty Cryptographic Protocols", Ran Canetti, J. of Cryptology 2000. Referencia, PDF local copy.
• Herramientas: Compartimiento de Secretos (secret sharing)
  • [2] "How to Share a Secret". Adi Shamir. Commun. ACM 22(11): 612-613 (1979). Referencia, PDF local copy.
  • [3] "Non-interactive and Information-Theoretic Secure Verifiable Secret Sharing", Torben Pryds Pedersen, CRYPTO 1991. Referencia, PDF local copy.
  • [4] "A practical scheme for non-interactive verifiable secret sharing". P. Feldman, IEEE Symposium on Foundations of Computer Science, pages 427--437. IEEE, 1987. Referencia, PDF local copy.
  • [5] "A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting", Berry Schoenmakers, 1999. Referencia, PDF.
• Protocolos Genéricos:
  • [6] "Protocols for Secure Computations", Andrew C. Yao, FOCS 1982. PDF local.
  • [6a] "A Proof of Security of Yao's Protocol for Two-Party Computation", Y. Lindell and B. Pinkas. To appear in the Journal of Cryptology. Referencia, PS.GZ.
  • [6b] "An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries." Y. Lindell and B. Pinkas. In Eurocrypt 2007, Springer-Verlag (LNCS 4515), pages 52-78, 2007. PDF.
  • [7] "Completeness theorems for non-cryptographic fault-tolerant distributed computation", M. Ben-Or, S. Goldwasser y A. Wigderson, STOC 88. Referencia, PDF local copy.
  • [8] "How to play ANY mental game", O. Goldreich, S. Micali, A. Wigderson. Referencia, PDF.
  • [9] "Multiparty Unconditionally Secure Protocols", D. Chaum. C. Crepeau y I. Damgard, CRYPTO'87. Referencia, PDF local copy.
  • [10] "Two-Party Computing with Encrypted Data.", Seung Geol Choi, Ariel Elbaz, Ari Juels, Tal Malkin, Moti Yung, ASIACRYPT 2007. Referencia, PDF local copy.
• Seguridad bajo composición:
  • [11] "Universally Composable Security", R. Canetti, FOCS 2001.
  Referencia, PS.
  • [12] "Universally Composable Security with Pre-Existing Setup." R. Canetti, Y. Dodis, R. Pass and S. Walfish. TCC 2007. Referencia, PDF.
  • [13] "Obtaining Universally Composable Security: Towards the Bare Bones of Trust." R. Canetti. Asiacrypt 2007, LNCS 4833, pages 88-112 Referencia, PDF.
• Votación Electrónica:
  • [14] "A secure and optimally efficient multi-authority election scheme". R. Cramer, R. Gennaro, and B. Schoenmakers. In Eurocrypt '97. PDF.
  • [15] "Practical multi-candidate election system.", Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Jacques Stern, Guillaume Poupard. PODC 2001. PDF.
  • [16] "Receipt-Free Universally-Verifiable Voting With Everlasting Privacy". Tal Moran and Moni Naor. Crypto '06. Referencia, PDF.
  • [17] "Split-Ballot Voting: Everlasting Privacy With Distributed Trust". Tal Moran and Moni Naor. CCS '07. Referencia, PDF.
  • [18] "Secret-Ballot Receipts: True Voter-Verifiable Elections," David Chaum, IEEE Security and Privacy, vol. 2, no. 1, pp. 38-47, January-February, 2004 Referencia, PDF.
  • [19] "A simplified version of the Chaum voting scheme." J. W. Bryans and P. Y. A. Ryan. Technical Report CS-TR 843, University of Newcastle, 2004. Referencia, PDF.
  • [19b] "Analysis, Improvement, and Simplification of Prêt à Voter with Paillier Encryption". Zhe Xia, Steve A. Schneider, and James Heather, University of Surrey, U.K.; Jacques Traoré, EVT'08. Referencia, PDF.
  • [20] "Information-Theoretically Secure Voting Without an Honest Majority". Anne Broadbent and Alain Tapp, In Proceedings of the IAVoSS Workshop On Trustworthy Elections (WOTE 2008). Referencia, PDF.
• Mix networks, anonimato:
  • [21] "Untraceable electronic mail, return addresses, and digital pseudonyms." D. Chaum. Communications of the ACM, 24(2):84{88, 1981. Referencia, PDF.
  • [22] "Receipt-free mix-type voting scheme", K. Sako and J. Kilian, EUROCRYPT '95. PDF.
  • [23] "An Efficient Scheme for Proving a Shuffle." Furukawa, J. and Sako, K. Crypto 2001. PDF.
  • [24] "A Verifiable Secret Shuffle of Homomorphic Encryptions", Jens Groth, In Practice and Theory in Public Key Cryptography - PKC 2003, LNCS 2567. PDF, ppt charla.
  • [25] "A Non-interactive Shuffle with Pairing Based Verifiability." Jens Groth and Steve Lu. In Advances in Cryptology - ASIACRYPT 2007, LNCS 4833, pages 51-67. PDF, ppt charla.
• Minería de Datos Privada:
  • [26] "Privacy Preserving Data Mining.", Y. Lindell and B. Pinkas. In the Journal of Cryptology, 15(3):177-206, 2002. Versión extendida del artículo de Crypto 2000, Springer-Verlag (LNCS 1880), pages 36-54, 2000. Referencia, PS.GZ.
  • [27] "Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries.", C. Hazay and Y. Lindell. Por aparecer en TCC 2008. Referencia, PDF.
• Estructuras de datos privadas:
  • [28] "Zero-Knowledge Sets", (2003). Referencia PDF
  • [29] "Mercurial Commitments with Applications to Zero-Knowledge Sets", (2006). Referencia, PDF.
• Otras Aplicaciones:
  • [30] "Off-line Karma: A Decentralized Currency for Peer-to-peer and Grid Applications." Flavio D. Garcia and Jaap-Henk Hoepman. In proceedings of 3rd Applied Cryptography and Network Security (ACNS 2005), Lecture Notes in Computer Science, Vol. 3531, pages 364-377. Springer Verlag. PDF.

• Miércoles 13 de Agosto: [No habrá reunión]
• Miércoles 20 de Agosto: Presentador: A. Hevia, Tema: conceptos, paper [1].
• Miércoles 27 de Agosto: Presentador: A. Hevia, Tema: conceptos paper [1], parte II.
• Miércoles 3 de Septiembre: Suspendida
• Miércoles 10 de Septiembre: Presentador: A. Hevia, Tema: secret sharing, papers [2,3,4], opcional [5].
• Miércoles 17 de Septiembre: [Feriado]
• Miércoles 24 de Septiembre: Presentador: A. Hevia, Tema: Conceptos de ZK,PoK
• Miércoles 31 de Septiembre: [Olimpiadas/No hay clase]
• Miércoles 8 de Octubre: Presentador: P. Camacho, Tema: [28]
• Miércoles 15 de Octubre: Presentador: P. Camacho, Tema: [29]
• Miércoles 22 de Octubre: Generic multiparty protocol de BGW [7]
• Miércoles 29 de Octubre: Presentador: F. Krell, Tema: Privacy Preserving Data Mining [26]
• Miércoles 5 de Noviembre: Presentador: P. Seguel, Tema: Mix-networks, Chaum's [21] (introduccion) y Sako-Killian [22] (en detalle)
• Miércoles 12 de Noviembre: Presentador: ??, Tema: Yao's two-party protocols [6,6a,6b]
• Miércoles 19 de Noviembre: [Disponible]
• Miércoles 26 de Noviembre: [Disponible]
• Miércoles 3 de Diciembre: Presentador: F. Krell, Tema: [por anunciar]

• Apuntes del curso de Criptografía de Mihir Bellare: Postgrado.
• Apuntes de clase de Secret Sharing en CS513 en Cornell (2000).
• Artículo de Wikipedia
• Recomendado: Tutorial de Computación Multipartita Segura y sus aplicaciones a minería de datos privada (PDF).
sobre Secure Multiparty Computation (SMC).
• Muy breve introducción a Secure Computation y breve tutorial por Joe Killian.
• Breve reporte de Computación Multipartita en la práctica.
• Workshop on Secure Multiparty Protocols (SMP 2004). Incluye transparencias de varias charlas en temas de SMC.
• Recomendado: Tutorial de Universal Composability: Security and Composition of Cryptographic Protocols: A Tutorial. R. Canetti. (Distributed Computing column of SIGACT News, Vol. 37, Nos. 3 &acmp; 4, 2006). Link corresponde a una versión actualizada.
• 6.897 Selected Topics in Cryptography, curso dictado por Ran Canetti en MIT, 2004.
• Presentación de un "survey" de Secret Shuffles (Mix nets), Heiko Stamer, 2005.

Evaluación:

La evaluación se basa en la presentació de artículos y participación en clases.

Bibliografía:

1. Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
2. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997
3. Mihir Bellare y Phil Rogaway, “Introduction to Cryptography, Lecture Notes”, University of California San Diego, 2006. (Disponible en versiones del curso para pregrado, y de postgrado)
4. Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
5. Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
6. Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry, “Foundamentals of Computer Security”, Springer, 2003

Última modificación: 3 Noviembre 2008.