Ring signatures enable a user to sign a message so that a ring of possible signers is identified, without revealing exactly which member of that ring actually generated the signature. In some situations, however, an actual signer may possibly want to expose himself, for instance, if doing so, he will acquire an enormous benefit. In this paper, a signature scheme with designated verifiability based on Schnorr ring signature is proposed. The scheme provides a confirmation procedure, in which the real signer is able to convince a designated party that he is the one who generates the signature. The confirming procedure involves an interactive Zero-Knowledge proof protocol, which is non-transferable, and it only can be triggered by the signer. Based on the intractability of Discrete Logarithm Problem (DLP), the scheme is existentially unforgeable under adaptive-chosen message attack in the random oracle model.
Authentication is primary process by which you can verify that someone is legitimate user or not. The identification of an entity or person is based on the username and password provided to that entity. In security systems, authentication is playing an important role by which it provides access to the system to an entity based on their identity. Authentication only ensures that the entity who is claims to be, but do not passes any information about the access rights of the entity. The zero- knowledge protocol used to provide data security and zero-knowledge transfer during authentication. The proposed model for node authentication using zero - knowledge proof for secure login is much faster than existing model in terms of execution time, CPU usage, time complexity and performance. It also provides security features likes confidentiality, integrity, authentication and non-repudiation.
Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this study, the authors propose the first ring signature scheme whose size is O (log 2 N ), where N is the number of users in the ring. They achieve this result by improving Chandran et al .โs ring signature scheme presented at the International Colloquium on Automata, Languages and Programming 2007. Their scheme uses a common reference string and nonโinteractive zeroโknowledge proofs. The security of their scheme is proven without requiring random oracles.
A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.
Bitcoin is a decentralized crypto-currency, and an accompanying protocol, created in 2008. Bitcoin nodes continuously generate and propagate blocks---collections of newly approved transactions that are added to Bitcoin's ledger. Block creation requires nodes to invest computational resources, but also carries a reward in the form of bitcoins that are paid to the creator. While the protocol requires nodes to quickly distribute newly created blocks, strong nodes can in fact gain higher payoffs by withholding blocks they create and selectively postponing their publication. The existence of such selfish mining attacks was first reported by Eyal and Sirer, who have demonstrated a specific deviation from the standard protocol (a strategy that we name SM1). In this paper we extend the underlying model for selfish mining attacks, and provide an algorithm to find $ฮต$-optimal policies for attackers within the model, as well as tight upper bounds on the revenue of optimal policies. As a consequence, we are able to provide lower bounds on the computational power an attacker needs in order to benefit from selfish mining. We find that the profit threshold -- the minimal fraction of resources required for a profitable attack -- is strictly lower than the one induced by the SM1 scheme. Indeed, the policies given by our algorithm dominate SM1, by better regulating attack-withdrawals. Using our algorithm, we show that Eyal and Sirer's suggested countermeasure to selfish mining is slightly less effective than previously conjectured. Next, we gain insight into selfish mining in the presence of communication delays, and show that, under a model that accounts for delays, the profit threshold vanishes, and even small attackers have incentive to occasionally deviate from the protocol. We conclude with observations regarding the combined power of selfish mining and double spending attacks.
Gurchetan S. Grewal, Mark Ryan, Liqun Chen, Michael R. Clarkson
Du-Vote is a new remote electronic voting protocol that eliminates the often-required assumption that voters trust general-purpose computers. Trust is distributed in Du-Vote between a simple hardware token issued to the voter, the voter's computer, and a server run by election authorities. Verifiability is guaranteed with high probability even if all these machines are controlled by the adversary, and privacy is guaranteed as long as at least either the voter's computer, or the server and the hardware token, are not controlled by the adversary. The design of the Du-Vote protocol is presented in this paper. A new non-interactive zero-knowledge proof is employed to verify the server's computations. Du-Vote is a step towards tackling the problem of internet voting on user machines that are likely to have malware. We anticipate that the methods of Du-Vote can be used in other applications to find ways of achieving malware tolerance, that is, ways of securely using platforms that are known or suspected to have malware.
Zero-knowledge (ZK) proofs have become a central building block for a variety of modern security protocols. Modern ZK constructions, such as the Groth-Sahai proof system, offer novel types of cryptographic flexibility: a participant is able to re-randomize existing ZK proofs to achieve, for instance, message unlink ability in anonymity protocols, she can hide public parts of a ZK proof statement to meet her specific privacy requirements, and she can logically compose ZK proofs in order to construct new proof statements. ZK proof systems that permit these transformations are called malleable. However, since these transformations are accessible also to the adversary, analyzing the security of these protocols requires one to cope with a much more comprehensive attacker model -- a challenge that automated protocol analysis thus far has not been capable of dealing with. In this work, we introduce the first symbolic abstraction of malleable ZK proofs. We further prove the computational soundness of our abstraction with respect to observational equivalence, which enables the computationally sound verification of privacy properties. Finally, we show that our symbolic abstraction is suitable for ProVerif, a state-of-the-art cryptographic protocol verifier, by verifying an improved version of the anonymous webs of trust protocol.
In this chapter we will look at two different applications of information-theoretic multiparty computation (MPC), a practical application and a theoretical application. The example of a practical application is the use of MPC to clear a commodity derivative market. The focus will be on the algorithmic tricks used to implement the auction efficiently. The theoretical application is the use of MPC to realize so-called zero-knowledge proofs. A zero-knowledge proof is a way for a prover to convince a verifier about the validity of a statement without leaking any information on why the statement is true. This can be seen as an MPC problem with n = 2 parties. However, since the minimal requirement for information-theoretic MPC is that fewer than n /2 parties are corrupted, information-theoretic MPC does not seem to help in constructing zero-knowledge proofs. However, as we shall see, a technique sometimes called MPC in the head can be used to turn an efficient, secure MPC for a given relation into an efficient zero-knowledge proof for the same relation. A Double Auction In this section we look at a concrete application of MPC, with a main focus on the algorithmic tricks needed to efficiently do a secure auction. Along the way, we will look at how to efficiently and securely compare two integers secret shared among the parties. 9.1.1 Introduction The algorithmic techniques we will look at are fairly general, but it is instructive to view them in a practical context. We will look at how they have been used to clear the Danish market for contracts on sugar beets from 2008 and until the time of this writing. This was the first industrial application of MPC. More historical details on this can be found later and in the Notes section at the end of this chapter. In the economic field of mechanism design, the concept of a trusted third party has been a central assumption since the 1970s. The field has grown in momentum since it was initiated and has turned into a truly cross-disciplinary field. Today, many practical mechanisms require a trusted third party.
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.
A peer-to-peer network, enabling different parties to jointly store and run computations on data while keeping the data completely private. Enigma's computational model is based on a highly optimized version of secure multi-party computation, guaranteed by a verifiable secret-sharing scheme. For storage, we use a modified distributed hashtable for holding secret-shared data. An external blockchain is utilized as the controller of the network, manages access control, identities and serves as a tamper-proof log of events. Security deposits and fees incentivize operation, correctness and fairness of the system. Similar to Bitcoin, Enigma removes the need for a trusted third party, enabling autonomous control of personal data. For the first time, users are able to share their data with cryptographic guarantees regarding their privacy.
Daniel Cabarcas, Denise Demirel, Florian Gรถpfert, Jean Lancrenon ยท 5 authors
Abstract. Commitment schemes are among cryptographyโs most im-portant building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes ap-plied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where com-mitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commit-ment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approxi-mation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness prop-erty of a given commitment while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construc-tion yields two more interesting features: one is the ability to โconvertโ a Pedersen commitment into a lattice-based one, and the other one is the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.
Unlink ability and accountability are conflicting yet critical requirements for on-line transactions that need to be addressed in order to preserve users' privacy as well as to protect service providers in today identity ecosystems. In this poster paper we introduce a pseudonymous identity management system in which users can carry out unlink able on-line transactions without having to disclose their actual identity to the service providers. At the same time, the service providers have strong assurance about the authenticity of the identity and credentials. In our approach, users' identity is cryptographically encoded in pseudonymous identity tokens issued by trusted identity providers. Our system includes a lightweight policy language which enables users and service providers to express their requirements pertaining to pseudonymous identity verification and a suite of protocols based on zero-knowledge-proofs which enables the fulfillment of these requirements.
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.
๋ณธ ๋ ผ๋ฌธ์์๋ ๋ฏธ๋ฆฌ ์๋ ค์ง ์์์ ๋คํญ์๊ณผ ์ํธํ๋ ๋คํญ์์ ๊ณฑ์ ์ ์ํํ ํ, ํด๋น ๊ณฑ์ ์ด ์ ๋นํ๊ฒ ์ํ๋์์์ ๋ณด์ด๊ธฐ ์ํด ์ฆ๋ช ์ (Prover)์ ๊ฒ์ฆ์ (Verifier)๊ฐ์ ๋คํญ์ ์๋ฑ์ฑ ์์ง์์ฆ๋ช (Zero-knowledge Proof) ํ๋กํ ์ฝ์ ์ผ๋ฐํํ ์ ์๋ ๋ฐฉ๋ฒ์ ๋ค๋ฃฌ๋ค. ์ด๋ฅผ ์ํ์ฌ ๋คํญ์์ ์๋ฑ์ฑ์ ์ฆ๋ช ํ๋ ์ผ๋ฐํ๋ ํ๋กํ ์ฝ์ ์ ์ํ๊ณ ๋๋ค์ค๋ผํด (Random Oracle) ๋ชจ๋ธ์์ ์์ ์ฑ์ ์ฆ๋ช ํ๋ค. ์ด๋ฌํ ๊ธฐ๋ฒ์ ์์ ํ ์งํฉ์ฐ์ฐ ๊ธฐ๋ฒ์ ํฌํจํ์ฌ ๋คํญ์์ ๊ธฐ๋ฐํ ๋ค์๊ฐ ์ฐ์ฐ๊ธฐ๋ฒ (Secure Multi-party Computation)์ ์ ์ฉ๋ ์ ์๋ค. In this paper, we are interested in a generalization of zero-knowledge interactive protocols between prover and verifier, especially to show that the product of an encrypted polynomial and a random polynomial, but published by a secure commitment scheme was correctly computed by the prover. To this end, we provide a generalized protocol for proving that the resulting polynomial is correctly computed by an encrypted polynomial and another committed polynomial. Further we show that the protocol is also secure in the random oracle model. We expect that our generalized protocol can play a role of building blocks in implementing secure multi-party computation including private set operations.
This habilitation thesis deals with cryptographic primitives that preserve the algebraic structure of underlying objects (messages, keys, etc) and their applications to the design of non-interactive zero-knowledge proofs and privacy-enhancing cryptographic primitives.In 2008, Groth and Sahai showed how to make these proof systems relatively efficient in abelian groups endowed with a bilinear map. These techniques, however, require to work with lower-level primitives where handled objects all live in a cyclic abelian group. Among other things, we need to sign messages without destroying their algebraic structure (in particular, without hashing them first) so as to be able to efficiently prove properties about hidden signed messages. The first part of this thesis describes a structure-preserving signature scheme which was the first efficient realization under previously studied algorithmic assumptions. These tools are also utilized in the design of a novel revocation mechanism for group signatures, which allow users to anonymously sign messages on behalf of a population they belong to. The second part of this thesis considers structure-preserving signatures endowed with homomorphic properties. We show how to use them in the design of non-malleable cryptographic primitives. Using linearly homomorphic structurepreserving signatures, we notably obtain non-malleable commitments to group elements and non-interactive zero-knowledge proofs, as well as public-key encryption schemes that resist chosen-ciphertext attacks.
Ghassan Karame, Elli Androulaki, Marc Roeschlin, Arthur Gervais ยท 5 authors
Bitcoin is a decentralized payment system that relies on Proof-of-Work (PoW) to resist double-spending through a distributed timestamping service. To ensure the operation and security of Bitcoin, it is essential that all transactions and their order of execution are available to all Bitcoin users. Unavoidably, in such a setting, the security of transactions comes at odds with transaction privacy. Motivated by the fact that transaction confirmation in Bitcoin requires tens of minutes, we analyze the conditions for performing successful double-spending attacks against fast payments in Bitcoin, where the time between the exchange of currency and goods is short (in the order of a minute). We show that unless new detection techniques are integrated in the Bitcoin implementation, double-spending attacks on fast payments succeed with considerable probability and can be mounted at low cost. We propose a new and lightweight countermeasure that enables the detection of double-spending attacks in fast transactions. In light of such misbehavior, accountability becomes crucial. We show that in the specific case of Bitcoin, accountability complements privacy. To illustrate this tension, we provide accountability and privacy definition for Bitcoin, and we investigate analytically and empirically the privacy and accountability provisions in Bitcoin.
Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain-based transaction ledger, maintained through proofs-of-work that also serve to generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of computational costs and scalability. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding doublespending attacks.
Chinyang Henry Tseng, Shiau-Huey Wang, Woei-Jiunn Tsaur
As our aging population significantly grows, personal health monitoring is becoming an emerging service and can be accomplished by large-scale, low-power sensor networks, such as Zigbee networks. However, collected medical data may reveal patient privacy, and should be well protected. We propose a Hierarchical and Dynamic Elliptic Curve Cryptosystem based self-certified public key scheme (HiDE) for medical data protection. To serve a large amount of sensors, HiDE provides a hierarchical cluster-based framework consisting of a Backbone Cluster and several Area Clusters. In an Area Cluster, a Secure Access Point (SAP) collects medical data from Secure Sensors (SSs) in the sensor network, and transmits the aggregated data to a Root SAP located in the Backbone Cluster. Therefore, the Root SAP can serve a considerable number of SSs without establishing separate secure sessions with each SS individually. To provide dynamic secure sessions for mobile SSs connecting SAP, HiDE introduces the Elliptic Curve Cryptosystem based Self-certified Public key scheme (ESP) for establishing secure sessions between each pair of Cluster Head (CH) and Cluster Member (CM). In ESP, the CH can issue a public key to a CM, and computes a Shared Session Key (SSK) with that CM without knowing the CM's secrete key. This concept satisfies the Zero Knowledge Proof so CHs can dynamically build secure sessions with CMs without managing a CM's secrete keys. Our experiments in realistic implementations and Network Simulation demonstrate that ESP requires less computation and network overhead than the Rivest-Shamir-Adleman (RSA)-based public key scheme. In addition, security analysis shows keys in ESP are well protected. Thus, HiDE can protect the confidentiality of sensitive medical data with low computation overhead, and keep appropriate network performance for wireless sensor networks.
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.
Michel Abdallaโ, Fabrice Benhamouda, Philip MacKenzie
J-PAKE is an efficient password-authenticated key exchange protocol that is included in the Open SSL library and is currently being used in practice. We present the first proof of security for this protocol in a well-known and accepted model for authenticated key-exchange, that incorporates online and offline password guessing, concurrent sessions, forward secrecy, server compromise, and loss of session keys. This proof relies on the Decision Square Diffie-Hellman assumption, as well as a strong security assumption for the non-interactive zero-knowledge (NIZK) proofs in the protocol (specifically, simulation-sound extractability). We show that the Schnorr proof-of-knowledge protocol, which was recommended for the J-PAKE protocol, satisfies this strong security assumption in a model with algebraic adversaries and random oracles, and extend the full J-PAKE proof of security to this model. Finally, we show that by modifying the recommended labels in the Schnorr protocol used in J-PAKE, we can achieve a security proof for J-PAKE with a tighter security reduction.
Eli BenโSasson, Alessandro Chiesa, Matthew Green, Eran Tromer ยท 5 authors
Non-interactive zero-knowledge proofs (NIZKs) are a powerful cryptographic tool, with numerous potential applications. However, succinct NIZKs (e.g., zk-SNARK schemes) necessitate a trusted party to generate and publish some public parameters, to be used by all provers and verifiers. This party is trusted to correctly run a probabilistic algorithm (specified by the the proof system) that outputs the public parameters, and publish them, without leaking any other information (such as the internal randomness used by the algorithm), violating either requirement may allow malicious parties to produce convincing "proofs" of false statements. This trust requirement poses a serious impediment to deploying NIZKs in many applications, because a party that is trusted by all users of the envisioned system may simply not exist. In this work, we show how public parameters for a class of NIZKs can be generated by a multi-party protocol, such that if at least one of the parties is honest, then the result is secure (in both aforementioned senses) and can be subsequently used for generating and verifying numerous proofs without any further trust. We design and implement such a protocol, tailored to efficiently support the state-of-the-art NIZK constructions with short and easy-to-verify proofs (Parno et al. IEEE S&P '13, Ben-Sasson et al. USENIX Sec '14, Danezis et al., ASIACRYPT '14). Applications of our system include generating public parameters for systems such as Zero cash (Ben-Sasson et al. IEEE S&P '13) and the scalable zero-knowledge proof system of (Ben-Sasson et al. CRYPTO '14).