The idea of Zero Knowledge Proof (ZKP) was first proposed by Goldwasser, Micali and Racko [S. Goldwasser, et al. 1989.] in 1989. It is a mutual protocol to solve the problem: the prover demonstrates to the verifier that he has some secret information, but after that the verifier doesnât know what the secret information is. In the verification process, the prover lets out zero information about the secret to the verifier. ZKP can be divided into two basic kinds: interactive and non-interactive zero knowledge proof . Zero knowledge proof protocols are used extensively in the field of information security, such as identity authentication, fair exchange, key agreement, electronic voting and electronic payment system, etc.
Abstract. Pedersen commitments are important cryptographic primi-tives. They allow a prover to commit to a certain value without revealing any information about it and without the prover being able to change its mind later on. Since the first property holds unconditionally this is an essential primitive for many schemes providing long-term confidential-ity. However, the second property only holds computationally. Hence, in the long run bindingness is lost, making the primitive improper for long-lived systems. Thus in this paper, we describe a protocol that, in a sense, prolongs the bindingness of a given Pedersen commitment. More precisely, we demonstrate how to prove in perfect zero-knowledge that a new Pedersen commitment- generated with a larger security param-eter- and a corresponding old commitment both commit to the same value. We stress that this is a non-trivial procedure. Up until now the only known perfect zero-knowledge proof techniques for proving mes-sage equivalence of two commitments work when both commitments use isomorphic message spaces. However, as we will show in this work, to prolong the security of Pedersen commitments we cannot tolerate this restriction. Our prolonging technique works for non-isomorphic message spaces, is efficient, can be repeated an arbitrary number of times, main-tains unconditional confidentiality, and allows to preserve the format of the Pedersen commitments. This makes the construction presented here an important contribution to long-lived systems. Finally, we illustrate this by discussing how commitments with prolongable bindingness can be used to allow for archiving solutions that provide not only integrity but also confidentiality in the long-term.
The article proposes a novel construction of sign-cryption scheme with provable security which is most suited to be implement on smart card. It is secure in random oracle model and the security relies on Decisional Bilinear Diffie-Hellmann Problem. The proposed scheme is secure against adaptive chosen ciphertext attack (indistiguishbility) and adaptive chosen message attack (unforgeability). The scheme have the security properties anonymity and forward security. Also it is inspired by zero-knowledge proof and is publicly verifiable. The scheme has applied for mutual authentication to authenticate identity of smart card's user and reader via Application protocol Data units. This can be achieved by the verification of the signature of the proposed scheme. Also the sensitive information are stored in the form of ciphertext in Read Only Memory of smart cards. These functions are performed in one logical step at a low computational cost.
For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,Δ)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}Δ^{-2}\right)$ in time/circuit size, which is better by a factor $Δ^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.
Cryptography relies on Mathematics in all its aspects, beginning from the constructions relying on various mathematical theories, continuing with security evaluation of cryptographic systems, and proving their security, and finally ending in implementation.Recently, new security threats are posed by the emerging quantum computing technology.Specifically, quantum algorithms can break some public-key encryption schemes such as RSA and Elgamal, which are widely used for protection of computer systems and networks.This issue demands us to develop a new generation of cryptographic systems, which will serve as secure alternatives to the currently used ones.Such the new systems are referred to as the post-quantum cryptography.One promising direction in post-quantum cryptography is the systems whose security is based on hardness of mathematical problems arising in the context of coding theory.In particular, the problem of decoding random linear codes has been studied for over 30 years, and still no polynomial-time solution has been proposed, even when using quantum algorithms.In this thesis, we focus on this area, which is called the code-based cryptography.The first code-based public-key encryption (PKE) scheme was introduced by R.J. McEliece in 1978.Since then, various code-based public-key encryption, digital signature and identification schemes were introduced, but currently, one of the main challenges is to introduce more advanced cryptographic functionalities based on coding.In this thesis, first, we give a brief introduction about post-quantum cryptography and codebased cryptography, and then we provide the background information about the cryptographic primitives, which we will study, as well as the relevant notions and results from coding theory and cryptography.Next, we introduce our contributions as follows.Firstly, we study zero-knowledge (ZK) identification schemes based q-ary linear codes.We show that when q < 5, a straightforward generalization of Stern's ZK identification scheme (1993) is more efficient in terms of both communication and computation, as compared to the ZK identification scheme by Cayrel, Vron and El Yousfi Alaoui (2010), which is specifically designed for q-ary codes.Secondly, we introduce the first proof of plaintext knowledge (PPK) for the McEliece PKE and the Niederreiter PKE.These protocols allow the encryptor to prove the knowledge of the plaintext contained in a given ciphertext to any party, who does not hold the secret key for decryption.We also provide a performance evaluation for the proposed schemes.
In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of weakly Random-Self-Reducible public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as weakly Random-Self-Reducible. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel â PKC 13] to prove lower bounds for leakage-resilient security. Indeed, 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. Our results show that the open problem of [Ananth, Goyal, Pandey â Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. â STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).
Randomized encodings of functions can be used to replace a âcomplexâ function $f(x)$ by a âsimplerâ randomized mapping $\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding $\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\hat{x}$, where the online complexity of computing $\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\hat{x}$ consists of $n$ encryption keys of length $\kappa$ each, where $n=|x|$ and $\kappa$ is a security parameter. Thus, the online rate $|\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\{0,1\}^n\to\{0,1\}^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie--Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.
Abstract. In a secure physical computation, a set of parties each have physical inputs and jointly compute a function of their inputs in a way that reveals no information to any party except for the output of the function. Recent work in CRYPTOâ14 presented examples of physical zero-knowledge proofs of physical properties, a special case of secure physical two-party computation in which one party has a physical input and the second party verifies a boolean function of that input. While the work suggested a general framework for modeling and analyzing physi-cal zero-knowledge protocols, it did not provide a general theory of how to prove any physical property with zero-knowledge. This paper takes an orthogonal approach using disposable circuits (DC)âcheap hardware tokens that can be completely destroyed after a computationâan ex-tension of the familiar tamper-proof token model. In the DC model, we demonstrate that two parties can compute any function of their physical inputs in a way that leaks at most 1 bit of additional information to either party. Moreover, our result generalizes to any multi-party physical computation. Formally, our protocols achieve unconditional UC-security with input-dependent abort. 1
The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's technique has given rise to various powerful applications and is a key component in all known protocols with non-black-box simulation. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity. A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals such as simultaneously resettable zero-knowledge, proofs of knowledge, and resettable security from one-way functions. While previous works required tailored modifications to Barak's technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions. The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality, thus settling a question left open by Barak et al. In the converse direction, we show a generic transformation from any resettably sound zero-knowledge protocol to a family of functions that cannot be obfuscated.
Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels · 5 authors
Conventional cryptographic services such as hardware-security modules and software-based key-management systems offer the ability to apply a pseudorandom function (PRF) such as HMAC to inputs of a client's choosing. These services are used, for example, to harden stored password hashes against offline brute-force attacks.
We propose a modern PRF service called PYTHIA designed to offer a level of flexibility, security, and ease-of-deployability lacking in prior approaches. The keystone of PYTHIA is a new cryptographic primitive called a verifiable partially-oblivious PRF that reveals a portion of an input message to the service but hides the rest. We give a construction that additionally supports efficient bulk rotation of previously obtained PRF values to new keys. Performance measurements show that our construction, which relies on bilinear pairings and zero-knowledge proofs, is highly practical. We also give accompanying formal definitions and proofs of security.
We implement PYTHIA as a multi-tenant, scalable PRF service that can scale up to hundreds of millions of distinct client applications on commodity systems. In our prototype implementation, query latencies are 15 ms in local-area settings and throughput is within a factor of two of a standard HTTPS server. We further report on implementations of two applications using PYTHIA, showing how to bring its security benefits to a new enterprise password storage system and a new brainwallet system for Bitcoin.
Code-based public-key encryption schemes (PKE) are the candidates for post-quantum cryptography, since they are believed to resist the attacks using quantum algorithms. The most famous such schemes are the McEliece encryption and the Niederreiter encryption. In this paper, we present the zero-knowledge (ZK) proof systems for proving statements about data encrypted using these schemes. Specifically, we present a proof of plaintext knowledge for both PKE's, and also a verifiable McEliece PKE. The main ingredients of our constructions are the ZK identification schemes by Stern from Crypto'93 and by Jain, Krenn, Pietrzak, and Tentes from Asiacrypt'12.
Abstract. LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instanti-ations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys. In this paper, we mount interpolation attacks (algebraic attacks intro-duced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of 2â38 of its 80-bit key instances could be broken 223 times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about 1000 times faster. In order to obtain these results, we had to develop novel techniques and optimize the original interpolation attack in new ways. While some of our new techniques exploit specific internal properties of LowMC, others are more generic and could be applied, in principle, to any block cipher.
A Probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form âx â L â by querying only few bits of the proof. A zero-knowledge PCP (ZKPCP) is a PCP with the additional guarantee that the view of any verifier querying a bounded number of proof bits can be efficiently simulated given the input x alone, where the simulated and actual views are statistically close. Originating from the first ZKPCP construction of Kilian et al. (STOC â97), all previous constructions relied on locking schemes, an unconditionally secure oracle-based commitment primitive. The use of locking schemes makes the verifier inherently adaptive, namely, it needs to make at least two rounds of queries to the proof. Motivated by the goal of constructing non-adaptively verifiable ZKPCPs, we suggest a new technique for compiling standard PCPs into ZKPCPs. Our approach is based on leakage-resilient circuits, which are circuits that withstand certain âside-channel â attacks, in the sense that these attacks reveal nothing about the (properly encoded) input, other than the output. We observe that the verifierâs oracle queries constitute a side-channel attack on the wire-values of the circuit
2 source records
Cryptographic Implementations and Security
Physical Unclonable Functions (PUFs) and Hardware Security
Motivated by the goal of removing trusted setup assumptions from cryptography, we introduce the notion of witness signatures. This primitive allows any party with a valid witness to an NP statement to sign a message on behalf of that statement. We also require these signatures to be unforgeable: that is, producing a signature on a new message (even given several message, signature pairs) should be as hard as computing a witness to the NP statement itself. Witness signatures are closely related to previously well-studied notions such as non-malleable non-interactive zero knowledge arguments, and signatures of knowledge. In this work, we formalize this notion and show that most natural definitions are impossible in the plain model without any setup assumptions. While still wanting to avoid a central trusted setup, we turn to the tamper proof hardware token model of Katz (Eurocrypt 2007). Interestingly, we show witness signatures in the hardware token model are closely related to what we call non-malleable multi-prover zero-knowledge proofs in the plain model (i.e. without hardware tokens). We initiate the study of non-malleable multi-prover zero-knowledge proofs, and, provide an unconditional construction of single round non-malleable two-prover zero-knowledge proofs. We then use this primitive to obtain an unconditional
Patrick McCorry, Siamak F. Shahandashti, Dylan Clarke, Feng Hao
Abstract. Bitcoin is designed to protect user anonymity (or pseudonymity) in a financial transaction, and has been increasingly adopted by major e-commerce websites such as Dell, PayPal and Expedia. While the anonymity of Bitcoin transactions has been extensively studied, little attention has been paid to the security of post-transaction correspondence. In a commercial ap-plication, the merchant and the user often need to engage in follow-up corre-spondence after a Bitcoin transaction is completed, e.g., to acknowledge the receipt of payment, to confirm the billing address, to arrange the product de-livery, to discuss refund and so on. Currently, such follow-up correspondence is typically done in plaintext via email with no guarantee on confidentiality. Obviously, leakage of sensitive data from the correspondence (e.g., billing ad-dress) can trivially compromise the anonymity of Bitcoin users. In this paper, we initiate the first study on how to realise end-to-end secure communica-tion between Bitcoin users in a post-transaction scenario without requiring any trusted third party or additional authentication credentials. This is an important new area that has not been covered by any IEEE or ISO/IEC se-curity standard, as none of the existing PKI-based or password-based AKE schemes are suitable for the purpose. Instead, our idea is to leverage the Bit-coinâs append-only ledger as an additional layer of authentication between previously confirmed transactions. This naturally leads to a new category of AKE protocols that bootstrap trust entirely from the block chain. We call this new category âBitcoin-based AKE â and present two concrete protocols: one is non-interactive with no forward secrecy, while the other is interactive with additional guarantee of forward secrecy. Finally, we present proof-of-concept prototypes for both protocols with experimental results to demonstrate their practical feasibility.
Feroz Ahmad Ahmad, Prashant Kumar, Gulshan Shrivastava, Med Salim Bouhlel
ON 12 JANUARY 2009 a pseudonymous entity signed a transaction that instructed a distributed network to transfer a small amount of digital currency to Hal Finney, one ofthe key figures of the cypherpunk movement. After a few minutes, the transaction was recorded on a distributed public ledger, permanently updating the balance ofbothparties. This transactionâ the first Bitcoin transactionâmarked the beginning of a new era of decentralized payment systems, ushering in a variety of financial Services that do not depend on any centralized clearinghouse or other financial middleman. Bitcoin is regarded by many as a powerful technological innovation that could disrupt many sectors, in the realm of finance and beyond. But the underlying technology on which the network operates, the Bitcoin blockchain can do much more than that. Just as the internet did in the early-1990s, blockchain technology carries with it a whole new range of promises concerning how decentralization can support and promote individual freedoms and autonomy. Blockchain proponents believe that Bitcoin and other cryptocurrency platforms will revolutionize mechanisms of value exchange in the same way that the internet transformed information sharing, by providing a platform for people to exchange digital resources, in a secure and decentralized manner without the need to rely on any intermediary or trusted authority. But this revolutionary potential also carries with it serious implications for censorship, intellectual property, and the regulated flow of information. A blockchain is a decentralized database of transactions maintained by a distributed network of computers, which all contribute to the verification and the validation of transactions. Once accepted, these transactions are recorded inside a âblockâ of transactions, which incorporates a reference to previous blocks. This creates a long chain of blocksâa âblockchainââthat stores the history of all transactions in a chronological order. Every block contains information about a particular set of transactions, a reference to the preceding block in the blockchain, and the answer to a complex mathematical puzzle that is used to validate the data associated with that block. A copy of the blockchain is stored on every computer in the network, making it virtually impossible for anyone unilaterally to modify the data stored on this decentralized database: if anyone tries to modify any transaction the fraud will be immediately detected by all other network participants.
Open access
43 source records
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
In this paper, we describe our analysis of a recently proposed electric vehicle charing protocol. The protocol builds on complicated cryptographic primitives such as commitment, zero-knowledge proofs, BBS+ signature and etc. Moreover, interesting properties such as secrecy, authentication, anonymity, and location privacy are claimed on this protocol. It thus presents a challenge for formal verification, as existing tools for security protocol analysis lack support for all the required features. In our analysis, we employ and combine the strength of two state-of-the-art symbolic verifiers, Tamarin and Prove if, to check all important properties of the protocol.