International Association
for Cryptologic Research

The linear layer, which is basically a binary non-singular matrix, is an integral part of cipher construction in a lot of private key ciphers. As a result, optimising the linear layer for device implementation has been an important research direction for about two decades. The Boyar-Peralta's algorithm (SEA'10) is one such common algorithm, which offers significant improvement compared to the straightforward implementation. This algorithm only returns implementation with XOR2 gates, and is deterministic. Over the last couple of years, some improvements over this algorithm has been proposed, so as to make support for XOR3 gates as well as make it randomised. In this work, we take an already existing improvement (Tan and Peyrin, TCHES'20) that allows randomised execution and extend it to support three input XOR gates. This complements the other work done in this direction (Banik et al., IWSEC'19) that also supports XOR3 gates with randomised execution. Further, noting from another work (Maximov, Eprint'19), we include one additional tie-breaker condition in the original Boyar-Peralta's algorithm. Our work thus collates and extends the state-of-the-art, at the same time offers a simpler interface. We show several results that improve from the lastly best-known results.

Let $p$ be a polynomial, and let $p^{(i)}(x)$ be the result of iterating the polynomial $i$ times, starting at an input $x$. The case where $p(x)$ is the homogeneous polynomial $x^2$ has been extensively studied in cryptography. Due to its associated group structure, iterating this polynomial gives rise to a number of interesting cryptographic applications such as time-lock puzzles and verifiable delay functions. On the other hand, the associated group structure leads to quantum attacks on the applications.

In this work, we consider whether inhomogeneous polynomials, such as $2x^2+3x+1$, can have useful cryptographic applications. We focus on the case of polynomials mod $2^n$, due to some useful mathematical properties. The natural group structure no longer exists, so the quantum attacks but also applications no longer immediately apply. We nevertheless show classical polynomial-time attacks on analogs of hard problems from the homogeneous setting. We conclude by proposing new computational assumptions relating to these inhomogeneous polynomials, with cryptographic applications.

Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of whom might even be corrupted. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation—we call such parties “doomed.”

In this work we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous “best-possible security” version of secure communication) in the Universal Composability (UC) framework of Canetti. Our result offers the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC.

Non-interactive publicly verifiable secret sharing (PVSS) schemes allow parties to re-share a secret in a decentralized setting in the presence of malicious parties. A recently proposed application of PVSS schemes is to enable permissionless proof-of-stake blockchains to ``keep a secret" via a sequence of committees that share that secret. Such committees can use the secret to produce signatures on the blockchain's behalf, or to disclose hidden data conditioned on consensus that some event has occurred. Such a setting may involve thousands of parties, so the PVSS scheme that it uses must be very efficient, both in computation and communication. Yet, previous PVSS schemes have large proofs and/or require many exponentiations over large groups.

We present a non-interactive PVSS scheme in which the underlying encryption scheme is based on the learning with errors (LWE) problem. While lattice-based encryption schemes are very fast, they have issues with bandwidth (long ciphertexts and public keys). We deal with the bandwidth issue in two ways. First, we adapt the Peikert-Vaikuntanathan-Waters (PVW) encryption scheme to the multi-receiver setting so that the bulk of the parties' keys is a common random string, and so that we get good amortized communication: $\Omega(1)$ plaintext/ciphertext rate (rate $\approx 1/60$ for 100 parties, $\approx 1/8$ for 1000 parties, approaching 1/2 as the number of parties grows). Second, we use bulletproofs over a DL-group of order about 256 bits to get compact proofs of correct encryption of shares. Switching from the lattice setting to the DL setting is relatively painless, as we equate the LWE modulus with the order of the group, and apply dimension reduction to vectors before the switch to minimize the number of exponentiations in the bulletproof. An implementation of our PVSS for 1000 parties showed that it's quite practical, and should remain so with up to a two order of magnitude increase in the group size.

Software implementations of the number-theoretic transform (NTT) method often leverage Harvey’s butterfly to gain speedups. This is the case in cryptographic libraries such as IBM’s HElib, Microsoft’s SEAL, and Intel’s HEXL, which provide optimized implementations of fully homomorphic encryption schemes or their primitives. We extend the Harvey butterfly to the radix-4 case for primes in the range [2^31, 2^52). This enables us to use the vector multiply sum logical (VMSL) instruction, which is available on recent IBM Z^(R) platforms. On an IBM z14 system, our implementation performs more than 2.5x faster than the scalar implementation of SEAL we converted to native C. In addition, we implemented a mixed-radix implementation that uses AVX512-IFMA on Intel’s Ice Lake processor, which happens to be ~1.1 times faster than the super-optimized implementation of Intel’s HEXL. Finally, we compare the performance of some of our implementation using GCC versus Clang compilers and discuss the results.

Homomorphic secret sharing (HSS) for a function $f$ allows input parties to distribute shares for their private inputs and then locally compute output shares from which the value of $f$ is recovered. HSS can be directly used to obtain a two-round multiparty computation (MPC) protocol for possibly non-threshold adversary structures whose communication complexity is independent of the size of $f$. In this paper, we propose two constructions of HSS schemes supporting parallel evaluation of a single low-degree polynomial and tolerating multipartite and general adversary structures. Our multipartite scheme tolerates a wider class of adversary structures than the previous multipartite one in the particular case of a single evaluation and has exponentially smaller share size than the general construction. While restricting the range of tolerable adversary structures (but still applicable to non-threshold ones), our schemes perform $\ell$ parallel evaluations with communication complexity approximately $\ell/\log\ell$ times smaller than simply using $\ell$ independent instances. We also formalize two classes of adversary structures taking into account real-world situations to which the previous threshold schemes are inapplicable. Our schemes then perform $O(m)$ parallel evaluations with almost the same communication cost as a single evaluation, where $m$ is the number of parties.

TCC'21 will take place will take place in Raleigh, United States on November 8-11 2021.

Early registration closes on October 24th. Visit: https://tcc.iacr.org/2021/registration.php to register.

If you have any questions or doubts, contact the General Chair Alessandra Scafuro

The 2021 Election for Directors of the IACR Board is now open.

You may vote as often as you wish now through November 16th using the Helios https://heliosvoting.org cryptographically-verifiable election system, but only your last vote will be counted.

Please see for a brief overview of how the Helios system works and https://www.iacr.org/elections/eVoting/ for information on the IACR decision to adopt Helios.

2021 members of the IACR (generally people who attended an IACR event in 2020) should shortly receive, or have already received, voting credentials from system@heliosvoting.org sent to their email address of record with the IACR. Please check your spam folder first if you believe that you haven't received the mail. Questions about this election may be sent to elections@iacr.org.

Information about the candidates can be found below and also at https://iacr.org/elections/2021/candidates.php.

The importance of efficient multi-exponen- tiation algorithms in a large spectrum of cryptographic applications continues to grow. Many of the algorithms proposed in the past pay attention exclusively on the minimization of the number of modular multiplications. However, a short reduction of the multiplicative com- plexity can be easily overshadowed by other figures of merit. In this article we demonstrate a large number of practical results aimed at concrete cryptographic tasks requiring multi-exponentiations and provide rec- ommendations on the best possible algorithmic strate- gies for different selection of security parameters.

Bulletproofs (Bünz et al. IEEE S&P 2018) are a celebrated ZK proof system that allows for short and efficient proofs, and have been implemented and deployed in several real-world systems. In practice, they are most often implemented in their non-interactive version obtained using the Fiat-Shamir transform, despite the lack of a formal proof of security for this setting.

Prior to this work, there was no evidence that malleability attacks were not possible against Fiat-Shamir Bulletproofs. Malleability attacks can lead to very severe vulnerabilities, as they allow an adversary to forge proofs re-using or modifying parts of the proofs provided by the honest parties. In this paper, we show for the first time that Bulletproofs (or any other similar multi-round proof system satisfying some form of weak unique response property) achieve simulation-extractability in the algebraic group model.

This implies that Fiat-Shamir Bulletproofs are non-malleable.

Block cipher DEFAULT has been proposed as a differential fault analysis immune cipher at Asiacrypt 2021. In this paper, we show that one can find the key of the initial version of DEFAULT with complexity $2^{16}$ by injecting 112 faults. However, our idea does not work in the modified version of the cipher.

In a recent talk of Hallgren on a joint work with Eldar (Sept 21, 2021, Simons Institute), a polynomial-time quantum algorithm for solving BDD in a certain class of lattices was claimed. We show here that known classical (and even, deterministic) polynomial-time algorithms already achieve this result.

Branching program (BP) is a DAG-based non-uniform computational model for L/poly class. It has been widely used in formal verification, logic synthesis, and data analysis. As a special BP, a decision tree is a popular machine learning classifier for its effectiveness and simplicity. In this work, we propose a UC-secure efficient multi-party computation platform for outsourced branching program and/or decision tree evaluation. We construct a constant-round protocol and a poly-round protocol. In particular, the overall (online + offline) communication cost of our poly-round protocol is $O(d(\ell + \log m+\log n))$ and its round complexity is $2d-1$, where $m$ is the DAG size, $n$ is the number of features, $\ell$ is the feature length, and $d$ is the longest path length. To enable efficient oblivious hopping among the DAG nodes, we propose a lightweight $1$-out-of-$N$ shared OT protocol with logarithmic communication in both online and offline phase. This partial result may be of independent interest to some other cryptographic protocols. Our benchmark shows, compared with the state-of-the-arts, the proposed constant-round protocol is up to 10X faster in the WAN setting, while the proposed poly-round protocol is up to 15X faster in the LAN setting.

Dot-product is a widely used operation in many machine learning and scientific computing algorithms. Recently, NVIDIA has introduced dot-product instructions (DP2A and DP4A) in modern GPU architectures, with the aim of accelerating machine learning and scientific computing applications. These dot-product instructions allow the computation of multiply-and-add instructions in a clock cycle, effectively achieving higher throughput compared to conventional 32-bit integer units. In this paper, we show that the dot-product instruction can also be used to accelerate matrix-multiplication and polynomial convolution operations, which are commonly found in post-quantum lattice-based cryptographic schemes. In particular, we propose a highly optimized implementation of FrodoKEM, wherein the matrix-multiplication is accelerated by the dot-product instruction. We also present specially designed data structures that allow an efficient implementation of Saber key encapsulation mechanism, utilizing the dot-product instruction to speed-up the polynomial convolution. The proposed FrodoKEM implementation achieves 4.37x higher throughput in terms of key exchange operations per second than the state-of-the-art implementation on V100 GPU. This paper also presents the first implementation of Saber on GPU platforms, achieving 124,418, 120,463, and 31,658 key exchange operations per second on RTX3080, V100, and T4 GPUs, respectively. Since matrix-multiplication and polynomial convolution operations are the most time-consuming operations in lattice-based cryptographic schemes, our proposed techniques are likely to benefit other similar algorithms. The proposed high throughput implementation of KEMs on various GPU platforms allows the heavy computations (KEMs) to be offloaded from the server. This is very useful for many emerging applications like Internet of Things and cloud computing.

Mixed integer linear programming (MILP) based tools are used to estimate the strength of block ciphers against the cryptanalytic attacks. The existing tools use partial difference distribution table (p-DDT) approach to optimize the probability of differential characteristics for large (≥8-bit) S-box based ciphers. We propose to use the full difference distribution table (DDT) with the probability of each possible propagation for MILP modeling of large S-boxes. This requires more than 16 variables to represent the linear inequalities of each propagation and corresponding probabilities. The existing tools (viz. Logic Friday) cannot handle the linear inequalities in more than 16 variables. In this paper, we present a new tool (namely MILES) to minimize the linear inequalities in more than 16 variables. This tool reduces the number of inequalities by minimizing the truth table corresponding to the DDT of S-box. We use our tool to minimize the linear inequalities for 8-bit S-boxes (AES and SKINNY) and get better results than existing tools. We show the application of MILES on 8-bit S-box based lightweight block cipher PIPO. There are 20621 inequalities in 23 variables corresponding to the possible propagations in DDT and these are minimized to 6035 inequalities using MILES. MILP model based on these linear inequalities is used to optimizethe probability of differential characteristics for round-reduced PIPO. For the first time, the MILP problem consisting the inequalities of full DDT for 8-bit S-box is solved to optimize the probability of differential characteristics.

We define the class of triplicate functions as a generalization of 3-to-1 functions over the finite field F 2 n for even values of n. We investigate the properties and behavior of triplicate functions, and of 3-to-1 among triplicate functions, with particular attention to the conditions under which such functions can be APN. We compute the exact number of distinct differential sets of power APN functions, quadratic 3-to-1 functions, and quadratic APN permutations; we show that, in this sense, quadratic 3-to-1 functions are a generalization of quadratic power APN functions for even dimensions, while quadratic APN permutations are generalizations of quadratic power APN functions for odd dimensions. We survey all known infinite families of APN functions with respect to the presence of 3-to-1 functions among them, and conclude that for even n almost all of the known infinite families contain functions that are quadratic 3-to-1 or EA-equivalent to quadratic 3-to-1 functions. Using the developed framework, we give the first proof that the infinite APN families of Budaghyan, Helleseth and Kaleyski; of Gologlu; and of Zheng, Kan, Li, Peng, and Tang have a Gold-like Walsh spectrum. We also give a simpler univariate representation of the Gogloglu family for dimensions n = 2m with m odd than the ones currently available in the literature. We conduct a computational search for quadratic 3-to-1 functions in even dimensions n ≤ 12. We find one new APN instance for n = 8, six new APN instances for n = 10, and the first sporadic APN instance for n = 12 since 2006. We provide a list of all known 3-to-1 APN functions for n ≤ 12.

This paper proposes a threshold-optimal ECDSA scheme based on the first threshold signature scheme by Gennaro et al. with efficient non-interactive signing for any $t+1$ signers in the group, provided the total group size is more than twice the threshold $t$. The scheme does not require any homomorphic encryption or zero-knowledge proofs and is proven to be robust and unforgeable with identifiable aborts tolerating at most $t$ corrupted participants. The security of the scheme is proven in a simulation-based definition, assuming DDH and that ECDSA is existentially unforgeable under chosen message attack. To evaluate the performance of the protocol, it has been implemented in C++ and the results demonstrate the non-interactive signing phase takes 0.12ms on average meaning over 8000 signatures can be created per second. With pre-signing phase, it takes 3.35ms in total, which is over 144 times faster than the current state of the art.

An OR-proof is a protocol that enables a user to prove the possession of a witness for one of two (or more) statements, without revealing which one. Abe and Okamoto (CRYPTO 2000) used this technique to build a partially blind signature scheme whose security is based on the hardness of the discrete logarithm problem. Inspired by their approach, we present BlindOR, an efficient blind signature scheme from OR-proofs based on lattices over modules. Using OR-proofs allows us to reduce the security of our scheme from the MLWE and MSIS problems, yielding a much more efficient solution compared to previous works.

In 2020, Bernard and Roux-Langlois introduced the Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé in 2019. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-$\mathcal{S}$-unit lattice, which requires classical subexponential time.

In this paper, our main contribution is to extend these experiments to 192 cyclotomic fields of any conductor $m$ and of degree up to $190$. Building upon new results from Bernard and Kucera on the Stickelberger ideal, we construct a maximal set of independent $\mathcal{S}$-units lifted from the maximal real subfield using explicit Stickelberger generators obtained via Jacobi sums. Hence, we obtain full-rank log-$\mathcal{S}$-unit sublattices fulfilling the role of approximating the full Tw-PHS lattice. Notably, our obtained approximation factors match those from Bernard and Roux-Langlois using the original log-$\mathcal{S}$-unit lattice in small dimensions.

As a side result, we use the knowledge of these explicit Stickelberger elements to remove almost all quantum steps in the CDW algorithm, by Cramer, Ducas and Wesolowski in 2021, under the mild restriction that the plus part of the class number verifies $h^{+}_{m}\leq O(\sqrt{m})$.

We propose a multi-party computation (MPC) protocol over $\mathbb{Z}_{2^k}$ secure against actively corrupted majority from somewhat homomorphic encryption. The main technical contributions are: (i) a new efficient packing method for $\mathbb{Z}_{2^k}$-messages in lattice-based somewhat homomorphic encryption schemes, (ii) a simpler reshare protocol for level-dependent packings, (iii) a more efficient zero-knowledge proof of plaintext knowledge on cyclotomic rings $\mathbb{Z}[X]/\Phi_M(X)$ with $M$ being a prime. Integrating them, our protocol shows from 2.2x upto 4.8x improvements in amortized communication costs compared to the previous best results. Our techniques not only improve the efficiency of MPC over $\mathbb{Z}_{2^k}$ considerably, but also provide a toolkit that can be leveraged when designing other cryptographic primitives over $\mathbb{Z}_{2^k}$.