Privacy-preserving analytics is indeed a critical enabler for businesses that want to glean insights from sensitive data while protecting individual privacy. Tighter regulation and growing concern over data abuse have, respectively, driven the development of techniques involving zero-knowledge proofs and secure multiparty computation. These systems are set to establish trust boundaries among partner organisations while gently permitting significant information transfers for the decision-making process. The practically verifiable assurance of data secrecy is what makes these protocols particularly attractive in sectors heavily reliant on data analysis, like healthcare, banking, and law enforcement. Such integrated architectures guarantee controlled overhead while delivering high-quality output through cryptographic primitives. Real-life implementations show that it is indeed possible to strike a balance between the efficiency of the system and its security constraints. Enhanced Interoperabillty, along with modularity, will allow more widespread use in diverse ecosystems where insights derived from data drive enterprise innovation alongside robust privacy protections.
In the context of cloud computing, services are held on cloud servers, where the clients send their data to the server and obtain the results returned by server. However, the computation, data and results are prone to tampering due to the vulnerabilities on the server side. Thus, verifying the integrity of computation is important in the client-server setting. The cryptographic method known as Zero-Knowledge Proof (ZKP) is renowned for facilitating private and verifiable computing. ZKP allows the client to validate that the results from the server are computed correctly without violating the privacy of the server’s intellectual property. Zero-Knowledge Succinct NonInteractive Argument of Knowledge (zkSNARKs), in particular, has been widely applied in various applications like blockchain and verifiable machine learning. Despite their popularity, existing zkSNARKs approaches remain highly computationally intensive. For instance, even basic operations like matrix multiplication require an extensive number of constraints, resulting in significant overhead. In addressing this challenge, we introduce $z k V C$, which optimizes the ZKP computation for matrix multiplication, enabling rapid proof generation on the server side and efficient verification on the client side. zkVC integrates optimized ZKP modules, such as Constraint-reduced Polynomial Circuit (CRPC) and Prefix-Sum Query (PSQ), collectively yielding a more than $\mathbf{1 2}$-fold increase in proof speed over prior methods. The code is available at https://github.com/UCF-Lou-Lab-PET/zkformer.
Delaram Kahrobaei, Ludovic Perret, Martina Vigorito
Abstract Bidoux and Gaborit introduced a new general technique to improve zero-knowledge ( ZK ) proof-of-knowledge ( PoK ) schemes for a large set of well-known post-quantum hard computational problems such as the syndrome decoding, the permuted kernel, the rank syndrome decoding, and the multivariate quadratic ( MQ ) problems. In particular, the authors’ idea in the study of Bidoux and Gaborit was to use the structure of these problems in the multi-instance setting to minimize the communication complexity of the resulting ZK PoK schemes. The security of the new schemes is then related to new hard problems. In this article, we focus on the new multivariate-based ZK PoK and the corresponding new underlying problem: the so-called <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} . We present a new efficient probabilistic algorithm for solving the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} which is polynomial-time if <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>m</m:mi> <m:mo>−</m:mo> <m:mi>n</m:mi> <m:mo>∈</m:mo> <m:mi>O</m:mi> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:math> m-n\in O\left(1) . We also present experimental results showing that the algorithm is efficient in practice.
I. D. Ioganson, QApp, Vadim Davydov, Jean-Michel Nikodemovich Dakuo · 5 authors
In the paper, a novel isogeny-based protocol for mental poker game is presented. This protocol allows multiple users to create and shuffle a deck of cards, and then issue a card to a specific user. Two versions of the protocol are developed: one without validation, which protects only against passive adversaries, and one with validation, which also allows detecting active interference with the protocol using zero-knowledge proof protocols. To validate the resulting solution, a C program was developed that implements the described protocol. This demonstrates the practical applicability of the proposed solution while ensuring protection against quantum attacks.
Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.
Katharina Koschatko, Reinhard Lüftenegger, Christian Rechberger
Gröbner basis cryptanalysis of hash functions and ciphers, and their underlying permutations, has seen renewed interest recently. Anemoi (Crypto’23) is a permutation-based hash function that is efficient for a variety of arithmetizations used in zero-knowledge proofs. In this paper, exploring both theoretical bounds as well as experimental validation, we present new complexity estimates for Gröbner basis attacks on the Anemoi permutation over prime fields.We cast our findings in what we call the six worlds of Gröbner basis cryptanalysis. As an example, keeping the same security arguments of the design, we conclude that at least 41 instead of 37 rounds would need to be used for 256-bit security, whereby our suggestion does not yet include a security margin.
Open access
Polynomial and algebraic computation
Cryptography and Residue Arithmetic
Mathematics, Computing, and Information Processing
Abstract In an Instance-Hiding Interactive Proof (IHIP) (Beaver et al., in: Menezes and Vanstone (eds) Advances in cryptology—CRYPTO 1990, proceedings, lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), Springer, pp 326–338, 1990), an efficient verifier with a private input x interacts with an unbounded prover to determine whether x is contained in a language $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> . In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties and may be seen as a generalization of the influential concept of randomized encodings (Ishai and Kushilevitz, in: Proceedings 41st annual symposium on foundations of computer science, pp 294–304, 2000; Applebaum et al., in: 45th annual IEEE symposium on foundations of computer science, pp 166–175, 2004; Agrawal et al., in: Halldórsson, Iwama, Kobayashi, Speckmann (eds) Automata, languages, and programming, Springer, Berlin, Heidelberg, pp 1–13, 2015) and as a counterpart to zero-knowledge proofs (Goldwasser et al., in: Symposium on the theory of computing, 1985). We investigate the properties and power of such instance-hiding proofs and show the following: Any language with an IHIP is contained in $${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>NP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mrow> <mml:mi>coNP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> </mml:mrow> </mml:math> . If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. IHIP’s are closed under composition with any efficiently computable function. We further study a stronger version of IHIP (that we call Simulatable IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above: Any language with a Simulatable IHIP is contained in $${\textsf{AM}}\cap {\textsf{coAM}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>AM</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>coAM</mml:mi> </mml:mrow> </mml:math> . If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.
Open access
2 source records
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.
Nicholas Brandt, Dennis Hofheinz, Michael Klooß, Michael Reichle
We construct the first blind signature scheme that achieves all of the following properties simultaneously: – it is tightly secure under a standard (i.e., non-interactive, non-q-type) computational assumption, – it does not require pairings, – it does not rely on generic, non-black-box techniques (like generic NIZK proofs). The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 Zp-elements. Our scheme starts from a pairing-based non-blind signature scheme (Abe et al., JoC 2023), and uses recent techniques of Chairattana-Apirom, Tessaro, and Zhu (CRYPTO 2024) to replace the pairings used in this scheme with non-interactive zero-knowledge proofs in the random oracle model. This conversion is not generic or straightforward (also because the mentioned previous works have converted only significantly simpler signature schemes), and we are required to improve upon and innovate existing techniques in several places. As an interesting side note, and unlike previous works, our techniques only require a non-programmable random oracle, and our signature scheme achieves predicate blindness (which means that the user can prove state ments about the signed message during the signing process).
Zero-knowledge proof (ZKP) systems have surged attention and held a fundamental role in contemporary cryptography. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) protocols dominate the ZKP usage, implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. The former refers to circuits that lack the necessary constraints, resulting in unexpected solutions and causing the verifier to accept a bogus witness, and the latter refers to circuits that are constrained excessively, resulting in lacking necessary solutions and causing the verifier to accept no witness. This article introduces a novel approach for pinpointing two distinct types of bugs in ZKP circuits. The method involves encoding the arithmetic circuit constraints to polynomial equation systems and solving them over finite fields by the computer algebra system . The classification of verification results is refined, greatly enhancing the expressive power of the system. A tool, AC 4 , is proposed to represent the implementation of the method. Experiments show that AC 4 demonstrates an increase in the solved rate, showing a 36.7% improvement over Picus and CIVER, and a slight improvement over halo2-analyzer, a checker for halo2 circuits. Within a solvable range, the checking time has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.
Signatures post-quantiques à partir de techniques de calcul multipartite Le développement actuel des ordinateurs quantiques pousse la communauté cryptographique à mettre au point de nouveaux cryptosystèmes dont la sécurité se fonde sur la difficulté à résoudre des problèmes cryptographiques résistant au calcul quantique. Dans le cadre de cette thèse, nous nous sommes focalisés sur la conception de schémas de signatures électroniques construits à partir de preuves à divulgation nulle de connaissance (zero-knowledge proofs of knowledge). Plus précisément, nous nous sommes intéressés au paradigme “MPC-in-the-Head” (littéralement, “calcul-multipartite-dans-la-tête”) qui fournit une méthode générique de construire de telles preuves en utilisant des techniques de calcul multipartite sécurisé. Nous proposons plusieurs nouveaux schémas de signatures utilisant le paradigme “MPC-in-the-Head”. La plupart d’entre eux sont compétitifs avec les schémas existants dans l’état de l’art post-quantique. Ils produisent des signatures ayant des tailles entre 5 et 20 kylo-octets (pour un niveau de sécurité de 128 bits) et possèdent de très petites clés (de moins de 200 octets). Les problèmes difficiles sur lesquels la sécurité de ces schémas se fonde sont très variés. Certains schémas s’appuient sur des hypothèses de sécurité issues de la théorie des codes correcteurs d’erreurs, telle que celle sur la difficulté à résoudre le problème de décodage par syndrome pour des codes linéaires aléatoires. Les autres schémas s’appuient sur la difficultés à résoudre un système d’équations quadratiques, le problème de la somme de sous-ensembles ou le problème MinRank. Nous avons également mis au point deux nouvelles techniques de MPC-in-the-Head. La première vise à gérer efficacement les situations où le secret est de petite taille avec un grand modulus. La seconde consiste en une nouvelle méthode pour transformer un protocole de calcul multipartite en preuve de divulgation nulle de connaissance. Cette nouvelle transformation offre des nouveaux compromis entre coût de communication et temps de calcul. En particulier, elle permet de produire des algorithmes de vérification très rapides. Plusieurs soumissions à l’appel du NIST pour des schémas de signatures post-quantiques supplémentaires s'appuient (parfois partiellement) sur des idées développées dans le cadre de cette thèse.
The objective of this memory is to give a purely algebraic proof of the Sauer- Shelah-Perles Lemma (inspired by the elegant proof in [FrPa,1983]), based only in duality in the Q−algebra Q[Vn] of polynomial functions de_ned on the zero-dimensional algebraic variety of subsets of the set [n] := {1, 2, . . . , n}. In fact, two di_erent proofs of this lemma will be given. Furthermore, we prove how several other classical results from Combinatorics are particular examples of a Trace (Inversion) Formula in _nite Q−algebras. For instance, one of this results is the general form of the Inclusion-Exclusion Principle (both with direct and reverse order associated to subsets inclusion). This approach also allows us to show a basis of the space of null t−designs, which di_ers from the one described in Theorem 4 of [DeFr,1982]. All results are still true if we replace Q[Vn] by K[Vn], where K is a perfect _eld of characteristic di_erent from 2. This memory has then the underlying purpose of connecting two _elds of mathematical knowledge that are not usually connected, at least not in this form.
Abstract The MinRank problem is an NP-complete problem that is prevalent in multivariate cryptography and its goal is to find a non-zero linear combination of given a series of matrices over a ring such that the obtained matrix has a small rank. At Asiacrypt 2001, two Zero-Knowledge Proofs of Knowledge (ZKPoK) for the MinRank problem are proposed, and we call them MRZK and MRZK$^{\dagger }$, respectively. The latter is an improved version of the proof size of the former. However, the efficiency of MRZK$^{\dagger }$ has been open and not analyzed. While the MRZK protocol is secure, it must be repeated many times due to the soundness error $2/3$, which leads to the large proof size. For 128-bit security, the MRZK protocol is executed at least 219 iterations and the proof size is about 32 KB. In this paper, we first show that the efficiency of MRZK$^{\dagger }$ is impractical due to unreasonable parameter size. However, when the parameter size is tuned and the efficiency is improved, an imposter can be efficiently constructed. Then, to alleviate the large proof size of MRZK, inspired by the technique designing ZKPoK (Eurocrypt 2020), we propose a sigma protocol with helper to prove the solution to the MinRank problem. Finally, we transform the sigma protocol with helper into a standard ZKPoK (MRZK$^{\sharp }$) by removing the helper. The MRZK$^{\sharp }$ protocol can achieve any small soundness error and enjoy the proof size of about 15 KB (53% improvement over MRZK).
Метою роботи є оптимізувати множення точок еліптичної кривої на скаляр за допомогою модернізованого метода “Подвійне скалярне множення з використанням трюку Штрауса-Шаміра з урахуванням Skew representation” та багато інших підходів. Ще однією метою роботи - зробити використання множення точок еліптичної кривої на скаляр безпечним в межах протоколу Zero-knowledge proof. З'ясувати, який метод множення буде найдешевшим в контексті визначеної метрики. Об’єктом дослідження є множення точок еліптичної кривої на скаляр в системі гаджет бібліотеках рекурсивних zk-Snark’s. Множення повинно виконуватися до стандартів протоколу Zero-knowledge proof. Також розглянуто варіанти практичного застосування описаних методів. У роботі виконане теоретичне та практичне дослідження, огляд алгоритмів та методів розв’язання задачі оптимізації з використанням різноманітних хитростей та підходів. Кодова база була написана мовою програмування Rust в бібліотеці franklin-crypto. Арифметизація, яка застосовується в бібліотеці – Plonkish та lookup table. Крива, яка була використана для тестування множення – Bn256. Ключові слова : точки еліптичної кривої, Zero-knowledge proof, мовою програмування Rust.
Electronic voting is one of the most interesting application of modern cryptography, as it involves many innovative tools (such as homomorphic public-key encryption, non-interactive zero-knowledge proofs, and distributed cryptography) to guarantee several a priori contradictory security properties: the integrity of the tally and the privacy of the individual votes. While many efficient solutions exist for honest-but-curious voters, that follow the official procedure but try to learn more than just the public result, preventing attacks from malicious voters is much more complex: when voters may have incentive to send biased ballots, the privacy of the ballots is much harder to satisfy, whereas this is the crucial security property for electronic voting. We present a new technique to prove that an ElGamal ciphertext contains a message from a specific subset (quasi-adaptive NIZK of subset membership), using linearly-homomorphic signatures. The proofs are both quite efficient to generate, allowing the use of low-power devices to vote, and randomizable, which is important for the strong receipt-freeness property. They are well-suited to prevent vote-selling and replay attacks, which are the main threats against the privacy in electronic voting, with security proofs in the generic group model and the random oracle model.
Alex Ozdemir, Gereon Kremer, Cesare Tinelli, Clark Barrett
Abstract We study satisfiability modulo the theory of finite fields and give a decision procedure for this theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this theory, we construct SMT queries that encode translation validation for various zero knowledge proof compilers applied to Boolean computations. We evaluate our procedure on these benchmarks. Our experiments show that our implementation is superior to previous approaches (which encode field arithmetic using integers or bit-vectors).
The assignment problem is an essential problem in many application fields and frequently used to optimize resource usage. The problem is well understood and various efficient algorithms exist to solve the problem. However, it was unclear what practical performance could be achieved for privacy preserving implementations based on multiparty computation (MPC) by leveraging more efficient solution strategies than MPC based simplex solvers for linear programs. We solve this question by implementing and comparing different optimized MPC algorithms to solve the assignment problem for reasonable problem sizes. Our empirical approach revealed various insights to MPC based optimization and we measured a significant (50x) speedup compared to the known simplex based approach. Furthermore, we also study the overhead introduced by making the results publicly verifiable by means of non-interactive zero-knowledge proofs. By leveraging modern proof systems we also achieve significant speedup for proof and verification times compared to the previously proposed approaches as well as compact proof sizes.
This work is focused on the description of one verifiable encryption scheme, specifically a zero-knowledge proof of knowledge protocol. Verifiable encryption allows us to prove properties of data without revealing its content. The main goal of the presented method is verification of knowledge of a secret key. This method can be used for group signa- tures, multiple steps secret sharing, key escrow protocols, and many others cryptographic protocols. It is based on the hardness of the Ring-LWE problem and problems of finding solutions to linear relations over some ring. It uses the principle of rejection sampling. The method is build on two closely described cryptographic protocols, Ring-LWE and Fiat-Shamir with aborts. It uses the construction of polynomial rings R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1
—Algebra is one of the important fields of mathematics. It concerns with the study and manipulation of mathematical symbols. It also concerns with the study of abstractions such as groups, rings, and fields. Due to the development of these abstractions, it is extended to consider other structures, such as vectors, matrices, and polynomials, which are non-numerical objects. Computer algebra is the implementation of algebraic methods as algorithms and computer programs. Recently, many algebraic cryptosystem protocols are based on non-commutative algebraic structures, such as authentication, key exchange, and encryptiondecryption processes are adopted. Cryptography is the science that aimed at sending the information through public channels in such a way that only an authorized recipient can read it. Ring theory is the most attractive category of algebra in the area of cryptography. In this paper, we employ the algebraic structure called skew -Armendariz rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is established and illustrated through numerical example, and its soundness and completeness are proved