Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Breaking and Fixing Anonymous Credentials for the Cloud
Get PDFIn an attribute-based credential (ABC) system, users obtain a digital certificate on their personal attributes, and can later prove possession of such a certificate in an unlinkable way, thereby selectively disclosing chosen attributes to the service provider. Recently, the concept of encrypted ABCs (EABCs) was introduced by Krenn et al. at CANS 2017, where virtually all computation is outsourced to a semi-trusted cloud-provider called wallet, thereby overcoming existing efficiency limitations on the user’s side, and for the first time enabling “privacy-preserving identity management as a service”.
While their approach is highly relevant for bringing ABCs into the real world, we present a simple attack allowing the wallet to learn a user\u27s attributes when colluding with another user -- a scenario which is not covered by their modeling but which needs to be considered in practice. We then revise the model and construction of Krenn et al. in various ways, such that the above attack is no longer possible. Furthermore, we also remove existing non-collusion assumptions between wallet and service provider or issuer from their construction. Our protocols are still highly efficient in the sense that the computational effort on the end user side consists of a single exponentiation only, and otherwise efficiency is comparable to the original work of Krenn et al
Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular
Get PDFWe consider the problem of proving in zero knowledge that an element of a public set satisfies a given property without disclosing the element, i.e., for some , `` and holds\u27\u27. This problem arises in many applications (anonymous cryptocurrencies, credentials or whitelists) where, for privacy or anonymity reasons, it is crucial to hide certain data while ensuring properties of such data.
We design new \textit{modular} and \textit{efficient} constructions for this problem through new \textit{commit-and-prove zero-knowledge systems for set membership}, i.e. schemes proving for a value that is in a public commitment . We also extend our results to support {\em non-membership proofs}, i.e. proving .
Being commit-and-prove, our solutions can act as plug-and-play modules in statements of the form `` and holds\u27\u27 by combining our set (non-)membership systems with any other commit-and-prove scheme for . Also, they work with Pedersen commitments over prime order groups which makes them compatible with popular systems such as Bulletproofs or Groth16.
We implemented our schemes as a software library, and tested experimentally their performance. Compared to previous work that achieves similar properties---the clever techniques combining zkSNARKs and Merkle Trees in Zcash---our solutions offer more flexibility, shorter public parameters and -- faster proving time for a set of size
A notion on S-boxes for a partial resistance to some integral attacks
Get PDFIn two recent papers, we introduced and studied the notion of th-order sum-freedom of a vectorial function . This notion generalizes that of almost perfect nonlinearity (which corresponds to ) and has some relation with the resistance to integral attacks of those block ciphers using as a substitution box (S-box), by preventing the propagation of the division property of -dimensional affine spaces. In the present paper, we show that this notion, which is rarely satisfied by vectorial functions, can be weakened while retaining the property that the S-boxes do not propagate the division property of -dimensional affine spaces. This leads us to the property that we name th-order -degree-sum-freedom, whose strength decreases when increases, and which coincides with th-order sum-freedom when . The condition for th-order -degree-sum-freedom is that, for every -dimensional affine space , there exists a non-negative integer of 2-weight at most such that . We show, for a general th-order -degree-sum-free function , that can always be taken smaller than or equal to under some reasonable condition on , and that it is larger than or equal to , where is the algebraic degree of . We also show two other lower bounds: one, that is often tighter, by means of the algebraic degree of the compositional inverse of when is a permutation, and another (valid for every vectorial function) by means of the algebraic degree of the indicator of the graph of the function. We study examples for (case in which corresponds to APNness) showing that finding of 2-weight 2 can be challenging, and we begin the study of power functions, for which we prove upper bounds. We study in particular the multiplicative inverse function (used as an S-box in the AES), for which we characterize the th-order -degree-sum-freedom by the coefficients of the subspace polynomials of -dimensional vector subspaces (deducing the exact value of when divides ) and we extend to th-order -degree-sum-freedom the result that it is th-order sum-free if and only if it is th-order sum-free
Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience
Get PDFMulti-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, allows processes to agree on a valid -bit value, despite faulty processes behaving maliciously. Among hash-based solutions for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol achieves optimal message complexity, (near-)optimal bit complexity, and optimal time complexity. However, it only tolerates up to adaptive failures. In contrast, the best known optimally resilient protocol, FIN-MVBA, exchanges messages and bits. This highlights a fundamental question: can a hash-based protocol be designed for the asynchronous setting with adaptive faults that simultaneously achieves both optimal complexity and optimal resilience?
In this paper, we take a significant step toward answering the question. Namely, we introduce Reducer, an MVBA protocol that retains HMVBA\u27s complexity while improving its resilience to . Unlike Reducer, Reducer++ does not rely on SMBA. Instead, it employs a novel approach involving hash functions modeled as random oracles to ensure termination. Reducer++ maintains constant time complexity, quadratic message complexity, and quasi-quadratic bit complexity, with constants dependent on
Computationally Efficient Asynchronous MPC with Linear Communication and Low Additive Overhead
Get PDFWe explore the setting of asynchronous multi-party computation (AMPC) with optimal resilience , and develop an efficient protocol that optimizes both communication and computation.
The recent work by Goyal, Liu-Zhang, and Song [Crypto\u27 24] was the first to achieve AMPC with amortized linear communication cost without using computationally heavy public-key cryptography. However, its additive communication overhead renders it impractical for most real-world applications.
It is possible to reduce the communication overhead significantly by leveraging cryptographic tools such as %random oracle hash,
homomorphic commitments, public-key cryptography, or zero-knowledge proofs; however, the corresponding AMPC protocols introduce computation overhead of public-key cryptographic operations that become bottleneck as grows. Overall, achieving AMPC with linear communication complexity, low additive communication overhead, and low computation overhead remains an open challenge.
In this work, we resolve this efficiency challenge by utilizing the random oracle model. By relying solely on computationally efficient primitives such as random oracle hash and symmetric-key cryptography, our protocol is not only efficient in terms of computation and communication overhead but also post-quantum secure. For a circuit with multiplication gates, our protocol achieves communication per multiplication gate with an additive overhead of communication. In terms of computation, our protocol only introduces an additive overhead of hash computations independent of the circuit size
Faster Proofs and VRFs from Isogenies
Get PDFWe improve recent generic proof systems for isogeny knowledge by Cong, Lai, Levin based on circuit satisfiability, by using radical isogeny descriptions to prove a path in the underlying isogeny graph. We then present a new generic construction for a verifiable random function (VRF) based on a one-more type hardness assumption and zero-knowledge proofs. We argue that isogenies fit the constraints of our construction and instantiate the VRF with a CGL walk and our new proofs. As a different contribution, we also propose a new VRF in the effective group action description of isogenies. Our protocol takes a novel approach based on the polynomial-in-the-exponent technique, but without the need of a trusted setup or heavy preprocessing. We compare our protocols to the current state-of-the-art isogeny VRFs by Leroux and Lai, with a particular emphasis on computational efficiency
General Functional Bootstrapping using CKKS
Get PDFThe Ducas-Micciancio (DM) and Chilotti-Gama-Georgieva-Izabachene (CGGI) cryptosystems provide a general privacy-preserving computation capability. These fully homomorphic encryption (FHE) cryptosystems can evaluate an arbitrary function expressed as a general look-up table (LUT) via the method of functional bootstrapping. The main limitation of DM/CGGI functional bootstrapping is its efficiency because this procedure has to bootstrap every encrypted number separately. A different bootstrapping approach, based on the Cheon-Kim-Kim-Song (CKKS) FHE scheme, can achieve much smaller amortized time due to its ability to bootstrap many thousands of numbers at once. However, CKKS does not currently provide a functional bootstrapping capability that can evaluate a general LUT. An open research question is whether such capability can be efficiently constructed. We give a positive answer to this question by proposing and implementing a general functional bootstrapping method based on CKKS-style bootstrapping. We devise a theoretical toolkit for evaluating an arbitrary function using the theory of trigonometric Hermite interpolations, which provides control over noise reduction during functional bootstrapping. Our experimental results for 8-bit LUT evaluation show that the proposed method achieves the amortized time of 0.72 milliseconds, which is three orders of magnitude faster than the DM/CGGI approach and 6.8x faster than (a more restrictive) amortized functional bootstrapping method based on the Brakerski/Fan-Vercauteren (BFV) FHE scheme
An Undetectable Watermark for Generative Image Models
Get PDFWe present the first undetectable watermarking scheme for generative image models. Undetectability ensures that no efficient adversary can distinguish between watermarked and un-watermarked images, even after making many adaptive queries. In particular, an undetectable watermark does not degrade image quality under any efficiently computable metric. Our scheme works by selecting the initial latents of a diffusion model using a pseudorandom error-correcting code (Christ and Gunn, 2024), a strategy which guarantees undetectability and robustness. We experimentally demonstrate that our watermarks are quality-preserving and robust using Stable Diffusion 2.1. Our experiments verify that, in contrast to every prior scheme we tested, our watermark does not degrade image quality. Our experiments also demonstrate robustness: existing watermark removal attacks fail to remove our watermark from images without significantly degrading the quality of the images. Finally, we find that we can robustly encode 512 bits in our watermark, and up to 2500 bits when the images are not subjected to watermark removal attacks. Our code is available at https://github.com/XuandongZhao/PRC-Watermark
MatriGear: Accelerating Authenticated Matrix Triple Generation with Scalable Prime Fields via Optimized HE Packing
Get PDFThe SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries. Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares called authenticated triples are generated. However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are required.
In this work, we propose a new protocol for the SPDZ offline phase, MatriGear, which improves upon the previous state-of-the-art construction, TopGear (Baum et al., SAC \u2719), and its variant for matrix triples (Chen et al., Asiacrypt \u2720). Our protocol aims to achieve a speedup in matrix triple generation and support for larger prime fields up to 4096 bits in size. To achieve this, we devise a variant of the BFV scheme and a new homomorphic matrix multiplication algorithm optimized for our purpose.
As a result, our protocol achieves about 3.6x speedup for generating scalar triples in a 1024-bit prime field and about 34x speedup for generating 128x128 matrix triples. In addition, we reduce the size of evaluation keys from 27.4 GB to 0.22 GB and the communication cost for MAC key generation from 816 MB to 16.6 MB
The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs
Get PDFThis paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs