Privacy and security in the current modern, digital communication and data transfer-oriented world has become imperative. Most commonly used encryption methods often involve exposing sensitive information, which might be an open gate for potential vulnerabilities. This paper aims to explore the topic of applying ZKPs in cybersecurity in a comprehensive manner. For this purpose, Proposed work will provide an exhaustive description of the basic concepts of Zero-Knowledge Proofs , which refer to both the interactive and non-interactive forms of the product. Additionally, the study will focus on presenting various cryptographic protocols and algorithms utilizing Zero-Knowledge Proofs , such as zk-SNARKs and zk-STARKs . In addition to theoretical studies, Proposed work analyze the practical implementation details of Zero-Knowledge Proofs implementations , cryptographic libraries, programming languages, and frameworks commonly used to create ZKP-based applications . Zero-knowledge proofs enable groundbreaking approaches to address cybersecurity problems with an emphasis on user privacy and data confidentiality. On average, cryptographic operations experienced delays of approximately 10 milliseconds which was not intrusive for real-time systems. The system’s throughout remained at a steady average of 100 Mbps all times, so it performed well at processing data despite cryptographic overhead. The packet delivery ratio was constantly high at 98%, implying that most data packets were delivered consistently even over encrypted communication paths.
Conventionally, organizations have used Privileged Access Management (PAM) techniques to secure, control, and monitor access to their critical information and resources. The PAM concepts have envisioned designing protocols that help protect user accounts that are deemed to have access to sensitive data ?the most valuable asset of a business. While in the past these techniques have proven vital to data protection and security, the onset of increasingly sophisticated technologies and more determined malicious actors warrants a change of data control and privacy strategies. It becomes impossible to secure a system to achieve 100 percent efficiency. Any system that is attached to the internet is vulnerable to cyberattacks. Hackers have numerous ways to compromise systems if traditional boundary security mechanisms are deployed. Detecting an intrusion in such a setup becomes increasingly challenging if an attacker successfully breaches that boundary layer of defense. Since traditional authentication and authorization might not be reliable in network systems, the zero - knowledge proof model comes in handy. Adding the zero - knowledge proof to the PAM to authenticate users or members and disclose or anonymize them through decentralized identifiers helps in solving the identification and privacy protection problem. We propose a PAM and zero - knowledge proof - inspired approach to address the authentication, data security, and privacy concerns. A zero - knowledge proof is a method that allows the prover to prove to the verifier that they know a certain information without disclosing it.
With the emergence of Web3, decentralized network protocol technologies have been vigorously developed. As a pioneer for decentralized real-time communication systems, Matrix is an open standard based on a federation specification protocol. Anyone can set up a self-hosted homeserver to participate in the global Matrix network and communicate with others in chat rooms. In this paper, we conduct the first in-depth measurement and exploratory research on Matrix’s ecosystem and security. We designed and implemented several investigation techniques to empirically delve into Matrix federation from various aspects (homeservers, rooms, and users). In the end, we identified a number of interesting findings and potential vulnerabilities, including anti-decentralization phenomena, cybersecurity threats in homeservers, and the confidentiality of encrypted rooms being compromised.
Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers, essentially using x ↦ x3 as an S-box.In this paper, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds, for any linear layer, provided that the round-constants are well chosen.As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet.Well-known security arguments, in particular based on the wide-trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present two new primitives (the tweakable block cipher Snare and the permutation-based hash function Stir) that are built using state-of-the-art security arguments, but which are actually deeply flawed. Indeed, the key schedule of Snare ensures the presence of a subspace chain that significantly simplifies an algebraic attack against it, and the round constants of Stir force the presence of a subspace chain aligned with the rate and capacity of the permutation. This in turns implies the existence of many easy-to-find solutions to the so-called CICO problem.
Open access
Cryptographic Implementations and Security
Physical Unclonable Functions (PUFs) and Hardware Security
Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier
Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear component due to its efficiency in these applications as well as its strong resistance against the differential and linear cryptanalysis. In this paper, we target the MPC-friendly ciphers AIM and RAIN used for the post-quantum signature schemes AIMer (CCS 2023 and NIST PQC Round 1 Additional Signatures) and Rainier (CCS 2022), respectively. Specifically, we can find equivalent representations of 2-round RAIN and full-round AIM, respectively, which make them vulnerable to either the polynomial method, or the crossbred algorithm, or the fast exhaustive search attack. Consequently, we can break 2-round RAIN with the 128/192/256-bit key in only 2111/2170/2225 bit operations. For full-round AIM with the 128/192/256-bit key, we could break them in 2136.2/2200.7/2265 bit operations, which are equivalent to about 2115/2178/2241 calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.
Samuel Dittmer, Karim Eldefrawy, Stéphane Graham-Lengrand, Steve Lu · 6 authors
Despite the notable advances in the development of high-assurance, verified implementations of cryptographic protocols, such implementations typically face significant performance overheads, particularly due to the penalties induced by formal verification and automated extraction of executable code. In this paper, we address some core performance challenges facing computer-aided cryptography by presenting a formal treatment for accelerating such verified implementations based on multiple generic optimizations covering parallelism and memory access. We illustrate our techniques for addressing such performance bottlenecks using the Line-Point Zero-Knowledge (LPZK) protocol as a case study. Our starting point is a new verified implementation of LPZK that we formalize and synthesize using EasyCrypt; our first implementation is developed to reduce the proof effort and without considering the performance of the extracted executable code. We then show how such (automatically) extracted code can be optimized in three different ways to obtain a 3000x speedup and thus matching the performance of the manual implementation of LPZK of lpzkv2.[13] We obtain such performance gains by first modifying the algorithmic specifications, then by adopting a provably secure parallel execution model, and finally by optimizing the memory access structures. All optimizations are first formally verified inside EasyCrypt, and then executable code is automatically synthesized from each step of the formalization. For each optimization, we analyze performance gains resulting from it and also address challenges facing the computer-aided security proofs thereof, and challenges facing automated synthesis of executable code with such an optimization.
Yuyang Sang, Ning Luo, Samuel Judson, Ben Chaimberg · 8 authors
A zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Ou uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification. We contribute: (1) A front-end language where users can write proof statements as imperative programs in a familiar syntax; (2) A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and (3) A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.
The paper proposes a cryptographic protocol two-factor authentication with the zero-knowledge over the extended field GF(2m) on elliptic curves using biometric data and private key of the user. The implementation of a cryptographic protocol with zero-knowledge proof based on elliptic curves allows significantly reducing the size of protocol parameters and increasing the cryptographic strength (computational complexity of the breaking). The cryptographic protocol was modeled in the High-Level Protocol Specification Language, the model validation and protocol verification was performed using the Security Protocol Animator tool for Automated Validation of Internet Security Protocols and Applications. The software verification of the cryptographic protocol was performed using the software modules On the Fly Model Checker and Constraint Logic based Attack Searcher.
A pivotal feature of IPv6 is its plug-and-play capability that enables hosts to integrate seamlessly into networks. In the absence of a trusted authority or security infrastructure, the challenge for hosts is generating their own address and verifying ownership of others. Cryptographically Generated Addresses (CGA) solves this problem by binding IPv6 addresses to hosts' public keys to prove address ownership. CGA generation involves solving a cryptographic puzzle similar to Bitcoin's Proof-of-Work (PoW) to deter address spoofing. Unfortunately, solving the puzzle often causes undesirable address generation delays, which has hindered the adoption of CGA. In this paper, we present Bitcoin-Certified Addresses (BCA), a new technique to bind IPv6 addresses to hosts' public keys. BCA reduces the computational cost of generating addresses by using the PoW computed by Bitcoin nodes to secure the binding. Compared to CGA, BCA provides better protection against spoofing attacks and improves the privacy of hosts. Due to the decentralized nature of the Bitcoin network, BCA avoids reliance on a trusted authority, similar to CGA. BCA shows how the PoW computed by Bitcoin nodes can be reused, which saves costs for hosts and makes Bitcoin mining more efficient.
The integration of cryptographic algorithms like Advanced Encryption Standard (AES) and Elliptic Curve Cryptography (ECC) is pivotal in bolstering the core attributes of blockchain technology, especially in achieving decentralization, tamper resistance, and anonymization within the realm of medical applications. Despite their widespread utilization, the conventional AES and ECC face significant hurdles in security and efficiency when dealing with expansive medical data, posing a challenge to the effective preservation of patient privacy. In light of these challenges, this study introduces HAE (hybrid AES and ECC), an innovative hybrid cryptographic algorithm that ingeniously amalgamates the robustness of AES with the agility of ECC. HAE is designed to symmetrically encrypt original data with AES while employing ECC for the asymmetric encryption of the initial AES key. This strategy not only alleviates the complexities associated with AES key management but also enhances the algorithm’s security without compromising its efficiency. We provide an in-depth exposition of HAE’s deployment within a framework tailored for medical scenarios, offering empirical insights into its enhanced performance metrics. Our experimental outcomes underscore HAE’s exemplary security, time efficiency, and optimized resource consumption, affirming its potential as a breakthrough advancement for augmenting blockchain applications in the medical sector, heralding a new era of enhanced data security and privacy within this critical domain.
The utilization of the broadband subliminal channel allows a sender to covertly transmit a message to a receiver through digital signatures. This method requires the sender to relinquish the signing key to the receiver. As a result, the receiver has the ability to employ the signing key to sign any data on behalf of the sender without the sender’s knowledge or consent. Meanwhile, difficulties may arise if the sender is unwilling to disclose the signing key to the receiver. In this paper, we propose a broadband subliminal channel that can be used in digital signature schemes (e.g., DSA, ECDSA, ElGamal, and Schnorr) without disclosing the signing key to the receiver. As it writes the message on a digital signature, we call it WMoS. We first implement WMoS in the Elliptic Curve Digital Signature Algorithm (ECDSA). We then provide the security proof to show that signatures generated in WMoS have the same security level as standard ECDSA signatures. Moreover, we discuss the variants of WMoS in ECDSA and use them to construct applications. Furthermore, we use the implementation of WMoS to generate a signature for an Ethereum transaction to demonstrate its feasibility. We also evaluate the efficiency of WMoS in ECDSA, and the results show that WMoS in ECDSA can generate a signature as efficiently as the standard ECDSA.
Deebakkarthi Chinnasame Rani, Sai Ganesh Janakiraman, K. S. Chandra, Elambharathi Padmavathi Thangavel · 7 authors
Presented herein is a novel algorithm for multi-round, zero-knowledge proof (ZKP), devised specifically for authenticating factorisation proofs within a variety of cryptographic applications. This advanced algorithm, while maintaining computational complexity within acceptable bounds, offers a secure and proficient solution. The functionality of the algorithm is marked by multiple rounds of interaction between the Prover and Verifier. Initially, the Prover generates a random value and calculates a commitment. Subsequently, the Verifier issues a random challenge, eliciting a computed response from the Prover. To validate the proof, the Verifier verifies the equality of the commitment and the computed response. Efficaciousness of the proposed multi-round ZKP algorithm is demonstrated across diverse input sizes and parameters. Results indicate a success rate exceeding 90% on average, showcasing the robustness of the method. The recurring interaction between the Verifier and Prover enhances the Prover's authentication, thereby improving the algorithm’s reliability. Implementation of the algorithm, achievable through standard cryptographic tools and protocols, can fortify the security of multiple cryptographic applications. A significant application can be found in Digital Identity Management Systems (DIMS). Currently, these systems are vulnerable to a myriad of threats, including identity spoofing, data breaches, and internal security risks. The application of the ZKP algorithm can simultaneously augment security and withhold sensitive information, potentially transforming the DIMS security landscape. Future research may focus on improving the efficiency and scalability of the multi-round ZKP algorithm. There also remains a vast potential for exploring additional applications of this technique within various cryptographic domains.
Mustafa Ibrahim Alnajjar, Mehmet Sabır Kiraz, Ali H. Al‐Bayatti, Süleyman Kardaş
A distributed ledger is a shared and synchronized database across multiple designated nodes, often referred to as miners, validators, or peers. These nodes record, distribute, and access data to ensure security and transparency. However, these nodes can be compromised and manipulated by selectively choosing which user transactions to include, exclude, or reorder, thereby gaining an unfair advantage. This is known as a miner/maximal extractable value (MEV) attack. Existing solutions can be classified into various categories, such as MEV auction platforms and time-based ordering properties, which rely on private transaction Mempools. In this paper, we first identify some architectural weaknesses inherent in the latest proposals that divide the block creation and execution roles into separate functions: block builders and block executors. The existing schemes mainly suffer from the verifiability of the decryption process, where a corrupted builder or executor can simply deny the inclusion of specific targeted transactions by exploiting the fact that all transactions are in plain format. To address this, we propose an enhanced version that incorporates a verifiable decryption process. On a very high level, within our proposal, whenever an Executor or a Builder performs a decryption, the decrypted values must be broadcasted. This enables any entity in the network to publicly verify whether the decryption was executed correctly, thus preventing malicious behavior by either party from going undetected. We also define a new adversary model for MEV and conduct a comprehensive security analysis of our protocol against all kinds of potential adversaries related to MEV. Finally, we present the performance analysis of the proposed solution.
Open access
2 source records
Physical Unclonable Functions (PUFs) and Hardware Security
In cryptography, Zero-knowledge proof (ZKP) is a protocol that enables a party to demonstrate the accuracy of a given statement without revealing any additional information beyond the validity of the statement itself. This protocol ensures both the confidentiality and integrity of the computation, and has therefore become widely utilized in various industries for privacy-preserving, including online age verification and electronic voting. The most computationally demanding component of most Zero Knowledge Proof systems is the Multi-Scalar Multiplication (MSM) module. To address this issue and achieve low power and cost efficient MSM for different applications, a novel heterogeneous MSM architecture, ZodiacMSM, is developed. The architecture utilizes the Pippenger algorithm and a multi-chip design with memory access partitioning, which enables scalable performance for polynomials of various sizes in different ZKP applications. The performance of this architecture increases almost linearly with the number of nodes. ZodiacMSM supports multiple elliptic curves through reconfigurable fully-pipelined point-addition to achieve lower latency and minimize scheduler effort. When evaluated in 28nm, ZodiacMSM is able to achieve 2.3x speedup on MSM with single node and 32x speedup on 16 nodes compared to previous peer-reviewed state-of-the-art ASIC results [8].
With the increasing interest for advanced protocols for Multi Party Computation, Fully-Homomorphic Encryption or Zero Knowledge proofs, a need for cryptographic algorithms with new constraints has emerged. These algorithms, called Arithmetization-Oriented ciphers, seek to minimize the number of field multiplications in large finite fields F2n or Fp. Among them, Ciminion is an encryption algorithm proposed by Dobraunig et al. in Eurocrypt 2021. In this paper, we show a new univariate modelization on a variant of Ciminion proposed by the designers. This instance restricts the attacker to at most 2 s/2 data, where s is the security level. Because the designers chose to reduce the number of rounds in that specific attacker model, we are able to attack the cipher for large security levels. We also propose some slight modifications of Ciminion that would overcome this vulnerability.
The rise of modern cryptographic protocols such as Zero-Knowledge proofs and secure Multi-party Computation has led to an increased demand for a new class of symmetric primitives. Unlike traditional platforms such as servers, microcontrollers, and desktop computers, these primitives are designed to be implemented in arithmetical circuits. In terms of security evaluation, arithmetization-oriented primitives are more complex compared to traditional symmetric cryptographic primitives. The arithmetization-oriented permutation Grendel employs the Legendre Symbol to increase the growth of algebraic degrees in its nonlinear layer. To analyze the security of Grendel thoroughly, it is crucial to investigate its resilience against algebraic attacks. This paper presents a preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods. A technique is introduced that enables the elimination of two complete rounds of substitution permutation networks (SPN) in the sponge hash function without significant additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By employing this strategy, our attack achieves a gain of two additional rounds compared to the previous state-of-the-art attack. With no compromise to its security margin, this approach deepens our understanding of the design and analysis of such cryptographic primitives.
Aydin Abadi, Dan Ristea, Artem Grigor, Steven J. Murdoch
Time-Lock Puzzles (TLPs) enable a client to lock a message such that a server can unlock it only after a specified time. They have diverse applications, such as scheduled payments, secret sharing, and zero-knowledge proofs. In this work, we present a scalable TLP designed for real-world scenarios involving a large number of puzzles, where clients or servers may lack the computational resources to handle high workloads. Our contributions are both theoretical and practical. From a theoretical standpoint, we formally define the concept of a “Delegated Time-Lock Puzzle (D-TLP)”, establish its fundamental properties, and introduce an upper bound for TLPs, addressing a previously overlooked aspect. From a practical standpoint, we introduce the “Efficient Delegated Time-Lock Puzzle” (ED-TLP) protocol, which implements the D-TLP concept. This protocol enables both the client and server to securely outsource their resource-intensive tasks to third-party helpers. It enables realtime verification of solutions and guarantees their delivery within predefined time limits by integrating an upper bound and a fair payment algorithm. ED-TLP allows combining puzzles from different clients, enabling a solver to process them sequentially, significantly reducing computational resources, especially for a large number of puzzles or clients. ED-TLP is the first protocol of its kind. We have implemented ED-TLP and conducted a comprehensive analysis of its performance for up to 10,000 puzzles. The results highlight its significant efficiency in TLP applications, demonstrating that EDTLP securely delegates 99% of the client’s workload and 100% of the server’s workload with minimal overhead.
Rabimba Karanjai, Sangwon Shin, Xiong, and Wujie, Xinxin Fan · 11 authors
Cryptographic schemes like Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs), while offering powerful privacy-preserving capabilities, are often hindered by their computational complexity. Polynomial multiplication, a core operation in these schemes, is a major performance bottleneck. While algorithmic advancements and specialized hardware like GPUs and FPGAs have shown promise in accelerating these computations, the recent surge in AI accelerators (TPUs/NPUs) presents a new opportunity. This paper explores the potential of leveraging TPUs/NPUs to accelerate polynomial multiplication, thereby enhancing the performance of FHE and ZKP schemes. We present techniques to adapt polynomial multiplication to these AI-centric architectures and provide a preliminary evaluation of their effectiveness. We also discuss current limitations and outline future directions for further performance improvements, paving the way for wider adoption of advanced cryptographic tools.
We formalize security properties of zero-knowledge protocols and their proofs in EasyCrypt. Specifically, we focus on sigma protocols (three-round protocols). Most importantly, we also cover properties whose security proofs require the use of rewinding; prior work has focused on properties that do not need this more advanced technique. On our way we give generic definitions of the main properties associated with sigma protocols, both in the computational and information-theoretical setting. We give generic derivations of soundness, (malicious-verifier) zero-knowledge, and proof of knowledge from simpler assumptions with proofs which rely on rewinding. Also, we address sequential composition of sigma protocols. Finally, we illustrate the applicability of our results on three zero-knowledge protocols: Fiat-Shamir (for quadratic residues), Schnorr (for discrete logarithms), and Blum (for Hamiltonian cycles, NP-complete).
Modern cryptographic protocols such as zero-knowledge proofs and secure multi-party computation have increased the demand for a novel category of symmetric primitives. These primitives are not optimized for traditional platforms such as servers, microcontrollers, and desktop computers but rather for their ability to be implemented in arithmetic circuits. To enable efficient arithmetic operations, they define operations over larger finite fields and use low-degree invertible functions to construct their non-linear layers. Grendel is an arithmetization-oriented permutation that leverages the Legendre Symbol to enhance the growth of algebraic degrees in its non-linear layer. In this paper, we present a preimage attack on the sponge hash function instantiated with the full rounds of the Grendel permutation using algebraic methods. We introduce a technique that allows us to eliminate two full rounds of substitution permutation networks (SPN) in the sponge hash function with minimal or no additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By utilizing this strategy, our attack achieves an improvement of two additional rounds compared to the previous state-of-the-art attack. While not breaking its security margin, it allows us to further understand the design and analysis of such cryptographic primitives.
A commitment scheme is a cryptographic tool that allows one to commit to a hidden value, with the option to open it later at requested places without revealing the secret itself. Commitment schemes have important applications in zero-knowledge proofs and secure multi-party computation, just to name a few. This survey introduces a few multivariate polynomial commitment schemes that are built from a variety of mathematical structures. We study how Orion is constructed using hash functions; Dory, Bulletproofs, and Vampire using the inner-product argument; Signatures of Correct Computation using polynomial factoring; DARK and Dew using groups of unknown order; and Orion+ using a CP-SNARK. For each protocol, we prove its completeness and state its security assumptions.
Handong Cui, Kwan Yin Chan, Tsz Hon Yuen, Xin Kang · 5 authors
Abstract In most threshold Elliptic Curve Digital Signature Algorithm (ECDSA) signatures using additively homomorphic encryption, the zero-knowledge (ZK) proofs related to the ciphertext or the message space are the bottleneck in terms of bandwidth as well as computation time. In this paper, we propose a compact ZK proof for relations related to the Castagnos–Laguillaumie (CL) encryption, which is 33% shorter and 29% faster than the existing work in PKC 2021. We also give new ZK proofs for relations related to homomorphic operations over the CL ciphertext. These new ZK proofs are useful to construct a bandwidth-efficient universal composable-secure threshold ECDSA without compromising the proactive security and the non-interactivity. In particular, we lowered the communication and computation cost of the key refresh algorithm in the Paillier-based counterpart from $O(n^3)$ to $O(n^2)$. Considering a 5-signer setting, the bandwidth is better than the Paillier-based counterpart for up to 99, 95 and 35% for key generation, key refreshment and pre-signing, respectively.