International Association
for Cryptologic Research

We address the problem of user fast revocation in the lattice based CP-ABE by extending the scheme originally introduced in [A ciphertext policy attribute-based encryption scheme without pairings. J. Zhang, Z. Zhang - ICISC 2011]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice based CP-ABE scheme, hence providing post-quantum safety. In particular, we rely on semi-trusted "mediators" to provide a multi-step decryption capable of handling mediation without re-encryption. We comment on the scheme and its application and we provide performance experiments on a prototype implementation in the ABE spin-off library of Palisade to evaluate the overhead compared with the original scheme.

Comparison of integers, a traditional topic in secure multiparty computation since Yao's pioneering work on "Millionaires' Problem" (FOCS 1982), is also well studied in card-based cryptography. For the problem, Miyahara et al. (Theoretical Computer Science, 2020) proposed a protocol using binary cards (i.e., cards with two kinds of symbols) that is highly efficient in terms of numbers of cards and shuffles, and its extension to number cards (i.e., cards with distinct symbols). In this paper, with a different design strategy which we name "Tug-of-War technique", we propose new protocols based on binary cards and on number cards. For binary cards, our protocol improves the previous protocol asymptotically (in bit lengths of input integers) in terms of numbers of cards and shuffles when adopting ternary encoding of input integers. For number cards, at the cost of increasing the number of cards, our protocol improves the number of shuffles of the previous protocol even with binary encoding, and more with $q$-ary encoding where $q > 2$.

The increase in leakage power from advanced tech nodes elevates the risk of static power side-channel (S-PSC) attacks. While protective measures exist, they involve a security cost trade-off. Hardware Trojans, particularly PSC-based ones, represent another significant threat. Despite acknowledging the link between static power leakage, advanced tech nodes, and vulnerability to S-PSC attacks, the role of the components at the heart of this sensitive interplay – the standard cells – has not been extensively studied in commercial-grade IC design. We analyze this relationship for commercial 28nm and 65nm nodes using a regular AES design. Our CAD framework permits design optimization while assessing S-PSC vulnerability. Contrary to the belief that high-performance designs are more vulnerable, we find timing constraints and threshold-voltage cell ratios are pivotal factors. Also, we discover that an attacker can deploy highly effective, stealthy PSC-based Trojans without any gate overheads or compromising timing paths.

Given $\ell$ parties with sets $X_1, \dots, X_\ell$ of size $n$, we would like to securely compute the intersection $\cap_{i=1}^\ell X_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $t$.

In this work, we construct protocols with a quasilinear dependency on $t$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $n-t$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $\mathcal{O}(\lambda \ell \cdot\mathrm{poly}(t))$, where $\lambda$ is the security parameter, and transforms it into a protocol with communication complexity $\mathcal{O}(\lambda^2 \ell t \cdot\mathrm{polylog}(t))$.

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions.

We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}(n + \log(1/\delta)\log\log(1/\delta))$ space and $\mathcal{O}(\log(\log(n)/\delta))$-wise independent hash functions.

As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is highly non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest.

A multilinear polynomial is a multivariate polynomial that is linear in each variable. This paper presents a scheme to commit to multilinear polynomials and to later prove evaluations of committed polynomials. The construction of the scheme is generic and relies on additively homomorphic schemes to commit to univariate polynomials. As the construction requires to check that several committed univariate polynomials do not exceed given, separate bounds, the paper also gives a method to batch executions of any degree-check protocol on homomorphic commitments. For a multilinear polynomial in n ≥ 2 variables, the instantiation of the scheme with a hiding version of KZG commitments (Kate, Zaverucha and Goldberg at Asiacrypt 2010) gives a pairing-based scheme with evaluations proofs in which the prover sends n + 3 first-group elements, performs at most 5 · 2n−1 + 1 first-group scalar multiplication and uses only n+2 random field elements to achieve the zero-knowledge property. Verification requires at most 2n + 2 first-group scalar multiplications, two second-group scalar multiplications and three pairing computations.

Payment channels allow a sender to do multiple transactions with a receiver without recording each single transaction on-chain. While most of the current constructions for payment channels focus on UTXO-based cryptocurrencies with reduced scripting capabilities (e.g., Bitcoin or Monero), little attention has been given to the possible benefits of adapting such constructions to cryptocurrencies based on the account model and offering a Turing complete language (e.g., Ethereum). The focus of this work is to implement efficient payment channels tailored to the capabilities of account-based cryptocurrencies with Turing-complete language support in order to provide scalable payments that are interoperable across different cryptocurrencies and unlinkable for third-parties (e.g., payment intermediaries). More concretely, we continue the line of research on cryptocurrency universal payment channels (UPC) which facilitate interoperable payment channel transactions across different ledgers in a hub-and-spoke model, by offering greater scalability than point-to-point architectures. Our design proposes two different versions, UPC and AUPC. For UPC we formally describe the protocol ideas sketched in previous work and evaluate our proof-of-concept implementation. Then, AUPC further extends the concept of universal payment channels by payment unlinkability against the intermediary server.

A Single Sign-On (SSO) system allows users to access different remote services while authenticating only once. SSO can greatly improve the usability and security of online activities by dispensing with the need to securely remember or store tens or hundreds of authentication secrets. On the downside, today's SSO providers can track users' online behavior, and collect personal data that service providers want to see asserted before letting a user access their resources.

In this work, we propose a new policy-based Single Sign-On service, i.e., a system that produces access tokens that are conditioned on the user's attributes fulfilling a specified policy. Our solution is based on multi-party computation and threshold cryptography, and generates access tokens of standardized format. The central idea is to distribute the role of the SSO provider among several entities, in order to shield user attributes and access patterns from each individual entity. We provide a formal security model and analysis in the Universal Composability framework, against proactive adversaries. Our implementation and benchmarking show the practicality of our system for many real-world use cases.

Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.

In this work, we study the question whether these strong idealized models are necessary for proving the security of ECDSA. Specifically, we focus on the programmability of ECDSA's "conversion function" which maps an elliptic curve point into its $x$-coordinate modulo the group order. Unfortunately, our main results are negative. We establish, by means of a meta reductions, that an algebraic security reduction for ECDSA can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for ECDSA is unlikely to exist without strong idealization.

Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modelled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ciphers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offers a lower security level against TMTO attacks than expected from the key sizes. We provide detailed analyses of the key update mechanisms in TLS 1.3 and Signal, illustrate the importance of ephemeral key exchange, and show that the process that DTLS 1.3 and QUIC use to calculate AEAD limits is flawed. We provide many concrete recommendations for the analyzed protocols.

It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis.

After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.

The current article describes our journey understanding Cisco ASA randomness issues through years, leading to CVE-2023-20107 [CVE-2023-20107, CSCvm90511]. More generally, it also provides technical and practical feedback on what can and cannot be done regarding entropy sources in association with DRBGs and other random processing mechanisms.

In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly symmetric-key primitives, the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. In this paper, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. We consider the nonlinearity, which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. The lower bound of the nonlinearity of a function $F:G\rightarrow H$ over an arbitrary finite Abelian group was first given by Pott in 2004. However, the result was restricted to the case that the size of $G$ divides the size of $H$ due to its connection to relative difference sets. We complete the generalization from $\mathbb{F}_2^n$ to finite Abelian groups and give the lower bound of $\lambda_F$ for all different cases. Our result is deduced by the new links that we established between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups.

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap $n$ LWE ciphertexts simultaneously, reducing the total cost from $\tilde{O}(n^2)$ to $\tilde{O}(3^\epsilon n^{1+\frac{1}{\epsilon}})$ for arbitrary $\epsilon > 0$. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping.

In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.

In this work, we focus on maliciously secure 3PC for binary circuits with honest majority. While the state-of-the-art (Boyle et al. CCS 2019) has already achieved the same amortized communication as the best-known semi-honest protocol (Araki et al. CCS 2016), they suffer from a large computation overhead: when comparing with the best-known implementation result (Furukawa et al. Eurocrypt 2017) which requires $9\times$ communication cost of Araki et al., the protocol by Boyle et al. is around $4.5\times$ slower than that of Furukawa et al.

In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation.

Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$.

Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.

Sampling random values from a discrete Gaussian distribution with high precision is a major and computationally intensive operation of upcoming or existing cryptographic standards. FALCON is one such algorithm that the National Institute of Standards and Technology chose to standardize as a next-generation, quantum-secure digital signature algorithm. The discrete Gaussian sampling of FALCON has both flexibility and efficiency needs—it constitutes 72% of total signature generation in reference software and requires sampling from a variable mean and standard deviation. Unfortunately, there are no prior works on accelerating this complete sampling procedure. In this paper, we propose a hardware-software co-design for accelerating FALCON’s discrete Gaussian sampling subroutine. The proposed solution handles the flexible computations for setting the variable parameters in software and executes core operations with low latency, parameterized, and custom hardware. The hardware parameterization allows trading off area vs. performance. On a Xilinx SoC FPGA Architecture, the results show that compared to the reference software, our solution can accelerate the sampling up to 9.83× and the full signature scheme by 2.7×. Moreover, we quantified that our optimized multiplier circuits can improve the throughput over a straightforward implementation by 60%.

A succinct zero knowledge proof for regular language mem- bership, i.e., to prove a secret string behind an encryption (hash) belongs to a regular language is useful, e.g., for asserting that an encrypted email is free of malware. The great challenge in practice is that the regular language used is often huge. We present zkreg, a distributed commit- and-prove system that handles such complexity. In zkreg, cryptographic operations are encoded using arithmetic circuits, and input acceptance is modeled as a zero knowledge subset problem using Σ-protocols. We in- troduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects Σ-protocols and the Groth16 system with O(1) proof size and verifier cost. We present a close-to-optimal univariate instantiation of zk-VPD, a zero knowledge variation of the KZG polynomial commitment scheme, based on which an efficient zk-subset protocol is developed. We develop a 2-phase proof scheme to further exploit the locality of Aho-Corasick automata. To demonstrate the performance and scalability of zkreg, we prove that all ELF files (encrypted and hashed) in a Linux CentOS 7 are malware free. Applying inner pairing product argument, we obtain an aggregated proof of 1.96 MB which can be verified in 6.5 seconds.

We present a new, simple candidate broadcast encryption scheme for $N$ users with parameter size poly$(\log N)$. We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images, while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.

A decade of active research has led to practical constructions of zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) that are now being used in a wide variety of applications. Despite this astonishing progress, overheads in proof generation time remain significant.

In this work, we envision a world where consumers with low computational resources can outsource the task of proof generation to a group of untrusted servers in a privacy-preserving manner. The main requirement is that these servers should be able to collectively generate proofs at a faster speed (than the consumer). Towards this goal, we introduce a framework called zk-SNARKs-as-a-service ($\mathsf{zkSaaS}$) for faster computation of zk-SNARKs. Our framework allows for distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover. Moreover, the privacy of the prover's witness is ensured against any minority of colluding servers.

We design custom protocols in this framework that can be used to obtain faster runtimes for widely used zk-SNARKs, such as Groth16 [EUROCRYPT 2016], Marlin [EUROCRYPT 2020], and Plonk [EPRINT 2019]. We implement proof of concept zkSaaS for the Groth16 and Plonk provers. In comparison to generating these proofs on commodity hardware, we show that not only can we generate proofs for a larger number of constraints (without memory exhaustion), but can also get $\approx 22\times$ speed-up when run with 128 parties for $2^{25}$ constraints with Groth16 and $2^{21}$ gates with Plonk.

A fundamental result in classical cryptography is that pseudorandom generators are equivalent to one-way functions and in fact implied by nearly every classical cryptographic primitive requiring computational assumptions. In this work, we consider a variant of pseudorandom generators called quantum pseudorandom generators (QPRGs), which are quantum algorithms that (pseudo)deterministically map short random seeds to long pseudorandom strings. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes.

Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.

Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.

In this paper, we study oblivious key-value stores (OKVS) that enable encoding n key-value pairs into length $m$ encodings while hiding the input keys. The goal is to obtain high rate, $n/m$, with efficient encoding and decoding algorithms. We present $\mathsf{RB\text{-}OKVS}$ built on random band matrices that obtains near-optimal rates as high as 0.97 whereas prior works could only achieve rates up to 0.81 with similar encoding times.

Using $\mathsf{RB\text{-}OKVS}$, we obtain state-of-the-art protocols for private set intersection (PSI) and union (PSU). Our semi-honest PSI has up to 12% smaller communication and 13% reductions in monetary cost with slightly larger computation. We also obtain similar improvements for both malicious and circuit PSI. For PSU, our protocol obtains improvements of up to 22% in communication, 40% in computation and 21% in monetary cost. In general, we obtain the most communication- and cost-efficient protocols for all the above primitives.

Finally, we present the first connection between OKVS and volume-hiding encrypted multi-maps (VH-EMM) where the goal is to outsource storage of multi-maps while hiding the number of values associated with each key (i.e., volume). We present $\mathsf{RB\text{-}MM}$ with 16% smaller storage, 5x faster queries and 8x faster setup than prior works.