We introduce a new notion called `-isolated proofs of knowledge (`-IPoK). These are proofs of knowledge where a cheating prover is allowed to exchange up to ` bits of communication with some external adversarial environment during the run of the proof. Without any additional setup assumptions, no witness hiding protocol can be an `-IPoK for unbounded values of `. However, for any pre-defined threshold `, and any relation in NP and we construct an `-IPoK protocol for that relation. The resulting protocols are zero knowledge (ZK) in the standard sense, i.e., w.r.t. a verifier that communicates only with the prover during the proof. The cost of having a large threshold ` is a large communication complexity of the constructed protocol. We analyze these costs and present a solution that is asymptotically optimal. If a cheating verifier is allowed to communicate arbitrarily with an external environment, it is not possible to construct an `-IPoK that is also ZK with respect to such a verifier. As another new notion, we define `-isolated zero knowledge (`-IZK) where the verifier is `-isolated. For every relation in NP and every `, we construct an `-IPoK protocol that is also `-IZK. We describe several applications of `-IPoK protocols under the physical assumption that one can `isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) `-IPoK to prevent “man-in-the-middle” attacks on identification schemes. Prior results for this scenario required all verifiers to register keys under a PKI, or the ability to fully isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI `-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.
In this paper, a new forward secure threshold signature scheme is presented, which is the first one from bilinear pairings. Compared with the known schemes against malicious adversary, the new scheme needs the fewest interactions and is very efficient. As an additional contribution, we present a new interactive zero-knowledge proof protocol and convert it into a non-interactive protocol to verify the validity of part signatures in this scheme. The scheme is robust against malicious adversary and forward secure in the random oracle model
Fingerprinting schemes are technical means to discourage people from illegally redistributing the digital data they have legally purchased. These schemes enable the original merchant to identify the original users of the digital data. Anonymous fingerprinting schemes allow a seller to fingerprint information sold to a user without knowing the identity of the user and without the seller seeing the fingerprinted copy. Finding a (redistributed) fingerprinted copy enables the seller to find out and prove to third party whose copy it was. In this paper, we propose a new scheme of anonymous fingerprinting by using electronic wallet, in which, the user doesn't need making a computationally expensive zero-knowledge proof on finding a fingerprinted copy, the seller can directly determine the redistributor by a simple computation without the help of a registration authority and without making a search for the redistributor's public key in purchase record. In addition, our scheme can prevent the collusion of merchant and registration center to make false-accusation to honest users. By using electronic wallet, our scheme can be integrated with electronic payment system
2 source records
Advanced Steganography and Watermarking Techniques
Federated Identity Management (FIM) allows for securely provisioning certified user identities and attributes to relying parties. It establishes higher security and data quality compared to user-asserted attributes and provides for stronger user privacy protection than technologies based upon user-side attribute certificates. Therefore, industry pursues the deployment of FIM solutions as one cornerstone of the WS-Security framework. Current research proposes even more powerful methods for security and privacy protection in identity management with so called anonymous credential systems. Being based on new, yet well-researched, signature schemes and cryptographic zero-knowledge proofs, these systems have the potential to improve the capabilities of FIM by superior privacy protection, user control, and multiple use of single credentials. Unfortunately, anonymous credential systems and their semantics being based upon zero-knowledge proofs are incompatible with the XML Signature Standard which is the basis for the WS-Security and most FIM frameworks. We put forth a general construction for integrating anonymous credential systems with the XML Signature Standard and FIM protocols. We apply this method to the WS-Security protocol framework and thus obtain a very flexible WS-Federation Active Requestor Profile with strong user control and superior privacy protection.
A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration. These requirements limit the use of the schemes. We provide a new scheme that is proven secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. Furthermore, the important simplification in key management achieved is not at the cost of efficiency or assurance: our scheme matches or surpasses known ones in terms of signing time, verification time and signature size, and is proven secure in the random-oracle model under a standard (not bilinear map related) assumption. The proof is based on a simplified and general Forking Lemma that may be of independent interest.
A zero-knowledge proof (ZKP) is an interactive proof that allows a prover to prove the knowledge of a secret to a verifier without revealing it. ZKPs are powerful tools to deal with critical applications in security e-commerce. Existing ZKPs are iterative in nature; their protocols require multiple communication rounds. The cost of iteration makes ZKPs unsuitable in practice. We propose a new protocol that meets all the requirements of ZKPs, yet runs in one round. The new approach substantially reduces computation and communications costs. It makes ZKPs more suitable for practical cryptographic systems for both government and commercial applications.
The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the unpredictability property of random oracles [12]: If O is a random oracle then it is infeasible to find an inputx such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of CIFEs, where multi-input means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.
Let Lambda : {0, 1}ntimes {0,1}mrarr {0,1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y isin {0,1}mbe an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on Lambday). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form Lambda (x1, y) = z1,..., Lambda(xN,y) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(d, log N). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. given a CNF formula Psi(w1,..., wm) of size N, Alice can prove the satisfiability of Psi by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x isin {0, 1}n, Alice can prove the membership x isin L by a (computationally sound) non-interactive zero-knowledge proof of size polylog n. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y(x1) = z1,..., y(xN) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(m, log N). Our cryptographic assumptions include the existence of a poly-logarithmic symmetric-private-information-retrieval (SPIR) scheme, as defined in (C. Cachin et. al, 1999), and the existence of commitment schemes, secure against circuits of size exponential in the security parameter
Juan Ramón Troncoso-Pastoriza, Fernando Pérez‐González
Current zero-knowledge watermark detectors are based on a linear correlation between the asset features and a given secret sequence.This detection function is susceptible of being attacked by sensitivity attacks,for which zero-knowledge does not provide protection.In this paper a new zero-knowledge watermark detector robust to sensitivity attacks is presented,using the Generalized Gaussian Maximum Likelihood (ML)detector as basis.The inherent robustness that this detector presents against sensitivity attacks,together with the security provided by the zero-knowledge protocol that conceals the keys that could be used to remove the watermark or to produce forged assets,results in a robust and secure protocol.Additionally,two new zero-knowledge proofs for modulus and square root calculation are presented;they serve as building blocks for the zero-knowledge implementation of the Generalized Gaussian ML detector,and also open new possibilities in the design of high level protocols.
Advanced Steganography and Watermarking Techniques
Many electronic voting systems, classified mainly as homomorphic cryptography based, mix-net based and blind signature based, appear after the eighties when zero knowledge proofs were introduced. The common ground for all these three systems is that none of them works without real time cryptologic calculations that should be held on a server. As far as known, the agent-based approach has not been used in a secure electronic voting system. In this study, an agent-based electronic voting schema, which does not contain real time calculations on the server side, is proposed. Conventional cryptologic methods are used in the proposed schema and some of the requirements of an electronic voting system are constructed within the schema. The schema seems quite secure if the used cryptologic methods and agents are secure. In this paper, proposed schema will be explained and compared with already known electronic voting systems.
An identity-based signcryption scheme with (t,n) shared unsigncryption is proposed, which is the integration of the signcryption scheme, the (t,n) threshold scheme and zero knowledge proof for the equality of two discrete logarithms based on the bilinear map. In this scheme, any third party can verify the validity of the signature, but only more than t members in the recipient group can cooperatively recover the message m. As compared to the Zhang et al.'s signcryption scheme with (t,n) shared unsigncryption based on discrete logarithms, the proposed scheme has the following advantages: it provides both public verifiability and forward security; the key management problem is simplified because of using identity-based cryptosystem.
The output of a data mining algorithm is only as good as its inputs, and individuals are often unwilling to provide accurate data about sensitive topics such as medical history and personal finance. Individuals maybe willing to share their data, but only if they are assured that it will be used in an aggregate study and that it cannot be linked back to them. Protocols for anonymity-preserving data collection provide this assurance, in the absence of trusted parties, by allowing a set of mutually distrustful respondents to anonymously contribute data to an untrusted data miner.To effectively provide anonymity, a data collection protocol must be collusion resistant, which means that even if all dishonest respondents collude with a dishonest data miner in an attempt to learn the associations between honest respondents and their responses, they will be unable to do so. To achieve collusion resistance, previously proposed protocols for anonymity-preserving data collection have quadratically many communication rounds in the number of respondents, and employ (sometimes incorrectly) complicated cryptographic techniques such as zero-knowledge proofs.We describe a new protocol for anonymity-preserving, collusion resistant data collection. Our protocol has linearly many communication rounds, and achieves collusion resistance without relying on zero-knowledge proofs. This makes it especially suitable for data mining scenarios with a large number of respondents.
Two long-standing open problems exist on the fringe of complexity theory and cryptography: (1) Does there exist a reduction from an NP-complete problem to a one-way function? (2) Do parallelized versions of classical constant-round zero-knowledge proofs for NP conceal every "hard" bit of the witness to the statement proved? We show that, unless the polynomial-hierarchy collapses, black-box reductions cannot be used to provide positive answers to both questions
Recently, M. Sekhar gave a digital signature scheme with message recovery, where only a specific verifier can directly check the validity of the signature. A third party can distinguish a valid signature through a zero-knowledge proof protocol. However we find that the proposed scheme is insecure. A forgery attack strategy on M. Sekhar's scheme has been designed; anyone who has a valid signature can forge a signature on an arbitrary message. An improved signature scheme, which can resist the forgery attack and a zero-knowledge proof protocol with which a third party can distinguish a valid signature are presented. Also, the security of the improved scheme is analyzed
H. Imai, Kirill Morozov, Anderson C. A. Nascimento, Andreas Winter
Bit commitment is an important tool for constructing zero-knowledge proofs and multi-party computation. Unconditionally secure bit commitment can be based, in particular, on noisy channel or correlation where noise considered a valuable resource. Recently, Winter, Nascimento and Imai introduced the concept of commitment capacity, the maximal ratio between the length of a string which the sender commits to and the number of times the noisy channel/correlation is used. They also proved that for any discrete memoryless channel there exists a secure protocol achieving its commitment capacity however, no particular construction was given. Solving their open question, we provide an efficient protocol for achieving the commitment capacity of discrete memoryless systems (noisy channels and correlations).
In this paper we propose a two-round authenticated key agreement protocol using non-interactive zero-knowledge (NIZK) proofs. Essentially, a NIZK proof allows a prover to convince a verifier about the correctness of a statement without interaction. An obvious application of this is in a two-round key agreement protocol where each participant proves non-interactively the knowledge of the private key and a shared secret. Our key agreement protocol is based on this idea and is secure assuming the hardness of the Diffie-Hellman problem (DHP) and another related problem in bilinear maps.
A small size group signature scheme based on RSA cryptosystem is described in this paper. Due to the special algebraic structure of RSA, one public key and two corresponding private keys are available. The two private keys are used as signature keys for group members. The signature operation includes an ordinary RSA signature and a zero knowledge proof about signature key. Compared with most group schemes, it has low computational cost as to signature and verification.
In this paper, we propose a novel cryptography for ad hoc network security. In this cryptography, we present a new digital signature algorithm for identity authentication and key agreement scheme. The identity authentication is validated by zero-knowledge proof, and the identity authentication process includes the key agreement process, so the cryptography has high efficiency. Because of the fully distributed characteristics of ad hoc network, our security scheme has no central administration in the on-line process. The security analysis for our scheme indicated that the scheme can withstand the man-in-middle attack and message replay attack. The security of the scheme is guaranteed by the intractability of computing discrete logarithm
We prove that every problem in NP that has a zero-knowledge proof also has a zero-knowledge proof where the prover can be implemented in probabilistic polynomial time given an NP witness. Moreover, if the original proof system is statistical zero knowledge, so is the resulting efficient-prover proof system. An equivalence of zero knowledge and efficient-prover zero knowledge was previously known only under the assumption that one-way functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. Our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.
This thesis describes an electronic voting system based on Damg\\aa rd, Jurik and Nielsen's generalization of Paillier's probabilistic public key system. A threshold variant of this homomorphic cryptosystem is used to provide universally verifiable elections, where zero-knowledge proofs are used for proving correctness of votes.\n\nUsing this cryptosystem, an electronic voting system that supports voting for 1 out of $L$ candidates is described. Two types of encoding may be used to prove the validity of the votes. The number of proofs needed using normal encoding is linear in $L$, while the number of proofs needed using binary encoding is logarithmic in $L$. It is shown how to extend the system to allow casting a vote for $t$ out of $L$ candidates. This method may easily be used to carry out elections with weighted votes without any added complexity to the system.\n\nThe system is shown to satisfy the requirements for elections at The Norwegian University of Science and Technology (NTNU). A fully functional implementation of the electronic voting system as a distributed system, using Java Remote Method Invocation, is presented. The implementation is used to analyze the feasibility of using this voting system for future elections at NTNU. The implementation is tested using various keylengths and various election parameters. With a keylength of 1024 bits, the simulated time for verification of complex elections is small enough to be considered universally verifiable.
We propose cryptographic primitives for reading and assigning the (shared) secret found at a secret index in a vector of secrets. The problem can also be solved in constant round with existing general techniques based on arithmetic circuits and the “equality test” in [4]. However the proposed technique requires to exchange less bits. The proposed primitives require a number of rounds that is independent of the size N of the vector, and only depends (linearly) on the number t of computing servers. A previously known primitive for reading a vector at a secret index works only for 2party computations. Our primitives work for any number of computing participants/servers. The proposed techniques are secure against passive attackers, and zero knowledge proofs are provided to show that exactly one index of the array is read/written. The techniques work both with multiparty computations based on secret sharing and with multiparty computations based on threshold homomorphic encryption.