Abstract It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved. We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.
Abstract It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved. We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.
Abstract. We revisit the definitions of zero-knowledge in the Common Reference String (CRS) model and the Random Oracle (RO) model. We argue that even though these definitions syntactically mimic the standard zero-knowledge definition, they loose some of its spirit. In particular, we show that there exist a specific natural security property that is not captured by these definitions. This is the property of deniability. We formally define the notion of deniable zero-knowledge in these models and investigate the possibility of achieving it. Our results are different for the two models: – Concerning the CRS model, we rule out the possibility of achieving deniable zero-knowledge protocols in “natural ” settings where such protocols cannot already be achieved in plain model. – In the RO model, on the other hand, we construct an efficient 2-round deniable zero-knowledge argument of knowledge, that preserves both the zero-knowledge property and the proof of knowledge property under concurrent executions (concurrent zero-knowledge and concurrent proof-of knowledge). 1
The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random string and gives it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority, we only assume a majority of them generate the random string honestly. We demonstrate the use of this model for two fundamental cryptographic taks. We define non-interactive zero-knowledge in the multi-string model and construct NIZK proofs in the multi-string model. We also consider multi-party computation and show that any functionality can be securely realized in the multi-string model.
Abstract. Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a common reference string (CRS) available to parties executing the protocol. In either of the above settings, some assumption regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost. A natural question is whether it is possible to design protocols secure if either one of these assumptions holds, i.e., a protocol which is secure if either at most s players are dishonest or if up to t> s players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if s + t < n. 1
This thesis presents a theoretical analysis of round complexity in cryptographic sampling protocols. We study the following problem: how can n participants agree on a random sample from the distribution D without anybody knowing any secret information hidden in the chosen sample? How many rounds of interactions are needed in any such protocol? Which assumptions are required? These questions are particularly interesting in the context of multiparty computation (MPC) due to the extensive reliance (often unavoidable) on trusted setups such as common reference strings (CRSs). These are samples from known distributions made public before the beginning of the protocol. Security proofs often require CRSs to hide trapdoors. However, if these trapdoors get leaked, security is often fatally compromised. Since trusted setups are inherently single points of failure, it is desirable to generate CRSs in a distributed fashion using MPC protocols: as long as at least one of the participants remains honest, any trapdoor hidden in the CRS is guaranteed to remain secret. Previous research (Garg et al. TCC ’14) had shown that, in the setting of semi-honest security with dishonest majority, any functionality can be implemented in two rounds. In this thesis, we show that, using strong primitives such as indistinguishability obfuscation (iO), it is possible to build one-round sampling protocols. We call these constructions distributed samplers. We show that these protocols can be used to securely generate large amounts of correlated randomness with sublinear communication in a single round. We study different ways to upgrade our semi-honest construction to active security. First, we try to circumvent Cleve’s impossibility (STOC ’86) by allowing the adversary limited influence on the output of the protocol: we consider the functionality F_D^{Active} that proposes a polynomial number of different outputs to the adversary, letting it choose its favourite one (F_D^{Active} can still be used to generate CRSs). We show how to implement F_D^{Active} in one round by relying on a programmable random oracle. In subsequent work, we show that random oracles are necessary: any actively secure distributed samplers implementing F_D^{Active} needs to rely on a CRS that is non-reusable, as large as a sample from D and structured (unless D is an obliviously samplable distribution). This suggests that, without random oracles, simulation-based, actively secure distributed samplers provide no advantage over trusted dealers. We get around this impossibility by proposing new game-based definitions for actively secure distributed samplers. Hardness-preserving distributed samplers allow the removal of CRSs from MPC protocols preserving at the same time the hardness of search problems. Indistinguishability-preserving distributed samplers, on the other hand, substitute the trusted setup while preserving the functionality, however, the protocol needs to satisfy particular conditions. We show how to build distributed samplers with the defined properties by relying on extremely lossy functions, the subexponential security of iO and other primitives. Next, in the context of active security with dishonest majority, we study the feasibility of protocols producing unbiased samples with guaranteed output: to circumvent Cleve's impossibility, we assume the existence of an auxiliary functionality that, upon invocation, publishes a random , short k-bit string. We first study the question when D is the uniform distribution over {0, 1}^m where m>k. This problem is called coin tossing extension (CTE) (Bellare et al. PODC '96). We show the existence of O(1)-round CTE constructions producing an arbitrarily large quantity of unbiased randomness based on various assumptions (OWFs, DDH, QR and DCR, class groups). Our most important result is an LWE-based, one-round, UC-secure, n-party CTE protocol withstanding adaptive corruption. The protocol can be viewed as an explainable randomness extractor. By relying on distributed samplers and the auxiliary functionality, we build one-round unbiased sampling protocols for any distribution. Finally, we present a lower bound for statistically secure CTE with black-box simulation: an R-round protocol can generate at most k+R·O(log λ) bits of randomness.
In [AGP14] Ananth et al. showed that continual leakage-resilient non-transferable interactive proofs exist when a leak-free input-encoding phase is allowed and a common reference string is available. They left open the problem of removing the need of a common reference string. In [BGJK12] Boyle et al. showed that for some interesting functionalities continual leakage-resilient secure computation is possible when leak-free interactive preprocessing and input-encoding phases are allowed. They left open the problem of removing the interactive pre-processing. In this work we study the above questions. Our main contribution shows that leakage-resilient black-box zero-knowledge is impossible when relying on a leak-free input-encoding phase only (i.e., without CRS/preprocessing). Additionally, we also show that leakage-resilient multi-party computation for all functionalities is impossible (regardless of the number of players assuming just one corrupted player) when relying only on a leak-free input-encoding phase (i.e., without CRS/preprocessing). Our results are achieved by extending a technique of [NVZ13] to prove lower bounds for leakage-resilient security. Indeed as in [NVZ13] we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks.