Emanuele Raso, Lorenzo Bracciale, Pierluigi Gallo, Giorgio Bernardinetti ¡ 7 authors
Blockchain technology can be applied to smart grids to support business and management operations, and its distributed nature is advantageous when considering user-managed renewable systems. However, these new fully distributed systems raise a number of security and privacy issues. For this reason, numerous solutions integrating blockchain with privacy and security enhancing technologies, such as homomorphic encryption, secret sharing and zero-knowledge proof, have been proposed in the literature. The complexity of such systems from an algorithmic and protocol point of view is obvious, while the computational cost is less obvious and often overlooked by the authors. In this paper, we want to experimentally evaluate the computational weight of cryptographic techniques proposed to guarantee security and privacy on blockchains. We will take as reference commercial devices with computational capabilities similar to those we expect to find in smart grid devices. The results show that some techniques are not suitable for these scenarios and that architectural solutions must therefore be carefully designed.
Cryptography has proven to be one of the most contentious areas in modern society. For some it protects the rights of individuals to privacy and security, while for others it puts up barriers against the protection of our society. This book aims to develop a deep understanding of cryptography, and provide a way of understanding how privacy, identity provision and integrity can be enhanced with the usage of encryption. The book has many novel features including: ⢠full provision of Web-based material on almost every topic covered ⢠provision of additional on-line material, such as videos, source code, and labs ⢠coverage of emerging areas such as Blockchain, Light-weight Cryptography and Zero-knowledge Proofs (ZKPs) Key areas covered include: ⢠Fundamentals of Encryption ⢠Public Key Encryption ⢠Symmetric Key Encryption ⢠Hashing Methods ⢠Key Exchange Methods ⢠Digital Certificates and Authentication ⢠Tunneling ⢠Crypto Cracking ⢠Light-weight Cryptography ⢠Blockchain ⢠Zero-knowledge Proofs This book provides extensive support through the associated website of: http://asecuritysite.com/encryption
Due to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantum-secure signature proposal LegRoast. However, its security is not yet extensively studied. The Legendre PRF computes for a key$k$on input$x$the Legendre symbol$L_{k}(x)=(\frac{x+k}{p})$in some finite field$\mathbb{F}_{p}$. As standard notion, PRF security is analysed by giving an attacker oracle access to$L_{k}(\cdot)$. Khovratovich's collision-based algorithm recovers$k$using$L_{k}(\cdot)$in time$\sqrt{p}$with constant memory. It is a major open problem whether this birthday-bound complexity can be beaten. We show a somewhat surprising wide-ranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting. More precisely, we present a small memory multiple-key attack on$m$Legendre keys$k_{1}, \ldots, k_{m}$in time$\sqrt{mp}$, i.e. with amortized cost$\sqrt{p/m}$per key. This multiple-key attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker's profit. Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public$p$only - and not on a key$k$. Namely, an attacker may compute e.g. in precomputation time$p^{\frac{2}{3}}$a hint of size$p^{\frac{1}{3}}$. On receiving access to$L_{k}(\cdot)$in an online phase, the attacker then uses the hint to recover the desired key$k$in time only$p^{\frac{1}{3}}$. Thus, the attacker's online complexity again beats the birthday-bound. In addition, our precomputation attack can also be combined with our multiple-key attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking$m$keys one may spend time$mp^{\frac{2}{3}}$in the precomputation phase for constructing a hint of size$m^{2}p^{\frac{1}{3}}$. In an online phase, one then finds all$m$keys in total time only$p^{\frac{1}{3}}$. Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy key-independent precomputation pays off.
Online privacy protection is highly associated with verification since it is a part of communication between users and servers. Because privacy has a probability of leaking out during the transmissions. With a new method without knowing and verifying the privacy, the verification method will have a revolution. The traditional verification pattern can be rewritten. This paper introduces the history of verification or secret protection and specifically discusses the theory of zero-knowledge proof. After pointing out that the disadvantage of zero-knowledge is time-consuming, this paper expends the theory with zk-SNARK which stands for âzero-knowledge succinct non-interactive argument of knowledgeâ. The part of zk-SNARK gives 2 implementations by linear algebra and polynomial. This paper lists 3 applications of zk-SNARK, which are z-cash, filecoin and loopring 3.0 in detail. In the end, this paper presents the advantage of zero-knowledge proof with the comparison of other currencies and discusses the risk of using zero-knowledge proof as contracts.
Cryptographic Implementations and Security
Cryptography and Data Security
Physical Unclonable Functions (PUFs) and Hardware Security
By using zkSNARKs to prove that values have specific dependent types, it is possible to provably assure compatibility and correctness without revealing sensitive information and extend our trusted computing base well beyond our own system. The approach we developed expands the scope of what non-interactive zero-knowledge proofs can capture to include properties about both the execution and correctness of programs.
Probabilistically Checkable Proofs (PCPs) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form âxâLâ by querying only a few proof bits. Zero-Knowledge PCPs (ZK-PCPs) enhance standard PCPs to additionally guarantee that the view of any (possibly malicious) verifier querying a bounded number of proof bits can be efficiently simulated up to a small statistical distance. The first ZK-PCP construction of Kilian, Petrank and Tardos (STOC 1997), and following constructions employing similar techniques, necessitate that the honest verifier makes several rounds of queries to the proof. This undesirable property, which is inherent to their technique, translates into increased round complexity in cryptographic applications of ZK-PCPs. We survey two recent ZK-PCP constructionsâdue to Ishai, Yang and Weiss (TCC 2016-A), and Hazay, Venkitasubramaniam and Weiss (ITC 2021)âin which the honest verifier makes a single round of queries to the proof. Both constructions use entirely different techniques compared to previous ZK-PCP constructions, by showing connections to the seemingly-unrelated notion of leakage resilience. These constructions are incomparable to previous ZK-PCP constructions: while on the one hand the honest verifier only makes a single round of queries to the proof, these ZK-PCPs either obtain a smaller (polynomial) ratio between the query complexity of the honest and malicious verifiers or obtain a weaker ZK guarantee in which the ZK simulator is not necessarily efficient.
We propose a new, unifying framework that yields an array of cryptographic primitives with certified deletion. These primitives enable a party in possession of a quantum ciphertext to generate a classical certificate that the encrypted plaintext has been information-theoretically deleted, and cannot be recovered even given unbounded computational resources. - For X \in {public-key, attribute-based, fully-homomorphic, witness, timed-release}, our compiler converts any (post-quantum) X encryption to X encryption with certified deletion. In addition, we compile statistically-binding commitments to statistically-binding commitments with certified everlasting hiding. As a corollary, we also obtain statistically-sound zero-knowledge proofs for QMA with certified everlasting zero-knowledge assuming statistically-binding commitments. - We also obtain a strong form of everlasting security for two-party and multi-party computation in the dishonest majority setting. While simultaneously achieving everlasting security against all parties in this setting is known to be impossible, we introduce everlasting security transfer (EST). This enables any one party (or a subset of parties) to dynamically and certifiably information-theoretically delete other participants' data after protocol execution. We construct general-purpose secure computation with EST assuming statistically-binding commitments, which can be based on one-way functions or pseudorandom quantum states. We obtain our results by developing a novel proof technique to argue that a bit b has been information-theoretically deleted from an adversary's view once they output a valid deletion certificate, despite having been previously information-theoretically determined by the ciphertext they held in their view. This technique may be of independent interest.
Dimitris Mouris, Charles Gouert, Nektarios Georgios Tsoutsos
As integrated circuit (IC) design and manufacturing have become highly globalized, hardware security risks become more prominent as malicious parties can exploit multiple stages of the supply chain for profit. Two potential targets in this chain are third-party intellectual property (3PIP) vendors and their customers. Untrusted parties can insert hardware Trojans into 3PIP circuit designs that can both alter device functionalities when triggered or create a side channel to leak sensitive information such as cryptographic keys. To mitigate this risk, the absence of Trojans in 3PIP designs should be verified before integration, imposing a major challenge for vendors who have to argue their IPs are safe to use, while also maintaining the privacy of their designs before ownership is transferred. To achieve this goal, in this work we employ modern cryptographic protocols for zero-knowledge proofs and enable 3PIP vendors prove an IP design is free of Trojan triggers without disclosing the corresponding netlist. Our approach uses a specialized circuit compiler that transforms arbitrary netlists into a zero-knowledge-friendly format, and introduces a versatile Trojan detection module that maintains the privacy of the actual netlist.
Physical Unclonable Functions (PUFs) and Hardware Security
Integrated Circuits and Semiconductor Failure Analysis
Zhimei Sui, Joseph K. Liu, Jiangshan Yu, Xianrui Qin
We propose MoNet, the first bi-directional payment channel network with unlimited lifetime for Monero. It is fully compatible with Monero without requiring any modification of the current Monero blockchain. MoNet preserves transaction fungibility, i.e., transactions over MoNet and Monero are indistinguishable, and guarantees anonymity of Monero and MoNet users by avoiding any potential privacy leakage introduced by the new payment channel network. We also propose a new crypto primitive, named Verifiable Consecutive One-way Function (VCOF). It allows one to generate a sequence of statement-witness pairs in a consecutive and verifiable way, and these statement-witness pairs are one-way, namely it is easy to compute a statement-witness pair by knowing any of the pre-generated pairs, but hard in an opposite flow. By using VCOF, a signer can produce a series of consecutive adaptor signatures CAS. We further propose the generic construction of consecutive adaptor signature as an important building block of MoNet. We develop a proof-of-concept implementation for MoNet, and our evaluation shows that MoNet can reach the same transaction throughput as Lightning Network, the payment channel network for Bitcoin. Moreover, we provide a security analysis of MoNet under the Universal Composable (UC) security framework.
The deployed vehicles in an Internet of Vehicles (IoV) can take intelligent decisions by means of exchanging the real-time traffic-related information between the vehicles and IoV infrastructures. This further reduces the probability of the traffic jams and accidents. However, the insecure (public) communication among the various entities in IoV makes various security threats and attacks that can be launched by passive/active adversaries present in the network. In view of this context, there is a need of an efficient cryptographic primitive which can produce single compact signature. A multi-signature scheme (MSS) empowers a collection of signers to conjointly sign a given message using a single compact signature that can be verified by any verifier. Herein, we put forward a new identity-based multivariate MSS, namelyMV-MSS, which is built on top of the intractability of multivariate-quadratic (MQ) problem. The fact is that multivariate public key cryptosystem provides fast, post-quantum safe and efficient primitives, which makes it the front runner candidate among the post-quantum cryptographic candidates.MV-MSSis proven to be secure in the existential unforgeability under chosen-message and chosen identity attack model if solving the MQ problem is NP-hard. We then incorporate the designedMV-MSSin IoV application where the leader (cluster head) selected from a group of vehicles in a dynamic cluster forms the multi-signatures on the messages securely received from its member vehicles. Later, the messages along with their multi-signatures are forwarded to the nearby road-side unit (RSU) of the cluster head, which are then forwarded to a cloud server in the blockchain center maintained by a Peer-to-Peer (P2P) cloud servers network. In this way, the messages and their signatures considered as transactions are put in blocks and added into a public blockchain with the help of consensus algorithm. A comparative study among the proposedMV-MSSand other existing schemes shows thatMV-MSSis efficient and secure as compared to other schemes. Finally, a blockchain implementation through simulation study has been performed to show its practical use in IoV application.
Abstract Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O (1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have âescaped the hegemonyâ of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing $$\text{ SNARG } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mspace/><mml:mtext>SNARG</mml:mtext><mml:mspace/></mml:mrow></mml:math> s, as well as resulting new efficiency features. Our contribution is threefold: (1) We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded âadversariesâ in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional âunstructuredâ PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as âsingle-ciphertext preprocessing SNARGs.â We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.
This paper presents an overview of the basic concepts of cryptography and encryption. The work aims at presenting the main concepts and concerns of encryption on a high-level of abstraction, allowing non-domain expert readers to navigate through these topics. Less traditional arguments are also shown, from the relevance of Key Management Services with its usage in Envelope Encryption, to Zero Knowledge proofs and their innovative applications. The crucial importance of securing communications between IoT devices and widely used algorithms to do so, are also discussed.
In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols have emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient cipher and hash function designs over $\mathbb{F}_p$ specifically for large odd primes $p$. In view of these efforts, in this work we build an \emph{algebraic framework} that allows the systematic exploration of viable and efficient design strategies for constructing symmetric-key (iterative) permutations over $\mathbb{F}_p$. We first identify iterative polynomial dynamical systems over finite fields as the central building block of almost all block cipher design strategies. We propose a generalized triangular polynomial dynamical system (GTDS), and based on the GTDS we provide a generic definition of an iterative (keyed) permutation over $\mathbb{F}_p^n$. Our GTDS-based generic definition is able to describe the three most well-known design strategies, namely SPNs, Feistel networks and Lai--Massey. Consequently, the block ciphers that are constructed following these design strategies can also be instantiated from our generic definition. Moreover, we find that the recently proposed \texttt{Griffin} design, which neither follows the Feistel nor the SPN design, can be described using the generic GTDS-based definition. We also show that a new generalized Lai--Massey construction can be instantiated from the GTDS-based definition. We further provide generic analysis of the GTDS including an upper bound on the differential uniformity and the correlation.
Dan Bogdanov, Joosep Jääger, Peeter Laud, Härmel Nestra ¡ 10 authors
We present ZK-SECREC, a domain-specific language for zero-knowledge (ZK) proofs. We focus on its type system, making the point that this is the most appropriate mechanism for tracking information flows in a statement that is meant to be proved using a zero-knowledge protocol. The appropriateness stems from the necessary distinctions between the two involved parties and between the computations made locally or on top of the protocol. The appropriateness also stems from how the types match with the major steps of typical ZK protocols, including the generation of Common Reference Strings. We compare the type system of ZK-SECREC with those of the previously proposed languages for ZK proofs and privacy-preserving computations, and show how ZK-SECREC handles certain aspects better.
Data security plays a major role in computer network. Because it helps to transmit data in secure way over the Internet. So we need to use strong security method for secure data transaction. Cryptography is a security tool which helps to transmit information from one place to another place over computer network. Cryptography follows encryption and decryption methods for data transmission. Cryptographic technique is completely based on key generation because it needs keys to transmit data between users. However cryptography works well in secure data transmission but it needs keys to provide security for data. In cryptography generation of keys taking more time than transmission of data. So in this paper we discuss about Zero-Knowledge Proof (ZKP) which is also based on cryptographic technique. ZKP is also useful in secure data transmission without sharing key values between users. This paper tells about overview of ZKP and how it is useful in data transmission.
Several challenges have been announced on arithmetization-oriented hash functions, with bounties funded by the Ethereum Foundation. In this note, we report on our work to solve several of these challenges, on Feistel-MiMC, Rescue Prime and Poseidon. Our results are obtained by writing the challenges as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma).