International Association
for Cryptologic Research

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}$.

Zero-Knowledge Proofs (ZKPs) are cryptographic primitives allowing a party to prove to another party that the former knows some information while keeping it secret. Such a premise can lead to the development of numerous privacy-preserving protocols in different scenarios, like proving knowledge of some credentials to a server without leaking the identity of the user. Even when the applications of ZKPs were endless, they were not exploited in the wild for a couple of decades due to the fact that computing and verifying proofs was too computationally expensive. However, the advent of efficient schemes (in particular, zk-SNARKs) made this primitive to break into the scene in fields like cryptocurrencies, smart-contracts, and more recently, self-sovereign scenarios: private-by-design identity management and authentication. Nevertheless, its adoption in environments like the Internet of Things (IoT) remains unexplored due to the computational limitations of embedded systems. In this paper, we introduce ZPiE, a C library intended to create ZKP applications to be executed in embedded systems. Its main feature is portability: it can be compiled, executed, and used out-of-the-box in a wide variety of devices. Moreover, our proof-of-concept has been proved to work smoothly in different devices with limited resources, which can execute state-of-the-art ZKP authentication protocols.

Attribute-Based Encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. Multi-Authority Attribute-Based Encryption (MA-ABE) is a generalization of ABE where the central authority is distributed across several independent parties.

We provide the first MA-ABE scheme from prime-order pairings where no trusted setup is needed and where the attribute universe of each authority is unbounded. Our constructions rely on a common modular blueprint that uses an Identity-Based Functional Encryption scheme for inner products (ID-IPFE) as an underlying primitive. Our presentation leads to simple proofs of security and brings new insight into the algebraic design choices that seem common to existing schemes. In particular, the well-known MA-ABE construction by Lewko and Waters (EUROCRYPT 2011) can be seen as a specific instantiation of our modular construction.

Our schemes enjoy all of their advantageous features, and the improvements mentioned. Furthermore, different instantiations of the core ID-IPFE primitive lead to various security/efficiency trade-offs: we propose an adaptively secure construction proven in the generic group model and a selectively secure one that relies on SXDH. As in previous work, we rely on a hash function (to generate matching randomness for the same user across different authorities while preserving collusion resistance) that is modeled as a random oracle.

Sender-anonymous end-to-end encrypted messaging allows sending messages to a recipient without revealing the sender’s identity to the messaging platform. Signal recently introduced a sender anonymity feature that includes an abuse mitigation mechanism meant to allow the platform to block malicious senders on behalf of a recipient. We explore the tension between sender anonymity and abuse mitigation. We start by showing limitations of Signal’s deployed mechanism, observing that it results in relatively weak anonymity properties and showing a new griefing attack that allows a malicious sender to drain a victim’s battery. We therefore design a new protocol, called Orca, that allows recipients to register a privacy-preserving blocklist with the platform. Without learning the sender’s identity, the platform can check that the sender is not on the blocklist and that the sender can be identified by the recipient. We construct Orca using a new type of group signature scheme, for which we give formal security notions. Our prototype implementation showcases Orca’s practicality.

Minimizing the energy cost and carbon footprint of the Bitcoin blockchain and related protocols is one of the most widely identified open questions in the cryptocurrency space. Substituting the proof-of-work (PoW) primitive in Nakamoto's longest chain protocol with a {\em proof of useful work} (PoUW) has been long theorized as an ideal solution in many respects but, to this day, the concept still lacks a convincingly secure realization.

In this work we put forth Ofelimos, a novel PoUW-based block\-chain protocol whose consensus mechanism simultaneously realizes a decentralized optimization-problem solver. Our protocol is built around a novel local search algorithm, which we call Doubly Parallel Local Search (DPLS), that is especially crafted to suit implementation as the PoUW component of our blockchain protocol. We provide a thorough security analysis of our protocol and additionally present metrics that reflect the usefulness of the system. As an illustrative example we show how DPLS can implement a variant of WalkSAT and experimentally demonstrate its competitiveness with respect to a vanilla WalkSAT implementation. In this way, our work paves the way for safely using blockchain systems as generic optimization engines for a variety of hard optimization problems for which a publicly verifiable solution is desired.

This work introduces second-order masked implementations of LED, Midori, SKINNY, and PRINCE ciphers which do not require fresh masks to be updated at every clock cycle. The main idea lies on a combination of the constructions given by Shahmirzadi and Moradi at CHES~2021, and the theory presented by Beyne et al. at Asiacrypt~2020. The presented masked designs only use a minimal number of shares, i.e., three to achieve second-order security, and we make use of a trick to pair a couple of S-boxes to reduce their latency. The theoretical security analyses of our constructions are based on the linear-cryptanalytic properties of the underlying masked primitive as well as SILVER, the leakage verification tool presented at Asiacrypt~2020. To improve this cryptanalytic analysis, we use the \emph{noisy probing model} which allows for the inclusion of noise in the framework of Beyne et al. We further provide FPGA-based experimental security analysis confirming second-order protection of our masked implementations.

The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into an non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $\Sigma$-protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $(2\mu + 1)$-move protocol is, in general, $Q^\mu$, where $Q$ is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $\mu$-fold sequential repetition of $\Sigma$-protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss.

In this work, we give positive and negative results on this question. On the positive side, we show that for $(k_1, \ldots, k_\mu)$-special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in $Q$ (instead of $Q^\mu$). On the negative side, we show that for $t$-fold parallel repetitions of typical $(k_1, \ldots, k_\mu)$-special-sound protocols, there is an attack which results in a security loss of about $(Q/\mu)^\mu \mu^{-t}$, assuming for simplicity that $t$ is an integer multiple of $\mu$.

We consider the task of designing secure computation protocols in an unstable network where honest parties can drop out at any time, according to a schedule provided by the adversary. This type of setting, where even honest parties are prone to failures, is more realistic than traditional models, and has therefore gained a lot of attention recently. Unlike previous works in the literature, we allow parties to return to the computation according to an adversarially chosen schedule and, moreover, we do not assume that these parties receive the messages that were sent to them while being offline. However, we do assume an upper bound on the number of rounds that an honest party can be off-line---otherwise protocols in this setting cannot guarantee termination within a bounded number of rounds.

We study the settings of perfect, statistical and computational security and design MPC protocols in each of these scenarios. We assume that the intersection of online-and-honest parties from one round to the next is at least $2t+1$, $t+1$ and $1$ respectively, where $t$ is the number of (actively) corrupt parties. We show the intersection requirements to be optimal. Our (positive) results are obtained in a way that may be of independent interest: we implement a traditional stable network on top of the unstable one, which allows us to plug in \textit{any} MPC protocol on top. This approach adds a necessary overhead to the round count of the protocols, which is related to the maximal number of rounds an honest party can be offline. We also present a novel, perfectly secure MPC protocol that avoids this overhead by following a more ``direct'' approach rather than building a stable network on top. We introduce our network model in the UC-framework and prove the security of our protocols within this setting.

In this paper, we present new techniques for proving the security of multi- and threshold signature schemes under discrete logarithm assumptions in the random oracle model. The purpose is to provide a simple framework for analyzing the relatively complex interactions of these schemes in a concurrent model, thereby reducing the risk of attacks. We make use of proofs of possession and prove that a Schnorr signature suffices as a proof of possession in the algebraic group model without any tightness loss. We introduce and prove the security of a simple, three-round multisignature $\mathsf{SimpleMuSig}$.

Using our new techniques, we prove the concurrent security of a variant of the $\mathsf{MuSig2}$ multisignature scheme that includes proofs of possession as well as the $\mathsf{FROST}$ threshold signature scheme. These are currently the most efficient schemes in the literature for generating Schnorr signatures in a multiparty setting. Our variant of $\mathsf{MuSig2}$, which we call $\mathsf{SpeedyMuSig}$, has faster key aggregation due to the proofs of possession.

Differential fault analysis (DFA) is a very powerful attack vector on implementations of symmetric cryptography. Most countermeasures are applied at the implementation level. At ASIACRYPT 2021, Baksi et al. proposed a design strategy that aims to provide inherent cipher level resistance against DFA by using S-boxes with linear structures. They argue that in their instantiation, the block cipher DEFAULT, a DFA adversary can learn at most 64 of the 128 key bits, so the remaining brute-force complexity of $2^{64}$ is impractical.

In this paper, we show that a DFA adversary can combine information across rounds to recover the full key, invalidating their security claim. In particular, we observe that such ciphers exhibit large classes of equivalent keys that can be represented efficiently in normalized form using linear equations. We exploit this in combination with the specifics of DEFAULT's strong key schedule to recover the key using less than 100 faulty computation and negligible time complexity. Moreover, we show that even an idealized version of DEFAULT with independent round keys is vulnerable to our information-combining attacks based on normalized keys.

We present a new OT-based two-party multiplication protocol that is almost as efficient as Gilboa's semi-honest protocol (Crypto '99), but has a high-level of security against malicious adversaries without further compilation. The achieved security suffices for many applications, and, assuming DDH, can be cheaply compiled into full security.