Lattice-based non-interactive zero-knowledge proof has been widely used in one-way communication and can be effectively applied to resist quantum attacks. However, lattice-based non-interactive zero-knowledge proof schemes have long faced and paid more attention to some efficiency issues, such as proof size and verification time. In this paper, we propose the non-interactive zero-knowledge proof schemes from RLWE-based key exchange by making use of the Hash function and public-key encryption. We then show how to apply the proposed schemes to achieve the fixed proof size and rapid public verification. Compared with previous approaches, our schemes can realize better effectiveness in proof size and verification time. In addition, the proposed schemes are secure from completeness, soundness, and zero-knowledge.
Diego F. Aranha, Sebastian Berndt, Thomas Eisenbarth, Okan Seker · 7 authors
We study masking countermeasures for side-channel attacks against signature schemes constructed from the MPC-in-the-head paradigm, specifically when the MPC protocol uses preprocessing. This class of signature schemes includes Picnic, an alternate candidate in the third round of the NIST post-quantum standardization project. The only previously known approach to masking MPC-in-the-head signatures suffers from interoperability issues and increased signature sizes. Further, we present a new attack to demonstrate that known countermeasures are not sufficient when the MPC protocol uses a preprocessing phase, as in Picnic3.We overcome these challenges by showing how to mask the underlying zero-knowledge proof system due to Katz–Kolesnikov–Wang (CCS 2018) for any masking order, and by formally proving that our approach meets the standard security notions of non-interference for masking countermeasures. As a case study, we apply our masking technique to Picnic. We then implement different masked versions of Picnic signing providing first order protection for the ARM Cortex M4 platform, and quantify the overhead of these different masking approaches. We carefully analyze the side-channel risk of hashing operations, and give optimizations that reduce the CPU cost of protecting hashing in Picnic by a factor of five. The performance penalties of the masking countermeasures ranged from 1.8 to 5.5, depending on the degree of masking applied to hash function invocations.
Open access
Cryptographic Implementations and Security
Chaos-based Image/Signal Encryption
Physical Unclonable Functions (PUFs) and Hardware Security
Ulrich Haböck, Alberto Garoffolo, Daniele Di Benedetto
This document describes Darlin, a succinct zero-knowledge argument of knowledge based on the Marlin SNARK (Chiesa et al., Eurocrypt 2020) and the `dlog' polynomial commitment scheme from Bootle et al. EUROCRYPT 2016. Darlin addresses recursive proofs by integrating the amortization technique from Halo (IACR eprint 2019/099) for the non-succinct parts of the dlog verifier, and we adapt their strategy for bivariate circuit encoding polynomials to aggregate Marlin's inner sumchecks across the nodes the recursive scheme. We estimate the performance impact of inner sumcheck aggregation by about 30% in a tree-like scheme of in-degree 2, and beyond when applied to linear recursion.
Cherlina Helena Purnamasari Panjaitan, Lisda Juliana Pangaribuan
Protocol Zero Knowledge Proof is one of the protocols in Cryptography that has a fairly good level of security, because it applies the concept of "Truly Zero Knowledge Proof" which is not leaking any information. This protocol is used in the Fiat Shamir, Guillou Quisquater and Schnorr Feige Algorithms, all of which are Cryptographic Algorithms using private keys and public keys. In the Public key, all three of these Algorithms use a random number generator at the values p and q to get the public key. In this study, the author will generate a public key generation test using CPRNG (Cryptographically-secure Pseudo-Random Number Generator) with the Blum Blum Shub algorithm. The test will be conducted on the Fiat Feige Algorithm, the formation of the key will use the Blum Blum Shub Algorithm, but the Identification Protocol still uses the Fiat Shamir Feige Algorithm. The results of this study show the Feige Fiat Algorithm with the Blum Blum Shub Algorithm as the key builder successfully identifies the pattern sent by the signer.
Leakage of private information has become a threat to the security of cryptography systems. It has become a common security requirement that a cryptography scheme should withstand various leakage attacks. The non-interactive zero-knowledge (NIZK) argument system, one-time lossy filter (OT-LF) and one-time signature were widely used to create the generic constructions of leakage-resilient identity-based encryption (IBE) scheme with chosen-ciphertext attack (CCA) security. However, the computational efficiency of the corresponding generic construction is low because the underlying cryptographic tool is low. Thus, to solve the above problem, a new cryptographic primitive, called identity-based hash proof system with two encapsulated-key (T-IB-HPS), is proposed. The new generic constructions of leakage resilient IBE scheme with CCA security is created from the T-IB-HPS and message authentication code (MAC), and the security of the above proposed scheme is proved from the security of the underlying cryptographic tool. To further show the practicability, an instantiation of T-IB-HPS is constructed, and the formal security proof of the above instantiation is shown based on the decisional bilinear Diffie-Hellman (DBDH) assumption. Compared with the previous generic constructions of leakage resilient IBE scheme with CCA security, since the underlying cryptographic tools with low computational efficiency are not used, our generic construction has high computational efficiency.
Abstract A nominative signature (NS) is a cryptographic primitive where two parties collude to produce a signature. It is a user certification system and has applications in a variety of sectors where nominee cannot trust heavily on the nominator to validate the nominee's certificate and only targeted entities are allowed to verify the signature on sensitive data. A new construction for NS from standard assumptions on lattice is provided. The authors’ construction relies on collision‐resistant preimage sampleable function and symmetric key primitives like collision‐resistant pseudorandom function and zero knowledge proof system ZKB ++ for Boolean circuits. The authors provide detailed security analysis and show that their construction achieves security under unforgeability , invisibility , impersonation , and non‐repudiation in the existing model. Furthermore, our construction exhibits non‐transferability . The security under non‐repudiation is achieved in the quantum random oracle model using Unruh transform to ZKB ++ .
Despite a considerable progress in verification of random and control logic, advances in formal verification of arithmetic designs have been lagging. This can be attributed mostly to the difficulty of efficient modeling of arithmetic circuits and data paths without resorting to computationally expensive Boolean methods, such as Binary Decision Diagrams (BDDs) and Boolean Satisfiability (SAT) that require ``bit blasting'', i.e., flattening the design to a bit-level netlist. Similarly, approaches that rely on computer algebra and Satisfiability Modulo Theories (SMT) methods are either too abstract to handle the bit-level complexity of arithmetic designs or require solving computationally expensive decision or satisfiability problems. On the other hand, theorem provers, popular solvers used in industry, require a significant human interaction and intimate knowledge of the design to guide the proof process. The work proposed in this thesis aims at overcoming the limitations of verifying arithmetic circuits, especially at the post-synthesis, implementation phase. It addresses the verification problem at an algebraic level, treating an arithmetic circuit and its specification as an algebraic system. Specifically, verification approach employed in this work is based on the algebraic rewriting method. In this method, the circuit is modeled in the algebraic domain, where both the circuit specification and its gate-level implementation are represented as polynomials. This work formally analyzes the algebraic approach and compares it with the established computer algebra methods based on Grobner basis reduction. It shows that algebraic rewriting is more effective than the Grobner basis reduction from the computational point of view. This thesis addresses two classes of arithmetic circuits that could not directly benefit from this type of functional verification, since performing algebraic rewriting of such circuits encounters a serious memory issue. The circuits that fall in the first category are approximate arithmetic circuits, such as truncated integer multipliers. Different truncation schemes are considered, including bit deletion, bit truncation, and rounding. The proposed verification method is based on reconstructing the truncated multiplier to a complete, exact multiplier; it is then followed by algebraic rewriting to prove that it indeed implements multiplication over the required range of bits. The reconstruction of the multiplier helps avoid the memory overload issue as it creates a "clean" multiplier with a well defined specification polynomial. The other class of circuits that suffer from memory overload during algebraic rewriting are circuits subjected to some arithmetic constraints. An example of such circuits is a divider, where the divisor value cannot be zero. The other example can be found in the basic blocks of the constant divider, where the value of carry into each block must be less than the divisor value. In general, such constraints will be modeled using the concept of vanishing monomials. A case-splitting method is proposed along with the modified algebraic rewriting to resolve the memory issue. The proposed verification method not only can prove that the circuit performs a correct function under the desired (valid) conditions, but also will test all the undesired (invalid) cases. This work also addresses logic debugging of combinational arithmetic circuits over field F<sub>2<sup>k</sup></sub> , including Galois field multipliers. Galois Field (GF) arithmetic has numerous applications in digital communication, cryptography and security engineering, and formal verification of such circuits is of prime importance. In addition to functional verification of GF multipliers, this work proposes a novel and effective method for identifying and correcting bugs in such circuits, commonly referred to as debugging. In this work we propose a novel approach to debugging of GF arithmetic circuits based on forward rewriting, which enables functional verification and debugging at the same time. This technique can handle multiple bugs, does not suffer from the polynomial size explosion encountered by other methods, and allows one to identify and automatically correct bugs in GF circuits. The techniques and algorithms proposed in this dissertation have been implemented in several computer programs, some stand-alone, and some integrated with a popular synthesis and verification tool, ABC. The experimental results for verification and debugging are compared with the state-of-the-art SAT, SMT, and other computer algebraic solvers.
LibSWIFFT is an open-source, production-ready C/C++ library providing SWIFFT, one of the fastest available secure hash functions that is also collision-resistant. SWIFFT also facilitates post-quantum digital signature schemes and zero-knowledge proofs of knowledge of a preimage (ZKPoKP). LibSWIFFT is optimized for short blocks of input and runs at a rate of less than 5 cycles/byte single-threaded on a modern commodity computer with AVX2. Other software providing SWIFFT, which are not claiming production-readiness as LibSWIFFT is, are the original implementation by the authors of SWIFFT (Micciancio, 2016) and the SWIFFT 8-bit (Karati & Safavi-Naini, 2018b) and 16-bit (Karati & Safavi-Naini, 2018a) AVX2 implementations for the multi-signature scheme K2SN-MSS (Karati & Safavi-Naini, 2019).
In addition to their usefulness in proving one’s identity electronically, identification protocols based on zero-knowledge proofs allow designing secure cryptographic signature schemes by means of the Fiat–Shamir transform or other similar constructs. This approach has been followed by many cryptographers during the NIST (National Institute of Standards and Technology) standardization process for quantum-resistant signature schemes. NIST candidates include solutions in different settings, such as lattices and multivariate and multiparty computation. While error-correcting codes may also be used, they do not provide very practical parameters, with a few exceptions. In this manuscript, we explored the possibility of using the error-correcting codes proposed by Stakhov in 2006 to design an identification protocol based on zero-knowledge proofs. We showed that this type of code offers a valid alternative in the error-correcting code setting to build such protocols and, consequently, quantum-resistant signature schemes.
Çalışmamızın konusu kripto paralara el konulması ve kripto paraların müsadere edilmesi oluşturmaktadır. Kripto paraların müsadere edilmesi oluşturmaktadır. Kripto paralar merkezi bir otorite tarafından denetlenmediğinden şüpheli faaliyetlerin tespiti, kullanıcıların kimliğinin belirlenmesi ve işlem kayıtlarının elde edilmesi adli ve idari makamların işlerini zorlaştırırken, suç teşkil eden fiilleri işleyen kişilere bu ödeme şekli ve transfer metodu cazip gelmektedir.
Karim Baghery, Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Nigel P. Smart · 5 authors
This paper introduces M-Circuits, a program representation which generalizes arithmetic and binary circuits. This new representation is motivated by the way modern multi-party computation (MPC) systems based on linear secret sharing schemes actually operate. We then show how this representation also allows one to construct zero knowledge proof (ZKP) systems based on the MPC-in-the-head paradigm. The use of the M-Circuit program abstraction then allows for a number of program-specific optimizations to be applied generically. It also allows to separate complexity and security optimizations for program compilation from those for application protocols (MPC or ZKP).
Javier Herranz, Ramiro Pinilla, Manuel Sánchez-Raya
In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on N, the number of shuffled ciphertexts.
Zero-Knowledge Proofs (ZKPs) are cryptographic primitives allowing a party to prove to another party that the former knows some information while keeping it secret. Such a premise can lead to the development of numerous privacy-preserving protocols in different scenarios, like proving knowledge of some credentials to a server without leaking the identity of the user. Even when the applications of ZKPs were endless, they were not exploited in the wild for a couple of decades due to the fact that computing and verifying proofs was too computationally expensive. However, the advent of efficient schemes (in particular, zk-SNARKs) made this primitive to break into the scene in fields like cryptocurrencies, smart-contracts, and more recently, self-sovereign scenarios: private-by-design identity management and authentication. Nevertheless, its adoption in environments like the Internet of Things (IoT) remains unexplored due to the computational limitations of embedded systems. In this paper, we introduce ZPiE, a C library intended to create ZKP applications to be executed in embedded systems. Its main feature is portability: it can be compiled, executed, and used out-of-the-box in a wide variety of devices. Moreover, our proof-of-concept has been proved to work smoothly in different devices with limited resources, which can execute state-of-the-art ZKP authentication protocols.
Carsten Baum, Alex J. Malozemoff, Marc B. Rosen, Peter Schöll
Zero knowledge proofs are an important building block in many cryptographic applications. Unfortunately, when the proof statements become very large, existing zero-knowledge proof systems easily reach their limits: either the computational overhead, the memory footprint, or the required bandwidth exceed levels that would be tolerable in practice. We present an interactive zero-knowledge proof system for boolean and arithmetic circuits, called $$\mathsf {Mac'n'Cheese}$$ , with a focus on supporting large circuits. Our work follows the commit-and-prove paradigm instantiated using information-theoretic MACs based on vector oblivious linear evaluation to achieve high efficiency. We additionally show how to optimize disjunctions, with a general OR transformation for proving the disjunction of m statements that has communication complexity proportional to the longest statement (plus an additive term logarithmic in m). These disjunctions can further be nested, allowing efficient proofs about complex statements with many levels of disjunctions. We also show how to make $$\mathsf {Mac'n'Cheese}$$ non-interactive (after a preprocessing phase) using the Fiat-Shamir transform, and with only a small degradation in soundness. We have implemented the online phase of $$\mathsf {Mac'n'Cheese}$$ and achieve a runtime of 144 ns per AND gate and 1.5 $$\upmu $$ s per multiplication gate in $$\mathbb {F} _{2^{61} - 1} $$ when run over a network with a 95 ms latency and a bandwidth of 31.5 Mbps. In addition, we show that the disjunction optimization improves communication as expected: when proving a boolean circuit with eight branches and each branch containing roughly 1 billion multiplications, $$\mathsf {Mac'n'Cheese}$$ requires only 75 more bytes to communicate than in the single branch case.
A cryptographic method of digitally securing cryptocurrency wallet seed phrase through Blind Key Encryption is discussed wherein two blind keys random in nature are generated and used to produce two ciphertexts. The mathematical algorithm used in blind key encryption is described in detail and also an explanation is provided as to how the encryption defeats hackers even after they could successfully compromise a ciphertext of the seed phrase along with its decryption key. Different scenarios of storing the ciphertexts are documented.
Pouriya Alikhani, Nicolas Brunner, Claude Crépeau, Sébastien Designolle · 8 authors
Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank's security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances ($\geqslant$400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain applications such as cryptocurrencies or smart contracts.
Open access
3 source records
Cryptography and Data Security
Physical Unclonable Functions (PUFs) and Hardware Security
Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK. We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set, and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access. Critically, we propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2łog n$ OTs per access, and (3) an efficient read-write memory, øurram, which uses $\frac1 2 łog^2 n$ OTs per access. øurram beats linear scan for RAM of size $>3$ elements! Prior ZK systems used generic ORAM costing orders of magnitude more. We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS'13]. Put together, our system is concretely efficient: for a processor instantiated with $512$KB of main memory, each processor cycle costs $24$KB of communication. We implemented our approach in \textttC++. On a 1Gbps LAN our implementation realizes a $2.1$KHz processor.
J Dharani, K Sundarakantham, Kunwar Singh, S. Mercy Shalinie
Blockchain technology has gained its attention from its application in bitcoin which circumvented the problem of double spending that existed in the prior digital currencies, through validation. Particularly permissioned blockchain framework became popular with organizations forming consortium that allowed only authorized entities to participate in the network. Hyperledger Fabric, a popular distributed ledger technology hosted by Linux Foundation has remarkable features because of the fact that it is open source. It stands out from other frameworks as it focuses on the privacy-preserving requirements of the enterprises. Apart from only allowing authenticated organizations to participate in the network it implements channels that allows a subset of organizations to communicate concealing the existence of such a channel to other members. Optionally fabric also provides anonymity and unlinkability of the participating clients through a cryptographic protocol suite called Idemix that operates based on zero-knowledge proofs. Fabric follows the execute-order-validate transaction flow as opposed to order-execute flow that had certain limitations in other platforms. For executing the transactions submitted by the clients, fabric has designated endorsing peers which holds the smart contract - programmable business logic. Endorsing peers or endorsers execute the transactions and attach their signatures to the results for validation purpose. But revealing the endorser identities may be a problem when there is conflict of interest among the enterprises. Hence to have an unbiased flow of work it is important to conceal the endorser identity. According to [1] anonymization of endorsing peers is still a open problem in fabric community. We propose a solution to this problem which uses linkable threshold ring signatures that conceals the identity of endorsers. Ring signatures are known for preserving the privacy of the signer in a group. Threshold ring signature allows t-out-of-n signers to collaborate on the signing procedure. Employing threshold ring signature implicitly addresses one more problem stated in [10] where the verifiers need to manually count the valid ring signature that increases the verification time. This process of separately verifying each of the signatures and checking if the number of signatures is more than the threshold value is replaced by having just one threshold signature collaboratively signed by the required endorsers.
While traditional symmetric algorithms like AES and SHA-3 are optimized for efficient hardware and software implementations, a range of emerging applications using advanced cryptographic protocols such as multi-party computation and zero knowledge proofs require optimization with respect to a different metric: arithmetic complexity. In this paper we study the design of secure cryptographic algorithms optimized to minimize this metric. We begin by identifying the differences in the design space between such arithmetization-oriented ciphers and traditional ones, with particular emphasis on the available tools, efficiency metrics, and relevant cryptanalysis. This discussion highlights a crucial point—the considerations for designing arithmetization-oriented ciphers are oftentimes different from the considerations arising in the design of software- and hardware-oriented ciphers. The natural next step is to identify sound principles to securely navigate this new terrain, and to materialize these principles into concrete designs. To this end, we present the Marvellous design strategy which provides a generic way to easily instantiate secure and efficient algorithms for this emerging domain. We then show two examples for families following this approach. These families — Vision and Rescue — are benchmarked with respect to three use cases: the ZK-STARK proof system, proof systems based on Rank-One Constraint Satisfaction (R1CS), and Multi-Party Computation (MPC). These benchmarks show that our algorithms achieve a highly compact algebraic description, and thus benefit the advanced cryptographic protocols that employ them.
Ethan Heilman, Neha Narula, Garrett Tanzer, James Peter Thomas. Lovejoy · 7 authors
We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA’s cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EUCMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).
How someone can get health insurance without sharing his health infor-mation? How you can get a loan without disclosing your credit score? There is a method to certify certain attributes of various data, either this is health metrics or finance information, without revealing the data itself or any other kind of personal data. This method is known as “zero-knowledge proofs”. Zero-Knowledge techniques are mathematical methods used to verify things without sharing or revealing underlying data. Zero-Knowledge protocols have vast applications from simple identity schemes and blockchains to de-fense research programs and nuclear arms control. In this article we present the basic principles behind ZKP technology, possible applications and the threats and vulnerabilities that it is subject to and we review proposed securi-ty solutions.
Tato diplomová práce se zabývá technologii blockchain se zaměřením na konsenzus protokoly, zvláště protokoly typu proof-of-stake. V této práci naleznete popis těchto protokolů následovaný popisem konsenzu v technologii blockchain. Prvotní kapitoly detailněji popisují a porovnávají jednotlivé proof-of-stake protokoly na základě teoretických znalostí. Druhá část práce se zaobírá návrhem a implementací testbedu, který je následně použitý pro praktické porovnání proof-of-stake protokolů. V závěrečné částí práce je diskutováno nad zjištěnými výsledky pozorováním testbedu a zjištěnými vlatnostmi protokolů. Na tomto základě práce ve svém konci naznačuje další směřování consesus protokolů, ba jejich případné zlepšení, a zvláště proof-of-stake typu protokolů.