IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
06 June 2023
Katerina Mitrokotsa, Sayantan Mukherjee, Jenit Tomy
Identity-Based Encryption (IBE) was introduced in order to reduce the cost associated with Public Key Infrastructure systems. IBE allows users to request a trusted Key Generation Centre (KGC) for a secret key on a given identity, without the need to manage public keys. However, one of the main concerns of IBE is that the KGC has the power to decrypt all ciphertexts as it has access to all (identity, secret key) pairs. To address this issue, Chow (PKC 2009) introduced a new security property against the KGC by employing a new trusted party called the Identity Certifying Authority (ICA). Emura et al. (ESORICS 2019) formalized this notion and proposed construction in the random oracle model.
In this work, we first identify several existing IBE schemes where the KGC can decrypt a ciphertext even without knowing the receiver's identity. This paves the way for formalizing new capabilities for the KGC. We then propose a new security definition to capture an adversarial KGC including the newly identified capabilities and we remove the requirement of an additional trusted party. Finally, we propose a new IBE construction that allows users to ask the KGC for a secret key on an identity without leaking any information about the identity to the KGC that is provably secure in the standard model against an adversarial KGC and corrupted users. Our construction is achieved in the composite order pairing groups and requires essentially optimal parameters.
Ulrich Haböck, Daniel Lubarov, Jacqueline Nabaglo
In this note we discuss Reed-Solomon codes with domain of definition within the unit circle of the complex extension $\mathbb C(F)$ of a Mersenne prime field $F$. Within this unit circle the interpolants of “real”, i.e. $F$-valued, functions are again almost real, meaning that their values can be rectified to a real representation at almost no extra cost. Second, using standard techniques for the FFT of real-valued functions, encoding can be sped up significantly. Due to the particularly efficient arithmetic of Mersenne fields, we expect these “almost native” Reed-Solomon codes to perform as native ones based on prime fields with high two-adicity, but less processor-friendly arithmetic.
Jiaxin Pan, Benedikt Wagner, Runzhi Zeng
We construct the first tightly secure authenticated key exchange (AKE) protocol from lattices. Known tight constructions are all based on Diffie-Hellman-like assumptions. Thus, our protocol is the first construction with tight security from a post-quantum assumption.
Our AKE protocol is constructed tightly from a new security notion for key encapsulation mechanisms (KEMs), called one-way security against checkable chosen-ciphertext attacks (OW- ChCCA). We show how an OW-ChCCA secure KEM can be tightly constructed based on the Learning With Errors assumption, leading to the desired AKE protocol. To show the usefulness of OW-ChCCA security beyond AKE, we use it to construct the first tightly bilateral selective-opening (BiSO) secure PKE. BiSO security is a stronger selective-opening notion proposed by Lai et al. (ASIACRYPT 2021).
Our AKE protocol is constructed tightly from a new security notion for key encapsulation mechanisms (KEMs), called one-way security against checkable chosen-ciphertext attacks (OW- ChCCA). We show how an OW-ChCCA secure KEM can be tightly constructed based on the Learning With Errors assumption, leading to the desired AKE protocol. To show the usefulness of OW-ChCCA security beyond AKE, we use it to construct the first tightly bilateral selective-opening (BiSO) secure PKE. BiSO security is a stronger selective-opening notion proposed by Lai et al. (ASIACRYPT 2021).
Lorenzo Grassi, Irati Manterola Ayala, Martha Norberg Hovd, Morten Øygarden, Håvard Raddum, Qingju Wang
Symmetric primitives are a cornerstone of cryptography, and have traditionally been defined over fields, where cryptanalysis is now well understood. However, a few symmetric primitives defined over rings Z_q for a composite number q have recently been proposed, a setting where security is much less studied. In this paper we focus on studying established algebraic attacks typically defined over fields and the extent of their applicability to symmetric primitives defined over the ring of integers modulo a composite q. Based on our analysis, we present an attack on full Rubato, a family of symmetric ciphers proposed by Ha et al. at Eurocrypt 2022 designed to be used in a transciphering framework for approximate fully homomorphic encryption. We show that at least 25% of the possible choices for q satisfy certain conditions that lead to a successful key recovery attack with complexity significantly lower than the claimed security level for five of the six ciphers in the Rubato family.
Vijay Dahiphale, Hrishikesh Raut, Gaurav Bansod, Devendra Dahiphale
The rise of low-power, cost-efficient internet-connected devices has led to a need for lightweight cryptography. The lightweight block cipher PRIDE, designed by Martin R. Albrecht, is one of the most efficient ciphers designed for IoT-constrained environments. It is useful for connected devices, requires fewer resources to implement, and has high performance. PRIDE is a software-oriented lightweight cipher optimized for microcontrollers. This paper focuses on the FPGA implementation of the PRIDE cipher by keeping throughput, energy, and power consumption metrics focused. The paper also presents a novel and simpler diagrammatical view of a Matrix Layer implementation of the PRIDE cipher. We also implemented the PRESENT cipher using the same metrics. We analyzed different design metrics on Field Programmable Gate Arrays (FPGAs) and compared the metrics of the PRIDE implementation with the well-known cipher PRESENT. This gives us an insight into the efficiency and reliability of PRIDE in IoT-constrained environments. We also proposed different architectures of the PRIDE cipher for 16-bit and 32-bit datapaths.
Ananya Appan, Ashish Choudhury
We initiate the study of the network agnostic MPC protocols with statistical security. Network agnostic protocols give the best possible security guarantees irrespective of the underlying network type. We consider the general-adversary model, where the adversary is characterized by an adversary structure which enumerates all possible candidate subsets of corrupt parties. The $\mathcal{Q}^{(k)}$ condition enforces that the union of no $k$ subsets from the adversary structure covers the party set. Given an unconditionally-secure PKI setup, known statistically-secure synchronous MPC protocols are secure against adversary structures satisfying the $\mathcal{Q}^{(2)}$ condition. Known statistically-secure asynchronous MPC protocols can tolerate $\mathcal{Q}^{(3)}$ adversary structures. Fix a set of $n$ parties $\mathcal{P} = \{P_1, ... ,P_n\}$ and adversary structures $\mathcal{Z}_s$ and $\mathcal{Z}_a$, satisfying the $\mathcal{Q}^{(2)}$ and $\mathcal{Q}^{(3)}$ conditions respectively, where $\mathcal{Z}_a \subset \mathcal{Z}_s$. Then, given an unconditionally-secure PKI, we ask whether it is possible to design a statistically-secure MPC protocol resilient against $\mathcal{Z}_s$ and $\mathcal{Z}_a$ in a synchronous and an asynchronous network respectively if the parties in $\mathcal{P}$ are unaware of the network type. We show that it is possible iff $\mathcal{Z}_s$ and $\mathcal{Z}_a$ satisfy the $\mathcal{Q}^{(2,1)}$ condition, meaning that the union of any two subsets from $\mathcal{Z}_s$ and any one subset from $\mathcal{Z}_a$ is a proper subset of $\mathcal{P}$. We design several important network agnostic building blocks with the $\mathcal{Q}^{(2,1)}$ condition, such as Byzantine broadcast, Byzantine agreement, information checking protocol, verifiable secret-sharing and secure multiplication protocol, whose complexity is polynomial in $n$ and $|\mathcal{Z}_s|$.
Anna Hambitzer, David Gerault, Yun Ju Huang, Najwa Aaraj, Emanuele Bellini
We introduce a deep learning ensemble (NNBits) as a tool for bit-profiling and evaluation of cryptographic (pseudo) random bit sequences. Onthe one hand, we show how to use NNBits ensemble to ex-plain parts of the seminal work of Gohr [16]: Gohr’s depth-1 neural distinguisher reaches a test accuracy of 78.3% in round 6 for SPECK32/64 [3]. Using the bit-level information provided by NNBits we can partially ex- plain the accuracy obtained by Gohr (78.1% vs. 78.3%). This is achieved by constructing a distinguisher which only uses the information about correct or incorrect predictions on the single bit level and which achieves 78.1% accuracy. We also generalize two heuristic aspects in the construction of Gohr’s network: i) the particular input structure, which reflects expert knowledge of SPECK32/64, as well as ii) the cyclic learning rate. On the other hand, we extend Gohr’s work as a statistical test on avalanche datasets of SPECK32/64, SPECK64/128, SPECK96/144, SPECK128/128, and AES-128. In combination with NNBits ensemble we use the extended version of Gohr’s neural network to draw a comparison with the NIST Statistical Test Suite (NIST STS) on the previously mentioned avalanche datasets. We compare NNBits in conjunction with Gohr’s generalized network to the NIST STS and conclude that the NNBits ensemble performs either as good as the NIST STS or better. Furthermore, we demonstrate cryptanalytic insights that result from bit-level profiling with NNBits, for example, we show how to infer the strong input difference (0x0040, 0x0000) for SPECK32/64 or infer a signature of the multiplication in the Galois field of AES-128.
Thomas Attema, Serge Fehr, Nicolas Resch
A classic result in the theory of interactive proofs shows that a special-sound $\Sigma$-protocol is automatically a proof of knowledge. This result is very useful to have, since the latter property is typically tricky to prove from scratch, while the former is often easy to argue---if it is satisfied. While classic $\Sigma$-protocols often are special-sound, this is unfortunately not the case for many recently proposed, highly efficient interactive proofs, at least not in this strict sense. Motivated by this, the original result was recently generalized to $k$-special sound $\Sigma$-protocols (for arbitrary, polynomially bounded $k$), and to multi-round versions thereof. This generalization is sufficient to analyze (e.g.) Bulletproofs-like protocols, but is still insufficient for many other examples.
In this work, we push the relaxation of the special soundness property to the extreme, by allowing an arbitrary access structure $\Gamma$ to specify for which subsets of challenges it is possible to compute a witness, when given correct answers to these challenges (for a fixed first message). Concretely, for any access structure $\Gamma$, we identify parameters $t_\Gamma$ and $\kappa_\Gamma$, and we show that any $\Gamma$-special sound $\Sigma$-protocol is a proof of knowledge with knowledge error $\kappa_\Gamma$ if $t_\Gamma$ is polynomially bounded. Similarly for multi-round protocols.
We apply our general result to a couple of simple but important example protocols, where we obtain a tight knowledge error as an immediate corollary. Beyond these simple examples, we analyze the FRI protocol. Here, showing the general special soundness notion is non-trivial, but can be done (for a certain range of parameters) by recycling some of the techniques used to argue ordinary soundness of the protocol (as an IOP). Again as a corollary, we then derive that the FRI protocol, as an interactive proof by using a Merkle-tree commitment, is a proof of knowledge with almost optimal knowledge error.
Finally, building up on the technique for the parallel repetition of $k$-special sound $\Sigma$-protocols, we show the same strong parallel repetition result for $\Gamma$-special sound $\Sigma$-protocol and its multi-round variant.
In this work, we push the relaxation of the special soundness property to the extreme, by allowing an arbitrary access structure $\Gamma$ to specify for which subsets of challenges it is possible to compute a witness, when given correct answers to these challenges (for a fixed first message). Concretely, for any access structure $\Gamma$, we identify parameters $t_\Gamma$ and $\kappa_\Gamma$, and we show that any $\Gamma$-special sound $\Sigma$-protocol is a proof of knowledge with knowledge error $\kappa_\Gamma$ if $t_\Gamma$ is polynomially bounded. Similarly for multi-round protocols.
We apply our general result to a couple of simple but important example protocols, where we obtain a tight knowledge error as an immediate corollary. Beyond these simple examples, we analyze the FRI protocol. Here, showing the general special soundness notion is non-trivial, but can be done (for a certain range of parameters) by recycling some of the techniques used to argue ordinary soundness of the protocol (as an IOP). Again as a corollary, we then derive that the FRI protocol, as an interactive proof by using a Merkle-tree commitment, is a proof of knowledge with almost optimal knowledge error.
Finally, building up on the technique for the parallel repetition of $k$-special sound $\Sigma$-protocols, we show the same strong parallel repetition result for $\Gamma$-special sound $\Sigma$-protocol and its multi-round variant.
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl
The computational overhead of a cryptographic task is the asymptotic ratio between the computational cost of securely realizing the task and that of realizing the task with no security at all.
Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2008) showed that secure two-party computation of Boolean circuits can be realized with constant computational overhead, independent of the desired level of security, assuming the existence of an oblivious transfer (OT) protocol and a local pseudorandom generator (PRG). However, this only applies to the case of semi-honest parties. A central open question in the area is the possibility of a similar result for malicious parties. This question is open even for the simpler task of securely realizing many instances of a constant-size function, such as OT of bits.
We settle the question in the affirmative for the case of OT, assuming: (1) a standard OT protocol, (2) a slightly stronger "correlation-robust" variant of a local PRG, and (3) a standard sparse variant of the Learning Parity with Noise (LPN) assumption. An optimized version of our construction requires fewer than 100 bit operations per party per bit-OT. For 128-bit security, this improves over the best previous protocols by 1-2 orders of magnitude.
We achieve this by constructing a constant-overhead pseudorandom correlation generator (PCG) for the bit-OT correlation. Such a PCG generates $N$ pseudorandom instances of bit-OT by locally expanding short, correlated seeds. As a result, we get an end-to-end protocol for generating $N$ pseudorandom instances of bit-OT with $o(N)$ communication, $O(N)$ computation, and security that scales sub-exponentially with $N$.
Finally, we present applications of our main result to realizing other secure computation tasks with constant computational overhead. These include protocols for general circuits with a relaxed notion of security against malicious parties, protocols for realizing $N$ instances of natural constant-size functions, and reducing the main open question to a potentially simpler question about fault-tolerant computation.
Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2008) showed that secure two-party computation of Boolean circuits can be realized with constant computational overhead, independent of the desired level of security, assuming the existence of an oblivious transfer (OT) protocol and a local pseudorandom generator (PRG). However, this only applies to the case of semi-honest parties. A central open question in the area is the possibility of a similar result for malicious parties. This question is open even for the simpler task of securely realizing many instances of a constant-size function, such as OT of bits.
We settle the question in the affirmative for the case of OT, assuming: (1) a standard OT protocol, (2) a slightly stronger "correlation-robust" variant of a local PRG, and (3) a standard sparse variant of the Learning Parity with Noise (LPN) assumption. An optimized version of our construction requires fewer than 100 bit operations per party per bit-OT. For 128-bit security, this improves over the best previous protocols by 1-2 orders of magnitude.
We achieve this by constructing a constant-overhead pseudorandom correlation generator (PCG) for the bit-OT correlation. Such a PCG generates $N$ pseudorandom instances of bit-OT by locally expanding short, correlated seeds. As a result, we get an end-to-end protocol for generating $N$ pseudorandom instances of bit-OT with $o(N)$ communication, $O(N)$ computation, and security that scales sub-exponentially with $N$.
Finally, we present applications of our main result to realizing other secure computation tasks with constant computational overhead. These include protocols for general circuits with a relaxed notion of security against malicious parties, protocols for realizing $N$ instances of natural constant-size functions, and reducing the main open question to a potentially simpler question about fault-tolerant computation.
André Schrottenloher, Marc Stevens
The meet-in-the-middle (MITM) technique has led to many key-recovery attacks on block ciphers and preimage attacks on hash functions. MITM attacks aim at finding efficiently the internal states conforming to a constrained computational path in the given design. The path is split into two independent computations (forward and backward) which are performed separately and then matched pairwise.
Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only covers AES-like designs. Schrottenloher and Stevens (CRYPTO 2022) proposed a different approach aiming at higher-level simplified models. However, their modeling was limited to cryptographic permutations.
In this paper, we extend the latter simplified modeling to also cover block ciphers with simple key schedules. The resulting modeling enables us to target a large array of primitives, typically lightweight SPN ciphers where the key schedule has a slow diffusion, or none at all. We give several applications such as full breaks of the PIPO-256 and FUTURE block ciphers, and reduced-round classical and quantum attacks on SATURNIN-Hash.
Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only covers AES-like designs. Schrottenloher and Stevens (CRYPTO 2022) proposed a different approach aiming at higher-level simplified models. However, their modeling was limited to cryptographic permutations.
In this paper, we extend the latter simplified modeling to also cover block ciphers with simple key schedules. The resulting modeling enables us to target a large array of primitives, typically lightweight SPN ciphers where the key schedule has a slow diffusion, or none at all. We give several applications such as full breaks of the PIPO-256 and FUTURE block ciphers, and reduced-round classical and quantum attacks on SATURNIN-Hash.
Morten Dahl, Daniel Demmler, Sarah Elkazdadi, Arthur Meyre, Jean-Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Samuel Tap, Michael Walter
We outline a secure and efficient methodology to do threshold distributed decryption for LWE based Fully Homomorphic Encryption schemes. The only ``difficult'' case being that of TFHE (due to the small parameters used in this scheme). We show that the standard technique of ``noise flooding'' can also be used with schemes with small parameters, by utilizing a switch to a scheme with slightly higher parameters and then utilizing the efficient bootstrapping operations which TFHE offers. Our protocol is proved secure via a simulation argument, making it's integration in bigger protocols easier to manage.
Zhengjun Cao, Lihua Liu
We show that the searchable encryption scheme [IEEE Trans. Parallel Distrib. Syst., 32 (3), 2021, 561--574] cannot work because the Data Provider's secret key $sk_{DP}$ and the Request User's secret key $sk_{RU}$ are not available to the Cloud Platform (CP) or the Internal Server (IS). The CP and IS cannot finish the secure bit-decomposition protocol, which requires CP or IS to decrypt the blinded integer so as to securely handle the least significant bit of the target integer.
Seny Kamara, Tarik Moataz
Sub-linear encrypted search algorithms (ESA) are highly efficient search algorithms that operate on end-to-end encrypted data. ESAs can be built using a variety of cryptographic primitives and can achieve different trade-offs between efficiency, expressiveness and leakage. Since the introduction of ESAs, cryptographers have focused on both minimizing and attacking their leakage but an important open problem in the field has been to provide a theoretical framework with which leakage can be analyzed and better understood.
In this work, we propose such a framework. We model leakage profiles as Bayesian networks and capture leakage attacks as statistical inference algorithms on these networks. We then formalize a notion we call coherence which, roughly speaking, captures the quality of the inference given some observed leakage and an auxiliary distribution. In this work, we focus on partial and full query recovery attacks, though our framework can be extended to capture data recovery attacks as well.
We then use our framework to study the coherence of two common leakage patterns---the query equality pattern and the volume pattern---against two well-known and powerful statistical inference techniques. In each case, we provide generic bounds on the coherence in the sense that they apply to arbitrary query and auxiliary distributions and concrete analyses for specific pairs of query and auxiliary distributions.
In this work, we propose such a framework. We model leakage profiles as Bayesian networks and capture leakage attacks as statistical inference algorithms on these networks. We then formalize a notion we call coherence which, roughly speaking, captures the quality of the inference given some observed leakage and an auxiliary distribution. In this work, we focus on partial and full query recovery attacks, though our framework can be extended to capture data recovery attacks as well.
We then use our framework to study the coherence of two common leakage patterns---the query equality pattern and the volume pattern---against two well-known and powerful statistical inference techniques. In each case, we provide generic bounds on the coherence in the sense that they apply to arbitrary query and auxiliary distributions and concrete analyses for specific pairs of query and auxiliary distributions.
Cody Freitag, Brent Waters, David J. Wu
Witness encryption is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of witness encryption relied on multilinear maps and indistinguishability obfuscation (iO), recent works have provided direct constructions of witness encryption that are more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using witness encryption to realize advanced cryptographic primitives previously known only in "obfustopia."
In this work, we give new constructions of trustless encryption systems from plain witness encryption (in conjunction with the learning-with-errors assumption): (1) flexible broadcast encryption (a broadcast encryption scheme where users choose their own secret keys and users can encrypt to an arbitrary set of public keys); and (2) registered attribute-based encryption (a system where users choose their own keys and then register their public key together with a set of attributes with a deterministic and transparent key curator). Both primitives were previously only known from iO. We also show how to use our techniques to obtain an optimal broadcast encryption scheme in the random oracle model.
Underlying our constructions is a novel technique for using witness encryption based on a new primitive which we call function-binding hash functions. Whereas a somewhere statistically binding hash function statistically binds a digest to a few bits of the input, a function-binding hash function statistically binds a digest to the output of a function of the inputs. As we demonstrate in this work, function-binding hash functions provide us new ways to leverage the power of plain witness encryption and use it as the foundation of advanced cryptographic primitives. Finally, we show how to build function-binding hash functions for the class of disjunctions of block functions from leveled homomorphic encryption; this in combination with witness encryption yields our main results.
In this work, we give new constructions of trustless encryption systems from plain witness encryption (in conjunction with the learning-with-errors assumption): (1) flexible broadcast encryption (a broadcast encryption scheme where users choose their own secret keys and users can encrypt to an arbitrary set of public keys); and (2) registered attribute-based encryption (a system where users choose their own keys and then register their public key together with a set of attributes with a deterministic and transparent key curator). Both primitives were previously only known from iO. We also show how to use our techniques to obtain an optimal broadcast encryption scheme in the random oracle model.
Underlying our constructions is a novel technique for using witness encryption based on a new primitive which we call function-binding hash functions. Whereas a somewhere statistically binding hash function statistically binds a digest to a few bits of the input, a function-binding hash function statistically binds a digest to the output of a function of the inputs. As we demonstrate in this work, function-binding hash functions provide us new ways to leverage the power of plain witness encryption and use it as the foundation of advanced cryptographic primitives. Finally, we show how to build function-binding hash functions for the class of disjunctions of block functions from leveled homomorphic encryption; this in combination with witness encryption yields our main results.
Giuseppe Persiano, Kevin Yeo
Oblivious RAMs (ORAMs) are an important cryptographic primitive that enable outsourcing data to a potentially untrusted server while hiding patterns of access to the data. ORAMs provide strong guarantees even in the face of a {\em persistent adversary} that views the transcripts of all operations and resulting memory contents. Unfortunately, the strong guarantees against persistent adversaries comes at the cost of efficiency as ORAMs are known to require $\Omega(\log n)$ overhead.
In an attempt to obtain faster constructions, prior works considered security against {\em snapshot adversaries} that only have limited access to operational transcripts and memory. We consider $(s,\ell)$-snapshot adversaries that perform $s$ data breaches and views the transcripts of $\ell$ total queries. Promisingly, Du, Genkin and Grubbs [Crypto'22] presented an ORAM construction with $O(\log \ell)$ overhead protecting against $(1,\ell)$-snapshot adversaries with the transcript of $\ell$ consecutive operations from a single breach. For small values of $\ell$, this outperforms standard ORAMs.
In this work, we tackle whether it is possible to further push this construction beyond a single breach. Unfortunately, we show that protecting against even slightly stronger snapshot adversaries becomes difficult. As our main result, we present a $\Omega(\log n)$ lower bound for any ORAM protecting against a $(3,1)$-snapshot adversary that performs three breaches and sees the transcript of only one query. In other words, our lower bound holds even if an adversary observes only memory contents during two breaches while managing to view the transcript of only one query in the other breach. Therefore, we surprisingly show that protecting against a snapshot adversary with three data breaches is as difficult as protecting against a persistent adversary
In an attempt to obtain faster constructions, prior works considered security against {\em snapshot adversaries} that only have limited access to operational transcripts and memory. We consider $(s,\ell)$-snapshot adversaries that perform $s$ data breaches and views the transcripts of $\ell$ total queries. Promisingly, Du, Genkin and Grubbs [Crypto'22] presented an ORAM construction with $O(\log \ell)$ overhead protecting against $(1,\ell)$-snapshot adversaries with the transcript of $\ell$ consecutive operations from a single breach. For small values of $\ell$, this outperforms standard ORAMs.
In this work, we tackle whether it is possible to further push this construction beyond a single breach. Unfortunately, we show that protecting against even slightly stronger snapshot adversaries becomes difficult. As our main result, we present a $\Omega(\log n)$ lower bound for any ORAM protecting against a $(3,1)$-snapshot adversary that performs three breaches and sees the transcript of only one query. In other words, our lower bound holds even if an adversary observes only memory contents during two breaches while managing to view the transcript of only one query in the other breach. Therefore, we surprisingly show that protecting against a snapshot adversary with three data breaches is as difficult as protecting against a persistent adversary
Seny Kamara, Abdelkarim Kati, Tarik Moataz, Jamie DeMaria, Andrew Park, Amos Treiber
Encrypted search algorithms (ESAs) enable private search on encrypted data and
can be constructed from a variety of cryptographic primitives. All known
sub-linear ESA algorithms leak information and, therefore, the design of leakage
attacks is an important way to ascertain whether a given leakage profile is
exploitable in practice. Recently, Oya and Kerschbaum (Usenix '22)
presented an attack called IHOP that targets the query equality
pattern---which reveals if and when two queries are for the same keyword---of a
sequence of dependent queries.
In this work, we continue the study of query equality leakage on dependent queries and present two new attacks in this setting which can work either as known-distribution or known-sample attacks. They model query distributions as Markov processes and leverage insights and techniques from stochastic processes and machine learning. We implement our attacks and evaluate them on real-world query logs. Our experiments show that they outperform the state-of-the-art in most settings but also have limitations in practical settings.
In this work, we continue the study of query equality leakage on dependent queries and present two new attacks in this setting which can work either as known-distribution or known-sample attacks. They model query distributions as Markov processes and leverage insights and techniques from stochastic processes and machine learning. We implement our attacks and evaluate them on real-world query logs. Our experiments show that they outperform the state-of-the-art in most settings but also have limitations in practical settings.
Dennis Dayanikli, Anja Lehmann
Password-based credentials (PBCs), introduced by Zhang et al. (NDSS'20), provide an elegant solution to secure, yet convenient user authentication. Therein the user establishes a strong cryptographic access credential with the server. To avoid the assumption of secure storage on the user side, the user does not store the credential directly, but only a password-protected version of it. The ingenuity of PBCs is that the password-based credential cannot be offline attacked, offering essentially the same strong security as standard key-based authentication. This security relies on a secret key of the server that is needed to verify whether an authentication token derived from a password-based credential and password is correct. However, the work by Zhang et al. assumes that this server key never gets compromised, and their protocol loses all security in case of a breach. As such a passive leak of the server's stored verification data is one of the main threats in user authentication, our work aims to strengthen PBC to remain secure even when the server's key got compromised.
We first show that the desired security against server compromise is impossible to achieve in the original framework. We then introduce a modified version of PBCs that circumvents our impossibility result and formally define a set of security properties, each being optimal for the respective corruption setting. Finally, we propose a surprisingly simple construction that provably achieves our stronger security guarantees, and is generically composed from basic building blocks.
We first show that the desired security against server compromise is impossible to achieve in the original framework. We then introduce a modified version of PBCs that circumvents our impossibility result and formally define a set of security properties, each being optimal for the respective corruption setting. Finally, we propose a surprisingly simple construction that provably achieves our stronger security guarantees, and is generically composed from basic building blocks.
Benedikt Auerbach, Charlotte Hoffmann, Guillermo Pascual-Perez
The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group.
In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH).
Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems.
A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions.
In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.
The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the $d$-strong discrete logarithm, the $d$-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup's GGM in its full generality, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach.
In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.
The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the $d$-strong discrete logarithm, the $d$-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup's GGM in its full generality, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach.
David Jacquemin, Anisha Mukherjee, Sujoy SINHA ROY, Péter Kutas
Isogeny-based cryptographic constructions are well-known in
the domain of post-quantum security. One such instance is SQISign, that
boasts the most compact key and signature sizes among all post-quantum
signature schemes. However, its current implementation is not free from
side-channel vulnerabilities. At certain steps within the signing proce-
dure, it relies on Cornacchia’s algorithm to represent an integer as a sum
of squares of two integers. This algorithm in turn uses a ‘half-GCD’ sub-
routine that is based on a non-constant time version of the Euclidean
algorithm. We show that if inputs of Cornacchia’s algorithm leaks, then
one can retrieve the signing key in polynomial time. We propose two
timing attack-resistant versions of Cornacchia’s algorithm. The first ver-
sion is based on a lattice reduction algorithm. We show that randomising
the starting basis with a unimodular matrix would make the execution
time independent of the input. The second version uses a constant-time
‘half-GCD’ algorithm that runs a fixed number of times for a given upper
bound on the size of inputs.
Hamza Abusalah
SNACKs are succinct non-interactive arguments of chain knowledge. They allow for efficient and generic solutions to blockchain light-client bootstrapping. Abusalah et al. construct SNACKs in the random oracle model for any \emph{single-chain} blockchain from any graph-labeling proof of sequential work (PoSW) scheme. Their SNACK construction is a PoSW-like protocol over the augmented blockchain. Unlike single-chain blockchains, such as proof-of-work and proof-of-stake blockchains, proof-of-space (PoSpace) blockchains are composed of two chains: a \emph{canonical} proof chain and a data chain. These two chains are related using a signature scheme.
In this work, we construct PoSW-enabled SNACKs for any PoSpace blockchain. Combined with the results of Abusalah et al., this gives the first solution to light-client bootstrapping in PoSpace blockchains. The space cost of our construction is \emph{two} hash values in each augmented PoSpace block. Generating SNACK proofs for a PoSpace blockchain is identical to generating SNACK proofs for single-chain blockchains and amounts to looking up a succinct number of augmented blocks.