Blockchain Papers

Ming-Jheng Li, Justie Su-Tzu Juan, Jennifer Hui-Chan Tsai

No abstract is available for this record.

Michael T. Goodrich, Florian Kerschbaum

In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main ideas behind our techniques are to use randomization and various schemes to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.

Hervé Chabanne, Céline Chevalier

No abstract is available for this record.

Bingsheng Zhang

No abstract is available for this record.

Marc Fischlin, Cristina Onete

No abstract is available for this record.

Carolin Lunemann, Jesper Buus Nielsen

We propose a coin-flip protocol which yields a string of strong, random coins and is fully simulatable against poly-sized quantum adversaries on both sides. It can be implemented with quantum-computational security without any set-up assumptions, since our construction only assumes mixed commitment schemes which we show how to construct in the given setting. We then show that the interactive generation of random coins at the beginning or during outer protocols allows for quantum-secure realizations of classical schemes, again without any set-up assumptions. As example applications we discuss quantum zero-knowledge proofs of knowledge and quantum-secure two-party function evaluation. Both applications assume only fully simulatable coin-flipping and mixed commitments. Since our framework allows to construct fully simulatable coin-flipping from mixed commitments, this in particular shows that mixed commitments are complete for quantum-secure two-party function evaluation. This seems to be the first completeness result for quantum-secure two-party function evaluation from a generic assumption.

David Bernhard, Véronique Cortier, Olivier Pereira, Ben Smyth · 5 authors

Abstract. Recent results show that the current implementation of He-lios, a practical e-voting protocol, does not ensure independence of the cast votes, and demonstrate the impact of this lack of independence on vote privacy. Some simple fixes seem to be available and security of the revised scheme has been studied with respect to symbolic models. In this paper we study the security of Helios using computational models. Our first contribution is a model for the property known as ballot privacy that generalizes and extends several existing ones. Using this model, we investigate an abstract voting scheme (of which the revised Helios is an instantiation) built from an arbitrary encryp-tion scheme with certain functional properties. We prove, generically, that whenever this encryption scheme falls in the class of voting-friendly schemes that we define, the resulting voting scheme provably satisfies ballot privacy. We explain how our general result yields cryptographic security guaran-tees for the revised version of Helios (albeit from non-standard assump-tions). Furthermore, we show (by giving two distinct constructions) that it is possible to construct voting-friendly encryption, and therefore voting schemes, using only standard cryptographic tools. We detail an instan-tiation based on ElGamal encryption and Fiat-Shamir non-interactive zero-knowledge proofs that closely resembles Helios and which provably satisfies ballot privacy. 1

Abhishek Jain, Omkant Pandey

This paper deals with efficient non-malleable zero-knowledge proofs forNP, based on general assumptions. We construct a simulation-sound zero-knowledge (ZK) protocol for NP, based only on the black-box use of one-way functions. Constructing such a proof system has been an open question ever since the original work of Dolev, Dwork, and Naor [DDN91]. In addition to the feasibility result, our protocol has a constant number of rounds, which is asymptotically optimal. Traditionally, the term non-malleable zero-knowledge (NmZK) refers to the original definition of [DDN91]; but today it is used loosely to also refer to simulation-soundness (SimSound) [Sah99], and simulation-extractability (SimExt) [PR05b]. While SimExt implies NmZK, the common perception is that SimExt is strongest of the three notions. A formal study of the definitional relationship between these three notions, however, has never been done. In the second part of this work, we try to correct this situation by initiating such a study. We show that in the “static” case, if an NmZK protocol is also an argument-of-knowledge, then it is in fact SimExt. Furthermore, in the most strict sense of the definition, SimSound does not necessarily follow from SimExt. These results are somewhat surprising because they are opposite to the common perception that SimExt is the strongest of the three notions.

Huijia Lin, Rafael Pass

No abstract is available for this record.

Brett Hemenway, Benoît Libert, Rafail Ostrovsky, Damien Vergnaud

No abstract is available for this record.

Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia

Abstract Two central notions of Zero Knowledge that provide very strong, yet seemingly incomparable security guarantees against malicious verifiers are those of Statistical Zero Knowledge and Resettable Zero Knowledge. The current state of the art includes several feasibility and impossibility results about the two notions separately. However, the challenging question of achieving Resettable Statistical Zero Knowledge (i.e., Resettable Zero Knowledge and Statistical Zero Knowledge simultaneously) for non-trivial languages is still open. In this paper, we show:- Resettable Statistical Zero Knowledge with efficient provers: Efficient-prover Resettable Statistical Zero-Knowledge proof systems exist for all languages that admit hash proof systems (e.g., QNR, QR, DDH, DCR). Furthermore, for these languages, as an application of our technique, we also construct a two-round resettable statistical witness-indistinguishable argument system.- Resettable Statistical Zero Knowledge with unbounded provers: Under the assumption that sub-exponentially hard one-way functions exist, rSZK = SZK. In other words, every language that admits a Statistical Zero-Knowledge (SZK) proof system also admits a Resettable Statistical Zero-Knowledge (rSZK) proof system. (Further, the result can be re-stated unconditionally provided there exists a sub-exponentially hard language in SZK). Moreover, under the assumption that (standard) one-way functions exist, all languages L such that the complement of L is random self reducible, admit a rSZK, in other words: co-RSR ⊆ rSZK. The round complexity of all our proof systems is Õ(log κ), where κ is the security parameter, and all our simulators are black-box. 1

Amang Sudarsono, Toru Nakanishi, Nobuo Funabiki

No abstract is available for this record.

Jens Groth

No abstract is available for this record.

Xiaofeng Chen, Qianhong Wu, Fangguo Zhang, Haibo Tian · 8 authors

No abstract is available for this record.

Xiaolan Zhang, Hong-xiang Sun, Hua Zhang, Qiaoyan Wen · 5 authors

A coin-tossing protocol lets two parties decide on a string that should be a random (or at least pseudorandom) string. In this paper, we focus on taking advantage of the perfectly hiding commitment scheme, constant-round perfect zero-knowledge arguments and arguments of knowledge to construct a two-party constant-round perfect protocol for secure coin-tossing, where both of two parties can obtain the common resulting coins and the resulting coins are guaranteed to be statistically close to uniform. The security of our protocol is obtained against malicious non-uniform adversaries that may arbitrarily deviate from the protocol specification. Comparing with the Barak's protocol, we utilize the black-box reduction in the process of security proof and the rounds of our protocol decrease obviously.

Giovanni Di Crescenzo, Javier Herranz, Germán Sáez

No abstract is available for this record.

Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder

The existing (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in collective decision making. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of "the wisdom of crowds". Very recently, a few liquid democracy implementations, e.g. Google Votes and Decentralized Autonomous Organization (DAO), are released; however, those systems only focus on the functionality aspect, as no privacy/anonymity is considered. In this work, we, for the first time, provide a rigorous study of liquid democracy under the Universal Composability (UC) frame- work. In the literature, liquid democracy was achieved via two separate stages -- delegation and voting. We propose an efficient liquid democracy e-voting scheme that uni es these two stages. At the core of our design is a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.

Abhilasha Bhargav-Spantzel, Anna Squicciarini, Rui Xue, Elisa Bertino

The problem of identity theft, that is, the act of impersonating others' identities by presenting stolen identifiers or proofs of identities, has been receiving increasing attention because of its high financial and social costs. In this paper, we address the problem of verification of such identifiers and proofs of identity. Our approach is based on the concept of privacy preserving multifactor verification of such identifiers and proofs achieved by the development of a new cryptographic primitive, which uses aggregate signatures on commitments that are then used for aggregate zero-knowledge proof of knowledge (ZKPK) protocols. The resultant signatures are very short and the ZKPs are succinct and efficient. We prove the security of our scheme under the co-gap Diffie-Hellman (co-GDH) assumption for groups with bilinear maps. Our cryptographic scheme is an improvement in terms of the performance, flexibility, and storage requirements than the existing efficient ZKPK techniques that may be used to prove under zero knowledge and the knowledge of multiple secrets.

Chunming Tang, Zhifeng Hao

Based on the interactive proof of Hamiltonian Cycle (HC) of large directed graph, which is a $\Sigma$-protocol, we construct a perfectly hiding and computationally binding trapdoor commitment in 2-round from any one-way permutation. Then, based on this trapdoor commitment, we construct perfect zero-knowledge argument of knowledge with negligible error probability in 2-round for $\mathcal{NP}$, assuming only the existence of a one-way permutation.

Hongda Li, Haixia Xu, Bao Li, Dengguo Feng

No abstract is available for this record.

Shuge Wang

To address the problem that the common authentication mechanism is not applicable to the P2P network system model with anonymous communication requirements.This paper,based on the improvement of the Diffle-Hellman key agreement protocol and the combination of the RSA digital signatures agreements and zero-knowledge proof GQ agreement,proposes a new token-based services authentication mechanism to identify the nodes in P2P anonymous communication systems.This mechanism,with the premise of guaranteeing various general characteristics of P2P anonymous communication system and introduction of the trusted third party node into P2P anonymous communication system,implements anonymous control and behavior management of various communication nodes in P2P anonymous communication system.It could resist the threat of various common networks attack and realize effective authentication of P2P anonymous communication system,thus improving the security management ability of P2P anonymous communication system.

Shundong Li

With the secret distribution of a publicly verifiable secret sharing accomplished,k old participants take the place of the dealer to distribute new shares to new participants when the dealer is off-line and new participants want to share the secret. This paper presents a more general (k,n+t) scheme transformed from the (k,n) scheme based on the publicly verifiable secret sharing scheme and non-interactive zero-knowledge proof when t(t≥1) new participants attach to the scheme. The (k,n+t) secret sharing scheme is publicly verifiable with the access structure and the former shares unchanged. Comparison with conventional publicly verifiable secret sharing schemes with enrollment ability shows that the (k,n+t) scheme flexibly allows multiple new participants to share the secret and reduces the public parameters and computational complexity.

Pla Information, Pla N

For most present threshold signature schemes,sub-sign member can not sign a message anonymously or theirs anonymity is very weak.To improve their anonymity,a strong anonymity (n,t) threshold signature scheme based on DAA (Direct Anonymous Attestation),which is adopted by Trusted Computing Group v1.2 specifications,is proposed.Compared with the others,the scheme colligates DAA,zero-knowledge proof and Feldman verifiable secret sharing technique to achieve untraceable sub-sign and insure strong anonymity of signers,even the verifier and the dealer are colluded.Besides strong anonymity,analysis shows the scheme also has the property of unforgeable share,verifiable sub-sign,and robustness etc.It can be used in the situations which desire high-level anonymity such as anonymous voting.

Suriadi Suriadi

In a digital world, users’ Personally Identifiable Information (PII) is normally managed with a system called an Identity Management System (IMS). There are many types of IMSs. There are situations when two or more IMSs need to communicate with each other (such as when a service provider needs to obtain some identity information about a user from a trusted identity provider). There could be interoperability issues when communicating parties use different types of IMS. To facilitate interoperability between different IMSs, an Identity Meta System (IMetS) is normally used. An IMetS can, at least theoretically, join various types of IMSs to make them interoperable and give users the illusion that they are interacting with just one IMS. However, due to the complexity of an IMS, attempting to join various types of IMSs is a technically challenging task, let alone assessing how well an IMetS manages to integrate these IMSs. The first contribution of this thesis is the development of a generic IMS model called the Layered Identity Infrastructure Model (LIIM). Using this model, we develop a set of properties that an ideal IMetS should provide. This idealized form is then used as a benchmark to evaluate existing IMetSs. Different types of IMS provide varying levels of privacy protection support. Unfortunately, as observed by Josang et al (2007), there is insufficient privacy protection in many of the existing IMSs. In this thesis, we study and extend a type of privacy enhancing technology known as an Anonymous Credential System (ACS). In particular, we extend the ACS which is built on the cryptographic primitives proposed by Camenisch, Lysyanskaya, and Shoup. We call this system the Camenisch, Lysyanskaya, Shoup - Anonymous Credential System (CLS-ACS). The goal of CLS-ACS is to let users be as anonymous as possible. Unfortunately, CLS-ACS has problems, including (1) the concentration of power to a single entity - known as the Anonymity Revocation Manager (ARM) - who, if malicious, can trivially reveal a user’s PII (resulting in an illegal revocation of the user’s anonymity), and (2) poor performance due to the resource-intensive cryptographic operations required. The second and third contributions of this thesis are the proposal of two protocols that reduce the trust dependencies on the ARM during users’ anonymity revocation. Both protocols distribute trust from the ARM to a set of n referees (n > 1), resulting in a significant reduction of the probability of an anonymity revocation being performed illegally. The first protocol, called the User Centric Anonymity Revocation Protocol (UCARP), allows a user’s anonymity to be revoked in a user-centric manner (that is, the user is aware that his/her anonymity is about to be revoked). The second protocol, called the Anonymity Revocation Protocol with Re-encryption (ARPR), allows a user’s anonymity to be revoked by a service provider in an accountable manner (that is, there is a clear mechanism to determine which entity who can eventually learn - and possibly misuse - the identity of the user). The fourth contribution of this thesis is the proposal of a protocol called the Private Information Escrow bound to Multiple Conditions Protocol (PIEMCP). This protocol is designed to address the performance issue of CLS-ACS by applying the CLS-ACS in a federated single sign-on (FSSO) environment. Our analysis shows that PIEMCP can both reduce the amount of expensive modular exponentiation operations required and lower the risk of illegal revocation of users’ anonymity. Finally, the protocols proposed in this thesis are complex and need to be formally evaluated to ensure that their required security properties are satisfied. In this thesis, we use Coloured Petri nets (CPNs) and its corresponding state space analysis techniques. All of the protocols proposed in this thesis have been formally modeled and verified using these formal techniques. Therefore, the fifth contribution of this thesis is a demonstration of the applicability of CPN and its corresponding analysis techniques in modeling and verifying privacy enhancing protocols. To our knowledge, this is the first time that CPN has been comprehensively applied to model and verify privacy enhancing protocols. From our experience, we also propose several CPN modeling approaches, including complex cryptographic primitives (such as zero-knowledge proof protocol) modeling, attack parameterization, and others. The proposed approaches can be applied to other security protocols, not just privacy enhancing protocols.