International Association
for Cryptologic Research

Security concerns about a machine learning model used in a prediction-as-a-service include the privacy of the model, the query and the result. Secure inference solutions based on homomorphic encryption (HE) and/or multiparty computation (MPC) have been developed to protect all the sensitive information. One of the most efficient type of solution utilizes HE for linear layers, and MPC for non-linear layers. However, for such hybrid protocols with semi-honest security, an adversary can malleate the intermediate features in the inference process, and extract model information more effectively than methods against inference service in plaintext. In this paper, we propose SEEK, a general extraction method for hybrid secure inference services outputing only class labels. This method can extract each layer of the target model independently, and is not affected by the depth of the model. For ResNet-18, SEEK can extract a parameter with less than 50 queries on average, with average error less than $0.03\%$.

In ASIACRYPT 2017, Rønjom et al. analyzed AES with yoyo attack. Inspired by their 4-round AES distinguisher, Grassi proposed the mixture differential cryptanalysis as well as a key recovery attack on 5-round AES, which was shown to be better than the classical square attack in computation complexity. After that, Bardeh et al. combined the exchange attack with the 4-round mixture differential distinguisher of AES, leading to the first secret-key chosen plaintext distinguisher for 6-round AES. Unlike the attack on 5-round AES, the result of 6-round key-recovery attack on AES has extremely large complexity, which implies the weakness of mixture difference to a certain extent. Our work aims at evaluating the security of AES-like ciphers against mixture differential cryptanalysis. We propose a new structure called a boomerang struncture and illustrate that a differential distinguisher of a boomerang struncture just corresponds to a mixture differential distinguisher for AES-like ciphers. Based on the boomerang structure, it is shown that the mixture differential cryptanalysis is not suitable to be applied to AES-like ciphers with high round number. In specific, we associate the primitive index with our framework built on the boomerang structure and give the upper bound for the length of mixture differentials with probability 1 on AES-like ciphers. It can be directly deduced from our framework that there is no mixture differential distinguisher for 6-round AES.

While research in post-quantum cryptography (PQC) has gained significant momentum, it is only slowly adopted for real-world products. This is largely due to concerns about practicability and maturity. The secure boot process of embedded devices is one s- cenario where such restraints can result in fundamental security problems. In this work, we present a flexible hardware/software co-design for hash-based signature (HBS) schemes which enables the move to a post-quantum secure boot today. These signature schemes stand out due to their straightforward security proofs and are on the fast track to standardisation. In contrast to previous works, we exploit the performance intensive similarities of the s- tateful LMS and XMSS schemes as well as the stateless SPHINCS+ scheme. Thus, we enable designers to use a stateful or stateless scheme depending on the constraints of each individual application. To show the feasibility of our approach, we compare our results with hardware accelerated implementations of classical asymmetric algorithms. Further, we lay out the usage of different HBS schemes during the boot process. We compare different schemes, show the importance of parameter choices, and demonstrate the performance gain with different levels of hardware acceleration.

During the design of a new primitive inspired by Squash we accidentally stumbled on the observation described in this note.

Let $n$ be a $k$-bit Mersenne number whose factors are unknown. Consider an $\ell$-bit secret number $x=2^{k/2}a+b$. We observe that there are parameter configurations where a chunk of the value $b^2$ is leaked even if $k<2\ell$.

This observation does not endanger any known scheme and in particular not Squash.

We present the first fully collusion resistant traitor tracing (TT) scheme for identity-based inner product functional encryption (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity traceable IBIPFE (EI-TIBIPFE), where secret keys and ciphertexts are computed for vectors u and v respectively. Additionally, each secret key is associated with a user identification information tuple (i , id, gid) that specifies user index i , user identity id and an identity gid of a group to which the user belongs. The ciphertexts are generated under a group identity gid′ so that decryption recovers the inner product between the vectors u and v if the user is a member of the group gid′, i.e., gid = gid′. Suppose some users linked to a particular group team up and create a pirate decoder that is capable of decrypting the content of the group, then the tracing algorithm extracts at least one id from the team given black-box access to the decoder. In prior works, such TT schemes are built for usual public key encryptions. The only existing TIPFE scheme proposed by Do, Phan, and Pointcheval [CT-RSA’20] can trace user indices but not the actual identities. Moreover, their scheme achieves selective security and private traceability, meaning that it is only the trusted authority that is able to trace user indices. In this work, we present the following TT schemes with varying parameters and levels of security: (1) We generically construct EI-TIBIPFE assuming the existence of IBIPFE. The scheme preserves the security level of the underlying IBIPFE. (2) We build an adaptively secure EI-TIPFE scheme from bilinear maps. Note that EI-TIPFE is a particular case of EI-TIBIPFE, which does not consider group identities. (3) Next, we construct a selectively secure EI-TIBIPFE from bilinear maps. As an intermediate step, we design the first IBIPFE scheme based on a target group assumption in the standard model. (4) Finally, we provide a generic construction of selectively secure EI-TIBIPFE from lattices, namely under the standard Learning With Errors assumption. Our pairing-based schemes support public traceability and the ciphertext size grows with $\sqrt{n}$, whereas in the IBIPFE and lattice-based ones, it grows linearly with n. The main technical difficulty is designing such an advanced TT scheme for an IBIPFE that is beyond IPFE and more suitable for real-life applications.

Over the last few years, deep learning is becoming the most trending topic for the classical cryptanalysis of block ciphers. Differential cryptanalysis is one of the primary and potent attacks on block ciphers. Here we apply deep learning techniques to model differential cryptanalysis more easily. In this paper, we report a generic tool using deep neural classifier that assists to find differential distinguishers for block ciphers with reduced round. We apply this approach for the differential cryptanalysis of ARX- based encryption schemes HIGHT, LEA, and SPARX. The result shows that our deep learning based distinguishers work with high accuracy for 14-round HIGHT, 13-Round LEA and 11-round SPARX. We also achieve an improvement of the lower bound of data complexity for these three ARX based ciphers.

Attribute-based encryption (ABE) extends public-key encryption to enable fine-grained control to encrypted data. However, this comes at the cost of needing a central trusted authority to issue decryption keys. A multi-authority ABE (MA-ABE) scheme decentralizes ABE and allows anyone to serve as an authority. Existing constructions of MA-ABE only achieve security in the random oracle model.

In this work, we develop new techniques for constructing MA-ABE for the class of subset policies (which captures policies such as conjunctions and DNF formulas) whose security can be based in the plain model without random oracles. We achieve this by relying on the recently-proposed "evasive" learning with errors (LWE) assumption by Wee (EUROCRYPT 2022) and Tsabury (CRYPTO 2022).

Along the way, we also provide a modular view of the MA-ABE scheme for DNF formulas by Datta et al. (EUROCRYPT 2021) in the random oracle model. We formalize this via a general version of a related-trapdoor LWE assumption by Brakerski and Vaikuntanathan (ITCS 2022), which can in turn be reduced to the plain LWE assumption. As a corollary, we also obtain an MA-ABE scheme for subset policies from plain LWE with a polynomial modulus-to-noise ratio in the random oracle model. This improves upon the Datta et al. construction which relied on LWE with a sub-exponential modulus-to-noise ratio. Moreover, we are optimistic that the generalized related-trapdoor LWE assumption will also be useful for analyzing the security of other lattice-based constructions.

We introduce a new notion of public key encryption, knowledge encryption, for which its ciphertexts can be reduced to the public-key, i.e., any algorithm that can break the ciphertext indistinguishability can be used to extract the (partial) secret key. We show that knowledge encryption can be built solely on any two-round oblivious transfer with game-based security, which are known based on various standard (polynomial-hardness) assumptions, such as the DDH, the Quadratic($N^{th}$) Residuosity or the LWE assumption.

We use knowledge encryption to construct the first three-round (weakly) simulatable oblivious transfer. This protocol satisfies (fully) simulatable security for the receiver, and weakly simulatable security ($(T, \epsilon)$-simulatability) for the sender in the following sense: for any polynomial $T$ and any inverse polynomial $\epsilon$, there exists an efficient simulator such that the distinguishing gap of any distinguisher of size less than $T$ is at most $\epsilon$.

Equipped with these tools, we construct a variety of fundamental cryptographic protocols with low round-complexity, assuming only the existence of two-round oblivious transfer with game-based security. These protocols include three-round delayed-input weak zero knowledge argument, three-round weakly secure two-party computation, three-round concurrent weak zero knowledge in the BPK model, and a two-round commitment with weak security under selective opening attack. These results improve upon the assumptions required by the previous constructions. Furthermore, all our protocols enjoy the above $(T, \epsilon)$-simulatability (stronger than the distinguisher-dependent simulatability), and are quasi-polynomial time simulatable under the same (polynomial hardness) assumption.

Several broadcast encryption (BE) constructions have been proposed since Fiat and Naor introduced the concept, some achieving short parameters size while others achieve better security. Since 1994, a lot of alternatives to BE have moreover been additionally proposed, such as the broadcast and trace (BT) primitive which is a combination of broadcast encryption and traitor tracing. Among the other variants of BE, the notion of augmented BE (AugBE), introduced by Boneh and Waters in 2006, corresponds to a BE scheme with the particularity that the encryption algorithm takes an index as an additional parameter. If an AugBE scheme is both message and index hiding, it has been proved that it can generically be used to construct a secure BT scheme. Hence, any new result related to the former gives an improvement to the latter. In this paper, we first show that both BE and AugBE can be obtained by using an identity-based encryption scheme with wildcard (WIBE). We also introduce the new notion of anonymous AugBE, where the used users set is hidden, and prove that it implies index hiding. We then provide two different WIBE constructions. The first one has constant size ciphertext and used to construct a new constant size ciphertext BE scheme with adaptive CPA security, in the standard model (under the $\SXDH{}$ assumption). The second WIBE provides pattern-hiding, a new definition we introduced, and serves as a basis for the first anonymous AugBE scheme (and subsequently a BT scheme since our scheme is also index hiding by nature) in the literature, with adaptive security in the standard model (under the $\XDLin{}$ assumption).

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.