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.
Zero-knowledge proof for any relation amongst committed values is crucial and widely applicable in the design of high level cryptographic schemes, especially in privacy-preserving protocols. Besides quantum resistance, efficiency is what we are most concerned about, including asymptotic efficiency and concrete efficiency. Jain et al. proposed a simple string commitment scheme based on the Learning Parity with Noise (LPN) problem (JKPT12), and then designed zero-knowledge proofs for valid opening, linear relation and multiplicative relation of committed values. As a result, they got an efficient zero-knowledge proof for any circuit C, with communication complexity $\mathcal{O}(t|C|\ell \log \ell )$, where t is a security parameter measuring soundness and ℓ is the secret length of the LPN problem. In this work, we improve the concrete communication complexity by combining some commitments in JKPT12 together. The proofs of linear relation and multiplicative relation are shortened by (6α + 4)ℓ and (42α+28)ℓ respectively, where ℓ is the size of LPN secret. As a result, the communication cost of the protocol proving arbitrary relation is reduced by a constant level.
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.
A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic en-cryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives were proposed recently. However, unlike traditional ones, there is no standard approach to design and analyze such block ciphers and the hash functions, therefore their security analysis needs to be done carefully. In 2018, StarkWare launched a public STARK-Friendly Hash (SFH) Challenge to select an efficient and secure hash function to be used within ZK-STARKs, transparent and post-quantum secure proof systems. The block cipher JARVIS is one of the first ciphers designed for STARK applications but, shortly after its publication, the cipher has been shown vulnerable to Gröbner basis attack. This paper aims to describe a Gröbner basis attack on new block ciphers, MiMC, GMiMCerfand the variants of JARVIS. We present the complexity of Gröbner basis attack on JARVIS-like ciphers. Then we give results from our experiments for the attack on reduced-round MiMC and a structure we found in the Gröbner basis attack for GMiMCerf•
Due to the high integration of wireless communication and networking technologies, the communication-based train control (CBTC) systems are exposed to additional cyber-attack surfaces, allowing sophisticated attackers to combine cyber attack vectors with physical attack means to achieve malicious goals. Notably, the decentralized authentication features are missing in existing communication protocols which make the CBTC be easily compromised by data tampering attacks, and lead to serious operational accidents. With outstanding advantages in decentralized authentication, blockchain provides new effective solutions for decentralized identity authentication in CBTC. Consequently, it is critical to study the complex physical consequences of cyber breaches from a cross-layer defense perspective. In this paper, we propose a novel cross-layer defense method for cyber security in blockchain empowered CBTC against data tampering attacks. In the physical layer, the joint Kalman filter and$\chi ^{2} $detector is proposed for the train state estimation and detection. In the cyber layer, an asymmetric encryption-based secure communication protocol with identity authentication and the blockchain-based distributed key management system with the adaptive consensus mechanism are designed for data communication security. Considering the unavailable direct observation of the CBTC cyber security states, a partially observable Markov (POMDP) decision model is constructed to derive the optimal adaptive consensus strategies for balancing cyber security and efficiency. Extensive simulation results show that the proposed blockchain empowered CBTC cross-layer defense method can effectively improve the cyber security protection capability and minimize the impact of data tampering attacks on the train operation.
By the means of asymptotic security of cryptographic security mechanism we can get knowledge about efficiency and tolerable features against various type of attacks compromised on it. Analytical study about how zero-knowledge proofs can be used with Diffie Hellman problem (DHP) are presented in this research. One of the better algorithms of discrete logarithm problem which is suggested by Henry for zero knowledge proofs is suitable for DHP problem for the robustness analysis of it. The efficiency of discrete logarithm algorithm for DHP problem and integer factorization problem are analyzed and made comparison between them and covariance and correlation between their asymptotic functions is obtained as final result which clearly give us idea about strong relationship between each other and correlation factor between them is high, so they are similar in nature.
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.