Follow blockchain research across journals, conferences, and preprint repositories.
122 results · page 4 of 6
M. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich · 7 authors
No abstract is available for this record.
Dan Boneh, Rosario Gennaro, Steven Goldfeder
No abstract is available for this record.
Jean‐Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki · 6 authors
No abstract is available for this record.
P. Hecht
Post-Quantum Cryptography (PQC) attempts to find cryptographic protocols resistant to attacks using Shor polynomial time algorithm for numerical field problems or Grover search algorithm. A mostly overlooked but valuable line of solutions is provided by non-commutative algebraic structures, specifically canonical protocols that rely on one-way trapdoor functions (OWTF). Here we develop an algebraic framework who could be applied to different asymmetric protocols like D-H KE (Diffie-Hellman key exchange), Public Key Encryption, Digital Signature, ZKP (zero-knowledge proof) authentication, Oblivious Transfer, Multi-Party Computing, and so on. The trapdoor one-way functions selected are (a) Triple decomposition Problem (TDP) developed by Kurt, where a known element is factored into a product of three unknown factors and (b) a new version of conjugacy search that we refer from now on as Blind Conjugacy Search Problem (BCSP). Our platform structure is the general linear group GL(d,F_p) d-square non-singular matrices of prime field values. We give support to the fact that this framework is cryptographically secure against classical attacks like linear algebra attacks, length-based attacks, side-channel attacks against square (or duplicate) and multiply (or sum) algorithm, high sensitivity to pseudo random deterministic generators, etc. At same time it is immune against quantum attacks (using Grover and Shor), if the size parameters are carefully selected. Semantic security and IND-CCA2 compliance for this framework is discussed.
Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Xavier Bultel, Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade · 10 authors
No abstract is available for this record.
Olivier Blazy, Philippe Gaborit, Julien Schrek, Nicolas Sendrier
In this paper we give the first blind signature protocol for code-based cryptography. Our approach is different from the classical original RSA based blind signature scheme, it is done in the spirit of the Fischlin approach [9] which is based on proofs of knowledge. To achieve our goal we consider a new tool for zero-knowledge (ZK) proofs, the Concatenated Stern ZK protocol, which permits to obtain an authentication protocol for concatenated matrices. A signature is then obtained from the usual Fiat-Shamir heuristic. We describe our blind signature protocol for cryptography based on Hamming metric and show how it can be extended to rank based cryptography. The security of our blind protocol is based on the security of a trapdoor function for the syndrome decoding problem: the CFS signature scheme for Hamming distance and on the more recent RankSign protocol for rank metric. We give proofs in the random oracle model (ROM) for our blind signature scheme, which rely on the Syndrome Decoding problem. The parameters we obtain for our protocol are practical for rank metric (200kBytes) for the signature length and 15kBytes for public key size) and a little less practical for Hamming distance.
Anwar Kh. Faraj, Areej M. Abduldaim, Shatha A. Salman, Nadia M. G. Al-Saidi
Algebra is one of the important fields of mathematics. It concerns in the study and manipulates of mathematical symbols. It also concerns with study of abstractions such as groups, rings and fields. Ring theory is the most attractive category of algebra in the area of cryptography. Recently, many algebraic cryptosystem protocols based on non-commutative algebraic structures such as; authentication, key exchange, and encryption-decryption processes are adopted. In this paper, we employ the algebraic structure called nil Armendariz (NA) rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is implemented and illustrated through numerical example, and its soundness and completeness are proved.
Rafaël del Pino, Vadim Lyubashevsky
For a linear function f, a vector \(\mathbf{x}\) with small coefficients, and a vector \(y=f(\mathbf{x})\), we would like to be able to give a zero-knowledge proof for the knowledge of an \(\mathbf{x}'\) with small coefficients that satisfies \(f(\mathbf{x}')=y\). This is a common scenario in lattice-based cryptography, and there is currently no satisfactory solution for this problem. All known protocols are built via the repetition of a basic protocol that only has constant (1/2 or 2/3) soundness error. This implies that the communication complexity of the final protocol will be at least a factor of k larger than that of the basic one, where k is the security parameter.
Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
Sebastian E. Schmittner
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.
Wang Ming-we
A new signature scheme based solely on the MQ-problem is presented,which satisfies the following properties:(1)Forward security,which means that a compromise of a key now does not necessarily expose old traffic.(2)Backward security,which means that a compromise of a key now does not necessarily expose future traffic.We do not have to revoke our public key and re-issue a new key system everytime we detect a key leak.We use two fundamental tools,such as zero knowledge proof and mulitivariate public crypto.Our basic model is Koichi Sakumoto's identifcation scheme which is transformed by parallel processing and Fiat-Shamir transforming.What is novel about our approach is the key updating algortithm,which makes our scheme preserve backward security besides the forward property.Finally,we prove that our scheme satisfies the security under the random oracle model.
Maheswara Rao Valluri
Authentication is a process by which an entity, which could be a person or intended computer, establishes its identity to another entity. In private and public computer networks including the Internet, authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.
Andrew Drucker
Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.
Xin Liu, Qiuliang Xu
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.
Carlos Aguilar, Philippe Gaborit, Julien Schrek
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
Carlos Aguilar, Philippe Gaborit, Julien Schrek
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.
Philippe Gaborit, Julien Schrek, Gilles Zémor
No abstract is available for this record.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran · 5 authors
No abstract is available for this record.
Yu-Feng Chien, Wing-Kai Hon
No abstract is available for this record.
Soojin Cho, Manpyo Hong
We use an idea of linear representations of the symmetric group to reduce the number of communication rounds in the verification protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We assume Paillier encryption scheme with which we can apply some known zero-knowledge proofs following the same line of approaches of Peng et al. Incidence matrices of 1-subsets and 2-subsets of a finite set is intensively used for the implementation, and the idea of <TEX>$\lambda$</TEX>-designs is employed for the improvement of the computational complexity.
Chunming Tang
∑-protocol is an important tool in cryptology field.In this paper,we will prove that any ∑-protocol has the following characters: ①it is a witness hiding protocol if there exist at least two witnesses on R;②there exists a ∑-protocol on any NP statement under the assumption of the existence of one-way permutation;③there exist ∑-protocols with computational zero-knowledge;④∑-protocol can be changed into a zero-knowledge proof.
Alberto Del Lungo, Claudio Marini, Elisa Mori
No abstract is available for this record.
Jens Groth, Amit Sahai
Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.