International Association
for Cryptologic Research

This paper presents the first protocols for Proactive Secret Sharing (PSS) that only require constant (in the number of parties, $n$) communication per party per epoch. By harnessing the power of expander graphs, we are able to obtain strong guarantees about the security of the system. We present the following PSS protocols: – A PSS protocol that provides privacy (but no robustness) against an adversary controlling $O(n)$ parties per epoch. – A PSS protocol that provides robustness (but no privacy) against an adversary controlling $O(n)$ parties per epoch. – A PSS protocol that provides privacy against an adversary controlling $O(n^{a})$ parties per epoch and provides robustness against an adversary controlling $O(n^{1−a})$ parties per epoch, for any constant $0 \leq a \leq 1$. Instantiating this with $a = \frac{1}{2}$ gives a PSS protocol that is proactively secure (private and robust) against an adversary controlling $O(\sqrt{n})$ parties per epoch. Additionally, we discuss how secure channels, whose existence is usually assumed by PSS protocols, are challenging to create in the mobile adversary setting, and we present a method to instantiate them from a weaker assumption.

Constructing advanced cryptographic primitives such as obfuscation or broadcast encryption from standard hardness assumptions in the post quantum regime is an important area of research, which has met with limited success despite significant effort. It is therefore extremely important to find new, simple to state assumptions in this regime which can be used to fill this gap. An important step was taken recently by Wee (Eurocrypt '22) who identified two new assumptions from lattices, namely evasive ${\sf LWE}$ and tensor ${\sf LWE}$, and used these to construct broadcast encryption and ciphertext policy attribute based encryption for ${\sf P}$ with optimal parameters. Independently, Tsabary formulated a similar assumption and used it to construct witness encryption (Crypto '22). Following Wee's work, Vaikuntanathan, Wee and Wichs independently provided a construction of witness encryption (Asiacrypt '22).

In this work, we advance this line of research by providing the first construction of multi-input attribute based encryption (${\sf MIABE}$) for the function class ${\sf NC_1}$ for any constant arity from evasive ${\sf LWE}$. Our construction can be extended to support the function class ${\sf P}$ by using evasive and a suitable strengthening of tensor ${\sf LWE}$. In more detail, our construction supports $k$ encryptors, for any constant $k$, where each encryptor uses the master secret key ${\sf msk}$ to encode its input $(\mathbf{x}_i, m_i)$, the key generator computes a key ${\sf sk}_f$ for a function $f \in {\sf NC}_1$ and the decryptor can recover $(m_1,\ldots,m_k)$ if and only if $f(\mathbf{x}_1,\ldots,\mathbf{x}_k)=1$. The only known construction for ${\sf MIABE}$ for ${\sf NC}_1$ by Agrawal, Yadav and Yamada (Crypto '22) supports arity $2$ and relies on pairings in the generic group model (or with a non-standard knowledge assumption) in addition to ${\sf LWE}$. Furthermore, it is completely unclear how to go beyond arity $2$ using this approach due to the reliance on pairings.

Using a compiler from Agrawal, Yadav and Yamada (Crypto '22), our ${\sf MIABE}$ can be upgraded to multi-input predicate encryption for the same arity and function class. Thus, we obtain the first constructions for constant-arity predicate and attribute based encryption for a generalized class such as ${\sf NC}_1$ or ${\sf P}$ from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor ${\sf LWE}$ assumption can be reduced to standard ${\sf LWE}$ in an important special case which was not known before. This adds confidence to the plausibility of the assumption and may be of wider interest.

Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong.

Formally verifying complete proofs of attack performance is a natural response but crashes into an insurmountable structural problem: there are large gaps between the best proven cost among known attack algorithms and the best conjectured cost among known attack algorithms. Ignoring conjectured speedups would be a security disaster.

This paper presents a case study demonstrating the feasibility and value of successfully formalizing what state-of-the-art attack analyses actually do. The input to this formalization is not a proof, and the output is not a formally verified proof; the formalization process nevertheless enforces clear definitions, systematically accounts for all algorithm steps, simplifies review, improves reproducibility, and reduces the risk of error.

Concretely, this paper's CryptAttackTester (CAT) software includes formal specifications of (1) a general-purpose model of computation and cost metric, (2) various attack algorithms, and (3) formulas predicting the cost and success probability of each algorithm. The software includes general-purpose simulators that systematically compare the predictions to the observed attack behavior in the same model. The paper gives various examples of errors in the literature that survived typical informal testing practices and that would have been immediately caught if CAT-enforced links had been in place.

The case study in CAT is information-set decoding (ISD), the top attack strategy against the McEliece cryptosystem. CAT formalizes analyses of many ISD algorithms, covering interactions between (1) high-level search strategies from Prange, Lee–Brickell, Leon, Stern, Dumer, May–Meurer–Thomae, and Becker–Joux–May–Meurer; (2) random walks from Omura, Canteaut–Chabaud, Canteaut–Sendrier, and Bernstein–Lange–Peters; and (3) speedups in core subroutines such as linear algebra and sorting.

Account Abstraction is a powerful feature that will transform today Web3 onboarding UX. This notes describes an EVM (Ethereum Virtual Machine) implementation of the well known secp256r1 curves optimized for the specificities of the EVM environment. Our optimizations rely on EVM dedicated XYZZ elliptic coordinates system, hacked precomputations, and assembly tricks to cut from more than 1M to 200K/62K (with or withoutprecomputations)

In this work, we revisit the severely limited throughput problem of cryptocurrencies and propose a novel rebalancing approach for Payment Channel Networks (PCNs). PCNs are a popular solution for increasing the blockchain throughput, however, their benefit depends on the overall users’ liquidity. Rebalancing mechanisms are the state-of-the-art approach to maintaining high liquidity in PCNs. However, existing opt-in rebalancing mechanisms exclude users that may assist in rebalancing for small service fees, leading to suboptimal solutions and under-utilization of the PCNs’ bounded liquidity.

We introduce the first rebalancing approach for PCNs that includes all users, following an “all for one and one for all” design philosophy that yields optimal throughput. The proposed approach introduces a double-auction rebalancing problem, which we term Musketeer, where users can participate as buyers (paying fees to rebalance) or sellers (charging fees to route transactions). The desired properties tailored to the unique characteristics of PCNs are formally defined, including the novel property of cyclic budget balance that is a stronger variation of strong budget balance. Basic results derived from auction theory, including an impossibility and multiple mechanisms that either achieve all desiderata under a relaxed model or sacrifice one of the properties, are presented. We also propose a novel mechanism that leverages time delays as an additional cost to users. This mechanism is provably truthful, cyclic budget balanced, individually rational, and economic efficient but only with respect to liquidity.

First, the WESP encryption algorithm is defined. Encryptions are created by a system of equations in which the equations are generated using the values of tables that act as the encryption key. Next, it is shown that if the encryption tables are not known, the equations in the system of equations cannot be known, and it is demonstrated that the system of equations cannot be solved if the equations are not known, and thus the encryption cannot be broken in a closed form. Then, we calculate for all symbols used in the algorithm, the minimum amount of trials needed, in order to be able to verity the trials. Since the algorithm is constantly updating key values the verifying becomes impossible if equations are not evaluated in order. The calculation shows that the minimum number of trials required is such that the number of trials, i.e., the time required to break the encryption, increases exponentially as the key size grows. Since there is no upper limit on the key size there is neither any upper limit on the time it requires to break the encryption. It is also shown that the well-known mathematical "P vs NP" problem is solved by the presented proof. Since there is at least one algorithm (WESP) that is NP (verifiable in polynomial time) but not P (solvable in polynomial time), P cannot be the same set as NP.

Since the announcement of the NIST call for a new lightweight cryptographic standard, a lot of schemes have been proposed in response. Xoodyak is one of these schemes and is among the finalists of the NIST competition with a sponge structure very similar to the Keccak hash function – the winner of the SHA3 NIST competition. In this paper with conditional cube attack technique, we fully recover the key of Xoodyak reduced to 6 and 7 rounds with time complexity resp. 2^{42.58} and 2^{76.003} in the nonce-reusing scenario. In our attack setting, we import the cube variables in the absorbing associated data phase, which has higher degree of freedom in comparison to data absorption phase. We use MILP tool for finding enough cube variables to perform the conditional key recovery attack. The 6-round attack is practical and has been implemented. To the best of our knowledge, this is the first proposed attack on 7-round Xoodyak.

FPGAs have been used in the cloud since several years, as accelerators for various workloads such as machine learning, database processes and security tasks. As for other cloud services, a highly desired feature is virtualization in which multiple tenants can share a single FPGA to increase utilization and by that efficiency. By solely using standard FPGA logic in the untrusted tenant, on-chip logic sensors allow remote power analysis side-channel and covert channel attacks on the victim tenant. However, such sensors are implemented by unusual circuit constructions, such as ring oscillators, delay lines, or unusual interconnect configuration, which might be easily detected by bitstream and/or netlist checking. In this paper, we show that such structural checking methods are not universal solutions as the attacks can make use of any normal circuits, which mean they are ``benign-looking'' to any checking method. We indeed demonstrate that -- without any additional and suspicious implementation constraints -- standard circuits intended for legitimate tasks can be misused as a sensor thereby monitoring instantaneous power consumption, and hence conducting key-recovery attacks. This extremely stealthy attack is a threat that can originate from the application layers, i.e. through various high-level synthesis approaches.

Anonymous or attribute-based credential (ABC) systems are a versatile and important cryptographic tool to achieve strong access control guarantees while simultaneously respecting the privacy of individuals. A major problem in the practical adoption of ABCs is their transferability, i.e., such credentials can easily be duplicated, shared or lent. One way to counter this problem is to tie ABCs to biometric features of the credential holder and to require biometric verification on every use. While this is certainly not a viable solution for all ABC use-cases, there are relevant and timely use-cases, such as vaccination credentials as widely deployed during the COVID-19 pandemic. In such settings, ABCs that are tied to biometrics, which we call Biometric-Bound Attribute-Based Credentials (bb-ABC), allow to implement scalable and privacy-friendly systems to control physical access to (critical) infrastructure and facilities.

While there are some previous works on bb-ABC in the literature, the state of affairs is not satisfactory. Firstly, in existing work the problem is treated in a very abstract way when it comes to the actual type of biometrics. Thus, it does not provide concrete solutions which allow for assessing their practicality when deployed in a real-world setting. Secondly, there is no formal model which rigorously captures bb-ABC systems and their security requirements, making it hard to assess their security guarantees. With this work we overcome these limitations and provide a rigorous formalization of bb-ABC systems. Moreover, we introduce two generic constructions which offer different trade-offs between efficiency and trust assumptions, and provide benchmarks from a concrete instantiation of such a system using facial biometrics. The latter represents a contact-less biometric feature that provides acceptable accuracy and seems particularly suitable to the above use-case.

In recent years there has been much focus on the development of core cryptographic primitives based on lattice assumptions. This has been driven by the NIST call for post-quantum key encapsulation and digital signature specifications. However, there has been much less work on efficient privacy-preserving protocols with post-quantum security.

In this work we present an efficient electronic voting scheme from lattice assumptions, ensuring the long-term security of encrypted ballots and voters' privacy. The scheme relies on the NTRU and RLWE assumptions. We begin by conducting an extensive analysis of the concrete hardness of the NTRU problem. Extending the ternary-NTRU analysis of Ducas and van Woerden (ASIACRYPT 2021), we determine the concrete fatigue point of NTRU to be $q=0.0058\cdot\sigma^2\cdot d^{\: 2.484}$ (above which parameters become overstretched) for modulus $q$, ring dimension $d$, and secrets drawn from a Gaussian of parameter $\sigma$. Moreover, we demonstrate that the nature of this relation enables a more fine-grained choice of secret key sizes, leading to more efficient parameters in practice.

Using the above analysis, our second and main contribution is to significantly improve the efficiency of the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). Replacing the BGV encryption scheme with NTRU we obtain a factor $\times 5.3$ reduction in ciphertext size and $\times 2.6$ more efficient system overall, making the scheme suitable for use in real-world elections.

As an additional contribution, we analyse the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022). We note that the NTRU security is much lower than claimed and propose new parameters. This results in only a minor efficiency loss, enabled by our NTRU analysis where previous parameter selection techniques would have been much more detrimental.

Time-lock puzzles wrap a solution $\mathrm{s}$ inside a puzzle $\mathrm{P}$ in such a way that ``solving'' $\mathrm{P}$ to find $\mathrm{s}$ requires significantly more time than generating the pair $(\mathrm{s},\mathrm{P})$, even if the adversary has access to parallel computing; hence it can be thought of as sending a message $\mathrm{s}$ to the future. It is known [Mahmoody, Moran, Vadhan, Crypto'11] that when the source of hardness is only a random oracle, then any puzzle generator with $n$ queries can be (efficiently) broken by an adversary in $O(n)$ rounds of queries to the oracle.

In this work, we revisit time-lock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of time-lock puzzles solely from quantum (accessible) random oracles. In particular, for any $n$-query classical puzzle generator, our attack only asks $O(n)$ (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing.

Assuming perfect completeness, we also show how to make the above attack run in exactly $n$ rounds while asking a total of $m\cdot n$ queries where $m$ is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask $n-1$ rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from $\Omega(mn \log n)$ to $mn$. Finally, assuming perfect completeness, we present an attack in the ``dual'' setting in which the puzzle generator is quantum while the solver is classical.

We then ask whether one can extend our classical-query attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv'2009] is false, then there is indeed a time-lock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto'22] about key agreements (that can have interactions in both directions) to time-lock puzzles (that only include unidirectional communication).

Practical Identity Based Encryption (IBE) schemes use the costly bilinear pairing computation. Clifford Cock proposed an IBE based on quadratic residuosity in 2001 which does not use bilinear pairing but was not efficient in practice, due to the large ciphertext size. In 2007, Boneh et al. proposed the first space efficient IBE that was also based on quadratic residuosity problem. It was an improvement over Cock's scheme but still the time required for encryption was quartic in the security parameter. In this paper, we propose a compact, space and time efficient identity based encryption scheme without pairing, based on a variant of Paillier Cryptosystem and prove it to be CPA secure. We have also proposed a CCA secure scheme based on the basic IBE scheme using the Fujisaki-Okamoto transformation. We have proved both the schemes in the random oracle model.

Succinct arguments that rely on the Merkle-tree paradigm introduced by Kilian (STOC 92) suffer from larger proof sizes in practice due to the use of generic cryptographic primitives. In contrast, succinct arguments with the smallest proof sizes in practice exploit homomorphic commitments. However these latter are quantum insecure, unlike succinct arguments based on the Merkle-tree paradigm.

A recent line of works seeks to address this limitation, by constructing quantum-safe succinct arguments that exploit lattice-based commitments. The eventual goal is smaller proof sizes than those achieved via the Merkle-tree paradigm. Alas, known constructions lack succinct verification. In this paper, we construct the first interactive argument system for NP with succinct verification that, departing from the Merkle-tree paradigm, exploits the homomorphic properties of lattice-based commitments. For an arithmetic circuit with N gates, our construction achieves verification time polylog(N) based on the hardness of the Ring Short-Integer-Solution (RSIS) problem.

The core technique in our construction is a delegation protocol built from commitment schemes based on leveled bilinear modules, a new notion that we deem of independent interest. We show that leveled bilinear modules can be realized from pre-quantum and from post-quantum cryptographic assumptions.

We introduce QARMAvii, a redesign of the tweakable block cipher QARMA to provide more robust security bounds and allow for longer tweaks, while keeping very similar latency and area values. The longer tweaks serve to address specific use cases and facilitate the design of modes of operation with higher security bounds. This is achieved by adopting new key and tweak schedules, and by making some changes to the 128-bit versions, as well as by performing a deeper security analysis.

The resulting cipher offers competitive latency and area in HW implementations.

Some of our results may be of independent interest. This includes new MILP models of certain classes of diffusion matrices, the comparative analysis of a full reflection cipher against an iterative half-cipher, and our boomerang attack framework.

Given three positive integers $n

Integer-order Rényi entropies are synthetic indices useful for the characterization of probability distributions. In recent decades, numerous studies have been conducted to arrive at valid estimates of these indices starting from experimental data, so to derive a suitable classification method for the underlying processes. However, optimal solutions have not been reached yet. A one-line formula limited to the estimation of collision entropy is presented here. The results of some specific Monte Carlo experiments gave evidence of its validity even for the very low densities of the data spread in high-dimensional sample spaces. The strengths of this method are unbiased consistency, generality and minimum computational cost.

We present a new attack against the PSSI problem, one of the three problems at the root of security of Durandal, an efficient rank metric code-based signature scheme with a public key size of 15 kB and a signature size of 4 kB, presented at EUROCRYPT'19. Our attack recovers the private key using a leakage of information coming from several signatures produced with the same key. Our approach is to combine pairs of signatures and perform Cramer-like formulas in order to build subspaces containing a secret element. We break all existing parameters of Durandal: the two published sets of parameters claiming a security of 128 bits are broken in respectively $2^{66}$ and $2^{73}$ elementary bit operations, and the number of signatures required to finalize the attack is 1,792 and 4,096 respectively. We implemented our attack and ran experiments that demonstrated its success with smaller parameters.

In this work, we propose the notion of homomorphic indistinguishability obfuscation ($\mathsf{HiO}$) and present a construction based on subexponentially-secure $\mathsf{iO}$ and one-way functions. An $\mathsf{HiO}$ scheme allows us to convert an obfuscation of circuit $C$ to an obfuscation of $C'\circ C$, and this can be performed obliviously (that is, without knowing the circuit $C$). A naive solution would be to obfuscate $C' \circ \mathsf{iO}(C)$. However, if we do this for $k$ hops, then the size of the final obfuscation is exponential in $k$. $\mathsf{HiO}$ ensures that the size of the final obfuscation remains polynomial after repeated compositions. As an application, we show how to build function-hiding hierarchical multi-input functional encryption and homomorphic witness encryption using $\mathsf{HiO}$.

The duplex construction is already well analyzed with many papers proving its security in the random permutation model. However, so far, the first phase of the duplex, where the state is initialized with a secret key and an initialization vector ($\mathit{IV}$), is typically analyzed in a worst case manner. More detailed, it is always assumed that the adversary is allowed to choose the $\mathit{IV}$ on its will. In this paper, we analyze how the security changes if restrictions on the choice of the $\mathit{IV}$ are imposed, varying from the global nonce case over the random $\mathit{IV}$ case to the $\mathit{IV}$ on key case. The last one, in particular, is the duplex analogue of the use of a nonce masked with a secret in AES-GCM in TLS 1.3. We apply our findings to duplex-based encryption and authenticated encryption, and discuss the practical applications of our results.

In this paper, we present video-based cryptanalysis, a new method used to recover secret keys from a device by analyzing video footage of a device’s power LED. We show that cryptographic computations performed by the CPU change the power consumption of the device which affects the brightness of the device’s power LED. Based on this observation, we show how attackers can exploit commercial video cameras (e.g., an iPhone 13’s camera or Internet-connected security camera) to recover secret keys from devices. This is done by obtaining video footage of a device’s power LED (in which the frame is filled with the power LED) and exploiting the video camera’s rolling shutter to increase the sampling rate by three orders of magnitude from the FPS rate (60 measurements per second) to the rolling shutter speed (60K measurements per second in the iPhone 13 Pro Max). The frames of the video footage of the device’s power LED are analyzed in the RGB space, and the associated RGB values are used to recover the secret key by inducing the power consumption of the device from the RGB values. We demonstrate the application of video-based cryptanalysis by performing two side-channel cryptanalytic timing attacks and recover: (1) a 256- bit ECDSA key from a smart card by analyzing video footage of the power LED of a smart card reader via a hijacked Internet-connected security camera located 16 meters away from the smart card reader, and (2) a 378-bit SIKE key from a Samsung Galaxy S8 by analyzing video footage of the power LED of Logitech Z120 USB speakers that were connected to the same USB hub (that was used to charge the Galaxy S8) via an iPhone 13 Pro Max. Finally, we discuss countermeasures, limitations, and the future of video-based cryptanalysis in light of the expected improvements in video cameras’ specifications.