We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions...) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt. In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information on it, even in a non-interactive way, without public-key primitives, and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstatesQIP and ZKstatesQMA.
Maryam Sheikhi Garjan, N. Gamze ORHON KILIÇ, Murat Cenk
The increasing demand for secure and anonymous transactions raises the popularity of ring signatures, which is a digital signature scheme that allows identifying a group of possible signers without revealing the identity of the actual signer. This paper presents efficient supersingular isogeny-based ring signature and linkable ring signature schemes that will find potential applications in post-quantum technologies. We develop the ring signature scheme by applying the Fiat-Shamir transform on the sigma protocol for a ring which we obtain from the supersingular isogeny-based interactive zero-knowledge identification scheme by adopting the scheme for a ring. We also extend our ring signature protocol with an additional parameter, i.e., a tag that provides to detect if a signer issues two signatures concerning the same ring by preserving anonymity and linkable anonymity. The signature size of our ring signature protocols increases logarithmically in the size of the ring thanks to the Merkle trees. We show the security proofs and efficiency analyses of the protocols offered. Moreover, we provide the implementation results of the supersingular isogeny-based ring signature, which offers small signature sizes for NIST post-quantum security levels.
Vaishnavi Nagaraja, Muhammad Rezal Kamel Ariffin, Terry Shue Chien Lau, Nurul Nur Hanisah Adenan · 7 authors
The identification protocol is a type of zero-knowledge proof. One party (the prover) needs to prove his identity to another party (the verifier) without revealing the secret key to the verifier. One can apply the Fiat–Shamir transformation to convert an identification scheme into a signature scheme which can be used for achieving security purposes and cryptographic purposes, especially for authentication. In this paper, we recall an identification protocol, namely the RankID scheme, and show that the scheme is incorrect and insecure. Then, we proposed a more natural approach to construct the rank version of the AGS identification protocol and show that our construction overcomes the security flaws in the RankID scheme. Our proposal achieves better results when comparing the public key size, secret key size, and signature size with the existing identification schemes, such as Rank RVDC and Rank CVE schemes. Our proposal also achieves 90%, 50%, and 96% reduction for the signature size, secret key size, and public key size when compared to the Rank CVE signature scheme.
Liqun Chen, Changyu Dong, Nada El Kassem, Christopher J. P. Newton · 5 authors
Direct Anonymous Attestation (DAA) was designed for the Trusted Platform Module (TPM) and versions using RSA and elliptic curve cryptography have been included in the TPM specifications and in ISO/IEC standards. These standardised DAA schemes have their security based on the factoring or discrete logarithm problems and are therefore insecure against quantum attackers. Research into quantum-resistant DAA has resulted in several lattice-based schemes. Now in this paper, we propose the first post-quantum DAA scheme from symmetric primitives. We make use of a hash-based signature scheme, which is a slight modification of SPHINCS+, as a DAA credential. A DAA signature, proving the possession of such a credential, is a multiparty computation-based non-interactive zero-knowledge proof. The security of our scheme is proved under the Universal Composability (UC) model. While maintaining all the security properties required for a DAA scheme, we try to make the TPM’s workload as low as possible. Our DAA scheme can handle a large group size (up to 2 60 group members), which meets the requirements of rapidly developing TPM applications.
Alex Ozdemir, Riad S. Wahby, Fraser Brown, Clark Barrett
Abstract Zero Knowledge Proofs (ZKPs) are cryptographic protocols by which a prover convinces a verifier of the truth of a statement without revealing any other information. Typically, statements are expressed in a high-level language and then compiled to a low-level representation on which the ZKP operates. Thus, a bug in a ZKP compiler can compromise the statement that the ZK proof is supposed to establish. This paper takes a step towards ZKP compiler correctness by partially verifying a field-blasting compiler pass, a pass that translates Boolean and bit-vector logic into equivalent operations in a finite field. First, we define correctness for field-blasters and ZKP compilers more generally. Next, we describe the specific field-blaster using a set of encoding rules and define verification conditions for individual rules. Finally, we connect the rules and the correctness definition by showing that if our verification conditions hold, the field-blaster is correct. We have implemented our approach in the CirC ZKP compiler and have proved bounded versions of the corresponding verification conditions. We show that our partially verified field-blaster does not hurt the performance of the compiler or its output; we also report on four bugs uncovered during verification.
The paper discusses the basic principles of construction and the main types of zeroknowledge succinct non-interactive argument of knowledge (zk-SNARK) which is used in the model of a three-way insecure computing environment and based on sets of polynomials. A number of zk-SNARK cryptographic protocols with different algorithms for generating public parameters (Trusted Setup) are given, constructing succinct proofs of reliability calculations (Prover) and public/designated verification of proofs (Verifier). The cases of satisfying the feasibility of discrete functions (arithmetic/ Boolean circuits) using different polynomial sets are presented in quadratic arithmetic programs (QAP), square arithmetic programs (SAP), quadratic span programs (QSP), square span programs (SSP), quadratic polynomial programs (QPP), etc., also the use of authenticated data are described. The cryptographic transformations needed to build zk-SNARKs based on symmetric and asymmetric hash functions, exponential knowledge problems, digital signatures, homomorphic encryption, bilinear pairings based on elliptic curves, etc. are presented. Examples of multilateral verifiable calculations based on zk-SNARK are given.
Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß · 7 authors
We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head. To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols. We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present $$\textsf{FAEST}$$ , a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.
Cryptocurrency is a digital payment system, created by non-banks, not subject to any official license, and is mainly mined using blockchain technology. The process of emission of cryptocurrency is called mining, and since cryptography is used, the meaning of "crypto" is mentioned at the beginning of the word currency. Cryptocurrency transactions do not require personal information. This means that users remain largely anonymous and transactions are largely confidential. However, every transaction is recorded, senders and receivers are known to the public. This way, all transactions are tracked, no transaction can be changed, manipulated or deleted afterwards. In this respect, cryptocurrencies are a bit more transparent than digital currencies. Cryptocurrencies and digital wallets, which are the most popular nowadays, are similar but have different functions. In this regard, the article we present is suitable for economically interested individuals or organizations.
Xin Liu, Xiaomeng Liu, Ruiling Zhang, Dan Luo · 6 authors
Manhattan distance is mainly used to calculate the total absolute wheelbase of two points in the standard coordinate system. The secure computation of Manhattan distance is a new geometric problem of secure multi-party computation. At present, the existing research secure computing protocols for Manhattan distance cannot resist the attack of malicious participants. In the real scene, the existence of malicious participants makes it necessary to study a solution that can resist malicious attacks. This paper first analyzes malicious attacks of the semi-honest model protocol of computing Manhattan distance and then designs an advanced protocol under the malicious model by using the Goldwasser–Micali encryption system and Paillier encryption algorithm, and utilizing some cryptographic tools such as the cut-choose method and zero-knowledge proof. Finally, the real/ideal model paradigm method is used to prove the security of the malicious model protocol. Compared with existing protocols, the experimental simulation shows that the proposed protocol can resist malicious participant attacks while maintaining high efficiency. It has practical value.
Tim Güneysu, Philip Hodges, Georg Land, Mike Ounsworth · 6 authors
Certificate authorities in public key infrastructures typically require entities to prove possession of the secret key corresponding to the public key they want certified. While this is straightforward for digital signature schemes, the most efficient solution for public key encryption and key encapsulation mechanisms (KEMs) requires an interactive challenge-response protocol, requiring a departure from current issuance processes. In this work we investigate how to non-interactively prove possession of a KEM secret key, specifically for lattice-based KEMs, motivated by the recently proposed KEMTLS protocol which replaces signature-based authentication in TLS 1.3 with KEM-based authentication. Although there are various zero-knowledge (ZK) techniques that can be used to prove possession of a lattice key, they yield large proofs or are inefficient to generate. We propose a technique called verifiable generation, in which a proof of possession is generated at the same time as the key itself is generated. Our technique is inspired by the Picnic signature scheme and uses the multi-party-computation-in-the-head (MPCitH) paradigm; this similarity to a signature scheme allows us to bind attribute data to the proof of possession, as required by certificate issuance protocols. We show how to instantiate this approach for two lattice-based KEMs in Round 3 of the NIST post-quantum cryptography standardization project, Kyber and FrodoKEM, and achieve reasonable proof sizes and performance. Our proofs of possession are faster and an order of magnitude smaller than the previous best MPCitH technique for knowledge of a lattice key, and in size-optimized cases can be comparable to even state-of-the-art direct lattice-based ZK proofs for Kyber. Our approach relies on a new result showing the uniqueness of Kyber and FrodoKEM secret keys, even if the requirement that all secret key components are small is partially relaxed, which may be of independent interest for improving efficiency of zero-knowledge proofs for other lattice-based statements.
Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger · 6 authors
We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.
Ning Luo, Timos Antonopoulos, William R. Harris, Ružica Piskač · 6 authors
Zero-knowledge (ZK) protocols enable one party to prove to others that it knows a fact without revealing any information about the evidence for such knowledge. There exist ZK protocols for all problems in NP, and recent works developed highly efficient protocols for proving knowledge of satisfying assignments to Boolean formulas, circuits and other NP formalisms. This work shows an efficient protocol for the converse: proving formula unsatisfiability in ZK (when the prover posses a non-ZK proof). An immediate practical application is efficiently proving safety of secret programs.
Mohamed A. El-Zawawy, Alessandro Brighente, Mauro Conti
The inclusion of drones in Internet of Vehicles (IoV) is a current trend that presents significant trade-offs. On the one hand, Unmanned Aerial Vehicles (UAVs) provide advantages such as enabling ground communications also when physical obstacles limit the connectivity. On the other hand, they increase the attack surface. For instance, physical attacks on drones provide the attacker with credentials that can be used to inject bogus information into the IoV network, thus jeopardizing not only security but also users’ safety. In this scenario, authentication plays a fundamental role to guarantee security. It is however fundamental to develop authentication protocols that can, at the same time, protect ground users’ data and prevent attacks to drones. However, currently available authentication schemes cannot guarantee security in case of attacks to drones. In this paper, we propose a Blockchain-supported authentication protocol for Drone-assisted IoV using Elliptic curve cryptography (BDIVE). Compared to existing authentication protocols, we extend the threat model from an honest-but-curious drone to active attacks against drones.BDIVEprovides both energy-efficiency, traceability, and accountability thanks to the use of blockchain at the Trusted Authority (TA). Using Burrow-Abadi–Needham (BAN) logic, we analyze and prove the security of mutual authentication inBDIVE. We also prove the security ofBDIVEagainst several attacks by implementing it in AVISPA. To assess its scalability and energy efficiency, we implementBDIVEusing Omnetpp with its Castalia simulator. The comparison ofBDIVEwith currently existing authentication protocols, shows that it reduces the energy consumption up to 70% and the computational cost up to 68%, while providing resistance to previously unconsidered attack vectors.
Recent advanced Zero-Knowledge protocols, along with other high-level constructions such as Multi-Party Computations (MPC), have highlighted the need for a new type of symmetric primitives that are not optimized for speed on the usual platforms (desktop computers, servers, microcontrollers, RFID tags...), but for their ability to be implemented using arithmetic circuits.Several primitives have already been proposed to satisfy this need. In order to enable an efficient arithmetization, they operate over large finite fields, and use round functions that can be modelled using low degree equations. The impact of these properties on their security remains to be completely assessed. In particular, algebraic attacks relying on polynomial root-finding become extremely relevant. Such attacks work by writing the cryptanalysis as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma, . . . ).The need for further analysis of these new designs has been recently highlighted by the Ethereum Foundation, as it issued bounties for successful attacks against round-reduced versions of several of them.In this paper, we show that the security analysis performed by the designers (or challenge authors) of four such primitives is too optimistic, and that it is possible to improve algebraic attacks using insights gathered from a careful study of the round function.First, we show that univariate polynomial root-finding can be of great relevance n practice, as it allows us to solve many of the Ethereum Foundation’s challenges on Feistel–MiMC. Second, we introduce a trick to essentially shave off two full rounds at little to no cost for Substitution-Permutation Networks (SPN). This can be combined with univariate (resp. multivariate) root-finding, which allowed to solve some challenges for Poseidon (resp. Rescue–Prime). Finally, we also find an alternative way to set up a system of equations to attack Ciminion, leading to much faster attacks than expected by the designers.