Research Projects
Research in Cryptography and Information Security 9807-12&26 Start date: 07/98	Shafi Goldwasser, Ronald L. Rivest and Mike Sipser MIT LCS Tatsuaki Okamoto NTT
Project summary

This project explores techniques for secure computation and communication based on cryptography.

The Cryptography and Information Security group is devoted to developing techniques for secure computation and communication, based primarily on cryptography. Recent NTT-sponsored research has focussed on the following topics (among others): secure electronic voting probabilistic property testing group signature schemes pseudonym systems derandomization techniques protocols secure against resettable adversaries The emphasis of our reseach which is expressed in our work on each of the above topics is on the development of novel frameworks and theoretical provably secure solutions to problems arising from applications.

We have designed an electronic voting scheme based on the paper, "A practical secret voting scheme for large scale elections", by Atsushi Fujioka, Tatsuaki Okamoto, and Kazuo Ohta (Proceedings AUSCRYPT '92, 1993, 244-251). The full web-based, java implementation protocol is listed (and available for downloading) here.

• Shafi Goldwasser (email)
• Ronald L. Rivest (email)
• Mike Sipser (email)
• Tatsuaki Okamoto (email)

• Mihir Bellare, Marc Fischlin, Shafi Goldwasser, Silvio Micali. "Identification Protocols Secure Against Reset Attacks." In Advances in Cryptology - Eurocrypt 2001 Proceedings, Lecture Notes in Computer Science volume 2045, B. Pfitzmann, ed., Springer-Verlag, 2001.
• Anna Lysyanskaya, Christopher Peikert. "Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes." Manuscript, 2001.
• Jan Camenisch, Anna Lysyanskaya. "An Identity Escrow Scheme with Appointed Verifiers." To appear in Crypto, 2001.
• Michel Abdalla and Leonid Reyzin. A New Forward-Secure Digital Signature Scheme. Advances in Cryptology -- Asiacrypt 2000, Taksuaki Okamoto, editor, Lecture Notes in Computer Science, volume 1976, Springer-Verlag, 2000.
• Boaz Barak, Oded Goldreich, Shafi Goldwasser and Yehuda Lindel. "Resettably-Sound Zero-Knowledge and its Applications, 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, Nevada October 14-17, 2001. To appear.
• Silvio Micali and Leonid Reyzin. "Min-Round Resettable Zero Knowledge in the Public Key Model." In Advances in Cryptology - Eurocrypt 2001 Proceedings, Lecture Notes in Computer Science volume 2045, B. Pfitzmann, ed., Springer-Verlag, 2001.
• Silvio Micali and Leonid Reyzin. "Soundness in the Public Key Model." To appear in Crypto 2001.
• Silvio Micali, Kazuo Ohta, and Leonid Reyzin. "Accountable-Subgroup Multisignatures." To appear in 8th ACM Conference on Computer and Communications Security, 2001.
• Andrej Bogdanov. Formal verification of simulations between I/O automata. Master of Engineering thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2001.
• Alan Fekete and Idit Keidar. A Framework for Highly Available Services Based on Group Communication. IEEE 21st International Conference on Distributed Computing Systems Workshops (ICDCS-21W 2001); the International Workshop on Applied Reliable Group Communication (WARGC), April 2001, pp. 57-62.
• Kyle W. Ingols and Idit Keidar. Availability Study of Dynamic Voting Algorithms. IEEE 21st International Conference on Distributed Computing Systems (ICDCS), April 2001, pp. 247-254.
• Idit Keidar and Roger Khazan. A Client-Server Approach to Virtually Synchronous Group Multicast: Specifications and Algorithms. IEEE 20th International Conference on Distributed Computing Systems (ICDCS), April 2000, pp. 344-355. Full version: MIT Lab. for Computer Science Tech. Report MIT-LCS-TR-794, submitted for journal publication.
• Idit Keidar, Roger Khazan, Nancy Lynch, and Alex Shvartsman. An Inheritance-Based Technique for Building Simulation Proofs Incrementally. To appear in ACM Transactions on Software Engineering and Methodology (TOSEM). Previous version in ICSE 2000, pp. 478-487.
• Carlos Livadas, Idit Keidar, and Nancy Lynch. Designing a Caching-Based Reliable Multicast Protocol. Fast abstract in the International Conference on Dependable Systems and Networks (DSN) July 1-4, 2001. P. Attie and N. Lynch. Dynamic I/O Automata: a Formal Model for Dynamic Systems. To appear in Concur, August 2001. Also to appear as brief announcement in the 20th ACM Symposium on Principles of Distributed Computing (PODC), August 2001.
• Ran Canetti, Tal Malkin, Kobbi Nissim. "Efficient Communication-Storage Tradeoffs for Multicast Encryption." Proc. of the 17th IACR Eurocrypt conference (EUROCRYPT '99).
• Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin. "One-way Functions are Essential for Single-Server Private Information Retrieval." Proc. of the 31st ACM Symp. on the Theory of Computing (STOC '99).
• Amos Beimel, Tal Malkin, Silvio Micali. "The All-Or-Nothing Nature of Two-Party Secure Computation." Proc. of the 19th IACR Crypto conference (CRYPTO '99).
• Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky. "Single Database Private Information Retrieval Implies Oblivious Transfer." Submitted for publication.
• Amos Beimel, Tal Malkin. "Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing." Submitted for publication.
• Ran Canetti, Ivan Damgard, Stefan Dziembowski, Yuval Ishai, Tal Malkin. "On Adaptive vs. Non-Adaptive Security of Multiparty Protocols." Submitted for publication.
• Amit Sahai, Venkatesan Guruswami, "Multiclass Learning, Boosting, and Error-Correcting Codes" appeared at COLT '99:
• Amit Sahai, Anna Lysyanskaya, Ronald Rivest, and Stephan Wolf, "Pseudonym Systems" appeared at SAC '99:
• Amit Sahai, Ravi Kumar and Sridhar Rajagopalan, "Coding constructions for blacklisting problems without computational assumptions", appeared at CRYPTO '99:
• Oded Goldreich, Amit Sahai, and Salil Vadhan "Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK", appeared at CRYPTO '99; full version at:
• Amit Sahai, Mihir Bellare, "Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization" appeared at CRYPTO '99; full version at:
• Amit Sahai, "Non-Malleable Non-Interactive Zero Knowledge and Chosen-Ciphertext Security" appeared at FOCS '99.
• Brandon DuRette, MIT EECS Bachelor's Thesis, "Multiple Administrators for Electronic Voting"
• Ran Raz, Omer Reingold, Salil Vadhan. Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. STOC `99.
• Madhu Sudan, Luca Trevisan and Salil Vadhan. Pseudorandom Generators without the XOR Lemma. STOC `99 & Complexity `99 joint session.
• Oded Goldreich, Salil Vadhan. Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. Complexity `99.
• Ran Raz and Omer Reingold, Error Reduction for Extractors. FOCS `99.
• Gennaro, Jarecki, Krawczyk, and Rabin, Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, published in Eurocrypt'99
• Ran Canetti, Gennaro, Jarecki, Krawczyk, and Rabin, Adaptive Security for Threshold Cryptosystems published in Crypto'99, in

Proposals:

• proposal 1998: 
• proposal 1999: 
• proposal 2000: 
• proposal 2001: 

NTT Bi-Annual Progress Report, July to December 1998:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, January to June 1999:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, July to December 1999:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, January to June 2000:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, June to December 2000:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, January to June 2001:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, July to December 2001:

• project report: 


• presentation slides: 

NTT Bi-Annual Progress Report, January to June 2002:

• project report: 


• presentation slides: 

• We have created a web page specifically for information relevant to the NTT-sponsored research by the CIS group.