Recent NTT-sponsored research has focussed on both introducing new cryptographic primitives and designing secure cryptographic protocols with repsect to existing definitions.

The emphasis of the research is on the development of novel frameworks and theoretical provably secure solutions to problems arising from applications.

We highlight progress made during this period on several ongoing projects.

Professor Goldwasser, together with Barak, Goldreich, and Lindell worked on Resettably-sound proofs and arguments. These concept was previously investigated by Reyzin and Micali in the public-key setting. These protocols maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. In the current work it is shown that resettably-sound zero-knowledge arguments for NP exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge proofs are possible only for languages in P/poly.Two applications of resettably-sound zero-knowledge arguments are presented. First, we construct resettable zero-knowledge arguments of knowledge for NP, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proof of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside BPP. Second, we construct a constant-round resettable zero-knowledge argument for NP in the public-key model, under the assumption that collision-free hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions.

We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are impossible to achieve using black-box simulations. In particular, only languages in BPP have resettably-sound arguments that are zero-knowledge with respect to black-box simulation. [BGGL]2. IDENTIFICATION SCHEMES IN PRESENCE of RESET ATTACKS.

Professor Goldwasser, worked on providing identification protocols that are secure even when the adversary can reset the internal state and/or randomization source of the user identifying itself, and when executed in an asynchronous environment like the Internet that gives the adversary concurrent access to instances of the user. These protocols are suitable for use by devices (like smartcards) which when under adversary control may not be able to reliably maintain their internal state between invocations. Several schemes, based on non-malleable encryption, signatures secure against chosen message attack, and proofs of knowledge, designed together with Bellare, Fischlin, and Micali appeared in Eurocrypt 2001 [BFGM] .3. RING SIGNATURESProfessor Rivest together with Shamir and Tauman introduce the notion of a ring signature: a digital signature that specifies a set of possible signers, such that the verifier can't tell which member actually produced the signature. Unlike group signatures, ring signatures have no group managers, no setup procedures, and no coordination: any user can sign on behalf of any set to which he belongs, and he can choose a new set for each message without getting the consent or assistance of the other members. The only requirement is that each possible signer is already using some public key signature scheme, such as RSA. Ring signatures provide an elegant way to leak authoritative secrets in an anonymous way, to implement designated-verifier signature schemes which can authenticate emails without undesired side effects, and to solve other problems in multiparty computations. Rivest et. al. proposed a ring signature scheme which is provably secure in the random oracle model, provides unconditional anonymity, and is exceptionally efficient: adding each ring member increases the cost of signing or verifying by a single modular multiplication and a single symmetric encryption.

An identity escrow scheme allows a member of a group to prove membership in this group without revealing any extra information. At the same time, in case of abise, his identity can still be discovered. Such a scheme allows anonymous access control. Recently Anna Lysyanskaya put forward the notion of an identity escrow scheme with appointed verifiers. Such a scheme allows the user to only convince the appointed verifier(s) if his membership; but no unauthorized verifier can become convinced of the user's membership even if the user fully cooperates, unless the user is completely under his control. We provide a formal definition of this new notion and give an efficient construction of an identity escrow scheme with appointed verifiers provably secure under common number-theoretic assumptions in the public-key model. Our framework and techniques easily translate to the setting of an anonymous credential system. [CL]5. THRESHOLD CRYPTOGRAPHYThreshold cryptosystems and signatures schemes provide ways to distribute trust throughout a group and increase the availability of cryptographic systems. Although the adversary is allowed to corrupt up to one half of the servers, the goal is to sustain the security of the underlying functionality. A standard approach in designing these protocols is to base them upon existing single-party systems having

the desired properties.

The best practical yet provably secure signature schemes known (Cramer-Shoup'99) rely upon the inversion of a prime number modulo a secret value. Recently [LP] we improved the distributed modular inversion protocol of Catalano, Gennaro and Halevi to make it secure against an adaptive adversary, thereby enabling threshold signature schemes with stronger security properties than any previous result.

As a tool, we also developed an adaptively-secure, erasure-free threshold version of the Paillier cryptosystem.6. ACCOUNTABLE-SUBGROUP MULTISIGNATURES

Leo Reyzin together with Silvio Micali, and Kazuo Ohta worked on Accountable-Subgroup Multisignatures will appear in 8^th ACM Conference on Computer and Communications Security, 2001 [MOR].Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.

2. Compare the relative strength of the RSA intractability assumption and the strong-RSA assumption.3. Professor Rivest plans to continue investigating technologies for voting. He is currently organizing (together with David Chaum) a specialized workshop on this topic (WOTE '01) which Kazuo Ohta (formerly of NTT) Tatsuaki Okamoto (currently at NTT) will attend. This workshop will be attended by many of the key researchers in the field. It is likely that this research will result in new directions for research in voting technologies, which we would then plan to pursue with the support of NTT.4. Extend the framework and results of identity escrow to electronic voting. In electronic voting, it is desirable that the user, even when fully cooperating, is unable to convince the mafia that he has voted in a certain way. Similar to our identity escrow setting, there are two adversaries here: the voter (whose behavior may be adversarial since he is communicating with the mafia) and the mafia. This problem has found a number of heuristic solutions, but a formal approach has not been considered.

5. Improve threshold signature schemes. For example, recently, a non-interactive signature scheme was proposed by Shoup. However, its security can only be proved for a static adversary and in the random oracle model. An interesting question to explore is how close to it one can come if these are relaxed. This can lead both to more efficient constructions and to lower bounds.

[BGGL] 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.[BFGM] 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.

[CL] Jan Camenisch, Anna Lysyanskaya. "An Identity Escrow Scheme with Appointed Verifiers." To appear in Crypto 2001. [LP] Anna Lysyanskaya, Christopher Peikert. "Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes." Manuscript, Asiacrypt 2001. To appear.[MOR] Silvio Micali, Kazuo Ohta, and Leonid Reyzin. "Accountable-Subgroup Multisignatures." To appear in 8th ACM Conference on Computer and Communications Security, 2001.