Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Weakly Super-Invertible Matrices and Constant Communication Dishonest Majority MPC
Get PDFIn recent years, there has been tremendous progress in improving the concrete communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting where for some constant , Sharing Transformation (Goyal , CRYPTO\u2722) and SuperPack (Escudero , EUROCRYPT\u2723) presented protocols with information-theoretic online phases requiring field elements of total communication per multiplication gate. However, Sharing Transformation assumes that their offline phase is instantiated by a trusted party, while SuperPack instantiates their offline phase with large communication of per multiplication gate assuming oblivious linear evaluation (OLE) correlations. The main bottleneck in instantiating the offline phases of both protocols is generating random packed beaver triples of the form , for random , and , where is the .
To address this bottleneck, our main technical contribution is introducing and constructing super-invertible matrices, a relaxation of super-invertible matrices in which sub-matrices have high (but not necessarily full) rank. This relaxation allows for matrices with only non-zero entries, enabling a first step towards generating packed beaver triples with total communication per underlying triple, assuming OLE correlations. As the second (and final) step, we use the efficient protocol of (Choudhury and Patra, Trans. Inform. Theory \u2717).
We also implement our packed beaver triple protocol and provide experimental results. Our new protocol obtains up to 38% smaller communication and 9% reduction in runtime compared to SuperPack\u27s triple protocol. Additionally, by instantiating SuperPack\u27s offline phase with our new protocol, we obtain up to 16% communication reductions.
Finally, we use our packed beaver triple protocol to instantiate the offline phase of Sharing Transformation, yielding a dishonest majority MPC protocol with total communication across both the offline and online phases
FOLEAGE: OLE-Based Multi-Party Computation for Boolean Circuits
No full textSecure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called multiplication triples, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function.
To date, the state-of-the-art secure multi-party computation protocols in the preprocessing model are tailored to secure computation of arithmetic circuits over large fields and require little communication in the preprocessing phase, typically O(N · m) to generate m triples among N parties. In contrast, when it comes to computing preprocessing for computations that are naturally represented as Boolean circuits, the state-of-the-art techniques have not evolved since the 1980s, and in particular, require every pair of parties to execute a large number of oblivious transfers before interacting to convert them to N-party triples, which induces an Ω(N^2 · m) communication overhead.
In this paper, we introduce FOLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. FOLEAGE exhibits excellent performance: It generates m multiplication triples over F2 using only N · m + O(N^2 · log m) bits of communication for N-parties, and can concretely produce over 12 million triples per second in the 2-party setting on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplication triples over the field F4. Roughly speaking, a PCG enables parties to stretch a short seed into a large number of pseudorandom correlations non-interactively, which greatly improves the efficiency of the offline phase in MPC protocols. Our construction significantly outperforms the state-of-the-art, which we demonstrate via a prototype implementation. This is achieved by introducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome Decoding assumption
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
Get PDFSponge hashing is a widely used class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a digest by once again iterating the block function on the final output bits. While much is known about the post-quantum security of the sponge construction when the block function is modeled as a random function or one-way permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem.
In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the ``double-sided zero-search\u27\u27 conjecture proposed by Unruh (eprint\u27 2021) and show that finding zero-pairs in a random -bit permutation requires at least many queries---and this is tight due to Grover\u27s algorithm. At the core of our proof lies a novel ``symmetrization argument\u27\u27 which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random permutation model
Practical Post-Quantum Signatures for Privacy
Get PDFThe transition to post-quantum cryptography has been an enormous challenge and effort for cryptographers over the last decade, with impressive results such as the future NIST standards. However, the latter has so far only considered central cryptographic mechanisms (signatures or KEM) and not more advanced ones, e.g., targeting privacy-preserving applications. Of particular interest is the family of solutions called blind signatures, group signatures and anonymous credentials, for which standards already exist, and which are deployed in billions of devices. Such a family does not have, at this stage, an efficient post-quantum counterpart although very recent works improved this state of affairs by offering two different alternatives: either one gets a system with rather large elements but a security proved under standard assumptions or one gets a more efficient system at the cost of ad-hoc interactive assumptions or weaker security models. Moreover, all these works have only considered size complexity without implementing the quite complex building blocks their systems are composed of. In other words, the practicality of such systems is still very hard to assess, which is a problem if one envisions a post-quantum transition for the corresponding systems/standards.
In this work, we propose a construction of so-called signature with efficient protocols (SEP), which is the core of such privacy-preserving solutions. By revisiting the approach by Jeudy et al. (Crypto 2023) we manage to get the best of the two alternatives mentioned above, namely short sizes with no compromise on security. To demonstrate this, we plug our SEP in an anonymous credential system, achieving credentials of less than 80 KB. In parallel, we fully implemented our system, and in particular the complex zero-knowledge framework of Lyubashevsky et al. (Crypto\u2722), which has, to our knowledge, not be done so far. Our work thus not only improves the state-of-the-art on privacy-preserving solutions, but also significantly improves the understanding of efficiency and implications for deployment in real-world systems
A Mempool Encryption Scheme for Ethereum via Multiparty Delay Encryption
Get PDFEthereum is a decentralized and permissionless network offering several attractive features. However, block proposers in Ethereum can exploit the order of transactions to extract value. This phenomenon, known as (MEV), not only disrupts the optimal functioning of different protocols but also undermines the stability of the underlying consensus mechanism. Furthermore, current block production architecture allows transaction censorship that compromises credible neutrality, a fundamental principle of Ethereum’s design philosophy.
In this work, we present a novel scheme to alleviate the censorship and MEV problem by separating transaction inclusion and execution, keeping transactions encrypted before execution. We formulate the notion of (MDE) and construct a practical MDE scheme based on time-lock puzzles. Our method excels in scalability (in terms of transaction decryption), efficiency (minimizing communication and storage overhead), and security (with minimal trust assumptions).
To demonstrate the effectiveness of our MDE scheme, we have implemented it on a local Ethereum testnet and prove its security under the presence of only one honest attestation aggregator per Ethereum slot
AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing
No full textWe optimise the verification of the SQIsign signature scheme. By using field extensions in the signing procedure, we are able to significantly increase the amount of available rational -power torsion in verification, which achieves a significant speed-up. This, moreover, allows several other speed-ups on the level of curve arithmetic. We show that the synergy between these high-level and low-level improvements gives significant improvements, making verification times faster, or up to times when using size-speed trade-offs, compared to the state of the art, without majorly degrading the performance of signing
Leakage-Free Probabilistic Jasmin Programs
Get PDFThis paper presents a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove the equivalence between both definitions. We also prove that our new characterizations are compositional and relate our new definitions to existing ones from prior work, which could only be applied to deterministic programs.
To provide practical evidence, we use the Jasmin framework to develop a rejection sampling algorithm and provide an EasyCrypt proof that ensures the algorithm\u27s implementation is leakage-free while not being constant-time
The supersingular endomorphism ring problem given one endomorphism
Get PDFGiven a supersingular elliptic curve and a non-scalar endomorphism of , we prove that the endomorphism ring of can be computed in classical time about , and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.
Along the way, we prove that the Primitivisation problem can be solved in polynomial time (a problem previously believed to be hard), and we prove that the action of smooth ideals on oriented elliptic curves can be computed in polynomial time (previous results of this form required the ideal to be powersmooth, i.e., not divisible by any large prime power).
Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results
On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing
Get PDFZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed.
One of the most important computations that is run through SNARK systems is the verification of Merkle tree (MT) opening proofs, which relies on the evaluation of a fixed-input-length (FIL) cryptographic compression function over binary MTs.
As classical, bit-oriented hash functions like SHA-2 are not compactly representable in SNARK frameworks, Arithmetization-Oriented (AO) cryptographic designs have emerged as an alternative, efficient solution.
Today, the majority of AO compression functions are built from the Sponge permutation-based hashing mode. While this approach allows cost savings, compared to blockcipher-based modes, as it does not require key-scheduling, AO blockcipher schedulers are often cheap to compute.
Furthermore, classical bit-oriented cryptography has long studied how to construct provably secure compression functions from blockciphers, following the Preneel-Govaerts-Vandewalle (PGV) framework. The potential efficiency gains together with the strong provable security foundations in the classic setting, motivate the study of AO blockcipher-based compression functions.
In this work, we propose PGV-LC and PGV-ELC, two AO blockcipher-based FIL compression modes inspired by and extending the classical PGV approach, offering flexible input and output sizes and coming with provable security guarantees in the AO setting. We prove the collision and preimage resistance in the ideal cipher model, and give bounds for collision and opening resistance over MTs of arbitrary arity.
We compare experimentally the PGV-ELC mode over the HADES blockcipher with its popular and widely adopted Sponge instantiation, Poseidon, and its improved variant Poseidon2.
Our resulting constructions are up to 3× faster than Poseidon and 2× faster than Poseidon2 in native x86 execution, up to 1.5× faster in the Groth16 SNARK framework, and up to 1.9× faster in the Plonky2 framework.
Finally, we study the benefits of using MTs of arity wider than two, proposing a new strategy to obtain a compact R1CS constraint system in such case. In fact, by combining an efficient parametrization of the HADES blockcipher over the PGV-ELC mode, together with an optimal choice of the MT arity, we measured an improvement of up to 9× in native MT construction time, and up to 2.5× in proof generation time, compared to Poseidon over binary MTs
Construction of Maiorana-McFarland type cryptographically significant Boolean functions with good implementation properties
Get PDFWe present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than gates on the number of input bits . We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR, each with a maximum fan-in of two) required to implement a given function. While prior studies have explored cryptographic parameters of such functions in theory, they often overlooked circuit-level efficiency, especially in high-dimensional settings. In this work, we construct a class of balanced functions with high nonlinearity, low absolute autocorrelation and high algebraic degree, yet realizable using a small number of logic gates. Towards application, this work provides additional design directions for cryptographic primitives in domains such as fault-resistant cryptography and homomorphic encryption, where both security and circuit efficiency at scale are critical. Further investigations are required towards actual hardware implementation of our proposed functions as well as to exploit them in concrete cipher designs