International Association
for Cryptologic Research

We argue that for all integers $N \geq 2$ and $g \geq 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k, \ldots, N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k \geq 2$. The formulae are complete: each iteration involves the extraction of $g(g+1)/2$ different $N$th roots (whence the epithet multiradical) and by varying which roots are chosen one computes all $N^{g(g+1)/2}$ extensions to an $(N^k, \ldots, N^k)$-isogeny of the incoming $(N^{k-1}, \ldots, N^{k-1})$-isogeny. Our argumentation is heuristic, but we provide concrete formulae for several prominent families. As our main application, we illustrate the use of multiradical isogenies by implementing a hash function from $(3,3)$-isogenies between Jacobians of superspecial genus-$2$ curves, showing that it outperforms its $(2,2)$-counterpart by an asymptotic factor $\approx 9$ in terms of speed.

The isogeny-based post-quantum schemes SIKE (NIST PQC round 3 alternate candidate) and CSIDH (Asiacrypt 2018) have received only little attention with respect to their fault attack resilience so far. We aim to fill this gap and provide a better understanding of their vulnerability by analyzing their resistance towards safe-error attacks. We present four safe-error attacks, two against SIKE and two against a constant-time implementation of CSIDH that uses dummy isogenies. The attacks use targeted bitflips during the respective isogeny-graph traversals. All four attacks lead to full key recovery. By using voltage and clock glitching, we physically carried out two of the attacks - one against each scheme -, thus demonstrate that full key recovery is also possible in practice.

The 2021 election is being held to fill the three IACR Director positions currently held by Mark Fischlin, Nadia Heninger and Anna Lysyanskaya, whose 3-year terms are ending.

Nominations are due by October 1st, 2021.
Information about nomination is available at https://iacr.org/elections/2021/announcement.html.

Multi-Key fully homomorphic encryption (MKFHE) allows computation on data encrypted under different and independent keys. The previous researches show that the ciphertext size of MKFHE scheme usually increases linearly or squarely with the number of parties, which restricts the application of the MKFHE scheme. In this paper, we propose a general construction of MKFHE scheme with compact ciphertext. Firstly, we construct the accumulated public key of the parties set with compact by accumulating every party’s public key under the CRS model. Secondly, all parties provide the ciphertext of their secret keys key which is encrypted by the accumulated public-key as the accumulated evaluation key. Thirdly, we run the bootstrapping process (or key switching process) on each party's ciphertext and accumulated evaluation key to refresh the ciphertext. Finally, We homomorphically calculate the refreshed ciphertext and decrypt it by the joint secret key. Furthermore, according to the advantages of TFHE-type scheme’s efficient bootstrapping and CKKS scheme supporting approximate data homomorphic computation, we improve the bootstrapping in our general scheme and specifically propose two efficient MKFHE schemes with compact ciphertext. Our work has two advantages. The one is that the ciphertext size of the proposed general scheme is independent of the number of parties, and the homomorphic computation is as efficient as the single-party full homomorphic encryption scheme. When the parties' set is updated, the ciphertext of the original set can continue to be used for homomorphic computation of the new parties' set after refreshed. Another advantage is that only by authorization can a party’s data be used in the homomorphic operation of a set, i.e., all parties need to regenerate their accumulated evaluation key with the set. Compared with the fully dynamic MKFHE scheme, the authorized MKFHE scheme we proposed supports parties to effectively control which set their data.

Here we consider a method for quickly testing for group membership in the groups $\G_1$, $\G_2$ and $\G_T$ (all of prime order $r$) as they arise on a type-3 pairing-friendly curve. As is well known endomorphisms exist for each of these groups which allows for faster point multiplication for elements of order $r$. The endomorphism applies if an element is of order $r$. Here we show that, under relatively mild conditions, the endomorphism applies {\bf if and only if} an element is of order $r$. This results in a faster method of confirming group membership. In particular we show that the conditions are met for the popular BLS family of curves.

In this paper, the authors construct a new type of cryptographic sequence which is named an extra-super increasing sequence, and give the definitions of the minimal super increasing sequence {a[1], a[2], ..., a[n]} and minimal extra-super increasing sequence {z[1], z[2], ..., z[n]}. Prove that the minimal extra-super increasing sequence is the odd-positioned subsequence of the Fibonacci sequence, namely {z[1], z[2], ..., z[n], ...} = {F[1], F[3], ..., F[2n-1], ...}, which indicates that the approach to the golden ratio phi through the difference (z[n+1] / z[n] - 1]) is more smooth and expeditious than through the ratio (F[n+1] / F[n]). Further prove that the limit of the term ratio difference between the two cryptographic sequences equals the golden ratio conjugate PHI, namely lim (n to infinity) (z[n+1] / z[n] - a[n+1] / a[n]) = PHI, which reveals the beauty of cryptography.

We study non-malleable secret sharing against joint leakage and joint tampering attacks. Our main result is the first threshold secret sharing scheme in the plain model achieving resilience to noisy-leakage and continuous tampering. The above holds under (necessary) minimal computational assumptions (i.e., the existence of one-to-one one-way functions), and in a model where the adversary commits to a fixed partition of all the shares into non-overlapping subsets of at most $t-1$ shares (where $t$ is the reconstruction threshold), and subsequently jointly leaks from and tampers with the shares within each partition.

We also study the capacity (i.e., the maximum achievable asymptotic information rate) of continuously non-malleable secret sharing against joint continuous tampering attacks. In particular, we prove that whenever the attacker can tamper jointly with $k > t/2$ shares, the capacity is at most $t - k$. The rate of our construction matches this upper bound.

An important corollary of our results is the first non-malleable secret sharing scheme against independent tampering attacks breaking the rate-one barrier (under the same computational assumptions as above).

Authenticated Key Exchange (AKE) protocols, by definition, guarantee both session key secrecy and entity authentication. Informally, session key secrecy means that only the legitimate parties learn the established key and mutual authentication means that one party can assure itself the session key is actually established with the other party. Today, an important application area for AKE is Internet of Things (IoT) systems, where an IoT device runs the protocol to establish a session key with a remote server. In this paper, we identify two additional security requirements for IoT-oriented AKE, namely Key Compromise Impersonation (KCI) resilience and Server Compromise Impersonation (SCI) resilience. These properties provide an additional layer of security when the IoT device and the server get compromised respectively. Inspired by Chan et al.'s bigdata-based unilateral authentication protocol, we propose a novel AKE protocol which achieves mutual authentication, session key secrecy (including perfect forward secrecy), and the above two resilience properties. To demonstrate its practicality, we implement our protocol and show that one execution costs about 15.19 ms (or, 84.73 ms) for the IoT device and 2.44 ms (or, 12.51 ms) for the server for security parameter λ =128 (or, λ =256). We finally propose an enhanced protocol to reduce the computational complexity on the end of IoT by outsourcing an exponentiation computation to the server. By instantiating the signature scheme with NIST's round three alternate candidate Picnic, we show that one protocol execution costs about 14.44 ms (or, 58.45 ms) for the IoT device and 12.78 ms (or, 46.34 ms) for the server for security parameter λ =128 (or, λ =256).

We introduce the concept of turn-based communication channel between two mutually distrustful parties with communication consistency, i.e. both parties have the same message history, and happens in sets of exchanged messages across a limited number of turns. Our construction leverages on timed primitives. Namely, we introduce a novel Delta-delay hash function definition in order to establish turns in the channel. Concretely, we introduce the one-way turn-based communication scheme and the two-way turn-based communication protocol and provide a concrete instantiation that achieves communication consistency.

Differential privacy is a concept to quantify the disclosure of private information that is controlled by the privacy parameter~$\varepsilon$. However, an intuitive interpretation of $\varepsilon$ is needed to explain the privacy loss to data engineers and data subjects. In this paper, we conduct a worst-case study of differential privacy risks. We generalize an existing model and reduce complexity to provide more understandable statements on the privacy loss. To this end, we analyze the impact of parameters and introduce the notion of a global privacy risk and global privacy leak.

Fault attacks have gained particular attention in recent years as they present a severe threat to security in rapidly rising Internet-of-Things (IoT) devices. IoT devices are generally security-critical and resource-constrained. Therefore, any security protocol deployed in these devices has to satisfy several constraints such as small area footprint, low power, and memory consumption. Combinational circuit implementation of S-box is preferable over look-up table (LUT) in terms of memory consumption as the memory operations are usually the costliest part of lightweight cipher implementations. In this work, we analyze the S-box of AES against a novel fault analysis technique, Semi-Permanent Stuck-At (SPSA) fault analysis. We pinpoint hotspots in an optimized implementation of AES S-box that weaken the cryptographic properties of the S-box, leading to key recovery attacks. Our work investigates new vulnerabilities towards fault analysis in combinational circuit implementation.

We present the first Oblivious RAM (ORAM) construction that for $N$ memory blocks supports accesses with worst-case $O(\log N)$ overhead for any block size $\Omega(\log N)$ while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.

The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur $\Theta(N)$ overhead. The previously best ORAM in terms of worst-case overhead achieves $O(\log ^2 N/\log\log N)$ overhead.

Technically, we design a novel de-amortization framework for modern ORAM constructions that use the ``shuffled inputs'' assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC '97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.

In today's real-world elections the choice of the voting scheme is often more subject to dogma and tradition than the result of an objective and scientific selection process. As a consequence, it is left to intuition whether the chosen scheme satisfies desired security properties, while objectively more suitable schemes might be rejected without due cause. Employing a scientific selection process to decide on a specific voting scheme is currently infeasibly cumbersome. Even those few schemes which have been thouroughly analyzed do not provide easily comparable analysis results or fail to provide the information desired for real-world application. Hence there is a strong need to increase meaningful comparability, allowing democracies to choose the voting scheme that is best suited for their setting. In this paper we analyze which factors currently impede the comparability of both classic and cryptographic voting schemes and which information is needed to facilitate meaningful comparisons. As a first result we find that there is a severe lack of general understanding of the workings and properties of the classic paper-based systems which are in use around the world today. In this we highlight that commonly voiced intuitive comparisons especially to classic paper-based voting lack the necessary scientific basis and are therefore no sufficient foundation. We then develop an analysis framework to concisely showcase the most important characteristics of a voting scheme as well as to enable comparisons to other schemes. The utility of our analysis framework is demonstrated by analyzing and comparing two examples. Our work underlines the need for more academic work towards the comparability of voting schemes and lays a foundation for addressing this issue.

The humble integers, $\mathbb{Z}$, are the backbone of many cryptosystems. When bridging the gap from theoretical systems to real-world implementations, programmers often look towards general purpose libraries to implement the arbitrary-precision arithmetic required. Alas, these libraries are often conceived without cryptography in mind, leaving applications potentially vulnerable to timing attacks. To address this, we present saferith, a library providing safer arbitrary-precision arithmetic for cryptography, through constant-time operations. The main challenge was in designing an API to provide this functionality alongside these stronger constant-time guarantees. We benchmarked the performance of our library against Go's big.Int library, and found an acceptable slowdown of only 2.56x for modular exponentiation, the most expensive operation. Our library was also used to implement a variety cryptosystems and applications, in collaboration with industrial partners ProtonMail and Taurus. Porting implementations to use our library is relatively easy: it took the first author under 8 hours to port Go's implementation of P-384.

Simpira Permutation is a Permutation design using the AES algorithm. The AES algorithm is the most widely used in the world, and Intel has developed a hardware accelerated AES instruction set (AES-NI) to improve the performance of encryption. By using AES-NI, Simpira can be improved further. However, low-end processors that do not support AES-NI require efficient implementation of Simpira optimization. In this paper, we introduce a optimized implementation of a Simpira Permutation in 8-bit AVR microcontrollers and 32-bit RISC-V processors, that do not support the AES instruction set. We firstly pre-computed round keys and omitted the Addroundkey. Afterward, the MixColumn and InvMixColumn of the final round (i.e. 12-th), which were added unnecessarily due to characteristics of Simpira using AES-NI, were omitted. In the AVR microcontroller, the Addroundkey consists of 16 operations, but it has been optimized by eliminating operations where the value of roundkeys is \texttt{0x00}, omitting Addroundkey to 4 operations. In the RISC-V processor, it is implemented using a same optimization technique of AVR implementation. We have carried out experiments 8-bit ATmega128 microcontroller and 32-bit RISC-V processor, which shows up-to \texttt{5.76$\times$ and 37.01$\times$} better performance enhancement than reference codes for the Simpira Permutation, respectively.

Collision attacks on AES-like hashing (hash functions constructed by plugging AES-like ciphers or permutations into the famous PGV modes or their variants) can be reduced to the problem of finding a pair of inputs respecting a differential of the underlying AES-like primitive whose input and output differences are the same. The rebound attack due to Mendel et al. is a powerful tool for achieving this goal, whose quantum version was first considered by Hosoyamada and Sasaki at EUROCRYPT 2020. In this work, we automate the process of searching for the configurations of rebound attacks by taking related-key differentials of the underlying block cipher into account with the MILP-based approach. In the quantum setting, our model guide the search towards characteristics that minimize the resources (e.g., QRAM) and complexities of the resulting rebound attacks. We apply our method to Saturnin-hash, SKINNY, and Whirlpool and improved results are obtained.

Homomorphic cryptography is used when computations are delegated to an untrusted third-party. However, there is a discrepancy between the untrustworthiness of the third-party and the silent assumption that it will perform the expected computations on the encrypted data. This may raise serious privacy concerns, for example when homomorphic cryptography is used to outsource resource-greedy computations on personal data (e.g., from an IoT device to the cloud). In this paper we show how to cost-effectively verify that the delegated computation corresponds to the expected sequence of operations, thus drastically reducing the necessary level of trust in the third-party. Our approach is based on the well-known modular extension scheme: it is transparent for the third-party and it is not tied to a particular homomorphic cryptosystem nor depends on newly introduced (and thus less-studied) cryptographic constructions. We provide a proof-of-concept implementation, THC (for "trustable homomorphic computation"), which we use to perform security and performance analyses. We then demonstrate its practical usability, in the case of a toy electronic voting system.

Polynomial multiplication is a core operation for public key cryptography, such as pre-quantum cryptography (e.g. elliptic curve cryptography) and post-quantum cryptography (e.g. code-based cryptography and multivariate-based cryptography). For this reason, the efficient and secure implementation of polynomial multiplication has been actively conducted for high availability and security level in application services. In this paper, we present all polynomial multiplication methods on modern 32-bit RISC-V processors. We re-designed expensive implementations of polynomial multiplication on legacy microcontrollers (e.g. 8-bit AVR, 16-bit MSP, and 32-bit ARM) for new instruction sets of 32-bit RISC-V processors. Secondly, we suggest the optimal operand length for each polynomial multiplication on 32-bit RISC-V processors. With this implementation technique and Karatsuba algorithm, we achieved scalable features, which ensures the polynomial multiplication in any operand lengths with reasonably fast performance. Third, we propose instruction set extensions for the optimal implementation of polynomial multiplication on 32-bit RISC-V processors. This new feature introduces significant performance enhancements. Lastly, the proposed implementation is a public domain and following researchers can easily re-produce the result.

It is known that fully homomorphic encryption (FHE) can be used to build efficient (labeled) Private Set Intersection protocols in the unbalanced setting, where one of the sets is much larger than the other (Chen et al. (CCS'17, CCS'18)). In this paper we demonstrate multiple algorithmic improvements upon these works. In particular, our protocol has an asymptotically better computation cost, requiring only $\bigO(\sqrt{\| X \|})$ homomorphic multiplications, and communication complexity sublinear in the larger set size $\| X \|$.

We demonstrate that our protocol is significantly better than that of Chen et al. (CCS'18) for many practical parameters, especially in terms of online communication cost. For example, when intersecting $2^{28}$ and 2048 item sets, our protocol reduces the online computation time by more than 71% and communication by more than 63%. When intersecting $2^{24}$ and 4096 item sets, our protocol reduces the online computation time by 27% and communication by 63%. Our comparison to other state-of-the-art unbalanced PSI protocols shows that our protocol has the best total communication complexity when $\| X \| \geq 2^{24}$. For labeled PSI our protocol also outperforms Chen et al. (CCS'18). When intersecting $2^{20}$ and $256$ item sets, with the larger set having associated 288-byte labels, our protocol reduces the online computation time by more than 67% and communication by 34%.

Finally, we demonstrate a modification that results in nearly constant communication cost in the larger set size $\| X \|$, but impractically high computation complexity on today's CPUs. For example, to intersect a $210$-item set with sets of size $2^{22}$, $2^{24}$, or $2^{26}$, our proof-of-concept implementation requires only 0.76 MB of online communication, which is more than a 24-fold improvement over Chen et al. (CCS'18).

A secret sharing scheme enables the dealer to share a secret among $n$ parties. A classic secret sharing scheme takes the number $n$ of parties and the secret as the input. If $n$ is not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev \cite[TCC 2016]{KNY16} first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work \cite[TCC 2016]{KNY16}, \cite[TCC 2017]{KC17} and \cite[Eurocrypt 2020]{BO20}, evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in \cite{BO20} are inspired by the scheme given in \cite{KNY16}, namely, these schemes rely on the scheme for st-connectivity which allows to generate infinite number of shares.

In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Most of the previous schemes mentioned above have more combinatorial flavor, while our schemes are more algebraic in nature. More precisely speaking, our evolving secret sharing schemes are obtained via either the Shamir secret sharing or arithmetic secret sharing from algebraic geometry codes alone. Our first scheme is an evolving $k$-threshold secret sharing scheme with share size $k^{1+\epsilon}\log t$ for any constant $\epsilon>0$. Thus, our scheme achieves almost the same share size as in \cite[TCC 2016]{KNY16}. Moreover, our scheme is obtained by a direct construction while the scheme in \cite[TCC 2016]{KNY16} that achieves the $(k-1)\log t$ share size is obtained by a recursive construction which makes their structure complicated. Our second scheme is an evolving $k_t$-threshold secret sharing scheme with any sequence $\{k_t\}_{t=1}^\infty$ of threshold values that has share size $t^4$. This scheme improves the share size by $\log t$ given in \cite{KC17} where a dynamic evolving $k_t$-threshold secret sharing scheme with the share size $O(t^4\log t)$ was proposed. In addition, we also show that if the threshold values $k_t$ grow in rate $\lfloor \beta t\rfloor$ for a real $\beta\in(0,1)$, then we have a dynamic evolving threshold secret sharing scheme with the share size $O(t^{4\beta})$. For $\beta<0.25$, this scheme has sub-linear share size which was not known before. Our last scheme is an evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme with constant share size. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique in \cite{KC17} can also transform all of our schemes to a robust scheme as our scheme is linear.\footnote{We note that by replacing the building block scheme with an arithmetic secret sharing scheme, the evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme in \cite{BO20} can also be multiplicative. However, their share size is much bigger than ours as each party hold multiple shares. }