International Association
for Cryptologic Research

Privacy and security challenges due to the outsourcing of data storage and processing to third-party cloud providers are well known. With regard to data privacy, Oblivious RAM (ORAM) schemes provide strong privacy guarantees by not only hiding the contents of the data (by encryption) but also obfuscating the access patterns of the outsourced data. But most existing ORAM datastores are not fault tolerant in that if the external storage server (which stores encrypted data) or the trusted proxy (which stores the encryption key and other meta- data) crashes, an application loses all of its data. To achieve fault-tolerance, we propose QuORAM, the first ORAM datastore to replicate data with a quorum-based replication protocol. QuORAM’s contributions are three-fold: (i) it obfuscates access patterns to provide obliviousness guarantees, (ii) it replicates data using a novel lock-free and decentralized replication protocol to achieve fault-tolerance, and (iii) it guarantees linearizable semantics. Experimentally evaluating QuORAM highlights counter-intuitive results: QuORAM in- curs negligible cost to achieve obliviousness when compared to an insecure fault-tolerant replicated system; QuORAM’s peak throughput is 2.4x of its non-replicated baseline; and QuORAM performs 33.2x better in terms of throughput than an ORAM datastore that relies on CockroachDB, an open- source geo-replicated database, for fault tolerance.

We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size $n$. The adversary also operates as a streaming algorithm, but has a much larger memory size $m \gg n$. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In this work, we construct message authentication and signatures in the BSM.

First, we consider the symmetric-key setting, where Alice and Bob share a small secret key. Alice can authenticate arbitrarily many messages to Bob by streaming long authentication tags of size $k \gg m$, while ensuring that the tags can be generated and verified using only $n$ bits of memory. We show a solution using local extractors (Vadhan; JoC '04), which allows for up to exponentially large adversarial memory $m = 2^{O(n)}$, and has tags of size $k= O(m)$. Second, we consider the same setting as above, but now additionally require each individual tag to be small, of size $k \leq n$. We show a solution is still possible when the adversary's memory is $m = O(n^2)$, which is optimal. Our solution relies on a space lower bound for leaning parities (Raz; FOCS '16). Third, we consider the public-key signature setting. A signer Alice initially streams a long verification key over an authentic channel, while only keeping a short signing key in her memory. A verifier Bob receives the streamed verification key and generates some short verification digest that he keeps in his memory. Later, Alice can sign arbitrarily many messages using her signing key by streaming the signatures to Bob, who can verify them using his verification digest. We show a solution for $m= O(n^2)$, which we show to be optimal. Our solution relies on a novel entropy lemma, of independent interest. We show that, if a sequence of blocks has sufficiently high min-entropy, then a large fraction of individual blocks must have high min-entropy. Naive versions of this lemma are false, but we show how to patch it to make it hold.

The System and Software Security (S3) group at The University of Manchester is looking for a Post-Doc in Secure and Verifiable AI Models to join our ambition EPSRC-funded EnnCore project (https://enncore.github.io/).

The successful candidate will enjoy designing, developing, and evaluating novel AI models that are secure and robust against attacks. The project will involve continuous interaction with experts in explainable AI, software testing and formal software verification.

The S3 group conducts a world-leading research in the space of explainable AI, automated software verification and testing. It develops award-winning software verification tools and regularly wins prices at international competitions.

Closing date for applications:

Contact: Mustafa Mustafa (mustafa.mustafa@manchester.ac.uk)

More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?jobid=22435

In CRYPTO'21, Shen et al. have proved that $\textsf{DbHtS}$ is secure up to $2^{2n/3}$ queries in the multi-user setting independent of the number of users, where the double block hash function $\textsf{H}$ consists of two independent $n$-bit keyed hash function $(\textsf{H}_{K_h,1}, \textsf{H}_{K_h, 2})$ such that each of the $n$-bit keyed hash function is $O(2^{-n})$ universal and regular. They have also demonstrated the applicability of their result to key-reduced variants of $\textsf{DbHtS}$ MACs including $\textsf{2K-SUM-ECBC}$, $\textsf{2K-PMAC\_Plus}$ and $\textsf{2K-LightMAC\_Plus}$ without requiring any additional domain separation. Recently, Guo and Wang have shown three instantiations of $\textsf{DbHtS}$ framework where each of their $n$-bit keyed hash functions is $O(2^{-n})$ universal and regular but the constructions are itself secure only up to the birthday bound. In this work, we show a sufficient condition on the underlying Double-block Hash ($\textsf{DbH}$) function under which we prove $3n/4$-bit multi-user security of $\textsf{DbHtS}$ construction in the ideal-cipher model. As an instantiation, we show that Polyhash based $\textsf{DbHtS}$ construction is multi-user secured up to $2^{3n/4}$ queries in the ideal-cipher model. Moreover, due to the result of the generic attack on $\textsf{DbHtS}$ constructions by Ga\"etan et al. in CRYPTO'18, our derived bound for the construction is tight.

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.