International Association
for Cryptologic Research

The Lightning Network (LN) is a second layer solution built on top of Bitcoin, aimed to solve Bitcoin's long transaction waiting times and high transaction fees. Empirical and theoretical studies show that the LN is tending towards the hub and spoke network topology. In this topology most of the nodes, the spokes, open a single channel to one of the few well-connected nodes, the hubs. This topology is known to be prone to failures, attacks, and privacy issues. In this work we introduce the Maypoles protocol in which most nodes open two channels instead of one. We show that this protocol benefits the network significantly by enhancing its stability, privacy, and resilience to attacks. We also examine the economic incentives of nodes to take part in Maypoles.

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order $p^3$ and exponent $p^2$ for certain exponentially large parameters. This implies an attack on SPDH-Sign, a signature scheme based on the SDLP, for such parameters. We also take a step toward proving the quantum polynomial time equivalence of SDLP and SCDH.

We survey various mathematical tools used in software works multiplying polynomials in $\mathbb{Z}_q [x] / ⟨x^n −αx−β⟩$. In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2.

There are three emphases in this paper: (i) modular arithmetic, (ii) homomorphisms, and (iii) vectorization. For modular arithmetic, we survey Montgomery, Barrett, and Plantard multiplications. For homomorphisms, we survey (a) various homomorphisms such as Cooley–Tukey FFT, Bruun’s FFT, Rader’s FFT, Karatsuba, and Toom– Cook; (b) various algebraic techniques for adjoining nice properties to the coefficient rings, including injections, Schönhage’s FFT, Nussbaumer’s FFT, and localization; and (c) various algebraic techniques related to the polynomial moduli, including twisting, composed multiplication, evaluation at ∞, Good–Thomas FFT, truncation, incomplete transformation, and Toeplitz matrix-vector product. For vectorization, we survey the relations between homomorphisms and the support of vector arithmetic. We then go through several case studies: We compare the implementations of modular multiplications used in Dilithium and Kyber, explain how the matrix-to-vector structure was exploited in Saber, and review the design choices of transformations for NTRU and NTRU Prime with vectorization. Finally, we outline several interesting implementation projects.

The Fiat-Shamir transform is a classical technique for turning any zero-knowledge $\Sigma$-protocol into a signature scheme.

In essence, the idea underlying this transform is that deriving the challenge from the digest of the commitment suppresses simulatability and hence provides non-interactive proofs of interaction.

It follows from that observation that if one wishes to preserve deniability the challenge size (per round) must be kept low. For instance in the original Fiat-Shamir protocol the authors recommend 18 bits but suggest that the challenge size can be made larger to reduce communication overhead, e.g. the value of 20 is proposed in \cite{micali}.

We show that even with relatively small challenge sizes \textsl{practical} deniability can be destroyed by having the verifier artificially impose upon himself the use of slowed-down hash function or by resorting to a trusted agency proposing an on-line deniability enforcement service against the provers community's will.

This paper presents 'KEM Sphinx', an enhanced version of the Sphinx packet format, designed to improve performance through modifications that increase packet header size. Unlike its predecessor, KEM Sphinx addresses performance limitations inherent in the original design, offering a solution that doubles processing speed. Our analysis extends to the adaptation of KEM Sphinx in a post-quantum cryptographic context, showing a transition with minimal performance degradation. The study concludes that the trade-off between increased size and improved speed and security is justifiable, especially in scenarios demanding higher performance. These findings suggest KEM Sphinx as a promising direction for efficient, secure communication protocols in an increasingly post-quantum cryptographic landscape.

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2(1+c)}\lfloor \frac{\log n}{\log 2}\rfloor-1$$ for $c>0$ fixed, then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{1}{1+c})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. In general, we show that all numbers of the form $2^n-1$ with carries of degree $$\kappa(2^n-1):=(\frac{1}{1+f(n)})\lfloor \frac{\log n}{\log 2}\rfloor-1$$ with $f(n)=o(\log n)$ and $f(n)\longrightarrow \infty$ as $n\longrightarrow \infty$ for $n\geq 4$ then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{2}{1+f(n)})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds.

Since 2015, there has been a significant decrease in the asymptotic complexity of computing discrete logarithms in finite fields. As a result, the key sizes of many mainstream pairing-friendly curves have to be updated to maintain the desired security level. In PKC'20, Guillevic conducted a comprehensive assessment of the security of a series of pairing-friendly curves with embedding degrees ranging from $9$ to $17$. In this paper, we focus on pairing-friendly curves with embedding degrees of 10 and 14. First, we extend the optimized formula of the optimal pairing on BW13-310, a 128-bit secure curve with a prime $p$ in 310 bits and embedding degree $13$, to our target curves. This generalization allows us to compute the optimal pairing in approximately $\log r/2\varphi(k)$ Miller iterations, where $r$ and $k$ are the order of pairing groups and the embedding degree respectively. Second, we develop optimized algorithms for cofactor multiplication for $\mathbb{G}_1$ and $\mathbb{G}_2$, as well as subgroup membership testing for $\mathbb{G}_2$ on these curves. Based on these theoretical results a new 128-bit secure curve emerges: BW14-351. Finally, we provide detailed performance comparisons between BW14-351 and other popular curves on a 64-bit platform in terms of pairing computation, hashing to $\mathbb{G}_1$ and $\mathbb{G}_2$, group exponentiations and subgroup membership testings. Our results demonstrate that BW14-351 is a strong candidate for building pairing-based cryptographic protocols.

In this paper, we show a new set of cryptographic primitives that generically leads to chosen ciphertext secure (CCA secure) public-key encryption (PKE). Specifically, we show how a (non-interactive, publicly verifiable) batch argument (BARG) for NP can be combined with a chosen plaintext secure PKE scheme to achieve a CCA secure one. The requirement of the succinctness of the proof size of a BARG in our result is rather mild: The proof size is $O(k^{\epsilon})$ for some non-negative constant $\epsilon < 1$ when the correctness of $k$ statements is simultaneously proved.

In this paper we propose a new hash-and-sign digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on the hardness of full-distance syndrome decoding. We propose parameter sets for three security levels (128-bits, 192-bits, and 256-bits) based on concrete estimations for hardness of the syndrome decoding problem and estimate the corresponding sizes of the keys and the signature for each level. The scheme has large public and private keys but very small signatures.

We optimize the number-theoretic transforms (NTTs) in Dilithium — a digital signature scheme recently standardized by the National Institute of Standards and Technology (NIST) — on Cortex-M3 and 8-bit AVR. The core novelty is the exploration of micro-architectural insights for modular multiplications. Recent work [Becker, Hwang, Kannwischer, Yang and Yang, Volume 2022 (1), Transactions on Cryptographic Hardware and Embedded Systems, 2022] found a correspondence between Montgomery and Barrett multiplications by relating modular reductions to integer approximations and demonstrated that Barrett multiplication is more favorable than Montgomery multiplication by absorbing the subtraction to the low multiplication. We first point out the benefit of Barrett multiplication when long and high multiplication instructions are unavailable, unusable, or slow. We then generalize the notion of integer approximations and improve the emulation of high multiplications used in Barrett multiplication.

Compared to the state-of-the-art assembly-optimized implementations on Cortex-M3, our constant-time NTT/iNTT are 1.38−1.51 times faster and our variable-time NTT/iNTT are 1.10−1.21 times faster. On our 8-bit AVR, we outperform Montgomery-based C implementations of NTT/iNTT by 6.37−7.27 times by simply switching to the proposed Barrett-based implementation. We additionally implement Barrett-based NTT/iNTT in assembly and obtain 14.10− 14.42 times faster code.

For the overall scheme, we provide speed-optimized implementations for Dilithium parameter sets dilithium2 and dilithium3 on Cortex-M3, and stack-optimized implementations for all parameter sets on Cortex-M3 and 8-bit AVR. We briefly compare the performance of speed-optimized dilithium3. Compared to the state-of-the-art assembly implementation on Cortex-M3, our assembly implementation reduces the key generation, signature generation, and signature verification cycles by 2.30%, 23.29%, and 0.69%. In the 8-bit AVR environment, our Barrett-based C implementation reduces the key generation, signature generation, and signature verification cycles by 45.09%, 56.80%, and 50.40%, respectively, and our assembly-optimized implementation reduces the cycles of each operation by 48.85%, 61.70%, and 55.08%, respectively.

In a recent ePrint, Brown and Monico propose new attacks on the tropical signature scheme of Chen, Grigoriev and Shpilrain. This note provides a new countermeasures against those attacks. Thereby, we (temporarily?) shift the fire from the signature algorithm to redirect attacks on the key and on tropical polynomial factorization.

The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in \mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. Previously, the best known algorithm for the SDLP was based on Kuperberg's subexponential time quantum algorithm. Still, the problem plays a central role in the security of certain proposed cryptosystems in the family of $\textit{semidirect product key exchange}$. This includes a recently proposed signature protocol called SPDH-Sign. In this paper, we show that the SDLP is even easier in some important special cases. Specifically, for a finite group $G$, we describe quantum algorithms for the SDLP in $G\rtimes \mathrm{Aut}(G)$ for the following two classes of instances: the first one is when $G$ is solvable and the second is when $G$ is a matrix group and a power of $\sigma$ with a polynomially small exponent is an inner automorphism of $G$. We further extend the results to groups composed of factors from these classes. A consequence is that SPDH-Sign and similar cryptosystems whose security assumption is based on the presumed hardness of the SDLP in the cases described above are insecure against quantum attacks. The quantum ingredients we rely on are not new: these are Shor's factoring and discrete logarithm algorithms and well-known generalizations.

This paper reviews common attacks in classical cryptography and plausible attacks in the post-quantum era targeted at CRYSTALS-Kyber. Kyber is a recently standardized post-quantum cryptography scheme that relies on the hardness of lattice problems. Although it has undergone rigorous testing by the National Institute of Standards and Technology (NIST), there have recently been studies that have successfully executed attacks against Kyber while showing their applicability outside of controlled settings. These include, but are not limited to, fault injections and side-channel attacks. This paper will discuss the effectiveness and details of common attacks, side-channel attacks, side-channel assisted chosen-ciphertext attacks, and fault-injection attacks, as well as possible defenses and their applicability against these attacks on Kyber. This paper aims to provide future researchers insight into what areas should be focused on to strengthen current as well as future cryptosystems. Some attacks discussed include chosen power analysis, timing attacks, primal and dual attacks on the underlying learning-with-errors problem, fault injections, and electromagnetic attacks.

While many modern cryptographic primitives have stood the test of time, attacker have already begun to expand their attacks beyond classical cryptanalysis by specifically targeting implementations. One of the most well-documented classes of such attacks are subversion (or substitution) attacks, where the attacker replaces the Implementation of the cryptographic primitive in an undetectable way such that the subverted implementation leaks sensitive information of the user during a protocol execution. The revelations of Snowden have shown that this is not only a dangerous theoretical attack, but an attack deployed by intelligence services. Several possible solutions for protection against these attacks are proposed in current literature. Among the most widely studied ones are cryptographic reverse firewalls that aim to actively remove the covert channel leaking the secret. While different protocols supporting such firewalls have been proposed, they do no guarantee security in the presence of concurrent runs. This situation was resolved by a recent work of Chakraborty et al. (EUROCRYPT 2022) that presented the first UC-model of such firewalls. Their model allows to provide security if a subverted party uses an honest firewall. However, using such a firewall also provides a possible new target for the attacker and in the case that an honest party uses a corrupted firewall, they were not able to prove any security guarantees. Furthermore, their model is quite complex and does not fit into the plain UC model. Hence, the authors needed to reprove fundamental theorems such as the composition theorem. Finally, the high complexity of their model also makes designing corresponding protocols a challenging task, as one also needs to reprove the security of the underlying protocol.

In this paper, we present a simpler model capturing cryptographic reverse firewalls in the plain UC model. The simplicity of our model allows to also reason about corrupted firewalls and still maintain strong security guarantees. Furthermore, we resolve the open question by Chakraborty et al. (EUROCRYPT 2022) and by Chakraborty et al. (EUROCRYPT 2023) and present the first direct UC-secure oblivious transfer protocol along with a cryptographic reverse firewall.

We design and implement GigaDORAM, a novel 3-server Distributed Oblivious Random Access Memory (DORAM) protocol. Oblivious RAM allows a client to read and write to memory on an untrusted server while ensuring the server itself learns nothing about the client's access pattern. Distributed Oblivious RAM (DORAM) allows a group of servers to efficiently access a secret-shared array at a secret-shared index.

A recent generation of DORAM implementations (e.g. FLORAM, DuORAM) has focused on building DORAM protocols based on Function Secret-Sharing (FSS). These protocols have low communication complexity and low round complexity but linear computational complexity of the servers. Thus, they work for moderate-size databases, but at a certain size, these FSS-based protocols become computationally inefficient.

In this work, we introduce GigaDORAM, a hierarchical-solution-based DORAM featuring poly-logarithmic computation and communication, but with an over $100\times$ reduction in rounds per query compared to previous hierarchical DORAM protocols. In our implementation, we show that for moderate to large databases where FSS-based solutions become computation-bound, our protocol is orders of magnitude more efficient than the best existing DORAM protocols. When $N = 2^{31}$, our DORAM is able to perform over 700 queries per second.

Homomorphic encryption (HE) enables computation on encrypted data, which in turn facilitates the outsourcing of computation on private data. However, HE offers no guarantee that the returned result was honestly computed by the cloud. In order to have such guarantee, it is necessary to add verifiable computation (VC) into the system.

The most efficient recent works in VC over HE focus on verifying operations on the ciphertext space of the HE scheme, which usually lacks the algebraic structure that would make it compatible with existing VC systems. For example, multiplication of ciphertexts in the current most efficient HE schemes requires non-algebraic operations such as real division and rounding. Therefore, existing works for VC over HE have to either give up on those efficient HE schemes, or incur a large overhead (an amount of constraints proportional to the ciphertext ring's size) in order to emulate these non-algebraic operations.

In this work, we move away from that paradigm by placing the verification checks in the plaintext space of HE, all while the prover remains computing on ciphertexts. We achieve this by introducing a general transformation for Interactive Oracle Proofs (IOPs) to work over HE, whose result we denote as HE-IOPs. We apply this same transformation to the FRI [Ben-Sasson et al., ICALP 2018] IOP of proximity and we show how to compile HE-Reed Solomon-encoded IOPs and HE-$\delta$-correlated-IOPs with HE-FRI into HE-IOPs.

Furthermore, our construction is compatible with a prover that provides input in zero-knowledge, and only relies on building blocks that are plausibly quantum-safe.

Aligning the security parameters of HE and FRI is a difficult task for which we introduce several optimizations. We demonstrate their efficiency with a proof-of-concept implementation in Python and show that, for an encrypted Reed Solomon codeword with degree bound $2^{11}$ and rate $1/16$ in a (plaintext) field of size $2^{256}$, we can run FRI's commit phase in just 43 minutes on a single thread on a c6i.metal instance (which could be reduced to less than a minute in a multi-threaded implementation in a large server). Verification takes less than 0.2 seconds, and, based on micro-benchmarks of the employed techniques, we show it could be up to 100 times faster in a fully optimized implementation.

Anonymous Zether, proposed by Bunz et al. (FC, 2020) and subsequently improved by Diamond (IEEE S&P, 2021) is an account-based confidential payment mechanism that works by using a smart contract to achieve privacy (i.e. identity of receivers to transactions and payloads are hidden). In this work, we look at simplifying the existing protocol while also achieving batching of transactions for multiple receivers, while ensuring consensus and forward secrecy. To the best of our knowledge, this work is the first to formally study the notion of forward secrecy in the setting of blockchain, borrowing a very popular and useful idea from the world of secure messaging. Specifically, we introduce: - FUL-Zether, a forward-secure version of Zether (Bunz et al., FC, 2020). - PRIvate DEcentralized Confidental Transactions (PriDe CT), a much-simplified version of Anonymous Zether that achieves competitive performance and enables batching of transactions for multiple receivers. - PRIvate DEcentralized Forward-secure Until Last update Confidential Transactions (PriDeFUL CT), a forward-secure version of PriDe CT. We also present an open-source, Ethereum-based implementation of our system. PriDe CT uses linear homomorphic encryption as Anonymous Zether but with simpler zero-knowledge proofs. PriDeFUL CT uses an updatable public key encryption scheme to achieve forward secrecy by introducing a new DDH-based construction in the standard model. In terms of transaction sizes, Quisquis (Asiacrypt, 2019), which is the only cryptocurrency that supports batchability (albeit in the UTXO model), has 15 times more group elements than PriDe CT. Meanwhile, for a ring of $N$ receivers, Anonymous Zether requires $6\log N$ more terms even without accounting for the ability to batch in PriDe CT. Further, our implementation indicates that, for $N=32$, even if there were 7 intended receivers, PriDe CT outperforms Anonymous Zether in proving time and gas consumption.

Predicate encryption (PE) is a type of public-key encryption that captures many useful primitives such as attribute-based encryption (ABE). Although much progress has been made to generically achieve security against chosen-plaintext attacks (CPA) efficiently, in practice, we also require security against chosen-ciphertext attacks (CCA). Because achieving CCA-security on a case-by-case basis is a complicated task, several generic conversion methods have been proposed, which typically target different subclasses of PE such as ciphertext-policy ABE. As is common, such conversion methods may sacrifice some efficiency. Notably, for ciphertext-policy ABE, all proposed generic transformations incur a significant decryption overhead. Furthermore, depending on the setting in which PE is used, we may also want to require that messages are signed. To do this, predicate signature schemes can be used. However, such schemes provide a strong notion of privacy for the signer, which may be stronger than necessary for some practical settings at the cost of efficiency.

In this work, we propose the notion of predicate extension, which transforms the predicate used in a PE scheme to include one additional attribute, in both the keys and the ciphertexts. Using predicate extension, we can generically obtain CCA-security and signatures from a CPA-secure PE scheme. For the CCA-security transform, we observe that predicate extension implies a two-step approach to achieving CCA-security. This insight broadens the applicability of existing transforms for specific subclasses of PE to cover all PE. We also propose a new transform that incurs slightly less overhead than existing transforms. Furthermore, we show that predicate extension allows us to create a new type of signatures, which we call PE-based signatures. PE-based signatures are weaker than typical predicate signatures in the sense that they do not provide privacy for the signer. Nevertheless, such signatures may be more suitable for some practical settings owing to their efficiency or reduced interactivity. Lastly, to show that predicate extensions may facilitate a more efficient way to achieve CCA-security generically than existing methods, we propose a novel predicate-extension transformation for a large class of pairing-based PE, covered by the pair and predicate encodings frameworks. In particular, this yields the most efficient generic CCA-conversion for ciphertext-policy ABE.

The succinct non-interactive argument of knowledge (SNARK) technique is widely used in blockchain systems to replace the costly on-chain computation with the verification of a succinct proof. However, when dealing with multiple proofs, most existing applications require each proof to be independently verified, resulting in a heavy load on nodes and high transaction fees for users. To improve the efficiency of verifying multiple proofs, we introduce SnarkFold, a universal SNARK-proof aggregation scheme based on incrementally verifiable computation (IVC). Unlike previous proof aggregation approaches based on inner product arguments, which have a logarithmic proof size and verification cost, SnarkFold achieves constant verification time and proof size. One core technical advance in SnarkFold, of independent interest, is the ``split IVC'': rather than using one running instance to fold/accumulate the computation, we employ two (or more) running instances of different types in the recursive circuit to avoid transferring into the same structure. This distinguishing feature is particularly well-suited for proof aggregation scenarios, as constructing arithmetic circuits for pairings can be expensive. We further demonstrate how to fold Groth16 proofs with our SnarkFold. With some further optimizations, SnarkFold achieves the highest efficiency among all approaches.

The Fiat-Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent constructions use it for multi-round protocols. However, in general the soundness error of the Fiat-Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of $(k_1,\dots,k_\mu)$-special-sound protocols the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal.

A natural next question is whether this positive result extends to the Fiat-Shamir transformation of so-called $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound protocols, a notion recently defined and analyzed in the interactive case, with the aim to capture the most general notion of special-soundness.

We show in this work that this is indeed the case. Concretely, we show that the Fiat--Shamir transformation of any $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound interactive proof is knowledge sound under the same condition under which the original interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random-oracle queries and independent of the number of rounds.

In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for $(k_1,\dots,k_\mu)$-special-sound protocols, which is based on an extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round analysis.