International Association
for Cryptologic Research

The LowMC family of block ciphers was first proposed by Albrecht et al. in [ARS+15], specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3-bit S-box as the sole non-linear transformation in the algorithm. In contrast, both the linear layer and round key generation are achieved through multiplications of full rank matrices over GF(2). The cipher is instantiable using a diverse set of default configurations, some of which have partial non-linear layers i.e., in which the S-boxes are not applied over the entire internal state of the cipher.

The significance of cryptanalysing LowMC was elevated by its inclusion into the NIST PQC digital signature scheme PICNIC in which a successful key recovery using a single plaintext/ciphertext pair is akin to retrieving the secret signing key. The current state-of-the-art attack in this setting is due to Dinur [Din21a], in which a novel way of enumerating the roots of a Boolean system of equation is morphed into a key recovery procedure that undercuts an ordinary exhaustive search in terms of time complexity for the variants of the cipher up to five rounds.

In this work, we demonstrate that this technique can efficiently be enriched with a specific linearization strategy that reduces the algebraic degree of the non-linear layer as put forward by Banik et al. [BBDV20]. This amalgamation yields a drastic reduction in terms of memory complexity across all instantiations of LowMC up to six rounds with a quasi-equivalent time complexity.

Single Secret Leader Election protocols (SSLE, for short) allow a group of users to select a random leader so that the latter remains secret until she decides to reveal herself. Thanks to this feature, SSLE can be used to build an election mechanism for proof-of-stake based blockchains. In particular, a recent work by Azouvi and Cappelletti (ACM AFT 2021) shows that in comparison to probabilistic leader election methods, SSLE-based proof-of-stake blockchains have significant security gains, both with respect to grinding attacks and with respect to the private attack. Yet, as of today, very few concrete constructions of SSLE are known. In particular, all existing protocols are only secure in a model where the adversary is supposed to corrupt participants before the protocol starts -- an assumption that clashes with the highly dynamic nature of decentralized blockchain protocols.

In this paper we make progress in the study of SSLE by proposing new efficient constructions that achieve stronger security guarantees than previous work. In particular, we propose the first SSLE protocol that achieves adaptive security. Our scheme is proven secure in the universal composability model and achieves efficiency comparable to previous, less secure, realizations in the state of the art.

In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1, \ldots, P_{q}) \in (\{0,1\}^{n})^{q}$ satisfying a system of equations of the form $X_i \oplus X_j = \lambda_{i,j}$ such that $X_1, X_2, \ldots$, $X_{q}$ are pairwise distinct is either 0 or greater than the average over all $\lambda_{i,j}$ values in $\{0,1\}^n$. This result is known as ``$P_i \oplus P_j$ for any $\xi_{\max}$'' or alternatively as Mirror Theory for general $\xi_{\max}$, which was later proved by Patarin in ICISC'05. Mirror theory for general $\xi_{\max}$ stands as a powerful tool to provide a high security guarantee for many block cipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps which are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ for any $\xi_{\max}$ theorem. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and provide updated security bounds. Our result is actually more general in nature as we consider equations of the form $X_i \oplus X_j = \lambda_k$ over a commutative group under addition, and of exponent 2.

Timing attack is a class of side-channel attacks that aims to leak secret information based on the time it takes to perform different operations. The biggest advantage of a timing attack is that it does not require sophisticated or expensive equipment to be carried out. Side Channels on FHE schemes have been reported on the client side which has the secret key. But the present project aims to delve into the counter intuitive question, can an analysis be performed on the server end which ideally has no information of the secret key. In this report, we investigate when homomorphic operations are performed on the ciphertexts stored in the server, can timing reveal information of the error used to mask the ciphertexts? Finally, can this be utilized to determine the secret key of the ciphering technique?

In recent years, Bitcoin and Ethereum have emerged as the two largest and most popular blockchain networks. While Bitcoin provides the most secure digital asset, Ethereum provides the smart contract execution platform with the richest application ecosystem. In this paper, we present RSK, a sidechain that extends Bitcoin with Ethereum-compatible and stateful smart contract functionality. RSK's goal is to bring Ethereum's advantages to Bitcoin, allowing Bitcoin users to fully benefit from decentralized finance without having to exchange their bitcoin for other assets or having to renounce Bitcoin's consensus security. As a sidechain, RSK does not define a currency of its own, and thus, RSK does not compete with Bitcoin as store of value. Instead, RSK extends Bitcoin with new capabilities without taking resources from the Bitcoin network. Among other features, RSK provides a highly secure mechanism to transfer bitcoins from Bitcoin and back, and implements a merged mining protocol that provides Bitcoin miners with additional fees without adding significant overhead.

Quantum computing is considered among the next big leaps in the computer science. While a fully functional quantum computer is still in the future, there is an ever-growing need to evaluate the security of the secret-key ciphers against a potent quantum adversary.

Keeping this in mind, our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256) with respect to the quantum implementation and the quantum key search using the Grover's algorithm. We develop a pool of implementations, by mostly reducing the circuit depth metrics. We consider various strategies for optimization, as well as make use of the state-of-the-art advancements in the relevant fields.

In a nutshell, we present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 98 percent for all variants of AES. Moreover, our qubit count - Toffoli depth product is improved from theirs by more than 75 percent. Moreover, we analyze the Jaques et al.'s Eurocrypt'20 implementations in details, fix its bugs and report corrected benchmarks. To the best of our finding, our work presents the currently best-known results, thereby improving from all the previous works (including the recent Eprint'22 paper by Huang and Sun).

We consider a foundational unsupervised learning task of k-means data clustering, in a federated learning (FL) setting consisting of a central server and many distributed clients. We develop SecFC, which is a secure federated clustering algorithm that simultaneously achieves 1) universal performance: no performance loss compared with clustering over central- ized data, regardless of data distribution across clients; 2) data privacy: each client’s private data and the cluster centers are not leaked to other clients and the server. In SecFC, the clients perform Lagrange encoding on their local data and share the coded data in an information-theoretically private manner; then leveraging the algebraic structure of the coding, the FL network exactly executes the Lloyd’s k-means heuristic over the coded data to obtain the final clustering. Experiment results on synthetic and real datasets demonstrate the universally superior performance of SecFC for different data distributions across clients, and its computational practicality for various combinations of system parameters. Finally, we propose an extension of SecFC to further provide membership privacy for all data points.

We provide counterexamples to the ``dream'' version of Yao's XOR Lemma. In particular, we put forward explicit candidates for hard predicates, such that the advantage of predicting the XOR of many independent copies does not decrease beyond some fixed negligible function, even as the number of copies gets arbitrarily large.

We provide two such constructions: 1) Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete class of circuits). It develops a general framework that may be of broader interest, and allows us to embed an instance of a resettably-secure multiparty computation protocol into a one-way function. Along the way, we design the first resettably-secure multiparty computation protocol for general functionalities in the plain model with super-polynomial simulation, under standard assumptions.

2) The second construction relies on public-coin differing-inputs obfuscation (PCdiO) along with a certain form of hash-function security called extended second-preimage resistance (ESPR). It starts with a previously known counterexample to the dream direct-product hardness amplification based on ESPR, and uses PCdiO to upgrade it into a counterexample for the XOR lemma.

Prior to our work, even completely heuristic counterexamples of this type were not known.

Anonymous credentials systems (ACs) are a powerful cryptographic tool for privacy-preserving applications and provide strong user privacy guarantees for authentication and access control. ACs allow users to prove possession of attributes encoded in a credential without revealing any information beyond them. A delegatable AC (DAC) system is an enhanced AC system that allows the owners of credentials to delegate the obtained credential to other users. This allows to model hierarchies as usually encountered within public-key infrastructures (PKIs). DACs also provide stronger privacy guarantees than traditional AC systems since the identities of issuers and delegators are also hidden. A credential issuer's identity may convey information about a user's identity even when all other information about the user is protected.

We present a novel delegatable anonymous credential scheme that supports attributes, provides anonymity for delegations, allows the delegators to restrict further delegations, and also comes with an efficient construction. In particular, our DAC credentials do not grow with delegations, i.e., are of constant size. Our approach builds on a new primitive that we call structure-preserving signatures on equivalence classes on updatable commitments (SPSEQ-UC). The high-level idea is to use a special signature scheme that can sign vectors of set commitments which can be extended by additional set commitments. Signatures additionally include a user's public key, which can be switched. This allows us to efficiently realize delegation in the DAC. Similar to conventional SPSEQ signatures, the signatures and messages can be publicly randomized and thus allow unlinkable showings in the DAC system. We present further optimizations such as cross-set commitment aggregation that, in combination, enable selective, efficient showings in the DAC without using costly zero-knowledge proofs. We present an efficient instantiation that is proven to be secure in the generic group model and finally demonstrate the practical efficiency of our DAC by presenting performance benchmarks based on an implementation.

PASS Encrypt is a lattice-based public key encryption scheme introduced by Hoffstein and Silverman in 2015. The efficiency and algebraic properties of PASS Encrypt and of the underlying partial Vandermonde knapsack problem (PV-Knap) make them an attractive starting point for building efficient post-quantum cryptographic primitives. Recall that PV-Knap asks to recover a polynomial of small norm from a partial list of its Vandermonde transform. Unfortunately, the security foundations of PV-Knap-based encryption are not well understood, and in particular, no security proof for PASS Encrypt is known. In this work, we make progress in this direction. First, we present a modified version of PASS Encrypt with a security proof based on decision PV-Knap and a leaky variant of it, named the PASS problem. We next study an alternative approach to build encryption based on PV-Knap. To this end, we introduce the partial Vandermonde LWE problem (PV-LWE), which we show is computationally equivalent to PV-Knap. Following Regev's design for LWE-based encryption, we use PV-LWE to construct an efficient encryption scheme. Its security is based on PV-LWE and a hybrid variant of PV-Knap and Polynomial LWE. Finally, we give a refined analysis of the concrete security of both schemes against best known lattice attacks.

Collapsing is a post-quantum strengthening of collision resistance, needed to lift many classical results to the quantum setting. Unfortunately, the only existing standard-model proofs of collapsing hashes require LWE. We construct the first collapsing hashes from the quantum hardness of any one of the following problems:

- LPN in a variety of low noise or high-hardness regimes, essentially matching what is known for collision resistance from LPN.

- Finding cycles on exponentially-large expander graphs, such as those arising from isogenies on elliptic curves.

- The "optimal" hardness of finding collisions in *any* hash function.

- The *polynomial* hardness of finding collisions, assuming a certain plausible regularity condition on the hash.

As an immediate corollary, we obtain the first statistically hiding post-quantum commitments and post-quantum succinct arguments (of knowledge) under the same assumptions. Our results are obtained by a general theorem which shows how to construct a collapsing hash $H'$ from a post-quantum collision-resistant hash function $H$, regardless of whether or not $H$ itself is collapsing, assuming $H$ satisfies a certain regularity condition we call "semi-regularity."

As of today, the Hermite constants $\gamma_n$ are only known for $n\in \{1,2,3,4,5,6,7,8,24\}$.

We noted that the known values of $(4/\gamma_n)^n$ coincide with the values of the minimal determinants of any $n$-dimensional integral lattice when the length of the smallest lattice element $\mu$ is fixed to 4.

Based on this observation, we conjecture that the values of $\gamma_n^n$ for $n=9,\ldots,23$ are those given in Table 2.

We provide a supporting argument to back this conjecture. We also provide a provable lower bound on the Hermite constants for $1\leq n\leq24$.

Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq n$, a collision of $f$ is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be $\Theta(2^{m/3})$, and matching algorithms are known for any value of $m$.

The situation becomes different when one is looking for \emph{multiple} collision pairs. Here, for $2^k$ collisions, a query lower bound of $\Theta(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of $m$, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met.

Our new method relies on a \emph{chained quantum walk} algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk.

As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$.

The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation. However, recent research has mostly focused on the small-party honest-majority setting of up to four parties, noting efficiency concerns. In this work, we extend the strategies to support a larger number of participants in an honest-majority setting with efficiency at the center stage.

Cast in the preprocessing paradigm, our semi-honest protocol improves the online complexity of the decade-old state-of-the-art protocol of Damgård and Nielson (CRYPTO'07). In addition to having an improved online communication cost, we can shut down almost half of the parties in the online phase, thereby saving up to 50$\%$ in the system's operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification, towards the end.

To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our improved protocols aid in bringing up to 60-80$\%$ savings in monetary cost over prior work.

In our paper " Optimal collision side-channel attack" (https://eprint.iacr.org/2019/828) we studied collision side-channel attacks, derived an optimal distinguisher for the key, and provided an optimal algorithm for maximizing the success rate of the attacks. In this note we show that the problem of key ranking using an optimal distinguisher for collision side-channel attacks is NP-hard.

We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The main idea of the MiF technique is to stop the difference propagation earlier in the cipher, allowing to use differentials with higher probability. This comes at the expense of a deeper analysis phase in the bottom rounds possible due to the slow diffusion of the target cipher. The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential’s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery.

We illustrate MiF in practice by reporting improved attacks on the ARX-based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck32 and 20 rounds of Speck64/128. Notably, our new attack on 11 rounds of Speck32 has practical analysis and data complexities of $2^{24.66}$ and $2^{26.70}$ respectively, and was experimentally verified, recovering the master key in a matter of seconds. It significantly improves the previous deep learning-based attack by Gohr from CRYPTO 2019, which has time complexity $2^{38}$. As an important milestone, our conventional cryptanalysis method sets a new high benchmark to beat for cryptanalysis relying on machine learning.

We propose a novel obfuscation technique that can be used to outsource hard satisfiability (SAT) formulas to the cloud. Servers with large computational power are typically used to solve SAT instances that model real-life problems in task scheduling, AI planning, circuit verification and more. However, outsourcing data to the cloud may lead to privacy and information breaches since satisfying assignments may reveal considerable information about the underlying problem modeled by SAT.

In this work, we develop CENSOR (privaCy prEserviNg obfuScation for Outsourcing foRmulas), a novel SAT obfuscation framework that resembles Indistinguishability Obfuscation. At the core of the framework lies a mechanism that transforms any formula to a random one with the same number of satisfying assignments. As a result, obfuscated formulas are indistinguishable from each other thus preserving the input-output privacy of the original SAT instance. Contrary to prior solutions that are rather adhoc in nature, we formally prove the security of our scheme. Additionally, we show that obfuscated formulas are within a polynomial factor of the original ones thus achieving polynomial slowdown. Finally, the whole process is efficient in practice, allowing solutions to original instances to be easily recovered from obfuscated ones.

A byproduct of our method is that all NP problems can be potentially outsourced to the cloud by means of reducing to SAT.

As an enhancement of quantum collision-resistance, the collapsing property of hash functions proposed by Unruh (EUROCRYPT 2016) emphasizes the hardness for distinguishing a superposition state of a hash value from a collapsed one. The collapsing property trivially implies the quantum collision-resistance. However, it remains to be unknown whether there is a reduction from the collapsing hash functions to the quantum collision-resistant hash functions. In this paper, we further study the relations between these two properties and derive two intriguing results as follows:

Firstly, when the size of preimages of each hash value is bounded by some polynomial, we demonstrate that the collapsing property and the collision-resistance must hold simultaneously. This result is proved via a semi-black-box manner by taking advantage of the invertibility of a unitary quantum circuit.

Next, we further consider the relations between these two properties in the exponential-sized preimages case. By giving a construction of polynomial bounded hash functions, which preserves the quantum collision-resistance, we show the existence of collapsing hash functions is implied by the quantum collision-resistant hash functions when the size of preimages is not too large to the expected value.

Our results indicate that the gap between these two properties is sensitive to the size of preimages. As a corollary, our results also reveal the non-existence of polynomial bounded equivocal collision-resistant hash functions.

Zero-knowledge defines that verifier(s) learns nothing but predefined statement(s); e.g., verifiers learn nothing except the program's path for the respective transaction in a zero-knowledge contract program. Intra-Privacy or insiders' zero-knowledge --- ability to maintain a secret in a multi-party computation --- is an essential security property for smart contracts of Confidential Transactions (CT). Otherwise, the users have to reveal their confidential coin amounts to each other even if it is not a condition of the contract, contradicting the idea of zero-knowledge. For example, in an escrow contract, the escrow should not learn buyers' or sellers' account balances if the escrow has to pay into their accounts. Current private computational platforms, including homomorphic encryption and (ZK-)SNARK, can not be used in CT's smart contracts because homomorphic encryption requires secret key sharing, and (ZK-)SNARK requires a different setup for each computation which has to be stored on the blockchain. Existing private smart contracts are not intra-private even though they are inter-private --- participants can maintain secrets from verifiers but not from other participants, accordingly. To fill this research gap, we introduce the notion of ``Confidential Integer Processing'' (CIP) with two intra-private single-setup zero-knowledge programming protocols, (1) ``CIP-DLP'' from the Discrete Log Problem (DLP) targeting Ring/Aggregable CT like Monero and Mimblewimble, and (2) ``CIP-SIS'' from Approximate (Ring-Modular-) Short Integer Solution Problem (Approx-SIS) aiming at lattice-based Ring/Aggregable CT. To the best of our knowledge, our CIP protocols are the first practical public zero-knowledge contract protocols that are also secure under the Universal Composability (UC) framework without any hardware magic or trusted offline computations.

In this paper, we study the class of those Boolean functions that are coset leaders of first order Reed-Muller codes. We study their properties and try to better understand their structure (which seems complex), by studying operations on Boolean functions that can provide coset leaders (we show that these operations all provide coset leaders when the operands are coset leaders, and that some can even produce coset leaders without the operands being coset leaders). We characterize those coset leaders that belong to the well known classes of direct sums of monomial Boolean functions and Maiorana-McFarland functions. Since all the functions of Hamming weight at most $2^{n-2}$ are automatically coset leaders, we are interested in constructing infinite classes of coset leaders having possibly Hamming weight larger than $2^{n-2}$.