UCLA

The main aim of cryptography is to provide the frameworks and solutions for information security. The fundamental weapons to protect information are interactions and private randomness. Since the breakthrough result, zero-knowledge proof system, by Goldwasser, Micali, and Rackoff in mid 80s, the cryptography community has endeavored to propose the new notions of information security and the relative solutions which more closely reflect the modern computing environment.

Concurrent security first introduced by Dwork, Naor, and Sahai was suggested to capture the information security in the modern internet environment. That is, the adversary may interact with a honest parties in many concurrent executions of a protocol where the messages are scheduled in any adversarial way.

Resettable security was first introduced by Canetti, Goldreich, Goldwasser, and Micali, which models the security issues in which parties have a limited source of private randomness. In other words, an adversary might interact with honest parties in many executions of a protocol while the honest parties are only allowed to use the polynomially bounded number of (hard-wired) randomness.

An important question is: "How much efficient protocol can we construct to achieve the above security in terms of round complexity?" Unfortunately, it has been showed that the best possible round complexity for such protocols is poly-logarithmic in the security parameter based on black-box simulation without help of external set-up assumptions. Thus, the question is now to minimize the round complexity of protocols with a minimal set-up assumption.

In this thesis, we positively answer the above question with help of set-up assumptions. Specifically, we consider two set-up assumptions, the Bare Public Key (BPK) model and the Cross-Domain (CD) model. The BPK model was first introduced by Canetti, Goldreich, Goldwasser, and Micali. In the BPK model, each party is required to register their public keys before the start of interacting with each other. The CD model is a newly proposed model in this work. In the CD model, we have domains which models key certification authorities in the real world and each party belongs to one of the domains.

In the BPK model, we show a constructions of constant-round simultaneously resettable zero-knowledge argument of knowledge with a standard cryptographic assumptions. As a main building block for this result, we show a construction of constant-round simultaneously resettable witness-indistinguishable argument of knowledge.

In the CD model, we show a construction of constant-round concurrently secure multi-party computation protocol with the fixed number of domains. On the other hand, we prove that if the number of domains is not fixed, such a constant-round protocol does not exist.