This is a draft proposal to renew the collaboration between NTT and MIT in the areas of cryptography and information security.

(Administrative note: In the past, the collaboration in the areas of cryptography and information secured with MIT faculty Goldwasser and Rivest was grouped, as an administrative matter, with collaboration in the area of quantum computation with MIT faculty Michael Sipser. Professor Sipser does not wish to continute his work in quantum computation.)

(Our progress reports contain more detailed information about the collaboration to date and the results produced; here we just mention some highlights and works that may not have been covered in previous progress reports.)

Accountable-Subgroup Multisignatures

(Silvio Micali, Kazuo Ohta, and Leonid Reyzin)

(Submitted.)

Abstract:

Before our work, there was no complete formal model for multisignatures, and many past proposal (including those made by NTT) were subsequently broken. We proposed the first model and achieved its strong security requirements very efficiently.

Improved Unconditionally Secure Commitment and Oblivious Transfer Schemes using Private Channels and a Trusted Initializer

(Kazuo Ohta and Ronald L. Rivest)

(Submitted.)

Abstract:

We improve earlier proposals by Rivest for implementing secure commitment schemes and secure oblivious transfer schemes under the assumption of the existence of private channels and the existence of a trusted initializer, by reducing the need for private channels and certain problems that could be caused by an outside adversary.

Protocols for Electronic Voting

(Kazuo Ohta, Mark Herschberg, Ben Adida, and Brandon W. DuRette)

(Covers two theses and considerable software development.)

Abstract:

We have explored in some depth the proposal by Fujioka, Okamoto, and Ohta for a practical large-scale electronic voting scheme. This proposal was the basis of an MIT EECS Master's thesis by Mark Herschberg and a MIT EECS B.S. thesis by Brandon W. DuRette, as well as extensive effort by Herschberg, Adida, and DuRette to implement this protocol in Java. The resulting software has been used successfully several times on MIT campus for student elections. More information on this project is available at http://theory.lcs.mit.edu/~cis/voting/voting.html

Extended Visit of Kazuo Ohta to MIT

(Kazuo Ohta; host Ronald L. Rivest)

Notes:

Kazuo Ohta visited MIT for the period from January 1998 to June 1999, approximately. He interacted and collaborated with several faculty and many students during his stay. We were pleased with this opportunity to collaborate with and learn from Kazuo Ohta.

These are segments drafted by various researchers in our group, outlining proposed research directions that look promising.

(by Anna Lysyanskaya)

Next year, we plan to continue working in threshold cryptography, multi-party computation, and anonymity in cryptographic protocols.

Threshold cryptography allows to create (really simulate) a trusted entity based on the assumption that at most a fraction of a set of dedicated servers can be cheating. In this setting, an adversary can choose a set of servers to corrupt in an adaptive manner. Our recent work explored guaranteeing security for threshold cryptosystems against such adaptive adversaries [1,2,3]. Several open questions remain: Construct adaptively secure threshold implementations of the Cramer-Shoup and the Gennaro-Halevi-Rabin signature schemes; Construct adaptively secure threshold Paillier cryptosystem. With Chris Peikert, a fellow student at the CIS group, we have made some progress on these and will continue working on them. Additional open problems in this area are the lower bounds on communication and round complexity of threshold cryptosystems, and threshold cryptography from general assumptions.

The more general problem of multi-party computation is also of interest. Specifically, interesting problems arise in the context of multi-party computation and that are of interest are the problem of implementing secure channels in the adaptively secure setting without a communication overheard, and the question of optimal-threshold adaptively secure multi-party computation made efficient under complexity assumptions.

Finally, a lot of our work recently has focused on anonymity in cryptographic protocols. As information becomes increasingly accessible, protecting the privacy of individuals becomes a more challenging task. Preserving user anonymity in cryptographic protocols is therefore crucial. While vistint IBM Zurich, and in collaboration with Jan Camenisch at IBM Zurich, Anna Lysyanskaya has developed a system that allows a user to obtain and show credentials anonymously [4] and a designated-verifier identity escrow scheme in which a user can convince a designated verifier that he is a member of some group, without disclosing any additional information, and without being able to prove group membership to anyone other than the designated verifier [5]. We propose using designated-verifier identity escrow schemes to obtain receipt-free voting protocols with strong receipt-freeness property. We also hope to extend the credential system results by considering more complicated scenarios.

[1] Stanislaw Jarecki, Anna Lysyanskaya. "Adaptively secure threshold cryptography: introducing concurrency, removing erasure." In Advances in Cryptology -- Proceedings of Eurocrypt2000, Springer-Verlag, May 2000.

[2] Stanislaw Jarecki, Anna Lysyanskaya "Adaptively secure threshold cryptography without erasures." Manuscript, 2000.

[3] Anna Lysyanskaya. "Threshold cryptography secure against the adaptive adversary, concurrently." Manuscript, 2000.

[4] Jan Camenisch, Anna Lysyanskaya. "An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation." In Advances in Cryptology -- Proceedings of Eurocrypt2001, Springer-Verlag, to appear, May 2001.

[5] Jan Camenisch, Anna Lysyanskaya. "An Identity Escrow Scheme with Designated Verifiers." Manuscript, 2001.

(by John Herzog)

Formal cryptography has achieved a level of mathematical maturity in the past few years. With strand spaces, for example, we've been able to provide simple pencil-and-paper proofs for conditions that previously needed to be verified by model checkers. There have also been some new approaches to automated tools, and other proof techniques based on different mathematical approaches.

However, the "Achilles heel" of all these techniques are the assumptions: both the freeness of the message algebra and the limited number of penetrator actions.

We propose to ground both of these assumptions in computational reasoning. The proposed research would be similar in flavor to that of Abadi and Rogaway, synthesizing research from two complementary communities.

(by Jennifer Mulligan)

We propose research developing lightweight cryptographic network protocols for a variety of purposes, including privacy, integrity, and authentication.

For example, we propose modifying the Guy Fawkes protocol by Ross Anderson et al. so that it is usable within a standard (or slightly modified) TCP/IP protocol. The Guy Fawkes protocol is an "interlock" protocol that uses fast algorithms (hash functions) to provide authentication of bi-directional data streams (after suitable initialization, or even after an intial phase where there is no active adversary). However, the Guy Fawkes protocol is not designed to accommodate the "windowing" allowed in TCP/IP, where a number of packets may be sent before an acknowledgement for the first is received. We wish to explore ways to extend Guy Fawkes to handle such "windowing". (If possible; the interlocking assumptions of Guy Fawkes are rather at odds with the flexible windowing assumptions of TCP/IP.)

(by Abhi Shelat)

We propose to investigate the security properties of two recently proposed block cipher algorithms, Kasumi and Noekeon.

The Kasumi block cipher forms the core of the 3GPP confidentiality and integrity algorithms, f8 and f9 respectively. The goal of the 3GPP group is to create a global standard for mobile communication systems. Therefore, it is crucial that the security elements of the standard be thoroughly evaluated. The current literature includes results which show that Kasumi is resistent to differential and linear cryptanalysis. However, it is unknown whether Kasumi's simple recursive structure does not in turn admit other exploits.

The Noekeon cipher is a substitution-linear transformation network in bit-slice mode, and as such similar to AES proposal Serpent. Unlike Serpent it has a high degree of symmetry that allows very fast and compact implementations and the demonstration of a high resistance against known attacks. Noekeon also claims resistance against side-channel attacks (timing, power). Since it has been submitted as a NESSIE candidate, it is important to understand whether such a simple cipher can be secure. In addition Noekeon is competing against NTT's NESSIE submission, Camelia.

(by Ron Rivest)

We would like to continue our research into protocols for electronic voting. Our previous work, as noted earlier, is based on the proposal of Fujioka, Okamoto, and Ohta. However, their proposal and our extensions of it, are still not "receipt-free": a voter can, after he has finished voting, prove to a third party exactly how he has voted. This is not a desirable property, as it enables vote-buying and coercion. There are other aspects of these protocols that cause difficulties in practice, such as the need for two separate actions by the voter.

We propose further investigation into voting protocols that are in fact receipt-free and practical.

We note that the recent U.S. presidential elections has stimulated a great deal of activity directed towards devising improved voting systems for use in the U.S. For example, MIT and the California Institute of Technology have a joint effort in this direction; former U.S. Presidents Jimmy Carter and Gerald Ford have another commission that is examining voting procedures. There is increasing pressure to move U.S. voting in a more "high-tech" direction; research on voting protocols as part of an NTT/MIT collaboration could have useful payoffs for democracy world-wide.

(by Adam Smith)

Quantum authentication codes: Until recently, it was not known how to authenticate _quantum_ messages based on a shared _classical_ key. Some schemes for this task have recently been given by Barnum, and by Crepeau, Gottesman, Smith, and Tapp. However, the schemes are either very inefficient in key use, or too complex to be implemented using current technology (or even technology for the forseeable future), or both.

Thus, it is important to find schemes for authenticating quantum information which are simple enough to be implemented onmore realistic devices and efficient enough too use only very little bits of the shared classic key. We propose to investigate such schemes, including some candidates based on quantum error-correcting codes.

The above list of suggested research directions is not intended to be exhaustive or comprehensive. We imagine that other directions will emerge serendipitiously (as often happens in theoretical research) or in discussions between NTT and MIT researchers.

We are of course open to suggestions from our NTT colleagues regarding research opportunities that may be of mutual interest.

For example, NTT currently has research into protocols for electronic auctions; this could easily be a topic for fruitful collaboration.

We have been pleased with our collaboration with NTT to date in the areas of cryptography and information security, and look forward to the possibility of continuing this collaboration and dialogue with our NTT colleagues.