International Association
for Cryptologic Research

We present a new template for building oblivious transfer from quantum information that we call the ``fixed basis'' framework. Our framework departs from prior work (eg., Crepeau and Kilian, FOCS '88) by fixing the correct choice of measurement basis used by each player, except for some hidden trap qubits that are intentionally measured in a conjugate basis.

We instantiate this template in the quantum random oracle model (QROM) to obtain simple protocols that implement, with security against malicious adversaries: - Non-interactive random-input bit OT in a model where parties share EPR pairs a priori. - Two-round random-input bit OT without setup, obtained by showing that the protocol above remains secure even if the (potentially malicious) OT receiver sets up the EPR pairs. - Three-round chosen-input string OT from BB84 states without entanglement or setup. This improves upon natural variations of the CK88 template that require at least five rounds.

Along the way, we develop technical tools that may be of independent interest. We prove that natural functions like XOR enable seedless randomness extraction from certain quantum sources of entropy. We also use idealized (i.e. extractable and equivocal) bit commitments, which we obtain by proving security of simple and efficient constructions in the QROM.

We present a new framework for building round-optimal one-sided statistically secure two party computation (2PC) protocols in the plain model. We demonstrate that a relatively weak notion of oblivious transfer (OT), namely a three round elementary oblivious transfer $\textsf{eOT}$ with statistical receiver privacy, along with a non-interactive commitment scheme suffices to build a one-sided statistically secure two party computation protocol with black-box simulation. Our framework enables the first instantiations of round-optimal one-sided statistically secure 2PC protocols from the CDH assumption and certain families of isogeny-based assumptions.

As part of our compiler, we introduce the following new one-sided statistically secure primitives in the pre-processing model that might also be of independent interest: 1. Three round statistically sender private random-OT where only the last OT message depends on the receiver's choice bit and the sender receives random outputs generated by the protocol. 2. Four round delayed-input statistically sender private conditional disclosure of secrets where the first two rounds of the protocol are independent of the inputs of the parties.

The above primitives are directly constructed from $\textsf{eOT}$ and hence we obtain their instantiations from the same set of assumptions as our 2PC.

CSI-FiSh is one of the most efficient isogeny-based signature schemes, which is proven to be secure in the Quantum Random Oracle Model (QROM). However, there is a bottleneck in CSI-FiSh in the threshold setting, which is that its public key needs to be generated by using $k-1$ secret keys. This leads to very inefficient threshold key generation protocols and also forces the parties to store $k-1$ secret shares. We present CSI-SharK, a new variant of $\textit{CSI}$-FiSh that has more $\textit{Shar}$ing-friendly $\textit{K}$eys and is as efficient as the original scheme. This is accomplished by modifying the public key of the ID protocol, used in the original CSI-FiSh, to the equal length Structured Public Key (SPK), generated by a $\textit{single}$ secret key, and then proving that the modified ID protocol and the resulting signature scheme remain secure in the QROM. We translate existing CSI-FiSh-based threshold signatures and Distributed Key Generation (DKG) protocols to the CSI-SharK setting. We find that DKG schemes based on CSI-SharK outperform the state-of-the-art actively secure DKG protocols from the literature by a factor of about $3$, while also strongly reducing the communication cost between the parties. We also uncover and discuss a flaw in the key generation of the actively secure CSI-FiSh based threshold signature scheme $\textit{Sashimi}$, that can prevent parties from signing. Finally, we discuss how (distributed) key generation and signature schemes in the isogeny setting are strongly parallelizable and we show that by using $C$ independent CPU threads, the total runtime of such schemes can basically be reduced by a factor $C$. As multiple threads are standard in modern CPU architecture, this parallelizability is a strong incentive towards using isogeny-based (distributed) key generation and signature schemes in practical scenarios.

The main protection against side-channel attacks consists in computing every function with multiple shares via the masking countermeasure. While the masking countermeasure was originally developed for securing block-ciphers such as AES, the protection of lattice-based cryptosystems is often more challenging, because of the diversity of the underlying algorithms. In this paper, we introduce new gadgets for the high-order masking of the NTRU cryptosystem, with security proofs in the classical ISW probing model. We then describe the first fully masked implementation of the NTRU Key Encapsulation Mechanism submitted to NIST, including the key generation. To assess the practicality of our countermeasures, we provide a concrete implementation on ARM Cortex-M3 architecture, and eventually a t-test leakage evaluation.

Anonymity is an (abstract) security goal that is especially important to threatened user groups. Therefore, widely deployed communication protocols implement various measures to hide different types of information (i.e., metadata) about their users. Before actually defining anonymity, we consider an attack vector about which targeted user groups can feel concerned: continuous, temporary exposure of their secrets. Examples for this attack vector include intentionally planted viruses on victims' devices, as well as physical access when their users are detained.

Inspired by Signal's Double-Ratchet Algorithm, Ratcheted (or Continuous) Key Exchange (RKE) is a novel class of protocols that increase confidentiality and authenticity guarantees against temporary exposure of user secrets. For this, an RKE regularly renews user secrets such that the damage due to past and future exposures is minimized; this is called Post-Compromise Security and Forward-Secrecy, respectively.

With this work, we are the first to leverage the strength of RKE for achieving strong anonymity guarantees under temporary exposure of user secrets. We extend existing definitions for RKE to capture attacks that interrelate ciphertexts, seen on the network, with secrets, exposed from users' devices. Although, at first glance, strong authenticity (and confidentiality) conflicts with strong anonymity, our anonymity definition is as strong as possible without diminishing other goals.

We build strongly anonymity-, authenticity-, and confidentiality-preserving RKE and, along the way, develop new tools with applicability beyond our specific use-case: Updatable and Randomizable Signatures as well as Updatable and Randomizable Public Key Encryption. For both new primitives, we build efficient constructions.

We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can access an AMQ-PDS through an API or who can learn its internal state by compromising the system running the AMQ-PDS. We develop simulation-based security definitions that speak to correctness and privacy of AMQ-PDS. Our definitions are general and apply to a broad range of adversarial settings. We use our defi- nitions to analyse the behaviour of both Bloom filters and insertion- only Cuckoo filters. We show that these AMQ-PDS can be provably protected through replacement or composition of hash functions with keyed pseudorandom functions in their construction. We also examine the practical impact on storage size and computation of providing secure instances of Bloom and insertion-only Cuckoo filters.

Due to the significant drop in prices for genome sequencing in the last decade, genome databases were constantly growing. This enabled genome analyses such as Genome-Wide Association Studies (GWAS) that study associations between a gene and a disease and allow to improve medical treatment. However, GWAS fails at the analysis of complex diseases caused by non-linear gene-gene interactions such as sporadic breast cancer or type 2 diabetes. Epistasis Analysis (EA) is a more powerful approach that complements GWAS and considers non-linear interactions between multiple parts of the genome and environment. Statistical genome analyses require large, well-curated genomic datasets, which are difficult to obtain. Hence, the aggregation of multiple databases is often necessary, but the sharing of genomic data raises severe privacy concerns and is subject to extensive regulations (e.g., GDPR or HIPAA), requiring further privacy protection for collaborative analyses. Although there has been work on private GWAS, there was a lack of attention to Private EA (PEA). In this work, we design the first secure and accurate PEA protocol, with security against passive adversaries. Our efficient PEA protocol consists of two subprotocols: (1) (optional) feature selection for filtering noisy features to reduce the input size for better efficiency and (2) finding relevant associations. For feature selection, we design two protocols based on Secure Multi-Party Computation (MPC) for Relief-F and TuRF. For finding associations, we design an MPC protocol for Multifactor Dimensionality Reduction (MDR). Our private MDR protocol is based on two novel, efficient building blocks, arithmetic greater than and arithmetic swap, which may be of independent interest. This approach omits the need for expensive conversions between sharing types in private MDR and reduces the communication by two orders of magnitude compared to a naïve design using garbled circuits. Our private MDR protocol runs in (extrapolated) three days on a practical database with 10,000 features for all two mutually combined features, i.e., considering about 50 million combinations.

At Eurocrypt 2022, Tang et al proposed a practical digital signature scheme in the context of post-quantum cryptography. The construction of that scheme is based on the assumed hardness of the alternating trilinear form equivalence problem (ATFE), the Goldreich-Micali-Widgerson (GMW) zero-knowledge protocol for graph isomorphism, and the Fiat-Shamir (FS) transformation. We refer to that scheme as the ATFE-GMW-FS scheme. The security of the ATFE-GMW-FS scheme was only proved in the random oracle model (ROM), and its security in the quantum random oracle model (QROM) was left as an open problem.

In this paper, we study the ATFE-GMW-FS scheme from two perspectives, namely the QROM security and (linkable) ring signature schemes. First, we provide two approaches of proving its QROM security, based on the perfect unique response property and lossy identification schemes, respectively. Second, we design (linkable) ring signatures based on the ATFE-GMW-FS scheme, inspired by a recent result of Beullens, Katsumata and Pintore (Asiacrypt 20) on isogeny-based cryptography.

This work presents a hardware design for constant-time implementation of the HQC (Hamming Quasi-Cyclic) code-based key encapsulation mechanism. HQC has been selected for the fourth-round of NIST's Post-Quantum Cryptography standardization process and this work presents first, hand-optimized design of HQC key generation, encapsulation, and decapsulation written in Verilog targeting implementation on FPGAs. The three modules further share a common SHAKE256 hash module to reduce area overhead. All the hardware modules are parametrizable at compile time so that designs for the different security levels can be easily generated. The architecture of the hardware modules includes novel, dual clock domain design, allowing the common SHAKE module to run at slower clock speed compared to the rest of the design, while other faster modules run at their optimal clock rate. The design currently outperforms the other hardware designs for HQC, and many of the fourth-round Post-Quantum Cryptography standardization process, with one of the best time-area products as well. For the dual clock design targeting lowest security level, we show that the HQC design can perform key generation in 0.12ms, encapsulation in 0.30ms, and decapsulation in 0.43ms when synthesized for an Xilinx Artix 7 FPGA. The performance can be increased even further at the cost of resources by increasing the level of parallelism, e.g. by having parallel polynomial multiplication modules in the encrypt module, or including even more clock domains, one for each of the main modules. The presented design will further be made available under open-source license.

Privacy is a notoriously difficult property to achieve in complicated systems and especially in electronic voting schemes. Moreover, electronic voting schemes is a class of systems that require very high assurance. The literature contains a number of ballot privacy definitions along with security proofs for common systems. Some machine-checked security proofs have also appeared. We define a new ballot privacy notion that captures a larger class of voting schemes. This notion improves on the state of the art by taking into account that verification in many schemes will happen or must happen after the tally has been published, not before as in previous definitions.

As a case study we give a machine-checked proof of privacy for Selene, which is a remote electronic voting scheme which offers an attractive mix of security properties and usability. Prior to our work, the computational privacy of Selene has never been formally verified. Finally, we also prove that MiniVoting and Belenios satisfies our definition.

In the classical model of computation, it is well established that one-way functions (OWF) are essential for almost every computational cryptographic application. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether a minimal primitive exists remains open.

We consider EFI pairs — efficiently samplable, statistically far but computationally indistinguishable pairs of distributions. Building on the work of Yan (2022) which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary and sufficient for a large class of quantum-cryptographic applications. Specifically, while it was known how to construct commitments schemes, oblivious transfer, and general secure multiparty computation from any EFI, we show how to construct EFI pairs from minimalistic versions of each one of these primitives. We also construct from EFI quantum computational zero knowledge (????) proofs for all of ???, and construct EFI pairs from essentially any non-trivial ????.

This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Kahrobaei, Tortora, Tota showed how, to any nilpotent group of class n, one can associate a non-interactive key exchange protocol between n+1 users. The multilinear commutator maps associated to nilpotent groups play a key role in this protocol. In the present paper, we explore some alternative platforms, such as pro-p groups.

In the Zendoo white paper we introduced a novel sidechain construction for Bitcoin-like blockchains, which allows a mainchain to create and communicate with sidechains of different types without knowing their internal structure. In this paper, we take a step further by introducing a comprehensive method for sidechains to communicate amongst each other. We will also discuss the details of a cross-chain token transfer protocol that extends the generic communication mechanism. With the cross-chain token transfer protocol, it can enable a broad range of new applications, such as an exchange platform, that allows the ability to trade tokens issued from different sidechains.

We propose a new, unifying framework that yields an array of cryptographic primitives with {\em certified deletion}. These primitives enable a party in possession of a quantum ciphertext to generate a classical certificate that the encrypted plaintext has been information-theoretically deleted, and cannot be recovered even given unbounded computational resources. For $X \in \{\mathsf{public}\text{-}\mathsf{key},\mathsf{attribute\text{-}based},\mathsf{fully\text{-}homomorphic},\mathsf{witness},\mathsf{timed}\text{-}\mathsf{release}\}$, our compiler yields post-quantum $X$ encryption with certified deletion, assuming post-quantum $X$ encryption. Assuming the existence of statistically-binding commitments, our compiler yields statistically-binding commitments with certified everlasting hiding as well as statistically-sound zero-knowledge proofs for QMA with certified everlasting zero-knowledge. We also introduce and construct information-theoretic secret sharing with certified deletion. While encryption with certified deletion was first introduced by Broadbent and Islam (TCC 2020) in the context of an information-theoretic one-time pad, existing proposals by Unruh (Eurocrypt 2014), Hiroka et al. (Asiacrypt 2021), Hiroka et al. (Crypto 2021), and Poremba (QIP 2022) for {\em public-key} primitives with certified deletion (1) have complex tailored constructions and non-generic proofs, (2) are not known to satisfy everlasting security after deletion in the plain model, and in many cases (3) resort to idealized models or stronger cryptographic assumptions like obfuscation. We remedy this situation by developing a novel proof technique to argue that a bit $b$ has been {\em information-theoretically deleted} from an adversary's view once they produce a valid deletion certificate, despite having been previously {\em information-theoretically determined} by the ciphertext they held in their view. This may be of independent interest. Finally, we take the notion of certified deletion a step further, and explore its implications in the context of mistrustful two-(and multi-)party cryptography. Here, there is a strong impossibility result by Unruh (Crypto 2013) building on Lo, Chau, and Mayers (Physical Review Letters) showing that everlasting security against \emph{every} party is impossible to achieve, even with quantum communication, and even if parties are computationally bounded during the protocol. Nevertheless, we introduce the notion of \emph{Everlasting Security Transfer}, enabling participants to dynamically request that \emph{any} party (or parties) information-theoretically delete their data, even \emph{after} the protocol execution completes. We show how to construct secure two-party and multi-party computation satisfying this notion of security, which is impossible to achieve in a classical world. Our constructions all assume only statistically-binding commitments, which can be built from one-way functions or pseudo-random quantum states.

All known instantiations for fully homomorphic encryption (FHE) produce noisy ciphertexts and rely on a technique called bootstrapping to reduce the noise so as to enable an arbitrary number of homomorphic operations. Bootstrapping is the main performance bottleneck and arguably the biggest obstacle to widespread adoption of FHE. Among the FHE schemes, TFHE and its variations present the appealing property of having a bootstrapping procedure---as well as its extension to programmable bootstrapping---that is relatively light-weight. The essential operations consist of a series of multiplications in $(Z/qZ)[X]/(X^N+1)$. While the NTT is seemingly the natural candidate for evaluating these multiplications in a fast and exact way, it restricts the possible choices for $q$ and $N$. To the authors' knowledge, all current implementations of TFHE with $q$ a power of two actually employ the FFT over the complex numbers instead. This introduces real numbers to the otherwise purely discrete algorithms, including all the drawbacks of the need to approximate them using finite precision.

This work studies the avenues available to apply the NTT in the context of TFHE-like schemes. In particular, it considers various combinations of coefficient rings and quotient polynomials that are compatible with the requirements of the underlying scheme. Importantly, this work provides methods for adapting the (programmable) bootstrapping to quotient polynomials beyond power-of-two cyclotomics. As a side effect, it also demonstrates how this may enhance the programmability of the bootstrapping.

Anonymity of public key encryption (PKE) requires that, in a multi-user scenario, the PKE ciphertexts do not leak information about which public keys are used to generate them. Corruptions are common threats in the multi-user scenario but anonymity of PKE under corruptions is less studied in the literature. In TCC 2020, Benhamouda et al. first provide a formal characterization for anonymity of PKE under a specific type of corruption. However, no known PKE scheme is proved to meet their characterization.

To the best of our knowledge, all the PKE application scenarios which require anonymity also require confidentiality. However, in the work by Benhamouda et al., different types of corruptions for anonymity and confidentiality are considered, which can cause security pitfalls. What's worse, we are not aware of any PKE scheme which can provide both anonymity and confidentiality under the same types of corruptions.

In this work, we introduce a new security notion for PKE called ANON-RSO$_k\&$C security, capturing anonymity under corruptions. We also introduce SIM-RSO$_k\&$C security which captures confidentiality under the same types of corruptions. We provide a generic framework of constructing PKE scheme which can achieve the above two security goals simultaneously based on a new primitive called key and message non-committing encryption (KM-NCE). Then we give a general construction of KM-NCE utilizing a variant of hash proof system (HPS) called Key-Openable HPS. We also provide Key-Openable HPS instantiations based on the matrix decisional Diffie-Hellman assumption. Therefore, we can obtain various concrete PKE instantiations achieving the two security goals in the standard model with compact ciphertexts. Furthermore, for some PKE instantiation, its security reduction is tight.

NOVA signature scheme is a UOV-type signature scheme over a non-commutative coefficient ring with a novel structural map. In this article we show that a randomly generated central map for the scheme is very likely insecure and may suffer from a forgery attack in polynomial time.

This paper introduces Ibex, an advertising system that reduces the amount of data that is collected on users while still allowing advertisers to bid on real-time ad auctions and measure the effectiveness of their ad campaigns. Specifically, Ibex addresses an issue in recent proposals such as Google’s Privacy Sandbox Topics API in which browsers send information about topics that are of interest to a user to advertisers and demand-side platforms (DSPs). DSPs use this information to (1) determine how much to bid on the auction for a user who is interested in particular topics, and (2) measure how well their ad campaign does for a given audience (i.e., measure conversions). While Topics and related proposals reduce the amount of user information that is exposed, they still reveal user preferences. In Ibex, browsers send user information in an encrypted form that still allows DSPs and advertisers to measure conversions, compute aggregate statistics such as histograms about users and their interests, and obliviously bid on auctions without learning for whom they are bidding. Our implementation of Ibex shows that creating histograms is 1.7–2.5× more expensive for browsers than disclosing user information, and Ibex’s oblivious bidding protocol can finish auctions within 550 ms. We think this makes Ibex capable of preserving a good experience while improving user privacy.

Privacy-preserving protocols for matchings on general graphs can be used for applications such as online dating, bartering, or kidney donor exchange. In addition, they can act as a building blocks for more complex protocols. While privacy preserving protocols for matchings on bipartite graphs are a well-researched topic, the case of general graphs has experienced significantly less attention so far. We address this gap by providing the first privacy-preserving protocol for maximum weight matching on general graphs. We present two protocol variants, which both compute an $1/2-$approximation instead of an optimal solution in favor of scalability. For $N$ nodes, the first variant requires $\mathcal{O}(N \log^2 N)$ rounds and $\mathcal{O}(N^3\log N)$ communication, and the second variant requires only $\mathcal{O}(N \log N)$ rounds and $\mathcal{O}(N^3)$ communication. We implement both variants and find that the first variant runs in $14.9$ minutes for $N=300$ nodes, while the second variant requires only $5.1$ minutes for $N=300$, and $12.5$~minutes for $N=400$.

In this paper we study the security of two constructions for variable-length universal hash functions by means of their universality. Both constructions make use of a fixed-length unkeyed function that we call a block function. One construction is serial and is an idealization of the compression phase of Pelican-MAC. The other construction is parallel and is an idealization of the compression phase of Farfalle. Both are instances of a class of functions we call semi-group accumulators. We prove that the universality of these constructions is fully determined by the differential probability of block function differentials and, if not a permutation, the relative frequency of block function outputs. We show that both block function parallelization and serialization have equal security (against forgery) in the Wegman-Carter(-Shoup) construction. However, for the block functions we target, parallelization can provide significantly better security than serialization in the Protected Hash (PH) construction. Moreover, below a certain data limit, PH provides better security than WC(S) for the block function parallelization, despite the fact that it does not require a nonce. We show evidence of this effect by taking Xoodoo[3] as the block function .