Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Understanding the new distinguisher of alternant codes at degree 2
Get PDFDistinguishing Goppa codes or alternant codes from generic
linear codes [FGO+11] has been shown to be a first step before being
able to attack McEliece cryptosystem based on those codes [BMT24].
Whereas the distinguisher of [FGO+11] is only able to distinguish Goppa
codes or alternant codes of rate very close to 1, in [CMT23a] a much more
powerful (and more general) distinguisher was proposed. It is based on
computing the Hilbert series of a Pfaffian modeling.
The distinguisher of [FGO+11] can be interpreted as computing .
Computing still gives a polynomial time distinguisher for alternant
or Goppa codes and is apparently able to distinguish Goppa or alternant
codes in a much broader regime of rates as the one of [FGO+11]. However,
the scope of this distinguisher was unclear. We give here a formula for
corresponding to generic alternant codes when the field size
satisfies , where r is the degree of the alternant code. We also
show that this expression for provides a lower bound in general.
The value of corresponding to random linear codes is known and
this yields a precise description of the new regime of rates that can be
distinguished by this new method. This shows that the new distinguisher
improves significantly upon the one given in [FGO+11]
New Techniques for Analyzing Fully Secure Protocols: A Case Study of Solitary Output Secure Computation
Get PDFSolitary output secure computation allows a set of mutually distrustful parties to compute a function of their inputs such that only a designated party obtains the output. Such computations should satisfy various security properties such as correctness, privacy, independence of inputs, and even guaranteed output delivery. We are interested in full security, which captures all of these properties. Solitary output secure computation has been the study of many papers in recent years, as it captures many real-world scenarios.
A systematic study of fully secure solitary output computation was initiated by Halevi et al. [TCC 2019]. They showed several positive and negative results, however, they did not characterize what functions can be computed with full security. Alon et al. [EUROCRYPT 2024] considered the special, yet important case, of three parties with Boolean output, where the output-receiving party has no input. They completely characterized the set of such functionalities that can be computed with full security. Interestingly, they also showed a possible connection with the seemingly unrelated notion of fairness, where either all parties obtain the output or none of them do.
We continue this line of investigation and study the set of three-party solitary output Boolean functionalities where all parties hold private inputs. Our main contribution is defining and analyzing a family of ``special-round\u27\u27 protocols, which generalizes the set of previously proposed protocols. Our techniques allow us to identify which special-round protocols securely compute a given functionality (if such exists). Interestingly, our analysis can also be applied in the two-party setting (where fairness is an issue). Thus, we believe that our techniques may prove useful in additional settings and deepen our understanding of the connections between the various settings
Registration-Based Encryption in the Plain Model
Get PDFRegistration-based encryption (RBE) is a recently developed alternative to identity-based encryption, that mitigates the well-known key-escrow problem by letting each user sample its own key pair. In RBE, the key authority is substituted by a key curator, a completely transparent entity whose only job is to reliably aggregate users\u27 keys. However, one limitation of all known RBE scheme is that they all rely on one-time trusted setup, that must be computed honestly.
In this work, we ask whether this limitation is indeed inherent and we initiate the systematic study of RBE in the plain model, without any common reference string. We present the following main results:
- (Definitions) We show that the standard security definition of RBE is unachievable without a trusted setup and we propose a slight weakening, where one honest user is required to be registered in the system.
- (Constructions) We present constructions of RBE in the plain model, based on standard cryptographic assumptions. Along the way, we introduce the notions of non-interactive witness indistinguishable (NIWI) proofs secure against chosen statements attack and re-randomizable RBE, which may be of independent interest.
A major limitation of our constructions, is that users must be updated upon every new registration.
- (Lower Bounds) We show that this limitation is in some sense inherent. We prove that any RBE in the plain model that satisfies a certain structural requirement, which holds for all known RBE constructions, must update all but a vanishing fraction of the users, upon each new registration. This is in contrast with the standard RBE settings, where users receive a logarithmic amount of updates throughout the lifetime of the system
On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations
Get PDFOne-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC\u2720). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open.
We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is , solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions
Adaptively Secure Threshold Blind BLS Signatures and Threshold Oblivious PRF
Get PDFWe show the first threshold blind signature scheme and threshold Oblivious PRF (OPRF) scheme which remain secure in the presence of an adaptive adversary, who can adaptively decide which parties to corrupt throughout the lifetime of the scheme. Moreover, our adaptively secure schemes preserve the minimal round complexity and add only a small computational overhead over prior solutions that offered security only for a much less realistic static adversary, who must choose the subset of corrupted parties before initializing the protocol.
Our threshold blind signature scheme computes standard BLS signatures while our threshold OPRF computes a very efficient 2HashDH OPRF [JKK14]. We prove adaptive security of both schemes in the Algebraic Group Model (AGM). Our adaptively secure threshold schemes are as practical as the underlying standard single-server BLS blind signature and 2HashDH OPRF, and they can be used to add cryptographic fault-tolerance and decentralize trust in any system that relies on blind signatures, like anonymous credentials and e-cash, or on OPRF, like the OPAQUE password authentication and the Privacy Pass anonymous authentication scheme, among many others
SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields
Get PDFPoly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today\u27s computer architectures and applications? To answer this question, we gather and systematize a body of knowledge concerning polynomial hash design and implementation that is spread across research papers, cryptographic libraries, and developers\u27 blogs. We develop a framework to automate the validation and benchmarking of the ideas that we collect. This approach leads us to five new candidate designs for polynomial hash functions. Using our framework, we generate and evaluate different implementations and optimization strategies for each candidate. We obtain substantial improvements over Poly1305 in terms of security and performance. Besides laying out the rationale behind our new designs, our paper serves as a reference for efficiently implementing polynomial hash functions, including Poly1305
Achieving Data Reconstruction Hardness and Efficient Computation in Multiparty Minimax Training
Get PDFGenerative models have achieved remarkable success in a wide range of applications. Training such models using proprietary data from multiple parties has been studied in the realm of federated learning. Yet recent studies showed that reconstruction of authentic training data can be achieved in such settings.
On the other hand, multiparty computation (MPC) guarantees standard data privacy, yet scales poorly for training generative models.
In this paper, we focus on improving reconstruction hardness during Generative Adversarial Network (GAN) training while keeping the training cost tractable. To this end, we explore two training protocols that use a public generator and an MPC discriminator: Protocol 1 (P1) uses a fully private discriminator, while Protocol 2 (P2) privatizes the first three discriminator layers. We prove reconstruction hardness for P1 and P2 by showing that (1) a public generator does not allow recovery of authentic training data, as long as the first two layers of the discriminator are private; and through an existing approximation hardness result on ReLU networks, (2) a discriminator with at least three private layers does not allow authentic data reconstruction with algorithms polynomial in network depth and size. We show empirically that compared with fully MPC training, P1 reduces the training time by and P2 further by
Ciphertext-Ciphertext Matrix Multiplication: Fast for Large Matrices
Get PDFMatrix multiplication of two encrypted matrices (CC-MM) is a key challenge for privacy-preserving machine learning applications. As modern machine learning models focus on scalability, fast CC-MM on large datasets is increasingly in demand.
In this work, we present a CC-MM algorithm for large matrices. The algorithm consists of plaintext matrix multiplications (PP-MM) and ciphertext matrix transpose algorithms (C-MT). We propose a fast C-MT algorithm, which is computationally inexpensive compared to PP-MM. By leveraging high-performance BLAS libraries to optimize PP-MM, we implement large-scale CC-MM with substantial performance improvements. Furthermore, we propose lightweight algorithms, significantly reducing the key size from MB to MB for CC-MM with comparable efficiency.
In a single-thread implementation, the C-MT algorithm takes seconds to transpose a encrypted matrix. The CC-MM algorithm requires seconds to multiply two encrypted matrices. For large matrices, our algorithm outperforms the state-of-the-art CC-MM method from Jiang-Kim-Lauter-Song [CCS\u2718] by a factor of over
Breaking Parallel ROS: Implication for Isogeny and Lattice-based Blind Signatures
Get PDFMany of the three-round blind signatures based on identification protocols are only proven to be -concurrently unforgeable for . It was only recently shown in a seminal work by Benhamouda et al. (EUROCRYPT\u2721) that this is not just a limitation of the proof technique. They proposed an elegant polynomial time attack against the -concurrently unforgeability of the classical blind Schnorr protocol for .
However, there are still many blind signatures following a similar recipe to blind Schnorr where the attack by Benhamouda et al. does not apply. This includes for instance the isogeny-based blind signature CSI-Otter by Katsumata et al (CRYPTO\u2723), the lattice-based blind signatures Blaze+ by Alkeilani et al. (ACISP\u2720) and BlindOR by Alkeilani et al. (CANS\u2720).
In this work, we provide a simple and novel attack on blind signatures based on identification protocols performing parallel repetition to reduce the soundness error. Our attack translates to a polynomial time break for the -concurrent unforgeability of CSI-Otter, Blaze+, and BlindOR for .
More formally, we define an intermediate problem called Parallel Random inhomogeneities in an Overdetermined Solvable system of linear equations (pROS) problem and show that an attack against pROS implies an attack to the above blind signatures.
One takeaway of our finding is that while parallel repetition allows to exponentially reduce the soundness error of an identification protocol, this has minimal effect on the resulting blind signature. Our attack is concretely very efficient and for instance breaks -concurrent unforgeability of CSI-Otter in time roughly hash computations
Signature-Free Atomic Broadcast with Optimal Messages and Expected Time
Get PDFByzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first information-theoretic (IT) and signature-free asynchronous ABC protocol that achieves optimal messages and expected time. Our ABC protocol adopts a new design, relying on a reduction from---perhaps surprisingly---a somewhat neglected primitive called multivalued Byzantine agreement (MBA)