A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. ‘94] shows that zeroknowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs - namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness. This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is “game-based” instead of “simulation-based.” Our construction builds on the work of Kuykendall and Zhandry [TCC ‘20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajíček and Pudlák’s 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert’s second problem (and, hence, also Gödel’s incompleteness theorem). Our highlevel idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.
The dawn of the disruptive quantum computing scenario marks a serious threat to the existence of traditional cryptosystems. With laws such as Shor’s, capable of factoring large integers in polynomial time, and Grover’s, able to speed up brute-force key searches, these attacks make conventional public-key infrastructures increasingly vulnerable, whereas even symmetric ciphers lose good measure of their strength. In this article, we focus on an elaborative description of a patented method for quantum-secure key generation, wherein Qabbalah (QBLH) complexity is utilized in the geometric-symbolic realm, in conjunction with magic number squares, phi/pi coordinate weighting, and tetrahedral trinary state encoding. The proposed system of TriGate QBLH Quantum-Safe Encryption converts seed inputs to multidimensional keys that resist linear algebraic attacks owing to non-linear permutations, irrational constant weighting, and topological complexity. Normally, pseudo-random number generators spatialize entropy in Euclidean geometry, as opposed to the present technique that places entropy in a completely non-Euclidean domain, where classical as well as quantum adversaries find it hard to traverse. We describe the method in detail, present its benefits over lattice- and hash-based post-quantum schemes, and walk through an example of its implementation. Consideration is also given to its potential integration with PQC standards, blockchain authentication, and decentralized finance applications. The system fuses symbolic mathematics, such as the 231 Gates of QBLH, with trinary logic mapped onto tetrahedral states to not only create encryption keys but also verifiable geometric signatures. This represents a paradigm shift toward geometric cryptography, which may be a viable method to realize scalable and trustworthy digital infrastructure in a quantum-threatened environment.
Card-based cryptography enables players to compute logical and arithmetic operations securely, such as bitwise AND and addition of integers. Several multiparty computation protocols and zero-knowledge proof protocols utilizing these secure computations have been developed as its applications. However, the realization of an efficient protocol for an arithmetic operation other than addition and subtraction remains an open problem. This paper proposes card-based protocols, based on integer commitment, for multiplication, division, and square root. Compared to general constructions for protocols for these operations based on binary integer commitment, the proposed protocols exhibit superior simplicity and efficiency. Furthermore, these protocols introduce novel applications for card-based cryptography to secure statistical data aggregation.
A zero-knowledge proof (ZKP) is an interactive proof between a prover and a verifier, with the prover's goal to convince the verifier that a solution of a computation problem exists without revealing any information about the solution itself. A card-based physical ZKP is an implementation of a ZKP using physical cards. Several metrics are used to measure the efficiency of card-based ZKPs, such as the numbers of required cards and shuffles. In this paper, we propose the first card-based ZKP for a puzzle Sudoku that uses only one shuffle. To achieve this, we use a technique of applying private operations interactively to prepare inputs for the protocol.
Julio López Fenner, Carlos Castillo-Muñoz, Francisco Escobar, Ana Bustamante-Mora · 5 authors
Privacy-preserving secure multi-party computation protocols are known to face scalability and efficiency challenges in environments where participants hold distinct attributes of the same records (vertical partitioning) or controls a subset of complete records (horizontal partitioning), as in cross-institutional health data analysis or federated IoT analytics, mostly because of communication overhead and the need to address adaptability to large scale or heterogeneous settings. This work introduces a novel MPC protocol based on the Damgård–Jurik cryptosystem and Schnorr zero-knowledge proofs (ZKP), designed to securely aggregate private data distributed across a number of parties. By combining homomorphic encryption with non-interactive ZKP’s, the protocol ensures privacy, correctness, and scalability, aligning with the principles of privacy-enhancing technologies (PETs). Our approach minimizes data exposure, allowing participants to audit results, and achieves linear O(N) communication complexity, thus making it suitable for large-scale applications in secure data analytics and collaborative computing.
This article presents a comprehensive framework for implementing privacy-preserving credit card reward systems using Secure Multi-Party Computation (SMPC) technologies. Traditional reward architectures require extensive sharing of sensitive transaction data across multiple entities, creating significant privacy risks, security vulnerabilities, and regulatory compliance challenges. It leverages cryptographic advances to enable card issuers, payment networks, and merchant partners to collaborate on reward calculations,fraud detection, and personalized offers without revealing sensitive transaction details to one another. The article explores the evolution of privacy-preserving technologies in financial systems, comparing Fully Homomorphic Encryption, Zero-Knowledge Proofs, and SMPC approaches. A detailed case study of a travel rewards program implementation demonstrates how this framework ensures data remains protected throughout the entire process while maintaining the performance characteristics necessary for production deployment. The system provides comprehensive privacy protection, enhances fraud detection capabilities through secure collaboration, and facilitates compliance with evolving privacy regulations.Performance evaluations confirm the practical viability of the article, with minimal latency impact, strong scalability characteristics, and robust security guarantees. It contributes to the growing field of privacy-enhancing technologies for financial services and offers a viable solution to balance analytical utility with privacy protection in consumer-facing applications.
Elvira Albert, Samir Genaim, Daniel Kirchner, Enrique Martin-Martin
Program optimization is a key factor for green software. In the context of the Ethereum blockchain, optimization is particularly relevant because there is a fee to pay for each EVM (Ethereum Virtual Machine) instruction executed and also there exist bytecode-size limitations for deploying the software on the blockchain. Still, optimization of EVM code is not as widely spread as one could imagine. This is at least partly due to the lack of trust in the correctness of the tools, as security is even more relevant than efficiency in the blockchain context in which bugs may cause huge economical losses. This article develops a formal verification framework using Coq to ensure the security of EVM optimizations performed on jump-free sequences of EVM bytecode. By means of Coq’s theorem proving capabilities, we are able to automatically verify/certify that an optimized jump-free sequence of EVM opcodes is semantically equivalent to a given original one. We also present an extension to our framework that can handle inter-block optimizations that propagate global information across blocks. We have applied our tool to successfully prove the security of peephole optimizations performed by the standard Solidity compiler, and also to existing EVM superoptimization tools (namely GASOL and Superstack) in which we have found bugs that have been reported and fixed.
Recently, the practical applications of advanced cryptographic protocols, such as Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero Knowledge Proofs (ZKP), have spurred the development of a series of new symmetric encryption primitives. These novel symmetric encryption primitives, referred to as Arithmetization-Oriented (AO) ciphers, aim to minimize the number of field multiplications in large finite fields, including 𝔽2n or 𝔽p. In order to evaluate the algebraic degrees of AO ciphers over 𝔽2n, the general monomial prediction technique was proposed by Cui et al. at ASIACRYPT 2022. However, when using their searching tool to evaluate the algebraic degrees of AO ciphers with complex affine layers, the efficiency is low, preventing solutions within a predetermined timeframe. In this study, we extend the propagation rules of monomials for field-based operations and present an automatic searching tool based on Mixed Integer Linear Programming (MILP) and Boolean Satisfiability (SAT) Problem for evaluating the upper bound of the algebraic degrees. Moreover, to accurately calculate the algebraic degrees of monomials in the SAT model, we improve the sequence encoding method, enabling it to accurately determine whether the monomials of degree d exist in the output. We apply our new searching tool to various AO ciphers, including Chaghri, MiMC, and Ciminion. For Chaghri, we compare our results with the Coefficient Grouping technique proposed by Liu et al. at EUROCRYPT 2023, and our results yield tighter upper bounds compared to Liu et al.’s findings. Additionally, we evaluate the algebraic degrees of Chaghri and MiMC with arbitrary complex affine layers and obtain tighter bounds compared to the results from Liu et al. at CRYPTO 2023. Regarding Ciminion, we have observed that starting from the 4-th round, the upper bound on the algebraic degrees for each round actually 1 degree lower than the previous bound. Our searching tool enables a more precise evaluation of the algebraic degrees of AO ciphers, contributing to a deeper understanding of the design and analysis of such primitives.
Sudoku tables as a special class of Latin squares are studied and a construction for each class of Sudoku tables is introduced. We provide a definition of a Sudoku table of size m as an m×m table with blocks of size s×d. Twin Sudoku tables of size m with(s, d)-subtables, where s is a divisor of d, are defined as Sudoku tables with (s × d)-subtables and (d×s)-subtables, simultaneously. Solid Sudoku cubes of size m, which are cubes with subcubes of size s×s×d, where s ≤ d and s·d = m, can be divided into subcubes in any face of the Sudoku cube. They have the property that each layer of the cube from each face, which is a table of size m, is a twin Sudoku table. Standard solid Sudoku cubes and 3D Sudoku puzzles are defined as solid cubes in which the subcubes of size m contain m different numbers, and they can be divided into subcubes of size x×y×z along the X, Y , and Z axes, respectively. Magic rectangles and nested magic rectangles are constructed. In addition, orthogonal balanced magic Sudoku tables as a class of Sudoku tables in which their blocks are magic are created and a method to construct nested Latin squares is presented. New classes of Sudoku puzzles are obtained from the construction of the Sudoku tables and Sudoku cubes. Since a Sudoku puzzle can be obtained from a Sudoku table by randomly removing some entries of the Sudoku table, creating a new class of Sudoku tables leads to a new class of Sudoku puzzles. To construct these new classes of Sudoku tables cyclotomic cosets of the algebraic group Zn are used. Sudoku tables have applications in different fields of study, and some of these applications are investigated. It is shown that they can be used in cryptography and zero-knowledge proof protocols. Sudoku puzzles are in the class of NP-complete problems, so zero knowledge proof protocols can be based on this class of problems. Sudoku tables like Latin squares can be used to generate locally repairable codes which have application in distributed storage systems.
Imagine sharing that you know a secret without revealing the secret itself. This is what zero-knowledge proofs (ZKPs) aim to do. In ZKPs there is a prover who claims knowledge of something and a verifier who checks this claim. The goal of this project is to further explore current technologies revolving around ZKPs and understand possible adaptations to an everyday application beyond blockchain use cases. To explore the practical use of ZKPs, this project introduces a web puzzle application that keeps the solutions of individual users private using ZKPs. A user can solve a logic- based puzzle like Binairo or Sudoku and check the validity of their solution by sharing only a ZKP of the solution. That way, the solution never leaves the user’s device. To further strengthen the security, the following two checks are implemented: (1) making sure that the solution matches the original puzzle, and (2) integrating the user’s ID during the generation process. These checks prevent users from reusing a proof to “solve” other puzzles or for the proof to be stolen by another user. To implement this application, different ZKP frameworks are considered. Circom and snarkjs are selected because of their active development, clear documentation and good web development capabilities. The final result is a secure application that demonstrates how ZKPs can be applied in a realistic and practical way. This highlights their broader potential in digital security. In most applications, the impact of ZKPs is intentionally hidden, as good cybersecurity aims to operate in the background. The ZKP-Puzzles application puts the ZKPs in the spotlight and visualizes how ZKPs work.
Open access
graph theory and CDMA systems
Graph Labeling and Dimension Problems
Advanced Steganography and Watermarking Techniques
The advent of 6G networks places very high demands on ultra-low latency, high throughput, and quantum-secure communication to power Industry 5.0 use cases. Traditional blockchain architectures, given their decentralized and secure nature, often fall short in meeting the performance and security requirements of such an ecosystem. In this paper, we present a post-quantum blockchain architecture that employs CRYSTALS-Dilithium and SPHINCS+ for digital signatures and block and transaction verification, respectively, along with zk-STARKs to facilitate scalable zero-knowledge proof-based privacy, and a DPoS+VDFs consensus protocol to satisfy fairness and efficiency. We prototyped and evaluated the proposed framework with a benchmarking setup composed of Python, PQClean, liboqs, and Google Benchmark tools. Experimental results demonstrate that the system achieves a 40% reduction in latency, a 35% increase in transaction throughput, and a 25% reduction in computational overhead due to the integration of zk-STARK. Furthermore, finality time for consensus was reduced by 30% by using the hybrid DPoS-VDF consensus approach. Comparative studies with various lattice-, hash-, and code-based quantum cryptographic primitives have shown that CRYSTALS-Dilithium and SPHINCS+ outperform others in key generation, signing, and verification performance indicators, and thus qualify as optimal solutions for edge-centric 6G infrastructures. Conversely, zk-Starks showed near-optimal timeliness and verification effectiveness among the several examined zero-knowledge proof schemes. These findings validate the proposed framework as an efficient, scalable, and performance-enhanced blockchain solution for securing industrial ecosystems with latency sensitivity in a 6G-enabled environment.
Aleksandra Szczegielniak-Rekiel, Krzysztof Kanciak, Jan M. Kelner
This study explored the diverse applications of zero-knowledge proofs (ZKPs) in next-generation network technologies, particularly in fifth-generation (5G) and emerging sixth-generation (6G) systems. ZKPs are cryptographic methods that enable one party to prove the validity of a statement without revealing the statement itself, thereby offering significant advantages in privacy-preserving authentication and authorization. Given these properties, ZKPs have garnered increasing research attention in contexts such as the Internet of Things (IoT), vehicular communications, and telecommunication protocols. To the best of our knowledge, this is the first study to provide a comprehensive, taxonomy-driven analysis of ZKP applications specifically designed for 5G and beyond. We categorize existing solutions according to the type of application, the underlying cryptographic technology, maturity level, and relevance to 6G. Furthermore, this paper examines how ZKPs can help mitigate various cybersecurity threats, such as distributed denial-of-service (DDoS) attacks, man-in-the-middle attacks, and location tracking. We also assess recent advancements in ZKP acceleration techniques and highlight the key implementation challenges. Finally, this study outlines promising directions for future research in this rapidly evolving field.
Open access
2 source records
Physical Unclonable Functions (PUFs) and Hardware Security
Sudoku is a popular pencil puzzle where a player fills in the empty cells with numbers on an n × n board so that each row, column, and -block must contain all the numbers from 1 to n; a typical puzzle size is n = 9. In 2007, Gradwohl, Naor, Pinkas, and Rothblum proposed a physical zero-knowledge proof protocol for Sudoku using a physical deck of cards; their card-based protocol requires 3nℓ shuffles, where ℓ is a security parameter to eliminate the soundness error. Since the invention of this seminal protocol, several soundness-error-free protocols were constructed to reduce the number of required shuffles; the state-of-the-art one was designed in 2023, which uses shuffles. In this paper, we show that only three or two shuffles are sufficient to construct a zero-knowledge proof protocol for Sudoku, no matter how large n is, i.e., we propose two card-based protocols using constant numbers (namely, 3 and 2) of shuffles. Our proposed protocols are simple and efficient enough for people to execute for a 9 × 9 Sudoku puzzle in reality.
Weihan Li, Zongyang Zhang, Yanpei Guo, Sherman S. M. Chow · 5 authors
Zero-knowledge range proof (ZKRP) asserts that a committed integerVlies in a given range like$[{0, 2^{n}-1}]$without other leakages ofV. It is vital in various privacy-preserving systems. Moving forward, the quest for post-quantum security is still in its infancy; the proof size of state-of-the-art lattice-based ZKRP (Lyubashevsky et al., CCS 20 and Couteau et al., Eurocrypt 21) remains linear inn, directly impacting the long-term sustainability in applications such as immutable ledgers. Confronting this unresolved impasse, we propose SHARP-PQ,i.e., succinct hash-based arbitrary-range proof with post-quantum security. SHARP-PQ offers proof size poly-logarithmic ton, optimized batch proofs, and versatile (new) capabilities. Its success stems from the improved inner product argument and exploitation of homomorphism. Empirically, SHARP-PQ features at least$10\times $smaller proof size for multiple ranges over lattice-based ZKRPs while maintaining competitive prover and verifier times. SHARP-PQ also outperforms ZKRPs directly constructed from hash-based generic zero-knowledge proofs at most$10 \times $.
A non-fungible token (NFT) is a kind of digital asset that signifies ownership or proof of authenticity of a special good or piece of material, such as artwork, music, films, or tweets. This study investigates how a deep convolutional generative adversarial network (DCGAN) can be used to create distinctive pictures of Cryptopunks that can be converted into NFTs. Cryptopunks, a pioneering form of NFTs, were introduced on the Ethereum blockchain in 2017 as part of a social experiment. In the NFT community, they have since grown in popularity as collectibles. To create brand-new, previously undiscovered characters, we trained a model on a dataset of existing Cryptopunks using the DCGAN architecture. In an effort to raise the calibre of the images produced, we tested various hyper settings and layer combinations. We also assessed the created images using a variety of criteria, such as the inception score and Fréchet inception distance, to make sure they were distinctive and of high calibre. Our experiments yielded a 15 % increase in the inception score and a 20 % decrease in the Fréchet inception distance, showing that our DCGAN model produces images that are more visually appealing and closer in quality to real Cryptopunks. These results highlight the effectiveness of our machine learning algorithms in improving the quality and uniqueness of NFT assets.
The introduction of non-fungible tokens (NFTs) has revolutionised digital ownership and asset management in the quickly changing environment of blockchain technology. NFTs are a kind of token that cannot be exchanged for another token. On the other hand, as the market for NFTs continues to grow, customers are becoming more and more interested in interoperability across various blockchain networks. Cross-chain non-fungible token markets have been developed as a result of this necessity. These marketplaces make it possible for different blockchain ecosystems to engage in transactions and interactions with one another. LayerZero and Chainlink are two technologies that are very significant in addressing the difficulty of interoperability across different chains.
Abstract A zero-knowledge proof is a cryptographic primitive that enables a prover to convince a verifier the validity of a mathematical statement (an NP statement) without revealing any secret inputs to the verifier. A special case, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK) is particularly designed for arithmetic circuit proof systems which have important applications in blockchain privacy. The major computations in this type of zkSNARK proofs with post-quantum security are polynomial evaluations and Lagrange interpolations over finite fields. Given a sequence over a finite field, in the field of coding and sequences research, we understand that there are two representations of the sequence, one is a univariate polynomial and the other, a multivariate polynomial. This is exactly what is done in those zero-knowledge proof systems to transform the proof of a R1CS relation to evaluate uni/multi variate polynomials at some random points in the finite field. In this paper, we present a comparative analysis on how to convert a rank 1 constrained satisfiability (R1CS) system (more general than a circuit system) into a polynomial equality and provide analysis on the concrete complexities of provers, proof sizes and verifiers. We use two concrete zkSNARK schemes, i.e., Polaris, univariate polynomial encodings and Spartan, multivariate polynomial encodings, as examples to show our analysis. Secondly, we propose to select interpolating sets as subfields instead of affine spaces of a large field for Lagrange interpolation. This new method has improved the performance of R1CS encodings largely. We comment that post-quantum secure zkSNARKs yield post-quantum digital signatures with security only depending on symmetric-key schemes. Some open problems are proposed at the end of the paper.
Abstract A zero-knowledge proof protocol is a cryptographic protocol in which a prover, who knows the witness to a statement, can convince a verifier that the statement is true without revealing any information about the witness. Although zero-knowledge proof protocols are typically executed on electronic computers, there is a line of research to design zero-knowledge proof protocols based on physical objects (e.g., a deck of cards). This is called physical zero-knowledge proof. In this paper, we construct a physical zero-knowledge proof protocol for a logical puzzle called Sukoro. Sukoro has many cells on the puzzle board, like Sudoku, where each cell must be empty or filled with a number from one to four, and each number must match the number of adjacent filled cells, and the same numbers must not be adjacent to each other. In addition, it has a rule that all filled cells must be connected, which is called the connectivity condition. Although some existing protocols deal with the connectivity condition, all existing methods are interactive , which requires the prover’s knowledge to determine how the cards are manipulated during the execution of the protocols. In this paper, we give a new method for verifying the connectivity condition in the non-interactive setting, which means that the protocol can be executed without the prover’s knowledge, and construct a physical zero-knowledge proof protocol for Sukoro.
Behzad Abdolmaleki, Noemi Glaeser, Sebastian Ramacher, Daniel Slamanig
Non-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (zk-SNARKs) increasingly see real-world adoption in large and complex systems. Many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and for practical use it is desirable to reduce the trust in the CRS generation. The latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large systems is the ability to securely compose them to obtain more complex protocols, e.g., via the Universal Composability (UC) framework. Relying on the UC framework allows arbitrary and secure composition of protocols in a modular way. In this work, we investigate whether zk-SNARKs can provide updatability and composability simultaneously. This is a challenging task as the UC framework rules out several natural techniques for such a construction. As our main result, we show that it is indeed possible to achieve these properties in a generic and modular way if we relax the succinctness properties of zk-SNARKs slightly to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness$w$. We argue that for various practical applications of zk-SNARKs this overhead is acceptable. Our starting point is the Lamassu framework (ACM CCS'20), which we extend in several directions. Our new generic compiler adds only minimal overhead, which we demonstrate by benchmarking its application to the Sonic proof system (ACM CCS'19).