International Association
for Cryptologic Research

The privacy pass protocol allows users to redeem anonymously issued cryptographic tokens instead of solving annoying CAPTCHAs. The issuing authority verifies the credibility of the user, who can later use the pass while browsing the web using an anonymous or virtual private network. Hendrickson et al. proposed an IETF draft (privacypass-rate-limit-tokens-00) for a rate-limiting version of the privacy pass protocol, also called rate-limited Privacy Pass (RlP). Introducing a new actor called a mediator makes both versions inherently different. The mediator applies access policies to rate-limit users’ access to the service while, at the same time, should be oblivious to the website/origin the user is trying to access. In this paper, we formally define the rate-limited Privacy Pass protocol and propose a game-based security model to capture the informal security notions introduced by Hendrickson et al.. We show a construction from simple building blocks that fulfills our security definitions and even allows for a post-quantum secure instantiation. Interestingly, the instantiation proposed in the IETF draft is a specific case of our construction. Thus, we can reuse the security arguments for the generic construction and show that the version used in practice is secure.

Authenticated PIR enables a server to initially commit to a database of $N$ items, for which a client can later privately obtain individual items with complexity sublinear in $N$, with the added guarantee that the retrieved item is consistent with the committed database. A crucial requirement is privacy with abort, i.e., the server should not learn anything about a query even if it learns whether the client aborts.

This problem was recently considered by Colombo et al. (USENIX '23), who proposed solutions secure under the assumption that the database is committed to honestly. Here, we close this gap, and present a solution that tolerates fully malicious servers that provide potentially malformed commitments. Our scheme has communication and client computational complexity $\mathcal{O}_{\lambda}(\sqrt{N})$, solely relies on the DDH assumption, and does not introduce heavy machinery (e.g., generic succinct proofs). Privacy with abort holds provided the server succeeds in correctly answering $\lambda$ validation queries, which, from its perspective, are computationally indistinguishable from regular PIR queries. In fact, server side, our scheme is exactly the DDH-based scheme by Colombo et al.

The linear layer of block ciphers plays an important role in their security. In particular, ciphers designed following the wide-trail strategy use the branch number of the linear layer to derive bounds on the probability of linear and differential trails. At FSE 2014, the LS-design construction was introduced as a simple and regular structure to design bitsliced block ciphers. It considers the internal state as a bit matrix, and applies alternatively an identical S-Box on all the columns, and an identical L-Box on all the lines. Security bounds are derived from the branch number of the L-Box. In this paper, we focus on bitsliced linear layers inspired by the LS-design construction and the Spook AEAD algorithm. We study the construction of bitsliced linear transformations with efficient implementations using XORs and rotations (optimized for bitsliced ciphers implemented on 32-bit processors), and a high branch number. In order to increase the density of the activity patterns, the linear layer is designed on the whole state, rather than using multiple parallel copies of an L-Box. Our main result is a linear layer for 128-bit ciphers with branch number 21, improving upon the best 32-bit transformation with branch number 12, and the one of Spook with branch number 16.

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function.

Significant advances have been made affirmatively answering this question within the two-party setting, based on a variety of structures and hardness assumptions. In contrast, in the multi-party setting, only one general approach is known: using Fully Homomorphic Encryption (FHE). This remains the state of affairs even for just three parties, with two corruptions.

We present a framework for achieving secure sublinear-communication $(N+1)$-party computation, building from a particular form of Function Secret Sharing for only $N$ parties. In turn, we demonstrate implications to sublinear secure computation for various function classes in the 3-party and 5-party settings based on an assortment of assumptions not known to imply FHE.

This work describes an existential signature forgery vulnerability of the current CMS and PKCS#7 signature standards. The vulnerability results from an ambiguity of how to process the signed message in the signature verification process. Specifically, the absence or presence of the so called SignedAttributes field determines whether the signature message digest receives as input the message directly or the SignedAttributes, a DER-encoded structure which contains a digest of the message. If an attacker takes a CMS or PKCS#7 signed message M which was originally signed with SignedAttributes present, then he can craft a new message M 0 that was never signed by the signer and has the DER-encoded SignedAttributes of the original message as its content and verifies correctly against the original signature of M . Due to the limited flexibility of the forged message and the limited control the attacker has over it, the fraction of vulnerable systems must be assumed to be small but due to the wide deployment of the affected protocols, such instances cannot be excluded. We propose a countermeasure based on attack-detection that prevents the attack reliably.

Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. Motivated by this framework, several FHE-friendly symmetric-key primitives have been proposed since the publication of LowMC at EUROCRYPT 2015. To apply the transciphering framework to the CKKS scheme, a new transciphering framework called the Real-to-Finite-Field (RtF) framework and a corresponding FHE-friendly symmetric-key primitive called HERA were proposed at ASIACRYPT 2021. Although HERA has a very similar structure to AES, it is considerably different in the following aspects: 1) the power map $x\mapsto x^3$ is used as the S-box; 2) a randomized key schedule is used; 3) it is over a prime field $\mathbb F_p$ with $p>2^{16}$. In this work, we perform the first third-party cryptanalysis of HERA, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we find it possible to peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we could construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a result, for HERA with 192 and 256 bits of security, respectively, we could break some parameters under the same assumption made by designers that the algebra constant $\omega$ for Gaussian elimination is $\omega=2$, i.e., Gaussian elimination on an $n\times n$ matrix takes $\mathcal{O}(n^{\omega})$ field operations. If using more conservative choices like $\omega\in\{2.8,3\}$, our attacks can also successfully reduce the security margins of some variants of \hera to only 1 round. However, the security of HERA with 80 and 128 bits of security is not affected by our attacks due to the high cost to find multiple collisions. In any case, our attacks reveal a weakness of HERA caused by the randomized key schedule and its small state size.

Lasso (Setty, Thaler, Wahby, ePrint 2023/1216) is a recent lookup argument that ensures that the prover cryptographically commits to only "small" values. This note describes BabySpartan, a SNARK for a large class of constraint systems that achieves the same property. The SNARK is a simple combination of SuperSpartan and Lasso. The specific class of constraint systems supported is a generalization of so-called Plonkish constraint systems (and a special case of customizable constraint systems (CCS)). Whereas a recent work called Jolt (Arun, Setty, and Thaler, ePrint 2023/1217) can be viewed as an application of Lasso to uniform computation, BabySpartan can be viewed as applying Lasso to non-uniform computation.

We present a secret-key encryption scheme based on random rank metric ideal linear codes with a simple decryption circuit. It supports unlimited homomorphic additions and plaintext absorptions as well as a fixed arbitrary number of homomorphic multiplications.

We study a candidate bootstrapping algorithm that requires no multiplication but additions and plaintext absorptions only. This latter operation is therefore very efficient in our scheme, whereas bootstrapping is usually the main reason which penalizes the performance of other fully homomorphic encryption schemes. However, the security reduction of our scheme restricts the number of independent ciphertexts that can be published. In particular, this prevents to securely evaluate the bootstrapping algorithm as the number of ciphertexts in the key switching material is too large.

Our scheme is nonetheless the first somewhat homomorphic encryption scheme based on random ideal codes and a first step towards full homomorphism. Random ideal codes give stronger security guarantees as opposed to existing constructions based on highly structured codes. We give concrete parameters for our scheme that shows that it achieves competitive sizes and performance, with a key size of 3.7 kB and a ciphertext size of 0.9 kB when a single multiplication is allowed.

We explore a new pathway to designing unclonable cryptographic primitives. We propose a new notion called unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. Using UPO, we present modular (and in some cases, arguably, simple) constructions of many primitives in unclonable cryptography, including, public-key quantum money, quantum copy-protection for many classes of functionalities, unclonable encryption, and single-decryption encryption.

Notably, we obtain the following new results assuming the existence of UPO:

- We show that any cryptographic functionality can be copy-protected as long as this functionality satisfies a notion of security, which we term as puncturable security. Prior feasibility results focused on copy-protecting specific cryptographic functionalities.

- We show that copy-protection exists for any class of evasive functions as long as the associated distribution satisfies a preimage-sampleability condition. Prior works demonstrated copy-protection for point functions, which follows as a special case of our result.

- We show that unclonable encryption exists in the plain model. Prior works demonstrated feasibility results in the quantum random oracle model.

We put forward a candidate construction of UPO and prove two notions of security, each based on the existence of (post-quantum) sub-exponentially secure indistinguishability obfuscation and one-way functions, the quantum hardness of learning with errors, and a new conjecture called simultaneous inner product conjecture.

This paper presents a comprehensive analysis of the verification algorithm of the CRYSTALS-Dilithium, focusing on a C reference implementation. Limited research has been conducted on its susceptibility to fault attacks, despite its critical role in ensuring the scheme’s security. To fill this gap, we investigate three distinct fault models - randomizing faults, zeroizing faults, and skipping faults - to identify vulnerabilities within the verification process. Based on our analysis, we propose a methodology for forging CRYSTALS-Dilithium signatures without knowledge of the secret key. Instead, we leverage specific types of faults during the verification phase and some properties about public parameters to make these signatures accepted. Additionally, we compared different attack scenarios after identifying sensitive operations within the verification algorithm. The most effective requires potentially fewer fault injections than targeting the verification check itself. Finally, we introduce a set of countermeasures designed to thwart all the identified scenarios rendering the verification algorithm intrinsically resistant to the presented attacks.

The notion of ``efficiently testable circuits'' (ETC) was recently put forward by Baig et al.~(ITCS'23). Informally, an ETC compiler takes as input any Boolean circuit $C$ and outputs a circuit/inputs tuple $(C',\mathbb{T})$ where (completeness) $C'$ is functionally equivalent to $C$ and (security) if $C'$ is tampered in some restricted way, then this can be detected as $C'$ will err on at least one input in the small test set $\mathbb{T}$. The compiler of Baig et al. detects tampering even if the adversary can tamper with \emph{all} wires in the compiled circuit. Unfortunately, the model requires a strong ``conductivity'' restriction: the compiled circuit has gates with fan-out up to 3, but wires can only be tampered in one way even if they have fan-out greater than one. In this paper, we solve the main open question from their work and construct an ETC compiler without this conductivity restriction. While Baig et al. use gadgets computing the AND and OR of particular subsets of the wires, our compiler computes inner products with random vectors. We slightly relax their security notion and only require that tampering is detected with high probability over the choice of the randomness. Our compiler increases the size of the circuit by only a small constant factor. For a parameter $\lambda$ (think $\lambda\le 5$), the number of additional input and output wires is $|C|^{1/\lambda}$, while the number of test queries to detect an error with constant probability is around $2^{2\lambda}$.

A secret-shared shuffle (SSS) protocol permutes a secret-shared vector using a random secret permutation. It has found numerous applications, however, it is also an expensive operation and often a performance bottleneck. Chase et al. (Asiacrypt'20) recently proposed a highly efficient semi-honest two-party SSS protocol known as the CGP protocol. It utilizes purposely designed pseudorandom correlations that facilitate a communication-efficient online shuffle phase. That said, semi-honest security is insufficient in many real-world application scenarios since shuffle is usually used for highly sensitive applications. Considering this, recent works (CANS'21, NDSS'22) attempted to enhance the CGP protocol with malicious security over authenticated secret sharings. However, we find that these attempts are flawed, and malicious adversaries can still learn private information via malicious deviations. This is demonstrated with concrete attacks proposed in this paper. Then the question is how to fill the gap and design a malicious secure CGP shuffle protocol. We answer this question by introducing a set of lightweight correlation checks and a leakage reduction mechanism. Then we apply our techniques with authenticated secret sharings to achieve malicious security. Notably, our protocol, while increasing security, is also efficient. In the two-party setting, experiment results show that our maliciously secure protocol introduces an acceptable overhead compared to its semi-honest version and is more efficient than the state-of-the-art maliciously secure SSS protocol from the MP-SPDZ library.

A multisignature scheme is used to aggregate signatures by multiple parties on a common message $m$ into a single short signature on $m$. Multisignatures are used widely in practice, most notably, in proof-of-stake consensus protocols. In existing multisignature schemes, the verifier needs the public keys of all the signers in order to verify a multisignature issued by some subset of signers. We construct new practical multisignature schemes with three properties: (i) the verifier only needs to store a constant size public key in order to verify a multisignature by an arbitrary subset of parties, (ii) signature size is constant beyond the description of the signing set, and (iii) signers generate their secret signing keys locally, that is, without a distributed key generation protocol. Existing schemes satisfy properties (ii) and (iii). The new capability is property (i) which dramatically reduces the verifier's memory requirements from linear in the number of signers to constant. We give two pairing-based constructions: one in the random oracle model and one in the plain model. We also show that by relaxing property (iii), that is, allowing for a simple distributed key generation protocol, we can further improve efficiency while continuing to satisfy properties (i) and (ii). We give a pairing-based scheme and a lattice-based scheme in this relaxed model.

Traditional key stretching lacks a strict time guarantee due to the ease of parallelized password guessing by attackers. This paper introduces Sloth, a key stretching method leveraging the Secure Element (SE) commonly found in modern smartphones to provide a strict rate limit on password guessing. While this would be straightforward with full access to the SE, Android and iOS only provide a very limited API. Sloth utilizes the existing developer SE API and novel cryptographic constructions to build an effective rate-limit for password guessing on recent Android and iOS devices. Our approach ensures robust security even for short, randomly-generated, six-character alpha-numeric passwords against adversaries with virtually unlimited computing resources. Our solution is compatible with approximately 96% of iPhones and 45% of Android phones and Sloth seamlessly integrates without device or OS modifications, making it immediately usable by app developers today. We formally define the security of Sloth and evaluate its performance on various devices. Finally, we present HiddenSloth, a deniable encryption scheme, leveraging Sloth and the SE to withstand multi-snapshot adversaries.

This paper examines the vulnerabilities inherent in prevailing Public Key Infrastructure (PKI) systems reliant on centralized Certificate Authorities (CAs), wherein a compromise of the CA introduces risks to the integrity of public key management. We present PKChain, a decentralized and compromise-tolerant public key management system built on blockchain technology, offering transparent, tamper-resistant, and verifiable services for key operations such as registration, update, query, validation, and revocation. Our innovative approach involves a novel threshold block validation scheme that combines a novel threshold cryptographic scheme with blockchain consensus. This scheme allows each validator to validate each public key record partially and proactively secures it before inclusion in a block. Additionally, to further validate and verify each block and to facilitate public verification of the public key records, we introduce an aggregate commitment signature scheme. Our contribution extends to the development of a new, efficient, and practical Byzantine Compromise-Tolerant and Verifiable (pBCTV) consensus model, integrating the proposed validation and signature schemes with practical Byzantine Fault Tolerance (pBFT). Through a comprehensive examination encompassing security analysis, performance evaluation, and a prototype implementation, we substantiate that PKChain is a secure, efficient, and robust solution for public key management.

Let's consider a scenario where the server encrypts data using AES-CBC without authentication and then sends only the encrypted ciphertext through TLS (without IV). Then, having a padding oracle, we managed to recover the initialization vector and the sensitive data, doing a cybersecurity audit for a Chilean company.

The classic stable matching algorithm of Gale and Shapley (American Mathematical Monthly '69) and subsequent variants such as those by Roth (Mathematics of Operations Research '82) and Abdulkadiroglu et al. (American Economic Review '05) have been used successfully in a number of real-world scenarios, including the assignment of medical-school graduates to residency programs, New York City teenagers to high schools, and Norwegian and Singaporean students to schools and universities. However, all of these suffer from one shortcoming: in order to avoid strategic manipulation, they require all participants to submit their preferences to a trusted third party who performs the computation. In some sensitive application scenarios, there is no appropriate (or cost-effective) trusted party. This makes stable matching a natural candidate for secure computation. Several approaches have been proposed to overcome this, based on secure multiparty computation (MPC), fully homomorphic encryption, etc.; many of these protocols are slow and impractical for real-world use. We propose a novel primitive for privacy-preserving stable matching using MPC (i.e., arithmetic circuits, for any number of parties). Specifically, we discuss two variants of oblivious stable matching and describe an improved oblivious stable matching on the random memory access model based on lookup tables. To explore and showcase the practicality of our proposed primitive, we present detailed benchmarks (at various problem sizes) of our constructions using two popular frameworks: SCALE-MAMBA and MP-SPDZ.

Homomorphic Encryption (HE) schemes such as BGV, BFV, and CKKS consume some ciphertext modulus for each multiplication. Bootstrapping (BTS) restores the modulus and allows homomorphic computation to continue, but it is time-consuming and requires a significant amount of modulus. For these reasons, decreasing modulus consumption is crucial topic for BGV, BFV and CKKS, on which numerous studies have been conducted.

We propose a novel method, called $\mathsf{mult}^2$, to perform ciphertext multiplication in the CKKS scheme with lower modulus consumption. $\mathsf{mult}^2$ relies an a new decomposition of a ciphertext into a pair of ciphertexts that homomorphically performs a weak form of Euclidean division. It multiplies two ciphertexts in decomposed formats with homomorphic double precision multiplication, and its result approximately decrypts to the same value as does the ordinary CKKS multiplication. $\mathsf{mult}^2$ can perform homomorphic multiplication by consuming almost half of the modulus.

We extend it to $\mathsf{mult}^t$ for any $t\geq 2$, which relies on the decomposition of a ciphertext into $t$ components. All other CKKS operations can be equally performed on pair/tuple formats, leading to the double-CKKS (resp. tuple-CKKS) scheme enabling homomorphic double (resp. multiple) precision arithmetic.

As a result, when the ciphertext modulus and dimension are fixed, the proposed algorithms enable the evaluation of deeper circuits without bootstrapping, or allow to reduce the number of bootstrappings required for the evaluation of the same circuits. Furthermore, they can be used to increase the precision without increasing the parameters. For example, $\mathsf{mult}^2$ enables 8 sequential multiplications with 100 bit scaling factor with a ciphertext modulus of only 680 bits, which is impossible with the ordinary CKKS multiplication algorithm.

Event date: to
Submission deadline: 15 February 2024
Notification: 15 April 2024

Event date: 3 June to 7 June 2024
Submission deadline: 15 January 2024
Notification: 30 January 2024