IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Designs for practical SHE schemes based on Ring-LWR
Full text linkThe Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key. </p
Structured Encryption for Indirect Addressing
Full text linkThe Structured Encryption (StE) framework can be used to capture the encryption and querying of complex data structures on an honest-but-curious server. In this work, we introduce a new type of StE called indirectly addressed multimap encryption (IA-MME). We propose two IA-MME schemes: the layered multimaps approach which extends and generalizes the existing multimap chaining approach, and a novel technique called the single multimap approach which has comparable efficiency and strictly better security. We demonstrate that our formalisms simplify and modularize StE solutions for real-world use cases in searchable encryption and SQL databases, and provide simulations demonstrating that our IA-MME constructions lead to tangible efficiency and security gains on realistic data. As a part of our techniques, we identify and correct a technical error in prior constructions — providing greater insight into issues that can arise when composing StE schemes. </p
POBA: Privacy-Preserving Operator-Side Bookkeeping and Analytics
Full text linkMany user-centric applications face a common privacy problem: the need to collect, store, and analyze sensitive user data. Examples include check-in/check-out based payment systems for public transportation, charging/discharging electric vehicle batteries in smart grids, coalition loyalty programs, behavior-based car insurance, and more. We propose and evaluate a generic solution to this problem. More specifically, we provide a formal framework integrating privacy-preserving data collection, storage, and analysis, which can be used for many different application scenarios, present an instantiation, and perform an experimental evaluation of its practicality.We consider a setting where multiple operators (e.g., different mobility providers, different car manufacturers and insurance companies), who do not fully trust each other, intend to maintain and analyze data produced by the union of their user sets. The data is collected in an anonymous (wrt. all operators) but authenticated way and stored in so-called user logbooks. In order for the operators to be able to perform analyses at any time without requiring user interaction, the logbooks are kept on the operator\u27s side. Consequently, this potentially sensitive data must be protected from unauthorized access. To achieve this, we combine several selected cryptographic techniques, such as threshold signatures and oblivious RAM. The latter ensures that user anonymity is protected even against memory access pattern attacks.To the best of our knowledge, we provide and evaluate the first generic framework that combines data collection, operator-side data storage, and data analysis in a privacy-preserving manner, while providing a formal security model, a UC-secure protocol, and a full implementation. With three operators, our implementation can handle over two million new logbook entries per day. </p
Round-Efficient Adaptively Secure Threshold Signatures with Rewinding
Full text link A threshold signature scheme allows distributing a signing key to users, such that any of them can jointly sign, but any cannot. It is desirable to prove adaptive security of threshold signature schemes, which considers adversaries that can adaptively corrupt honest users even after interacting with them. For a class of signatures that relies on security proofs with rewinding, such as Schnorr signatures, proving adaptive security entails significant challenges. This work proposes two threshold signature schemes that are provably adaptively secure with rewinding proofs. Our proofs are solely in the random oracle model (ROM), without relying on the algebraic group model (AGM). - We give a 3-round scheme based on the algebraic one-more discrete logarithm (AOMDL) assumption. The scheme outputs a standard Schnorr signature. - We give a 2-round scheme based on the DL assumption. Signatures output by the scheme contain one more scalar than a Schnorr signature. We follow the recent work by Katsumata, Reichle, and Takemure (Crypto 2024) that proposed the first threshold signature scheme with a rewinding proof of full adaptive security. Their scheme is a 5-round threshold Schnorr scheme based on the DL assumption. Our results significantly improve the round complexity. The protocol by Katsumata, Reichle, and Takemure can be viewed as applying a masking technique to Sparkle, a threshold Schnorr signature scheme by Crites, Komlo, and Maller (Crypto 2023). This work shows wider applications of the masking technique. Our first scheme is obtained by masking FROST, a threshold Schnorr protocol by Komlo and Goldberg (SAC 2020). The second scheme is obtained by masking a threshold version of HBMS, a multi-signature scheme by Bellare and Dai (Asiacrypt 2021). Katsumata, Reichle, and Takemure masked Sparkle at the cost of 2 additional rounds. Our main insight is that this cost varies across schemes, especially depending on how to simulate signing in the security proofs. The cost is 1 extra round for our first scheme, and is 0 for our second scheme. </p
Round-Optimal Authenticated Key Exchange with Full Forward Privacy
Full text link Privacy-preserving authenticated key exchange (PPAKE) is a cryptographic protocol that enables two users to exchange a session key while protecting users\u27 privacy (i.e., hiding the user\u27s identity) against the machine-in-the-middle adversary. To hide user identities, PPAKE messages are broadcast to the network, increasing communication complexity. In ASIACRYPT2022, Lyu et al. introduced a concept of robustness to reduce communication complexity. Roughly, robust PPAKE allows receivers to decide whether it is the intended user by processing the first message with its long-term secret key. As a result, only the intended user replies to the first message, and thus, messages in the network are reduced. However, if a user\u27s secret key is leaked, an adversary can also use it to determine whether the past first message was intended for the user, and thus, the PPAKE scheme of Lyu et al. does not have full forward privacy. Lyu et al. leave an open problem of constructing a PPAKE scheme with robustness and full forward privacy. In this work, we solve this problem by introducing a new framework called key updatable PPAKE (kuPPAKE). In kuPPAKE schemes, a long-term secret key is updated so that the updated key does not work for past messages. Therefore, robustness no longer conflicts with full forward privacy. We propose a generic construction of a 2-round kuPPAKE and show a concrete scheme in the standard model from DH-style assumptions over bilinear groups. </p
On the security of two blind signatures from code equivalence problems
Full text linkThe Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography. They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions.With the community gaining confidence in the security of these problems, new variants of these problems have been introduced to achieve particular functionalities in advanced protocols or efficiency improvements. A natural question is then whether the problem variants are as secure as the original ones.In this work, we consider three problem variants of LCE or MCE. We first consider a variant based on LCE, and reduce it to the original LCE assumption. This problem was presented in a prior version of the blind signature scheme, proposed by Duong, Khuc, Qiao, Susilo and Zhang. Second, we analyse an MCE variant, MIMCE, proposed in the context of another blind signature scheme, by Kutcha, Legrow and Persichetti, and show that the parameters proposed are not sufficient to reach the claimed bit security. Finally, we consider a multi-sample version of MIMCE which we solve in polynomial time. </p
Updatable Private Set Intersection from Structured Encryption
Full text linkMany efficient custom protocols have been developed for two-party private set intersection (PSI), that allow the parties to learn the intersection of their private sets. However, these approaches do not yield efficient solutions in the dynamic setting when the parties\u27 sets evolve and the intersection has to be computed repeatedly. In this work we propose a new framework for this problem of updatable PSI — with elements being inserted and deleted — in the semi-honest model based on structured encryption. The framework reduces the problem of updatable PSI to a new variant of structured encryption (StE) for an updatable set datatype, which may be of independent interest. Our final construction is a constant round protocol with worst-case communication and computation complexity that grows linearly in the size of the updates and only poly-logarithmically with the size of the accumulated sets. Our protocol is the first to support arbitrary inserts and deletes for updatable PSI. </p
Return of the Kummer: a Toolbox for Genus-2 Cryptography
Full text link This work expands the machinery we have for isogeny-based cryptography in genus 2 by developing a toolbox of several essential algorithms for Kummer surfaces, the dimension-2 analogue of x-only arithmetic on elliptic curves. Kummer surfaces have been suggested in hyper-elliptic curve cryptography since at least the 1980s and recently these surfaces have reappeared to efficiently compute (2,2)-isogenies. We construct several essential analogues of techniques used in one-dimensional isogeny-based cryptography, such as pairings, deterministic point sampling and point compression and give an overview of (2,2)-isogenies on Kummer surfaces. We furthermore show how Scholten\u27s construction can be used to transform isogeny-based cryptography over elliptic curves over Fp2 into protocols over Kummer surfaces over Fp. As an example of this approach, we demonstrate that SQIsign verification can be performed completely on Kummer surfaces, and, therefore, that one-dimensional SQIsign verification can be viewed as a two-dimensional isogeny between products of elliptic curves, </p
Split-key PRFs and Extended Hybrid Security for KEM Combiners
Full text linkKey encapsulation mechanism (KEM) combiners allow for the construction of hybrid KEMs that are secure as long as at least one of several underlying ingredient KEMs remains secure. In PKC 2018, Giacon, Heuer, and Poettering showed that parallel KEM combiners whose core function is a split-key pseudorandom function (PRF) satisfy IND-CCA security if at least one of the ingredient KEMs satisfies IND-CCA security. However, their result assumes that public keys of the combined KEM are generated independently from any instances of the ingredient KEMs, which may not hold in real-world applications. To address this, we introduce a new security model which captures adversarial access to both the combined KEM and (post-processed versions of) the ingredient KEMs. We show that security in this extended model can still be achieved if at least one ingredient KEM satisfies IND-CCA security, the core function is a split-key PRF, and the ingredient KEM outputs are post-processed using standard PRFs. We consider an application of this approach to hybrid KEMs in the S/MIME secure email standard. We also provide a new construction for a split-key PRF, which uses a t-resilient extractor to output a string of truly random bits from an input in which the adversary controls t bits, and show that this split-key PRF construction is secure in the standard model. </p
Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators
Full text linkWe study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to the compactness of the digest, previously added values may require updated witnesses as the set grows.In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates. Specifically, we show that if the accumulator value has bit-length , where is the number of accumulated values, then some values must incur witness updates. This improves upon the recent lower bound of [BCCK25] and matches the upper bound in [MQ23].Building on the framework of [MQR22], we introduce a new combinatorial structure that removes the fixed-update-time assumption. Our approach also applies to Registration-based Encryption [GHMR18], thereby resolving the open problem left in [MQR22]: it shows that the tight lower bound on decryption-update frequency continues to hold even without any fixed-update-time assumption. </p