Zero-Knowledge Proofs (ZKPs) have emerged as a revolutionary cryptographic technique that enables one party to prove knowledge of a statement without revealing any underlying information. ZKPs play a crucial role in enhancing cybersecurity by enabling privacy-preserving authentication, secure transactions, and data integrity verification. This paper explores the fundamentals of zero-knowledge proofs, including their classifications—interactive, non-interactive, and succinct proofs—along with real-world applications in secure communications, blockchain security, and identity verification. Furthermore, we discuss the challenges of implementing ZKPs and the potential future advancements in this cryptographic field
Víctor Gayoso Martínez, Luis Hernández–Álvarez, Luis Hernández Encinas
Blockchain is one of the most interesting emerging technologies nowadays, with applications ranging from cryptocurrencies to smart contracts. This paper presents a review of the cryptographic tools necessary to understand the fundamentals of this technology and the foundations of its security. Among other elements, hash functions, digital signatures, elliptic curves, and Merkle trees are reviewed in the scope of their usage as building blocks of this technology.
Edgar González Fernández, Guillermo Morales-Luna, Feliú Sagols
Current requirements for ensuring data exchange over the internet to fight against security breaches have to consider new cryptographic attacks. The most recent advances in cryptanalysis are boosted by quantum computers, which are able to break common cryptographic primitives. This makes evident the need for developing further communication protocols to secure sensitive data. Zero-knowledge proof systems have been around for a while and have been considered for providing authentication and identification services, but it has only been in recent times that its popularity has risen due to novel applications in blockchain technology, Internet of Things, and cloud storage, among others. A new zero-knowledge proof system is presented, which bases its security in two main problems, known to be resistant, up to now, against quantum attacks: the graph isomorphism problem and the isomorphism of polynomials problem.
Modern machine learning techniques have achieved surprisingly good standard test accuracy, yet classical machine learning theory has been unable to explain the underlying reason behind this success. The phenomenon of adversarial examples further complicates our understanding of what it means to have good generalization ability. Classifiers that generalize well to the test set are easily fooled by imperceptible image modifications, which can often be computed without knowledge of the classifier itself. The adversarial error of a classifier measures the error under which each test data point can be modified by an algorithm before it is given as input to the classifier. Followup work has showed that a tradeoff exists between optimizing for standard generalization error versus for adversarial error. This calls into question whether standard generalization error is the correct metric to measure. We try to understand the generalization capability of modern machine learning techniques through the lens of adversarial examples. To reconcile the apparent tradeoff between the two competing notions of error, we create new security definitions and classifier constructions which allow us to prove an upper bound on the adversarial error that decreases as standard test error decreases. We introduce a cryptographic proof technique by defining a security assumption in a simpler attack setting and proving a security reduction from a restricted black-box attack problem to this security assumption. We then investigate the double descent curve in the interpolation regime, where test error can continue to decrease even after training error has reached zero, to give a natural explanation for the observed tradeoff between adversarial error and standard generalization error. The second part of our work investigates further this notion of a black-box model by looking at the separation between being able to evaluate a function and being able to actually understand it. This is formalized through the notion of function obfuscation in cryptography. Given some concrete implementation of a function, the implementation is considered obfuscated if a user cannot produce the function output on a test input without querying the implementation itself. This means that a user cannot actually learn or understand the function even though all of the implementation details are presented in the clear. As expected this is a very strong requirement that does not exist for all functions one might be interested in. In our work we make progress on providing obfuscation schemes for simple, explicit function classes. The last part of our work investigates non-statistical biases and algorithms for nonconvex optimization problems. We show that the continuous-time limit of stochastic gradient descent does not converge directly to the local optimum, but rather has a bias term which grows with the step size. We also construct novel, non-statistical algorithms for two parametric learning problems by employing lattice basis reduction techniques from cryptography.
In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks.
The hardness of highly-structured computational problems gives rise to a variety of public-key primitives. On one hand, the structure exhibited by such problems underlies the basic functionality of public-key primitives, but on the other hand it may endanger public-key cryptography in its entirety via potential algorithmic advances. This subtle interplay initiated a fundamental line of research on whether structure is inherently necessary for cryptography, starting with Rudich’s early work (PhD Thesis '88) and recently leading to that of Bitansky, Degwekar and Vaikuntanathan (CRYPTO '17). Identifying the structure of computational problems with their corresponding complexity classes, Bitansky et al. proved that a variety of public-key primitives (e.g., public-key encryption, oblivious transfer and even functional encryption) cannot be used in a black-box manner to construct either any hard language that has NP-verifiers both for the language itself and for its complement, or any hard language (and even promise problem) that has a statistical zero-knowledge proof system - corresponding to hardness in the structured classes NP ∩ coNP or SZK, respectively, from a black-box perspective. In this work we prove that the same variety of public-key primitives do not inherently require even very little structure in a black-box manner: We prove that they do not imply any hard language that has multi-prover interactive proof systems both for the language and for its complement - corresponding to hardness in the class MIP ∩ coMIP from a black-box perspective. Conceptually, given that MIP = NEXP, our result rules out languages with very little structure. Already the cases of languages that have IP or AM proof systems both for the language itself and for its complement, which we rule out as immediate corollaries, lead to intriguing insights. For the case of IP, where our result can be circumvented using non-black-box techniques, we reveal a gap between black-box and non-black-box techniques. For the case of AM, where circumventing our result via non-black-box techniques would be a major development, we both strengthen and unify the proofs of Bitansky et al. for languages that have NP-verifiers both for the language itself and for its complement and for languages that have a statistical zero-knowledge proof system.
Privacy-focused crypto-currencies, such as Zcash or Monero, aim to provide strong cryptographic guarantees for transaction confidentiality and unlinkability.In this paper, we describe side-channel attacks that let remote adversaries bypass these protections.We present a general class of timing side-channel and traffic-analysis attacks on receiver privacy.These attacks enable an active remote adversary to identify the (secret) payee of any transaction in Zcash or Monero.The attacks violate the privacy goals of these crypto-currencies by exploiting side-channel information leaked by the implementation of different system components.Specifically, we show that a remote party can link all transactions that send funds to a user, by measuring the response time of that user's P2P node to certain requests.The timing differences are large enough that the attacks can be mounted remotely over a WAN.We responsibly disclosed the issues to the affected projects, and they have patched the vulnerabilities.We further study the impact of timing side-channels on the zero-knowledge proof systems used in these cryptocurrencies.We observe that in Zcash's implementation, the time to generate a zero-knowledge proof depends on secret transaction data, and in particular on the amount of transacted funds.Hence, an adversary capable of measuring proof generation time could break transaction confidentiality, despite the proof system's zero-knowledge property.Our attacks highlight the dangers of side-channel leakage in anonymous crypto-currencies, and the need to systematically protect them against such attacks.
The HighGear protocol (Eurocrypt 2018) is the fastest currently known approach to preprocessing for the SPDZ Multi-Party Computation scheme. Its backbone is formed by an Ideal Lattice-based Somewhat Homomorphic Encryption Scheme and accompanying Zero-Knowledge proofs. Unfortunately, due to certain characteristics of HighGear such current implementations limit the security parameters in a number of places. This is mainly due to memory and bandwidth consumption constraints. In this work we present a new approach to the ZKPoKs for the SPDZ Multi-Party Computation scheme. We rigorously formalize the original approach of HighGear and show how to improve upon it using a different proof strategy. This allows us to increase the security of the underlying protocols, whilst simultaneously also increasing the performance in terms of memory and bandwidth consumption as well as overall throughput of the SPDZ offline phase.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $\epsilon$-zero-knowledge. Concretely, we construct the following protocols:
- We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$-zero-knowledge property against quantum adversaries requires novel ideas.
- We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $\epsilon$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions.
At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.
In leakage resilient cryptography, there is a seemingly inherent restraint on the ability of the adversary that it cannot get access to the leakage oracle after the challenge. Recently, a series of works made a breakthrough to consider a postchallenge leakage. They presented achievable public key encryption (PKE) schemes which are semantically secure against after-the-fact leakage in the split-state model. This model puts a more acceptable constraint on adversary’s ability that the adversary cannot query the leakage of secret states as a whole but the functions of several parts separately instead of prechallenge query only. To obtain security against chosen ciphertext attack (CCA) for PKE schemes against after-the-fact leakage attack (AFL), existing works followed the paradigm of “double encryption” which needs noninteractive zero knowledge (NIZK) proofs in the encryption algorithm. We present an alternative way to achieve AFL-CCA security via lossy trapdoor functions (LTFs) without NIZK proofs. First, we formalize the definition of LTFs secure against AFL (AFLR-LTFs) and all-but-one variants (ABO). Then, we show how to realize this primitive in the split-state model. This primitive can be used to construct AFLR-CCA secure PKE scheme in the same way as the method of “CCA from LTFs” in traditional sense.
Les primitives lossy trapdoor, preuve à divulgation nulle de connaissance et applications Dans cette thèse, nous étudions deux primitives différentes : les lossy trapdoor functions (LTF) et les systèmes de preuve à divulgation nulle de connaissance. Les LTFs sont des familles de fonctions dans lesquelles les fonctions injectives et les fonctions lossy sont calculatoirement indistinguables. Depuis leur introduction, elles se sont avérées utiles pour la construction de diverses primitives cryptographiques. Nous donnons dans cette thèse des constructions efficaces d’une variante de la LTF : le filtre algébrique lossy. Avec cette variante, nous pouvons améliorer l’efficacité du schéma de chiffrement KDM-CCA et extracteur flous. Dans la deuxième partie de cette thèse, nous étudions les constructions de systèmes de preuve à divulgation nullle de connaissance. Nous donnons la première signature d’anneau de taille logarithmique avec la sécurité étroite en utilisant une variante de Groth-Kolhweiz Σ-protocole dans le modèle de l’oracle aléatoire. Nous proposons également une nouvelle construction d’arguments à divulgation nulle de connaissance non-intéractive et à vérifieur désigné (DVNIZK) sous l’hypothèse de réseaux Euclidiens. En utilisant cette nouvelle construction, nous construisons un système de vote basé sur les réseaux Euclidiens dans le modèle standard.
Lyra2REv2 is a hashing algorithm that consists of a chain of individual hashing algorithms, and it is used as a proof-of-work function in several cryptocurrencies. The most crucial and exotic hashing algorithm in the Lyra2REv2 chain is a specific instance of the general Lyra2 algorithm. This work presents the first hardware implementation of the specific instance of Lyra2 that is used in Lyra2REv2. Several properties of the aforementioned algorithm are exploited in order to optimize the design. In addition, an FPGA-based hardware implementation of a standalone miner for Lyra2REv2 on a Xilinx Multi-Processor System on Chip is presented. The proposed Lyra2REv2 miner is shown to be significantly more energy efficient than both a GPU and a commercially available FPGA-based miner. Finally, we also explain how the simplified Lyra2 and Lyra2REv2 architectures can be modified with minimal effort to also support the recent Lyra2REv3 chained hashing algorithm.
Omar A. Dawood, Othman I. Hammadi, Falath M. Mohammed
This paper proposes a new symmetric secret-key cipher for construction of block cipher model. This new approach is considered as a smart step that can be applied to the long process research of modern designing methods used in developing earlier symmetric algorithms. The present cipher can encrypt block lengths of 128-bit by employing Substitution-Permutation Network (SPN) structure. The present cipher uses three options of strong ciphering-key along with variable lengths of 192-bit for 12 rounds, 128-bit for 10 rounds and long ciphering key of 256-bit for 14 rounds similar to standard ciphers. The proposed algorithm has been designed to trust applications that are based on Bitcoin and crypto-currencies. The current algorithm intended to encrypt addresses of Bitcoin wallet that work quite similar to the e-mail address. The bitcoin wallet includes sensitive information like private secret keys and derived password that are highly confidential. The Advance Encryption Standard (AES) is employed to encrypt most of the bitcoin wallet database. The proposed cipher can act as a good substitute for the standard cipher that allows trusting the Bitcoin wallet database with high security and with a much more complex scheme. The key goal of the submitted algorithm is to build a new enhanced modern cipher with a secure and efficient applicable algorithm that can be used for crypto currencies applications employing a wide trail design strategy.
The Internet of Things (IoT) is very attractive because of its promises. However, it brings many challenges, mainly issues about privacy preservation and lightweight cryptography. Many schemes have been designed so far but none of them simultaneously takes into account these aspects. In this paper, we propose an efficient attribute-based credential scheme for IoT devices. We use elliptic curve cryptography without pairing, blind signing, and zero-knowledge proof. Our scheme supports block signing, selective disclosure, and randomization. It provides data minimization and transaction unlinkability. Our construction is efficient since smaller key size can be used, and computing time can be reduced. As a result, it is a suitable solution for IoT devices characterized by three major constraints, namely low-energy power, small storage capacity, and low computing power.
Lake Bu, Rashmi Agrawal, Hai Cheng, Michel A. Kinsy
The development and implementation of post-quantum cryptosystems have become a pressing issue in the design of secure computing systems, as general quantum computers have become more feasible in the last two years. In this work, we introduce a set of hardware post-quantum cryptographic primitives (PCPs) consisting of four frequently used security components, i.e., public-key cryptosystem (PKC), key exchange (KEX), oblivious transfer (OT), and zero-knowledge proof (ZKP). In addition, we design a high speed polynomial multiplier to accelerate these primitives. These primitives will aid researchers and designers in constructing quantum-proof secure computing systems in the post-quantum era.
Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.
Among the zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK), the simulation-extractable zk-SNARK (SE-SNARK) introduces a security notion of non-malleability. The existing pairing-based zk-SNARKs designed from linear encoding are known to be vulnerable to algebraic manipulation of the proof. The latest SE-SNARKs check the proof consistency by increasing the proof size and the verification cost. In particular, the number of pairings increases almost doubles due to further verification. In this article, we propose two novel SE-SNARK constructions with a single verification. The consistency check is subsumed in a single verification through employing a hash function. The proof size and verification time of the proposed SE-SNARK schemes are minimal in that it is the same as the state-of-the-art zk-SNARK without non-malleability. The proof in our SE-SNARK constructions comprises only three group elements (type III) in the QAP-based scheme and two group elements (type I) in the SAP-based scheme. The verification time in both requires only 3 pairings. The soundness of the proposed schemes is proven under the hash-algebraic knowledge (HAK) assumption and the (linear) collision-resistant hash assumption.