Jonathan Bootle, Vadim Lyubashevsky, Gregor Seiler
A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector \(\vec {s}\) with small coefficients satisfying \(A\vec {s}=\vec {u}\bmod \,q\). While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of \(\vec {s}'\) and c satisfying \(A\vec {s}'=\vec {u}c\) where \(\Vert \vec {s}'\Vert \gg \Vert \vec {s}\Vert \) and c is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern’s protocol (Crypto ’93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a \(\varSigma \)-protocol, each of whose iterations has soundness error \(2{/}3\), and thus requires over 200 repetitions to obtain soundness error of \(2^{-128}\), which is the main culprit behind the large size of the proofs produced.
Benjamin Hellouin de Ménibus, Ville Salo, Guillaume Theyssier
Abelian cellular automata (CAs) are CAs which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images have weak*-convergence towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e., randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA randomizes in Cesàro mean if and only if it has no soliton, i.e., a non-zero finite configuration whose time evolution remains bounded in space. This characterization generalizes previously known sufficient conditions for abelian CAs with scalar or commuting coefficients. Second, we exhibit examples of strong randomizers, i.e., abelian CAs randomizing in simple convergence; this is the first proof of this behaviour to our knowledge. We show, however, that no CA with commuting coefficients can be strongly randomizing. Finally, we show that some abelian CAs achieve partial randomization without being randomizing: the distribution of short finite words tends to the uniform distribution up to some threshold, but this convergence fails for larger words. Again this phenomenon cannot happen for abelian CAs with commuting coefficients.
Government officials and industry experts increasingly highlight today's data privacy and security vulnerabilities require new approaches to mitigate risk. Additional methods and techniques to address current vulnerabilities are needed especially between responsible parties within a large ecosystem like finance, healthcare, and education. New approaches leveraging cryptographic ledgers and blockchains are emerging as a potential solution. This paper proposes a layered architectural approach for cryptographic ledgers to aid in security and privacy controls of digital solutions.
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.
Abstract. In a secure physical computation, a set of parties each have physical inputs and jointly compute a function of their inputs in a way that reveals no information to any party except for the output of the function. Recent work in CRYPTO’14 presented examples of physical zero-knowledge proofs of physical properties, a special case of secure physical two-party computation in which one party has a physical input and the second party verifies a boolean function of that input. While the work suggested a general framework for modeling and analyzing physi-cal zero-knowledge protocols, it did not provide a general theory of how to prove any physical property with zero-knowledge. This paper takes an orthogonal approach using disposable circuits (DC)—cheap hardware tokens that can be completely destroyed after a computation—an ex-tension of the familiar tamper-proof token model. In the DC model, we demonstrate that two parties can compute any function of their physical inputs in a way that leaks at most 1 bit of additional information to either party. Moreover, our result generalizes to any multi-party physical computation. Formally, our protocols achieve unconditional UC-security with input-dependent abort. 1
The disadvantage of previous multi-coupon schemes is the lack of efficient protocol in which users can decide the maximal number of redemption according to their demands.And another deficiency is that they cannot remain secure in the concurrent case.This article remedied these obstacles by providing two improved systems with concurrent security.The first scheme was obtained by extending the underlying scheme of Blanton with the proof of two committed values and the Sigma-compiler for two round concurrent zero-knowledge argument.The second scheme(i.e.,the strengthened version of the first one) achieved more efficient security reduction by incorporating the straight-line extraction paradigm and removed random oracles by using the non-interactive zero-knowledge argument from homomorphic encryption.Compared with the other strongly unsplittable schemes,the first scheme has better communicational efficiency and the second one does not rely on the random oracle model.
Abstract. In this study, a novel pairing based strong designated verifier signature scheme based on non-interactive zero knowledge proofs is proposed. The security of the proposal is presented by sequences of games without random oracles; furthermore, this scheme has a security proof for the property of privacy of the signer’s identity in comparison with the scheme proposed by Zhang et al. in 2007. In addition, this proposal compared to the scheme presented by Huang et al. in 2011 supports non-delegatability. The non-delegatability of our proposal is achieved since we do not use the common secret key shared between the signer and the designated verifier in our construction. Furthermore, if a signer delegates her signing capability which is derived from her secret key on a specific message to a third party, then, the third party cannot generate a valid designated verifier signature due to the relaxed special soundness of the non-interactive zero knowledge proof. To the best of our knowledge, this construction is the first attempt to generate a designated verifier signature scheme with non-delegatability in the standard model, while satisfying of non-delegatability property is loose.
In this paper we present a new 5-pass identification scheme with asymptotic\ncheating probability 1/2 based on the syndrome decoding problem. Our protocol\nis related to the Stern identification scheme but has a reduced communication\ncost compared to previous code-based zero-knowledge schemes, moreover our\nscheme permits to obtain a very low size of public key and secret key. The\ncontribution of this paper is twofold, first we propose a variation on the\nStern authentication scheme which permits to decrease asymptotically the\ncheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice)\nbut with less communication. Our solution is based on deriving new challenges\nfrom the secret key through cyclic shifts of the initial public key syndrome; a\nnew proof of soundness for this case is given Secondly we propose a new way to\ndeal with hashed commitments in zero-knowledge schemes based on Stern's scheme,\nso that in terms of communication, on the average, only one hash value is sent\nrather than two or three. Overall our new scheme has the good features of\nhaving a zero-knowledge security proof based on well known hard problem of\ncoding theory, a small size of secret and public key (a few hundred bits), a\nsmall calculation complexity, for an overall communication cost of 19kb for\nauthentication (for a $2^{16}$ security) and a signature of size of 93kb\n(11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous\nschemes based on coding theory.\n
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a $2^{16}$ security) and a signature of size of 93kb (11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous schemes based on coding theory.
In recent years, the studies of blind signatures achieved a lot of results, but there still are many problems. Boneh and Boyen gave a new signature, derived the blind signature scheme from their idea. This paper first gave a blind signature without random oracles, with this property, the scheme was secure in standard model. Then, used common reference string to do non-interactive zero knowledge proof, made the blind signature into only two moves to achieve round optimal, and the concurrency operation of blind signature could be reach by this. For the algorithm is simple and not complicated, the blind signature is more efficient than the existing secure blind signature schemes,so save transmission bandwidth and improves transfer efficiency.
We proposed a new zero-knowledge proof of identity protocol based on Mandelbrot and Julia Fractal sets. The Fractal based zero-knowledge protocol was possible because of the intrinsic connection between the Mandelbrot and Julia Fractal sets. In the proposed protocol, the private key was used as an input parameter for Mandelbrot Fractal function to generate the corresponding public key. Julia Fractal function was then used to calculate the verified value based on the existing private key and the received public key. The proposed protocol was designed to be resistant against attacks. Fractal based zero-knowledge protocol was an attractive alternative to the traditional number theory zero-knowledge protocol.
This paper presents a new zero knowledge protocol for knowledge of (A,x,y),which is based on Cramer-shoup encryptionfrom linear assumption. Compared with reference,this protocol has one more parameter.
A new efficient normative signature scheme,based on discrete logarithm assumption and factoring assumption is proposed.A zero knowledge proof protocol between the nominee and a third party to verify the signature is also constructed.This signature can be transformed into an undeniable and fail-stop signature if necessary.The efficiency of different nominative signature schemes is also compared.
The existing protocols that are used to prove that a committed number x lies in a specific interval mostly prove that the integer x is no less than a and then repeat the same method to prove that b is no less than x.In order to delete the repetition in these methods a new protocol is proposed by integrating the protocol that two committed numbers are equal with the protocol of the CFT proof.A verifier can be convinced that the committed number x is neither less than the integer a nor more than the integer b after the protocol is operated only once,and hence the exact proof that x lies in the interval is achieved.The proposed protocol is a statistical zero-knowledge proof.In contrast to Boudot's protocol,our method reduces an exponentiation operation;the communication quantity decreases from(16 176) bits to(13 222) bits,and the communication efficiency increases by 18.26 percent.