Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, Dongxi Liu
We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree \(k\ge 2\), where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree \(k\ge 2\) have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (\(k=1\)) and a very specific quadratic case (\(k=2\)), which are obtained as a special case of our technique.
This paper addresses the problem of uploading large quantities of sensitive industrial data to a public distributed network by proposing a new framework. The framework combines the existing technologies of the distributed web and distributed ledger to provide a mechanism of encrypting data and choosing whom to share the data with. The framework is designed to work with existing platforms; the InterPlanetary File System (IPFS) and the Ethereum blockchain platforms are used as examples within this paper, though it is stated that similar platforms are capable of providing the requirements for the framework to operate. The framework uses the concept of the Diffie-Hellman Key Exchange (DHKE), and is implemented in three different mechanisms of the DHKE: one-step Elliptical-Curve Diffie-Hellman Key Exchange (ECDH); two-step ECDH; and Supersingular Isogeny Diffie-Hellman Key Exchange (SIDH). The paper discusses the security of each along with individual advantages and disadvantages, and concludes that the SIDH is the most appropriate implementation for future use due to it being post-quantum secure.
Most cryptocurrency systems or systems based on blockchain technology are currently using the elliptic curves digital signature algorithm (ECDSA) on the secp256k1 curve, which is susceptible to backdoors implemented by the curve creator (secp256k1). The paper proposes a multiple elliptic curves digi-tal signature algorithm (MECDSA), which allows not only for setting the number of elliptic curves according to practical security requirements, but also for editing the parameters of each elliptic curve. The performance analy-sis proves that the scheme is secure and efficient, and can avoid any back-doors implemented by curve creators. We suggest that the systems based on blockchain should operate in two elliptic curves considering the contradic-tion between security and efficiency.
This article describes how after the concept of anonymous credential systems was introduced in 1985, a number of similar systems have been proposed. However, these systems use zero-knowledge protocols to authenticate users, resulting in inefficient authentication during the stage of proving credential possession. To overcome this drawback, this article presents a signature scheme that uses partially blind signatures and chameleon hash functions such that both the prover and verifier achieve efficient authentication. In addition to providing a computational cost comparison table showing that the proposed signature scheme achieves a more efficient credential possession proving compared to other schemes, concrete security proofs are provided under a random oracle model to demonstrate that the proposed scheme satisfies the properties of anonymous credentials.
Preuves à divulgation nulle de connaissance efficaces à base de réseaux euclidiens et applications Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l’apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l’amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu’elles représentent un des piliers des protocols de confidentialité, n’ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité. Cette thèse s’attelle dans un premier temps à améliorer l’état de l’art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d’appartenance à un sous ensemble dont la taille est indépendante de l’ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent. Notre second propos est d’utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu’un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle.
Proposed cryptographic protocol with zero-knowledge proof on elliptic curves using one-way hash function, allowing to establish the truth of allegation and does not convey any additional information about the approval. Cryptographic protocols based on zero-knowledge proof allow identification, key exchange and other cryptographic operations to be performed without leakage of sensitive information during the information exchange. The implementation of the cryptographic protocol of the zero-knowledge proof on the basis of the mathematical apparatus of elliptic curves allows to significantly reduce the size of the protocol parameters and increase the cryptographic stability (computational complexity of the hacking problem). The security of cryptosystems on elliptic curves is based on the difficulty of solving the elliptic curve discrete logarithm problem. The completeness and correctness of the protocol is determined in the work, an example of calculation is given, the cryptographic protocol is modeled on the High-Level Protocol Specification Language, the model validation and verification of the protocol are performed. Software verification of the cryptographic protocol was performed using the software modules On the Fly Model Checker and Constraint Logic based Attack Searcher. To validation the cryptographic protocol for resistance to intruder attacks was used the Security Protocol Animator package for Automated Validation of Internet Security Protocols and Applications. The security of the proposed cryptographic protocol is based on the difficulty of solving the elliptic curve discrete logarithm problem and the cryptographic stability of the hash function. To implement the cryptographic protocol, you can use the recommended elliptical curves according to DSTU 4145-2000 and the hash function GOST 34.311-95.
We propose building a new PKC in a ring structure, the classification of rings being an open problem. The difficulty of the scheme is based on retrieving the eigenvalues of endomorphism on a finite type module over a non-commutative ring. It is resistant to a chosen cipher text attack. Working in the fraction ring of a non-commutative ring makes our scheme a zero-knowledge proof of knowledge, result indistinguishable, in the Naor-Yung model. Finally, a dramatic improvement in security is obtained through the drawing with uniform probability of the working ring at high frequency.
Jack Doerner, Yashvanth Kondi, Eysa Lee, Abhi Shelat
The Elliptic Curve Digital Signature Algorithm (ECDSA) is one of the most widely used schemes in deployed cryptography. Through its applications in code and binary authentication, web security, and cryptocurrency, it is likely one of the few cryptographic algorithms encountered on a daily basis by the average person. However, its design is such that executing multi-party or threshold signatures in a secure manner is challenging: unlike other, less widespread signature schemes, secure multi-party ECDSA requires custom protocols, which has heretofore implied reliance upon additional cryptographic assumptions such as the Paillier encryption scheme. We propose new protocols for multi-party ECDSA key-generation and signing with a threshold of two, which we prove secure against malicious adversaries in the random oracle model using only the Computational Diffie-Hellman Assumption and the assumptions already implied by ECDSA itself. Our scheme requires only two messages, and via implementation we find that it outperforms the best prior results in practice by a factor of 55 for key generation and 16 for signing, coming to within a factor of 12 of local signatures. Concretely, two parties can jointly sign a message in just over two milliseconds.
Bilinear maps (also called pairings) have been used for constructing various kinds of cryptographic primitives including (but not limited to) short signatures, identity-based encryption, attribute-based encryption, and non-interactive zero-knowledge proof systems. In known instantiations of cryptographic bilinear maps based on eliptic curves, source and target groups are different groups, which may restrict applications of bilinear maps. Cheon and Lee studied self-bilinear maps, which are bilinear maps whose source and target groups are identical. They showed huge potential of self-bilinear maps by showing that self-bilinear maps can be transformed into multilinear maps, which give further more cryptographic applications including (but not limited to) multiparty non-interactive key exchange, broadcast encryption, attribute-based encryption, homomorphic signatures, and obfuscation. However, they also showed a strong negative result on the existence of cryptographic self-bilinear maps. Namely, they showed that if there exists an efficiently computable self-bilinear map on a known order group, then the computational Diffie-Hellman (CDH) assumption does not hold on the group. This means that cryptographically useful self-bilinear maps do not exist on groups of known order. On the other hand, there is no negative result for self-bilinear maps on groups of unknown order. Indeed, Yamakawa et al. gave a partial positive result for self-bilinear maps on unknown order groups. Namely, they constructed self-bilinear maps with auxiliary information, which is a weaker variant of self-bilinear maps based on indistinguishability obfuscation. Though they showed that they are sufficient for some applications of self-bilinear maps, they are not as useful as "ideal" self-bilinear maps, which do not need auxiliary information. In this talk, we first review the construction of self-bilinear maps with auxiliary information given by Yamakawa et al. Then we consider the possibility of constructing ideal self-bilinear maps.
Card‐based physical access control systems are used by most people on a daily basis, for example, at work, in public transportation, or at hotels. Yet these systems have often very poor cryptographic protection. User identifiers and keys can be easily eavesdropped on and counterfeited. The privacy‐preserving features are almost missing in these systems. To improve this state, we propose a novel cryptographic scheme based on efficient zero‐knowledge proofs and Boneh‐Boyen signatures. The proposed scheme is provably secure and provides the full set of privacy‐enhancing features, that is, the anonymity, untraceability, and unlinkability of users. Furthermore, our scheme supports distributed multidevice authentication with multiple RFID (Radio‐Frequency IDentification) user devices. This feature is particularly important in applications for controlling access to dangerous sites where the presence of protective equipment is checked during each access control session. Besides the full cryptographic specification, we also show the results of our implementation on devices commonly used in access control applications, particularly the smart cards and embedded verification terminals. By avoiding costly operations on user devices, such as bilinear pairings, we were able to achieve times comparable to existing systems (around 500 ms), while providing significantly higher security, privacy protection, and features for RFID multidevice authentication.
Sharon Goldberg, Leonid Reyzin, Omar Sagga, Foteini Baldimtsi
In many applications, it is important to verify that an RSA public key (N; e) speci es a \npermutation over the entire space ZN, in order to prevent attacks due to adversarially-generated \npublic keys. We design and implement a simple and e cient noninteractive zero-knowledge \nprotocol (in the random oracle model) for this task. Applications concerned about adversarial \nkey generation can just append our proof to the RSA public key without any other modi cations \nto existing code or cryptographic libraries. Users need only perform a one-time veri cation of \nthe proof to ensure that raising to the power e is a permutation of the integers modulo N. For \ntypical parameter settings, the proof consists of nine integers modulo N; generating the proof \nand verifying it both require about nine modular exponentiations. \nWe extend our results beyond RSA keys and also provide e cient noninteractive zero- \nknowledge proofs for other properties of N, which can be used to certify that N is suitable \nfor the Paillier cryptosystem, is a product of two primes, or is a Blum integer. As compared to \nthe recent work of Auerbach and Poettering (PKC 2018), who provide two-message protocols for \nsimilar languages, our protocols are more e cient and do not require interaction, which enables \na broader class of applications.
Eli Ben‐Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner · 6 authors
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size \(O(\log ^2 n)\); it can be produced with \(O(n \log n)\) field operations and verified with O(n). At 128 bits of security, proofs are less than \({250}\,\mathrm{kB}\) even for several million constraints, more than \(10{\times }\) shorter than prior SNARGs with similar features.
Eli Ben‐Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev
The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such PCP/IOP systems in practice. To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity. For codes of block-length N, the arithmetic complexity of the (interactive) FRI prover is less than 6 * N, while the (interactive) FRI verifier has arithmetic complexity <= 21 * log N, query complexity 2 * log N and constant soundness - words that are delta-far from the code are rejected with probability min{delta * (1-o(1)),delta_0} where delta_0 is a positive constant that depends mainly on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems. Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of "proof composition" and thus used at most O(log log N) rounds. We show that when delta is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of "proof composition" rounds to Theta(log N) and thereby reduce prover and verifier running time for fixed soundness.
Rafaël del Pino, Vadim Lyubashevsky, Gregor Seiler
We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical -- all operations take less than half a second on a standard laptop. A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well. The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.
ECDSA is a standardized signing algorithm that is widely used in TLS, code signing, cryptocurrency and more. Due to its importance, the problem of securely computing ECDSA in a distributed manner (known as threshold signing) has received considerable interest. However, despite this interest, there is still no full threshold solution for more than 2 parties (meaning that any t -out-of- n parties can sign, security is preserved for any t-1 or fewer corrupted parties, and tłeq n can be any value thus supporting an honest minority) that has practical key distribution. This is due to the fact that all previous solutions for this utilize Paillier homomorphic encryption, and efficient distributed Paillier key generation for more than two parties is not known. In this paper, we present the first truly practical full threshold ECDSA signing protocol that has both fast signing and fast key distribution. This solves a years-old open problem, and opens the door to practical uses of threshold ECDSA signing that are in demand today. One of these applications is the construction of secure cryptocurrency wallets (where key shares are spread over multiple devices and so are hard to steal) and cryptocurrency custody solutions (where large sums of invested cryptocurrency are strongly protected by splitting the key between a bank/financial institution, the customer who owns the currency, and possibly a third-party trustee, in multiple shares at each). There is growing practical interest in such solutions, but prior to our work these could not be deployed today due to the need for distributed key generation.
Preuves à divulgation nulle de connaissance pour le calcul sécurisé Dans cette thèse, nous étudions les preuves à divulgation nulle de connaissance, une primitive cryptographique permettant de prouver une assertion en ne révélant rien de plus que sa véracité, et leurs applications au calcul sécurisé. Nous introduisons tout d’abord un nouveau type de preuves à divulgation nulle, appelées arguments implicites à divulgation nulle, intermédiaire entre deux notions existantes, les preuves interactives et les preuves non interactives à divulgation nulle. Cette nouvelle notion permet d’obtenir les mêmes bénéfices en terme d’efficacité que les preuves non-interactives dans le contexte de la construction de protocoles de calcul sécurisé faiblement interactifs, mais peut être instanciée à partir des mêmes hypothèses cryptographiques que les preuves interactives, permettant d’obtenir de meilleures garanties d’efficacité et de sécurité. Dans un second temps, nous revisitons un système de preuves à divulgation nulle de connaissance qui est particulièrement utile dans le cadre de protocoles de calcul sécurisé manipulant des nombres entiers, et nous démontrons que son analyse de sécurité classique peut être améliorée pour faire reposer ce système de preuve sur une hypothèse plus standard et mieux connue. Enfin, nous introduisons une nouvelle méthode de construction de systèmes de preuves à divulgation nulle sur les entiers, qui représente une amélioration par rapport aux méthodes existantes, tout particulièrement dans un modèle de type client-serveur, où un client à faible puissance de calcul participe à un protocole de calcul sécurisé avec un serveur à forte puissance de calcul.