Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, Daniele Venturi
Non-malleable codes are a natural relaxation of error correcting/detecting codes that have useful applications in the context of tamper resilient cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This paper introduces an extension of the standard non-malleability security notion ‐ so-called continuous non-malleability ‐ where we allow the adversary to tamper continuously with an encoding. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding. We show how to construct continuous non-malleable codes in the common split-state model where an encoding consist of two parts and the tampering can be arbitrary but has to be independent with both parts. Our main contributions are outlined below: 1. We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords C = (X0;X1) and C 0 = (X0;X 0 1 ) such that both codwords are valid, butX0 is the same in bothC andC 0 . A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that non of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting. 2. We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string. 3. We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.
Bitcoin has recently gained popularity as a peer-to-peer decentralized electronic currency system. It was designed to provide all the desirable properties of electronic cash. One of the desirable properties of Bitcoin is that it does not depend on a central authority like a bank or the government. This paper introduces Bitcoin and its characteristics together with its core components–block, block chain and transaction. Mechanisms for ensuring privacy and security in Bitcoin are also presented. Primitives like hash functions and digital signatures play important roles in providing cryptographic functionalities for Bitcoin. SHA-256 is used to prevent malicious parties from stealing and creating coins. Specific characteristics of this hash function and its suitability for bitcoin would be analyzed. The elliptic Curve digital signature Algorithm (ECDSA) is used for confirming identity of payer and validating truncation. Properties of the Elliptic curve used in ECDSA and the signature algorithm would also be technically analyzed together with their role in protecting the electronic currency for the next few decades.
Technology is linking the slightest of our actions to the virtual world. In such connected environments, cryptography aims at building schemes with provable security in order to mathematically protect the users' security in electronic exchanges. Relying on the existence of pairings in bilinear groups wherein the discrete logarithm problem is hard, this thesis puts forth mechanisms to efficiently enhance the privacy in three of the most fundamental cryptographic primitives, namely, digital signatures, encryption schemes and zero-knowledge proofs. Furthermore, these mechanisms support public verifiability so as to force the honesty of all participants in the standard model. We first focus on group signatures, a primitive proposed some 20 years ago, for which we propose the first efficient revocation mechanisms, overcoming the main obstacle to the deployment of this primitive in practical applications. We then focus on P-homomorphic signatures that make it possible to modify a signed message in a controlled way. In particular, we propose new mechanisms providing structure-preserving linearly homomorphic signatures, from which we build the first constant-size non-malleable commitments compatible with standard proof systems, as well as a generalization of this construction into a generic transformation. Finally we further investigate the unexpected applications of this kind of malleable signatures to non-malleable cryptography. This leads us to new proof systems for linear languages which in turn provide the most efficient publicly verifiable CCA-secure threshold encryption to date, and other new extensions.
A new signature scheme based solely on the MQ-problem is presented,which satisfies the following properties:(1)Forward security,which means that a compromise of a key now does not necessarily expose old traffic.(2)Backward security,which means that a compromise of a key now does not necessarily expose future traffic.We do not have to revoke our public key and re-issue a new key system everytime we detect a key leak.We use two fundamental tools,such as zero knowledge proof and mulitivariate public crypto.Our basic model is Koichi Sakumoto's identifcation scheme which is transformed by parallel processing and Fiat-Shamir transforming.What is novel about our approach is the key updating algortithm,which makes our scheme preserve backward security besides the forward property.Finally,we prove that our scheme satisfies the security under the random oracle model.
One of the central problems in the development of distributed systems is the design of cryptographic protocols that meet specified functional requirements and preserve user privacy. Methods of conventional encryption algorithms typically use PKI. In this paper we presented a method based on other approach. The authors have developed a cryptographic framework for access control, ensured the confidentiality of social relations, secrecy of resources and anonymity of users in social networks. The implementation of the protocols in the framework is combination of zero-knowledge proof and signature schemes Camenisch-Lysyanskaya.
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
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.
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.
Public key infrastructures (PKIs) enable users to look up and verify one another’s public keys based on identities. Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of identity retention; that is, they do not effectively prevent one user from registering a public key under another’s already-registered identity. In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention. Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup. 1
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.
Abstract. We show how to realize two-factor authentication for a Bitcoin wal-let employing the two-party ECDSA signature protocol adapted from MacKen-zie & Reiter (2004). We also present a prototypic implementation of a Bitcoin wallet that offers both: two-factor authentication and verification over a sepa-rate channel. Since we use a smart phone as the second authentication factor, our solution can be used with hardware already available to most users and the user experience is quite similar to the existing online banking authentication methods. 1.
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.