In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information- that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof. 1
Privacy is becoming an increasingly important issue in electronic commerce and other online activities that are growing in popularity. This work introduces a framework, called Peers for Privacy (P4P), for implementing many useful algorithms with provable privacy and adequate efficiency in a realistic adversary model at a reasonably large scale. The basic idea is to decompose an algorithm into a series of addition-only steps, which have very efficient private implementation using cryptographic tools. This simple model is surprisingly general and supports many algorithms prevalent in distributed data mining. Examples include linear algorithms like voting and summation, as well as nonlinear algorithms such as regression, classification, SVD, PCA, <i>k</i>-means, ID3, machine learning algorithms based on Expectation Maximization (EM), etc. In fact all algorithms in the statistical query model are supported. <p> The computation of the sums is based on a highly efficient verifiable secret sharing (VSS) scheme that allows secret-shared arithmetic operations to be done over small fields (e.g. 32 or 64 bits) where private arithmetic operations have the same cost as normal arithmetic. This thesis shows that this paradigm admits efficient zero-knowledge tools that can be used to verify the properties of user data such as equality and boundedness. These tools provide practical mechanisms to deal with cheating users. One such tool is an extremely efficient zero-knowledge proof that verifies the L2-norm of the user data is bounded by a constant. This is to prevent a malicious user from exerting too much influence on the computation. The verification uses a linear number of inexpensive small field operations, and only a logarithmic number of large-field (1024 bits or more) cryptographic operations, and can achieve orders of magnitude reduction in running time over standard techniques (from hours to seconds) for large-scale problems. Concrete examples are given to demonstrate how the framework supports private computation of popular algorithms such as SVD, link analysis and association rule mining. The thesis also includes schemes for scalable multicast encryption and bidirectional group communication. They provide secure data transmission support for the type of communication pattern required by the P4P framework and many other group-oriented applications
Secure Multiparty Computation technique plays an important role in the security research of distributed systems.This paper firstly summarizes the advances in theoretical and practical studies on SMC,and then analysis the basic protocols and its related cryptographic algorithms.Secondly,the key tools,secret share,homomorphic public key cryptography,mix network,zero knowledge proof,oblivious transfer and private comparison protocol in implementation SMC are studied deeply.Finally,some research directions in this area are also proposed.
This paper introduces a natural paradigm for fair exchange protocols, called ID-based partial proxy signature scheme. A security model with precise and formal definitions is presented, and an efficient and provably secure partial proxy signature scheme is proposed. This is a full ID-based optimistic fair exchange protocol. Unlike the vast majority of previously proposed protocols, this approach does not use any zero knowledge proofs, and thus avoids most of the costly computations.
Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the verifier to show to a third part that he has interacted with the prover. However, it has been shown that using quantum correlations the impossibility of transferring proofs can be successfully attacked. In this work we show two new protocols for proof transference, being the first one based on teleportation and the second one without using entangled states.
This paper proposes a forward-secure undeniable digital signature scheme based on zero-knowledge proof.By combining the undeniable digital signature with the forward-secure digital signature,the new scheme keeps the general property of undeniable digital signature,and has the character of forward-secure,namely,the loss can be reduced to the lowest once the secret key is lost(or stolen).The scheme has some features such as undeniable and unforgeable of the digital signature,and the size of key and signature are short.The idea of zero-knowledge proof is used in key update protocol,which guarantees key update is secure.The scheme is secure under the assumption of standard intractability problems.
Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/nonmembership of elements in/not in the committed set. We present a new primitive called Statistically Hiding Sets (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to witness independent proofs. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the “Merkletree/mercurial-commitment” paradigm used for all zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide statistical hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach.
2 source records
Advanced Steganography and Watermarking Techniques
Abstract. Statistical zero-knowledge (SZK) properties play an important role in designing cryptographic protocols that enforce honest behavior while maintaining privacy. This paper presents a novel approach for verifying SZK properties, using recently developed techniques based on approximate simulation relations. We formulate statistical indistinguishability as an implementation relation in the Task-PIOA framework, which allows us to express computational restrictions. The implementation relation is then proven using approximate simulation relations. This technique separates proof obligations into two categories: those requiring probabilistic reasoning, as well as those that do not. The latter is a good candidate for mechanization. We illustrate the general method by verifying the SZK property of the well-known identification protocol proposed by Girault, Poupard and Stern. ⋆ Supported by the MURI project:DARPA/AFOSR MURI F49620-02-1-0325 grant. 1
In this paper, we propose a zero-knowledge authenticated key agreement protocol with key confirmation (AKC) in asymmetric setting. The protocol has several desirable security attributes like some classical AKCs such as STS [7] and MQV [13]. One highlight of our protocol is its zero-knowledge property, which enables succinct proofs of the claimed security attributes, while the overhead in communication and computation resulting from the special design to achieve zero-knowledge is insignificant.
Digital signature has been a basal means of identity authentication in era of network information.To improve the security of the digital signature schemes based on zero-knowledge proof technology,the problem of signature forgery by the signer in digital signature schemes based on the zero-knowledge concept is studied,the potential problem of these schemes are analyzed,a modified scheme for obtaining against such forgery without any increase of computation complexity is proposed,the feasibility,security and computation complexity of the modified scheme is concretely analyzed.
Zero-knowledge proof is a protocol, and ElGamal's digital signature is widely applied. Gives a GMR module of zero-knowledge proof about ElGamal's digital signature which has little computation, high reliability, and easy to implement.
Lu Li, Jinsong Han, Lei Hu, Jinpeng Huai · 6 authors
Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the levels of security and anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype implementation. The strengths of pseudo trust include the lack of need for a centralized trusted party or CA, high scalability and security, low traffic and cryptography processing overheads, and man-in-middle attack resistance. We aim for the pseudo trust design to be included in the P2P trust and anonymity context.
We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a, b, c satisfy ab = c. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.
Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
The use of quantum correlations to attack security protocols is an important research line deserving growing attention. An important class of cryptographic protocols used as building blocks for several other more complex protocols is zero-knowledge proof systems. One of the properties that zero-knowledge proof systems are assumed to satisfy is that it is impossible for the verifier to show to a third party that he has interacted with the prover (impossibility of transferring proofs). Herein, it is shown how Bell pairs, together with tamper-proofing, can be used to break the impossibility of transferring proofs for an important class of zero-knowledge proof systems.
A zero-knowledge proof(ZKP) is a powerful tool which can be used and already be used for many cryptographic applications.But for the completeness property and the soundness property the existing zero-knowledge proofs are iterative in nature.The multiple communication rounds makes ZKPs unsuitable in practice.In this thesis,propose a new ZKP protocol which runs in one-round while ensure the completeness property and the soundness property.On the other hand,extend ZKPs to elliptic curves.At last,proposed a necessary condition which was needed by constructing a one-round zero-knowledge proofs protocol.
Zero-knowledge proof (ZKP) based authentication protocols provide a smart way to prove an identity of a node without giving away any information about the secret of that identity. There are many advantages as well as disadvantages to using this protocol over other authentication schemes, and challenges to overcome in order to make it practical for general use. This chapter examines the viability of ZKPs for use in authentication protocols in networks. It is concluded that nodes in a network can achieve a desired level of security by trading off key size, interactivity, and other parameters of the authentication protocol. This chapter also provides data analysis that can be useful in determining expected authentication times based on device capabilities. Pseudocode is provided for implementing a graph-based ZKP on small or limited processing devices.Request access from your librarian to read this chapter's full text.
2 source records
Cryptography and Data Security
Privacy-Preserving Technologies in Data
Physical Unclonable Functions (PUFs) and Hardware Security