We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: âą ZAPs (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions. âą NIWIs from indistinguishability obfuscation and one-way permutations. The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06]. âMIT. Email: nirbitan@csail.mit.edu. Part of this work was done while at Tel Aviv University. â Boston University. Email: omer@bu.edu. Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.
The growing demands of users and industry have led to an increase in both size and complexity of deployed software in recent years. This tendency mainly stems from a growing number of interconnected mobile devices and from the huge amounts of data that is collected every day by a growing number of sensors and interfaces.\nSuch increase in complexity imposes various challenges -- not only in terms of software correctness, but also with respect to security. This thesis addresses three complementary approaches to cope with the challenges: (i) appropriate high-level abstractions and verifiable translation methods to executable applications in order to guarantee flawless implementations, (ii) strong cryptographic mechanisms in order to realize the desired security goals, and (iii) convenient methods in order to incentivize the correct usage of existing techniques and tools.\nIn more detail, the thesis presents two frameworks for the declarative specification of functionality and security, together with advanced compilers for the verifiable translation to executable applications. Moreover, the thesis presents two cryptographic primitives for the enforcement of cloud-based security properties: homomorphic message authentication codes ensure the correctness of evaluating functions over data outsourced to unreliable cloud servers; and efficiently verifiable non-interactive zero-knowledge proofs convince verifiers of computation results without the verifiers having access to the computation input.
Abstract. Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called (1 + Δ)-leakage-resilient zero-knowledge, for any constant Δ> 0, because the total length of the leakage the simulator needs is (1 + Δ) times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of Δ = 0. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem. Key word: zero-knowledge proofs, proofs of knowledge, leakage-resilient, non-black-box simulation, constant-round. 1
In recent years there has been a fantastic boom of increasingly sophisticated âcryptographic objects â â identity-based encryption, fully-homomorphic encryption, functional encryption, and most recently, various forms of obfuscation. These objects often come in various flavors of security, and as these constructions have grown in number, complexity and inter-connectedness, the relationships between them have become increasingly confusing. We provide a new framework of cryptographic agents that unifies various cryptographic objects and security definitions, similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. Our contributions can be summarized as follows. âą Our main contribution is a new model of cryptographic computation, that unifies and extends cryptographic primitives such as Obfuscation, Functional Encryption, Fully Homomorphic En-cryption, Witness encryption, Property Preserving Encryption and the like, all of which can be cleanly modeled as âschemata â in our framework. We provide a new indistinguishability preserving (IND-PRE) definition of security that interpolates indistinguishability and simulation
Almost all existing password-based authenticated key exchange (PAKE) schemes achieve concurrent security in the standard model by relying on the common reference string (CRS) model. A drawback of the CRS model is to require a centralized trusted authority in the setup phase; thus, passwords of parties may be revealed if the authority ill-uses trapdoor information of the CRS. There are a few secure PAKE schemes in the plain model, but, these are not achievable in a constant round (i.e., containing a linear number of rounds). In this paper, we discuss how to relax the setup assumption for (constant round) PAKE schemes. We focus on the multi-string (MS) model that allows a number of authorities (including malicious one) to provide some reference strings independently. The MS model is a more relaxed setup assumption than the CRS model because we do not trust any single authority (i.e., just assuming that a majority of authorities honestly generate their reference strings). Though the MS model is slightly restrictive than the plain model, it is very reasonable assumption because it is very easy to implement. We construct a (concurrently secure) three-move PAKE scheme in the MS model (justly without random oracles) based on the Groce-Katz PAKE scheme. The main ingredient of our scheme is the multi-string simulation-extractable non-interactive zero-knowledge proof that provides both the simulation-extractability and the extraction zero-knowledge property even if minority authorities are malicious. This work can be seen as a milestone toward constant round PAKE schemes in the plain model.
We provide a new framework of cryptographic agents that unifies various modern âcryp- tographic objectsâ â identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation â similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as âschemataâ in our framework. Highlights of our framework include the following: âą We use a new indistinguishability preserving (IND-PRE) definition of security that in- terpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. IND-PRE-security is parameterized by the choice of the âtestâ family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature). âą We present a notion of reduction from one schema to another and a powerful composition theorem with respect to IND-PRE security. We show that obfuscation is a âcompleteâ schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction (â-reduction) that composes even when security is only with respect to certain restricted test families of importance. âą Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on standard model assumptions. We also illustrate how our framework can be applied to specific primitives like obfus- cation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives. âUniversity of Illinois, Urbana-Champaign. Email: sagrawl2@illinois.edu. â Indian Institute of Technology, Delhi. Email: shweta.a@gmail.com. âĄUniversity of Illinois, Urbana-Champaign. Email: mmp@illinois.edu.
Secure two-party computation cannot be fair against malicious adversaries, unless a trusted third party (TTP) or a gradual-release type super-constant round protocol is employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair via a partial simulation, which, we show, may lead to insecurity overall. We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yaoâs garbled circuits and zero-knowledge proofs. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore, even if the TTP becomes malicious and causes unfairness by colluding with one party, the security of the underlying protocol is still preserved.
In response to the need for secure one-round authenticated key exchange protocols providing both perfect forward secrecy and full deniability, we put forward a new paradigm for constructing protocols from a Diffie-Hellman type protocol plus a non-interactive designated verifier proof of knowledge (DV-PoK) scheme. We define the notion of DV-PoK which is a variant of non-interactive zero-knowledge proof of knowledge, and provide an efficient DVPoK scheme as a central technical building block of our protocol. The DV-PoK scheme possesses nice properties such as unforgeability and symmetry which help our protocol to achieve perfect forward secrecy and full deniability respectively. Moreover, the security properties are formally proved in the Canetti-Krawczyk model under the Gap Diffie-Hellman assumption. In sum, our protocol offers a remarkable combination of salient security properties and efficiency, and the notion of DV-PoK is of independent interests.
In anonymous reputation systems, where after an interaction between anonymous users, one of the users evaluates the peer by giving a rating. Ratings for a user are accumulated, which becomes the reputation of the user. By using the reputation, we can know the reliability of an anonymous user. Previously, anonymous reputation systems have been proposed, using an anonymous e-cash scheme. However, in the e-cash-based systems, the bank grasps the accumulated reputations for all users, and the fluctuation of reputations. These are private information for users. Furthermore, the timing attack using the deposit times is possible, which makes the anonymity weak. In this paper, we propose an anonymous reputation system, where the reputations of users are secret for even the reputation manager such as the bank. Our approach is to adopt an anonymous credential certifying the accumulated reputation of a user. Initially a user registers with the reputation manager, and is issued an initial certificate. After each interaction with a rater, the user as the ratee obtains an updated certificate certifying the previous reputation summed up by the current rating. The update protocol is based on the zero-knowledge proofs, and thus the reputations are secret for the reputation manager. On the other hand, due to the certificate, the user cannot maliciously alter his reputation.
SMC(Secure Multi-party Computation)mainly addresses the problem of cooperation within the distrustful partners,SMC requires the independence assurance of inputs and computation correctness,and meanwhile shouldn't leak any input to other partners. SMC could be widely used in internet ballot and internet auction. This paper analyzes the key technologies,including secure protocols,bit commitment,oblivious transfer,and zero-knowledge proof. Finally,the paper describes the applications of SMC,and these are significant in theory and practice.
We show how to construct a O(1)-round resettably-sound zero-knowledge argument of knowledge based on one-way functions where additionally the construction and proof of se-curity is black-box. Zero-knowledge proofs (ZK) are fundamental cryptographic constructs used in numerous applications. Formalized using a âsimulation â paradigm, ZK requires that for every malicious verifier there exists a âsimulator â that can indistinguishably reproduce the view of the verifier in an interaction with the honest prover. Resettable-soundness introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS 01) additionally demands the soundness property to hold even if the malicious prover is allowed to âreset â and ârestart â the verifier. Using the breakthrough non-black-box technique of Barak (FOCS 01) they also provided a constant-round construction of a resettably-sound ZK argument relying on the existence of collision-resistance hash-functions. This construction and subsequent constructions all rely on the underlying cryptographic primitive in a non black-box way. Recently, Goyal, Ostro-vsky, Scafuro and Visconti (STOC 14) showed how to extend the Barakâs technique to obtain a construction and proof of security that relies on the collision-resistant hash-function in a black-box manner while still having a non black-box simulator. Such a construction is referred to as semi black-box. From the work of Chung, Pass and Seth (STOC 13) we know that the minimal assumption required to construct resettably-sound ZK argument is the existence of one-way functions. In this work we close the gap between (semi) black-box and non black-box constructions by showing a black-box (round-efficient) resettably-sound argument relying on one-way functions only. 1
BenoĂźt Libert, Marc JĂłye, Moti Yung, Thomas Peters
To gain strong confidence in the security of a public-key scheme, it is most desirable for the security proof to feature a tight reduction between the adversary and the algorithm solving the underlying hard problem. Recently, Chen and Wee (Cryptoâ13) described the first Identity-Based Encryption scheme with almost tight security under a standard assumption. Here, âalmost tightâ means that the security reduction only loses a factor O(λ) âwhere λ is the security parameterâ instead of a factor proportional to the number of adversarial queries. Chen and Wee also gave the shortest signatures whose security almost tightly relates to a simple assumption in the standard model. Also recently, Hofheinz and Jager (Crypto â12) constructed the first CCA-secure public-key encryption scheme in the multi-user setting with tight security. These constructions give schemes that are significantly less efficient in length (and thus, processing) when compared with the earlier schemes with loose reductions in their proof of security. Hofheinz and Jagerâs scheme has a ciphertext of a few hundreds of group elements, and they left open the problem of finding truly efficient constructions. Likewise, Chen and Weeâs signatures and IBE schemes are somewhat less efficient than previous constructions with loose reductions from the same assumptions. In this paper, we consider space-efficient schemes with security almost tightly related to standard assumptions. We construct an efficient CCA-secure public-key encryption scheme whose chosen-ciphertext security in the multi-challenge, multi-user setting almost tightly relates to the DLIN assumption (in the standard model). Quite remarkably, the ciphertext size decreases to 69 group elements under the DLIN assumption whereas the best previous solution required about 400 group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla and Roy (Asiacryptâ13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by 37% under the Decision Linear assumption, by almost 50% under the K-LIN assumption, and it becomes only 3 group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.
Nico Döttling, Daniel Kraschewski, Jörn MĂŒllerâQuade, Tobias Nilges
Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Dottling, Kraschewski, Muller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for statistically secure computation in general (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.
J-PAKE is a Password-Authenticated Key Exchange protocol, proposed in 2008 and presented again in 2010 and 2011. It does not require any public key infrastructure but uses zero-knowledge proofs. J-PAKE has been submitted as a candidate for the IEEE P1363.2 standard for password-based public key cryptography, and included in OpenSSL and OpenSSH. Since December 2010, J-PAKE has been used in Mozilla Firefox web browser. In this paper, we show that J-PAKE is vulnerable to password compromise impersonation attack, replay attack, and unknown key-share attack. We also propose some improvements for thwarting replay and unknown key-share attacks.