Blockchain Papers

Francesc Sebé, Josep M. Miret, Jordi Pujolàs, Jordi Puiggalı́

No abstract is available for this record.

Kazi Md. Rokibul Alam, Shinsuke Tamura

This paper proposes a new electronic voting (e-voting) scheme that fulfills all the security requirements of e-voting. The key mechanism is the one that uses confirmation numbers involved in individual votes to make votes verifiable while disabling all entities including voters themselves to know the linkages between voters and their votes. Unlike complicated zero knowledge proof involved in many e-voting schemes, the confirmation numbers attain the verifiability requirement in a much more simple and intuitive way, then the scheme becomes scalable and practical.

계이기, 김만배, 최황규

This paper proposes a new undeniable signature scheme which uses one-way function and partition-selection method to proof its zero-knowledge respectively. The main idea is to protect the signer of a document against the document being digitally distributed without knowledge of signer. And we show that our scheme is so effective that message exchange only needs much fewer times during the confirmation protocol and disavowal protocol respectively. which is very useful for poor network environment keeping the communication times with both sides as few as possible. And our scheme allows verifier to verify that the signature is valid, while the signer doesn't know the original message and the signature, to preserve the privacy of the verifier.

Endre Bangerter, Stephan Krenn, Ahmad‐Reza Sadeghi, Thomas Schneider · 5 authors

Abstract. Zero-knowledge proofs of knowledge (ZK-PoK) play an important role in many cryptographic applications. Direct anonymous attestation (DAA) and the identity mixer anonymous authentication system are first real world applications using ZK-PoK as building blocks. But although being used for many years now, design and implementation of sound ZK-PoK remains challenging. In fact, there are security flaws in various protocols found in literatur. Especially for non-experts in the field it is often hard to design ZK-PoK, since a unified and easy to use theoretical framework on ZK-PoK is missing. With this paper we overcome important challenges and facilitate the design and implementation of efficient and sound ZK-PoK in practice. First, Camenisch et al. have presented at EUROCRYPT 2009 a first unified and modular theoretical framework for ZK-PoK. This is compelling, but makes use of a rather inefficient 6-move protocol. We extend and improve their framework in terms of efficiency and show how to realize it using efficient 3-move Σ-protocols. Second, we perform an exact security and efficiency analysis for our new protocol and various protocols found in the literature. The analysis yields novel- and perhaps surprising- results and insights. It reveals for instance that using a 2048 bit RSA modulus, as specified in the DAA standard, only guarantees an upper bound on the success probability of a malicious prover between 1/2 4 and 1/2 24. Also, based on that analysis we show how to select the most efficient protocol to realize a given proof goal. Finally, we also provide low-level support to a designer by presenting a compiler realizing our framework and optimization techniques, allowing easy implementation of efficient and sound protocols.

Massoud Hadian Dehkordi, Reza Alimoradi

Identification protocols have a very important role in the world of electronic communication. In an identification protocol, the prover (user) proves to the verifier (center) that it is truly the authorized user who is communicating with the center. In one round of batch identification scheme a user with several secret keys (identities) can prove itself to the verifier instead of several proofs. In this paper, the first Weil pairing will be introduced. In addition, we propose a new batch zero-knowledge identification scheme based on the Weil pairing hereafter considered the security analysis of our proposed scheme.

Federica Paci, Elisa Bertino, Sam Kerr, Anna Squicciarini · 5 authors

Abstract — Users increasingly use their mobile devices to communicate, to conduct business transaction and access resources and services. In such a scenario, digital iden-tity management (DIM) technology is fundamental in cus-tomizing user experience, protecting privacy, underpinning accountability in business transactions, and in complying with regulatory controls. Users identity consists of data, referred to as identity attributes, that encode relevant-security properties of the clients. However, identity attributes can be target of several attacks: the loss or theft of mobile devices results in a exposure of identity attributes; identity attributes that are send over WI-FI or 3G networks can be easily inter-cepted; identity attributes can also be captured via Bluetooth connections without the user’s consent; and mobile viruses, worms and Trojan horses can access the identity attributes stored on mobile devices if this information is not protected by passwords or PIN numbers. Therefore, assuring privacy and security of identity attributes, as well as of any sensitive information stored on mobile devices is crucial. In this paper we address such problems by proposing an approach to manage user identity attributes by assuring their privacy-preserving usage. The approach is based on the concept of privacy preserving multi-factor authentication achieved by a new cryptographic primitive which uses aggregate signatures on commitments that are then used for aggregate zero-knowledge proof of knowledge (ZKPK) protocols. We present the implementation of such approach on Nokia NFC cellular phones and report performance evaluation results. Index Terms — digital identity management, identity at-tributes, privacy, mobile devices I.

Joseph Y. Halpern, Rafael Pass, Vasumathi Raman

Halpern, Moses and Tuttle presented a definition of interactive proofs using a notion they called practical knowledge, but left open the question of finding an epistemic formula that completely characterizes zero knowledge; that is, a formula that holds iff a proof is zero knowledge. We present such a formula, and show that it does characterize zero knowledge. Moreover, we show that variants of the formula characterize variants of zero knowledge such as concurrent zero knowledge [Dwork, Naor, and Sahai 2004] and proofs of knowledge [Feige, Fiat, and Shamir 1987; Tompa and Woll 1987].

Federica Paci, Rodolfo Ferrini, Elisa Bertino

The WS-BPEL specification focuses on business processes the activities of which are assumed to be interactions with Web services. However, WS-BPEL processes go beyond the orchestration of activities exposed as Web services. There are cases in which people must be considered as additional participants to the execution of a process. The inclusion of humans, in turn, requires solutions to support the specification and enforcement of authorizations to users for the execution of human activities while enforcing authorization constraints. In this paper, we extend RBAC-WS-BPEL, a role-based authorization framework for WS-BPEL processes with an identity attribute-based role provisioning approach that preserves the privacy of the users who claim the execution of human activities. Such approach is based on the notion of identity records and role provisioning policies, and uses Pedersen commitments, aggregated zero knowledge proof of knowledge, and Oblivious Commitment-Based Envelope protocols to achieve privacy of user identity information.

Michael Backes, Martin P. Grochulla, Cătălin Hriţcu, Matteo Maffei

One of the important challenges when designing and analyzing cryptographic protocols is the enforcement of security properties in the presence of compromised participants. This paper presents a general technique for strengthening cryptographic protocols in order to satisfy authorization policies despite participant compromise. The central idea is to automatically transform the original cryptographic protocols by adding non-interactive zero-knowledge proofs.Each participant proves that the messages sent to the other participants are generated in accordance to the protocol.The zero-knowledge proofs are forwarded to ensure the correct behavior of all participants involved in the protocol, without revealing any secret data.We use an enhanced type system for zero-knowledge to verify that the transformed protocols conform to their authorization policy even if some participants are compromised.Finally, we developed a tool that automatically generates ML implementations of protocols based on zero-knowledge proofs.The protocol transformation, the verification, and the generation of protocol implementations are fully automated.

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

Chunming Tang, Zheng‐an Yao

No abstract is available for this record.

Rahul Jain, Alexandra Kolla, Gatis Midrijānis, Ben W. Reichardt

Let $L$ be a language decided by a constant-round quantum Arthur-Merlin ($\QAM$) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$. Our result also applies to any language having a three-round quantum interactive proof ($\QIP$), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L \notin \BQP$ would imply an impossibly-good quantum search algorithm.

Federica Paci, Ning Shang, Sam Kerr, Kevin Steuer · 6 authors

Users increasingly use their mobile devices for electronic transactions to store related information, such as digital receipts. However, such information can be target of several attacks. There are some security issues related to M-commerce: the loss or theft of mobile devices results in a exposure of transaction information; transaction receipts that are send over WI-FI or 3G networks can be easily intercepted; transaction receipts can also be captured via Bluetooth connections without the user's consent; and mobile viruses, worms and Trojan horses can access the transaction information stored on mobile devices if this information is not protected by passwords or PIN numbers. Therefore, assuring privacy and security of transactions' information, as well as of any sensitive information stored on mobile devices is crucial. In this paper, we propose a privacy-preserving approach to manage electronic transaction receipts on mobile devices. The approach is based on the notion of transaction receipts issued by service providers upon a successful transaction and combines Pedersen commitment and Zero Knowledge Proof of Knowledge (ZKPK) techniques and Oblivious Commitment-Based Envelope (OCBE) protocols. We have developed a version of such protocol for Near Field Communication (NFC) enabled cellular phones.

Kamesh Namuduri

Trust is a fundamental concept that enables cooperation and collaboration among the nodes in any network. Formal trust models are necessary for sharing information in a collaborative environment. Trust assessment methods that are commonly used in network applications or in social networks passively gather information about other nodes and take significant amount of time for assessing trust. Such models are not convenient for applications such as tactical airborne networks which are typically deployed for short durations of time.

Puwen Wei, Guoyan Zhang, Lijiang Zhang, Xiaoyun Wang

This paper shows that the protocol presented by Goyal et al. can be further simplified for a one-way function, with the simplified protocol being more practical for the decisional Diffie-Hellman assumption. Goyal et al. provided a general transformation from any honest verifier statistical zero-knowledge argument to a concurrent statistical zero-knowledge argument. Their transformation relies only on the existence of one-way functions. For the simplified transformation, the witness indistinguishable proof of knowledge protocols in “parallel” not only plays the role of preamble but also removes some computational zero-knowledge proofs, which Goyal et al. used to prove the existence of the valid openings to the commitments. Therefore, although some computational zero-knowledge proofs are replaced with a weaker notion, the witness indistinguishable protocol, the proof of soundness can still go through.

Ivan Damgaard, Carolin Lunemann

In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [Wat09] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [DFL+09], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.

Jianwei Ye, Xu-lu Jiao, Yuge Zhang

Based on the verifiable encryption and zero-knowledge proof protocols of Jarecki and Shmatikov and Pedersen’s verifiable threshold secret sharing scheme, this paper proposes a new full fair secure two-party computation protocols. For getting full fair, the new protocol employs a group of third-party servers. We prove that when more than two-thirds of the third-party servers are honest, the new protocol guarantees that two parties can get their correct outputs full fairly. In the new protocol, the computation is performed in the form of garbled circuit, and only two added interaction rounds are needed for full fairness.

Yingpeng Sang, Hong Shen, Hui Tian

We address the problems of privacy-preserving duplicate tuple matching (PPDTM) and privacy-preserving threshold attributes matching (PPTAM) in the scenario of a horizontally partitioned database among N parties, where each party holds a private share of the database's tuples and all tuples have the same set of attributes. In PPDTM, each party determines whether its tuples have any duplicate on other parties' private databases. In PPTAM, each party determines whether all attribute values of each tuple appear at least a threshold number of times in the attribute unions. We propose protocols for the two problems using additive homomorphic cryptosystem based on the subgroup membership assumption, e.g., Paillier's and ElGamal's schemes. By analysis on the total numbers of modular exponentiations, modular multiplications and communication bits, with a reduced computation cost which dominates the total cost, by trading off communication cost, our PPDTM protocol for the semihonest model is superior to the solution derivable from existing techniques in total cost. Our PPTAM protocol is superior in both computation and communication costs. The efficiency improvements are achieved mainly by using random numbers instead of random polynomials as existing techniques for perturbation, without causing successful attacks by polynomial interpolations. We also give detailed constructions on the required zero-knowledge proofs and extend our two protocols to the malicious model, which were previously unknown.

Sheng Zhong

Tompa and Woll constructed a zero-knowledge proof of knowing a square root of $X$ mod $N$, where $N$ is the product of two large, secret primes. In this paper, we construct a zero-knowledge proof of knowing a square root of $X_1$ or $X_2$ mod $N$. Compared with the existing solution to this problem, ours is significantly simpler.

Juan A. Garay, Aggelos Kiayias, Hong-Sheng Zhou

Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating" the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings than universal composition. Our translation methodology entails a sequence of steps that derive a corresponding canonical functionality given a game-based definition. In this way, we obtain a well-defined mapping of game-based security properties to their corresponding UC counterparts. Finally, we demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.

Jong-Ho Ryu, Jung-Chan Na

This paper present an alternative scheme to key escrow scheme which allows probabilistic law enforcement access to reveal the encrypted communications. Namely, key escrow authority can reveal the information between communication parties partially. Our scheme allows law enforcement access with probability p for each message. The scheme in this paper is basically the complemented scheme of Mihir Bellare and Ronald L. Rivest [2], and combine a publicly verifiable encryption technique and translucent cryptography based on non-interactive fractional oblivious transfer. This protocol allows such access with probability for each message, for a parameter between 0 and 1, which should be chosen to provide an appropriate balance between concerns for individual privacy and the need for such law enforcement access by government. This paper induct a set of distributed key escrow authorities(DEA). The scheme is based on the El-Gamal encryption, a proof scheme of knowledge of common exponent in publicly verifiable El-Gamal public-key encryption, and a set of distributed escrow authorities. In session key recovery phase by DEA, use only partial parameters from each key escrow authorities required for session key recovery that have been passed through zero-knowledge(ZK) interactive proof protocol. The scheme allows both the law enforcement access with probability and DEA to recover the session key used to encrypt communication by User A.

Stephen R. Tate, Roopa Vishwanathan

At the heart of many fair exchange problems is verifiable escrow: a sender encrypts some value using the public key of a trusted party (called the recovery agent), and then must convince the receiver of the ciphertext that the corresponding plaintext satisfies some property (e.g., it contains the sender’s signature on a contract). Previous solutions to this problem are interactive, and often rely on communication-intensive cut-and-choose zero-knowledge proofs. In this paper, we provide a solution that uses generic trusted hardware to create an efficient, non-interactive verifiable escrow scheme. Our solution allows the protocol to use a set of recovery agents with a threshold access structure, the verifiable group escrow notion which was informally introduced by Camenisch and Damgard and which is formalized here. Finally, this paper shows how this new non-interactive verifiable escrow scheme can be used to create an efficient optimistic protocol for fair exchange of signatures.

Wenbao Han

A publicly verifiable multi-secret sharing scheme is proposed, using non-interactive zero-knowledge proof protocol and Shamir’s sharing system. The security of the scheme is based on the intractability of integer factorization problem and discrete logarithm problem. The validity of the sharing distributed by the dealer can be verified by anyone. Recovering the secret, participants only need to provide a shadow of the sharing. It is difficult to get the sharing from the shadow. So the sharing can be reused to share the multi-secret. Moreover, the validity of the shadow can also be verified by anyone. So the scheme is secure, efficient, and can prevent both dealer and participant from cheating.

Qunshan Chen

CL-PKC is a kind of public-key cryptosystem,which was proposed recently.It preserves the advantages of non public-key certificate and also has solved the key escrow problem in the ID-PKC.Many people are highly concerned about the design method of safe and efficient signature scheme in the certificateless system.In this paper,we construct a new certificateless undeniable signature by using bilinear pairings and zero-knowledge proof protocol.