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
Ohad Klein, Ilan Komargodski
We study the local leakage resilience of Shamir's secret sharing scheme. In Shamir's scheme, a random polynomial $f$ of degree $t$ is sampled over a field of size $p>n$, conditioned on $f(0)=s$ for a secret $s$. Any $t$ shares $(i, f(i))$ can be used to fully recover $f$ and thereby $f(0)$. But, any $t-1$ evaluations of $f$ at non-zero coordinates are completely independent of $f(0)$. Recent works ask whether the secret remains hidden even if say only 1 bit of information is leaked from each share, independently. This question is well motivated due to the wide range of applications of Shamir's scheme. For instance, it is known that if Shamir's scheme is leakage resilient in some range of parameters, then known secure computation protocols are secure in a local leakage model.
Over characteristic 2 fields, the answer is known to be negative (e.g., Guruswami and Wootters, STOC '16). Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO '18) were the first to give a positive answer assuming computation is done over prime-order fields. They showed that if $t \ge 0.907n$, then Shamir's scheme is leakage resilient. Since then, there has been extensive efforts to improve the above threshold and after a series of works, the current record shows leakage resilience for $t\ge 0.78n$ (Maji et al., ISIT '22). All existing analyses of Shamir's leakage resilience for general leakage functions follow a single framework for which there is a known barrier for any $t \le 0.5 n$.
In this work, we a develop a new analytical framework that allows us to significantly improve upon the previous record and obtain additional new results. Specifically, we show: $\bullet$ Shamir's scheme is leakage resilient for any $t \ge 0.69n$. $\bullet$ If the leakage functions are guaranteed to be ``balanced'' (i.e., splitting the domain of possible shares into 2 roughly equal-size parts), then Shamir's scheme is leakage resilient for any $t \ge 0.58n$. $\bullet$ If the leakage functions are guaranteed to be ``unbalanced'' (i.e., splitting the domain of possible shares into 2 parts of very different sizes), then Shamir's scheme is leakage resilient as long as $t \ge 0.01 n$. Such a result is $provably$ impossible to obtain using the previously known technique.
All of the above apply more generally to any MDS codes-based secret sharing scheme.
Confirming leakage resilience is most important in the range $t \leq n/2$, as in many applications, Shamir’s scheme is used with thresholds $t\leq n/2$. As opposed to the previous approach, ours does not seem to have a barrier at $t=n/2$, as demonstrated by our third contribution.
Over characteristic 2 fields, the answer is known to be negative (e.g., Guruswami and Wootters, STOC '16). Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO '18) were the first to give a positive answer assuming computation is done over prime-order fields. They showed that if $t \ge 0.907n$, then Shamir's scheme is leakage resilient. Since then, there has been extensive efforts to improve the above threshold and after a series of works, the current record shows leakage resilience for $t\ge 0.78n$ (Maji et al., ISIT '22). All existing analyses of Shamir's leakage resilience for general leakage functions follow a single framework for which there is a known barrier for any $t \le 0.5 n$.
In this work, we a develop a new analytical framework that allows us to significantly improve upon the previous record and obtain additional new results. Specifically, we show: $\bullet$ Shamir's scheme is leakage resilient for any $t \ge 0.69n$. $\bullet$ If the leakage functions are guaranteed to be ``balanced'' (i.e., splitting the domain of possible shares into 2 roughly equal-size parts), then Shamir's scheme is leakage resilient for any $t \ge 0.58n$. $\bullet$ If the leakage functions are guaranteed to be ``unbalanced'' (i.e., splitting the domain of possible shares into 2 parts of very different sizes), then Shamir's scheme is leakage resilient as long as $t \ge 0.01 n$. Such a result is $provably$ impossible to obtain using the previously known technique.
All of the above apply more generally to any MDS codes-based secret sharing scheme.
Confirming leakage resilience is most important in the range $t \leq n/2$, as in many applications, Shamir’s scheme is used with thresholds $t\leq n/2$. As opposed to the previous approach, ours does not seem to have a barrier at $t=n/2$, as demonstrated by our third contribution.
Mariya Georgieva Belorgey, Sofia Dandjee, Nicolas Gama, Dimitar Jetchev, Dmitry Mikushin
We propose a novel protocol, Falkor, for secure aggregation for Federated Learning in the multi-server scenario based on masking of local models via a stream cipher based on AES in counter mode and accelerated by GPUs running on the aggregating servers. The protocol is resilient to client dropout and has reduced clients/servers communication cost by a factor equal to the number of aggregating servers (compared to the naïve baseline method). It scales simultaneously in the two major complexity aspects: 1) large number of clients; 2) highly complex machine learning models such as CNNs, RNNs, Transformers, etc. The AES-CTR-based masking function in our aggregation protocol is built on the concept of counter-based cryptographically-secure pseudorandom number generators (csPRNGs) as described in [SMDS'11] and subsequently used by Facebook for their torchcsprng csPRNG. We improve upon torchcsprng by careful use of shared memory on the GPU device, a recent idea of Cihangir Tezcan [Tezcan'21] and obtain 100x speedup in the masking function compared to a single CPU core.
In addition, we prove the semantic security of the AES-CTR-based masking function. Finally, we demonstrate scalability of our protocol in two real-world Federated Learning scenarios: 1) efficient training of large logistic regression models with 50 features and 50M data points distributed across 1000 clients that can dropout and securely aggregated via three servers (running secure multi-party computation (SMPC)); 2) training a recurrent neural network (RNN) model for sentiment analysis of Twitter feeds coming from a large number of Twitter users (more than 250,000 users). In case 1), our secure aggregation algorithm runs in less than a minute compared to a pure MPC computation (on 3 parties) that takes 27 hours and uses 400GB RAM machines as well as 1 gigabit-per-second network. In case 2), the total training is around $10$ minutes using our GPU powered secure aggregation versus 10 hours using a single CPU core.
In addition, we prove the semantic security of the AES-CTR-based masking function. Finally, we demonstrate scalability of our protocol in two real-world Federated Learning scenarios: 1) efficient training of large logistic regression models with 50 features and 50M data points distributed across 1000 clients that can dropout and securely aggregated via three servers (running secure multi-party computation (SMPC)); 2) training a recurrent neural network (RNN) model for sentiment analysis of Twitter feeds coming from a large number of Twitter users (more than 250,000 users). In case 1), our secure aggregation algorithm runs in less than a minute compared to a pure MPC computation (on 3 parties) that takes 27 hours and uses 400GB RAM machines as well as 1 gigabit-per-second network. In case 2), the total training is around $10$ minutes using our GPU powered secure aggregation versus 10 hours using a single CPU core.
Gideon Samid
For decades now, mathematical complexity is being regarded as the sole means to creating a sufficient distance between a ciphertext and its generating plaintext. Alas, mathematical complexity operates under the irremovable shadow of stealth cryptanalysis. By its nature mathematical complexity is vulnerable to smarter mathematicians and better equipped adversaries, which is a sufficient motivation to explore an alternative means to project security. Applying the Innovation Solution Protocol such an alternative has been found: randomness. Not as next to mathematical complexity, rather as its replacement. Unlike complexity, randomness is not vulnerable to smarter mathematicians and better equipped adversaries. It removes the shadow under which all modern ciphers operate by proposing a framework wherein the message transmitter may apply arbitrary quantities of ad-hoc randomness with which to secure a transmission over a secret key of arbitrary large size; and where only a part thereto may participate in any instance of encryption; and where security is increased in proportion to the amount of randomness involved. Handling the large quantities of randomness is 'messy' and inconvenient, albeit, the user, not the cipher designer, decides how much inconvenience to put up with in order to build sufficient security to meet the pressing threat. With sufficient randomness, transmission security may exceed One-Time-Pad (OTP) in as much as even the size of the plaintext is not determinable. Ciphers that shift the security responsibility to the user are called "Trans-Vernam", honoring Gilbert S. Vernam's OTP, or "Tesla Ciphers", reflective of the fact that Tesla offered a new power source for the automotive industry, much as the Tesla ciphers offer a new security source for cyberspace. The Tesla cryptographic modality has its security substantiated with a mathematical proof. It is Quantum ready and AI resistant. It is battery-friendly, and ultra fast. Albeit this proposal brings to question a long-established cryptographic premise, with all that is involved.
Noga Amit, Guy Rothblum
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.
Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash functions.
We show that $one$-$way\ functions$ suffice for obtaining constant-round arguments of almost-linear verification time for languages in $\mathbf{P}$ that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian's) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time.
Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for $\mathbf{NC}$ (indeed, even for $\mathbf{AC}^1$).
Charles Bouillaguet, Ambroise Fleury, Pierre-Alain Fouque, Paul Kirchner
The Number Field Sieve (NFS) is the state-of-the art algorithm for integer
factoring, and sieving is a crucial step in the NFS. It is a very
time-consuming operation, whose goal is to collect many relations. The
ultimate goal is to generate random smooth integers mod $N$ with their prime
decomposition, where smooth is defined on the rational and algebraic sides
according to two prime factor bases.
In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split into different stages depending on the size of the primes, but defining good parameters for all stages is based on heuristic and practical arguments. At the beginning, candidates are sieved by small primes on both sides, and if they pass the test, they continue to the next stages with bigger primes, up to the final one where we factor the remaining part using the ECM algorithm. On the one hand, first stages are fast but many false relations pass them, and we spend a lot of time with useless relations. On the other hand final stages are more time demanding but outputs less relations. It is not easy to evaluate the performance of the best strategy on the overall sieving step since it depends on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up this step since many improvements have been done on all other steps of the NFS. Based on the relations collected during the RSA-250 factorization and all parameters, we try to study different strategies to better understand this step. Many strategies have been defined since the discovery of NFS, and we provide here an experimental evaluation.
In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split into different stages depending on the size of the primes, but defining good parameters for all stages is based on heuristic and practical arguments. At the beginning, candidates are sieved by small primes on both sides, and if they pass the test, they continue to the next stages with bigger primes, up to the final one where we factor the remaining part using the ECM algorithm. On the one hand, first stages are fast but many false relations pass them, and we spend a lot of time with useless relations. On the other hand final stages are more time demanding but outputs less relations. It is not easy to evaluate the performance of the best strategy on the overall sieving step since it depends on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up this step since many improvements have been done on all other steps of the NFS. Based on the relations collected during the RSA-250 factorization and all parameters, we try to study different strategies to better understand this step. Many strategies have been defined since the discovery of NFS, and we provide here an experimental evaluation.
Benoit Libert
Vector commitment schemes are compressing commitments to vectors that make it possible to succinctly open a commitment for individual vector positions without revealing anything about other positions. We describe vector commitments enabling constant-size proofs that the committed vector is small (i.e., binary, ternary, or of small norm). As a special case, we obtain range proofs featuring the shortest proof length in the literature with only $3$ group elements per proof. As another application, we obtain short pairing-based NIZK arguments for lattice-related statements. In particular, we obtain short proofs (comprised of $3$ group elements) showing the validity of ring LWE ciphertexts and public keys. Our constructions are proven simulation-extractable in the algebraic group model and the random oracle model.
Solane El Hirch, Joan Daemen, Raghvendra Rohit, Rusydi H. Makarim
We introduce a new type of mixing layer for the round function of cryptographic permutations, called circulant twin column parity mixer (CPM), that is a generalization of the mixing layers in KECCAK-f and XOODOO. While these mixing layers have a bitwise differential branch number of 4 and a computational cost of 2 (bitwise) additions per bit, the circulant twin CPMs we build have a bitwise differential branch number of 12 at the expense of an increase in computational cost: depending on the dimension this ranges between $3$ and $3.34$ XORs per bit. Our circulant twin CPMs operate on a state in the form of a rectangular array and can serve as mixing layer in a round function that has as non-linear step a layer of S-boxes operating in parallel on the columns. When sandwiched between two ShiftRow-like mappings, we can obtain a columnwise branch number of 12 and hence it guarantees 12 active S-boxes per two rounds in differential trails. Remarkably, the linear branch numbers (bitwise and columnwise alike) of these mappings is only 4. However, we define the transpose of a circulant twin CPM that has linear branch number of 12 and a differential branch number of 4. We give a concrete instantiation of a permutation using such a mixing layer, named Gaston. It operates on a state of $5 \times 64$ bits and uses $\chi$ operating on columns for its non-linear layer. Most notably, the Gaston round function is lightweight in that it takes as few bitwise operations as the one of NIST lightweight standard ASCON. We show that the best 3-round differential and linear trails of Gaston have much higher weights than those of ASCON. Permutations like Gaston can be very competitive in applications that rely for their security exclusively on good differential properties, such as keyed hashing as in the compression phase of Farfalle.
Alexandru Cojocaru, Juan Garay, Fang Song
In this work we examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. Specifically, for search problems that are allowed to have multiple solutions and in which the input is sampled according to uniform or Bernoulli distributions, we establish their hybrid quantum-classical query complexities---i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms recently proposed by Rosmanis. Namely, for an arbitrary distribution $D$ on Boolean functions, the probability that an algorithm equipped with $\tau_c$ classical queries and $\tau_c$ quantum queries succeeds in finding a preimage of $1$ for a function sampled from $D$ is at most $\nu_D \cdot (2\sqrt{\tau_c} + 2\tau_q + 1)^2$, where $\nu_D$ captures the average (over $D$) fraction of preimages of $1$.
As applications of our results, we first revisit and generalize the formal security treatment of the Bitcoin protocol called the Bitcoin backbone [Eurocrypt 2015], to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we re-examine the generic security of hash functions
[PKC 2016] against quantum-classical hybrid adversaries.
Timo Glaser, Alexander May, Julian Nowakowski
Modern (lattice-based) cryptosystems typically sample their secret keys component-wise and independently from a discrete probability distribution $\chi$. For instance, KYBER has secret key entries from the centered binomial distribution, DILITHIUM from the uniform distribution, and FALCON from the discrete Gaussian.
As attacks may require guessing of a subset of the secret key coordinates, the complexity of enumerating such sub-keys is of fundamental importance.
Any length-$n$ sub-key with entries sampled from $\chi$ has entropy $\operatorname{H}(\chi)n$, where $\operatorname{H}(\chi)$ denotes the entropy of $\chi$.
If $\chi$ is the uniform distribution, then it is easy to see that any length-$n$ sub-key can be enumerated with $2^{\operatorname{H}(\chi)n}$ trials.
However, for sub-keys sampled from general probability distributions, Massey (1994) ruled out that the number of key guesses can be upper bounded by a function of the entropy alone.
In this work, we bypass Massey's impossibility result by focussing on the typical cryptographic setting, where key entries are sampled independently component-wise from some distribution $\chi$, i.e., we focus on $\chi^n$.
We study the optimal key guessing algorithm that enumerates keys in $\chi^n$ in descending order of probability, but we abort at a certain probability. As our main result, we show that for any discrete probability distribution~$\chi$ our aborted key guessing algorithm tries at most $2^{\operatorname{H}(\chi)n}$ keys, and its success probability asymptotically converges to $\frac 1 2$. Our algorithm allows for a quantum version with at most $2^{\operatorname{H}(\chi) n/ 2}$ key guesses. In other words, for any distribution $\chi$, we achieve a Grover-type square root speedup, which we show to be optimal.
For the underlying key distributions of KYBER and FALCON, we explicitly compute the expected number of key guesses and their success probabilities for our aborted key guessing for all sub-key lengths $n$ of practical interest. Our experiments strongly indicate that our aborted key guessing, while sacrificing only a factor of two in success probability, improves over the usual (non-aborted) key guessing by a run time factor exponential in $n$.
We study the optimal key guessing algorithm that enumerates keys in $\chi^n$ in descending order of probability, but we abort at a certain probability. As our main result, we show that for any discrete probability distribution~$\chi$ our aborted key guessing algorithm tries at most $2^{\operatorname{H}(\chi)n}$ keys, and its success probability asymptotically converges to $\frac 1 2$. Our algorithm allows for a quantum version with at most $2^{\operatorname{H}(\chi) n/ 2}$ key guesses. In other words, for any distribution $\chi$, we achieve a Grover-type square root speedup, which we show to be optimal.
For the underlying key distributions of KYBER and FALCON, we explicitly compute the expected number of key guesses and their success probabilities for our aborted key guessing for all sub-key lengths $n$ of practical interest. Our experiments strongly indicate that our aborted key guessing, while sacrificing only a factor of two in success probability, improves over the usual (non-aborted) key guessing by a run time factor exponential in $n$.
Bart Mennink, Charlotte Lefevre
The Ascon authenticated encryption scheme has recently been selected as winner of the NIST Lightweight Cryptography competition. Despite its fame, however, there is no known generic security analysis of its mode: most importantly, all related generic security results only use the key to initialize the state and do not take into account key blinding internally and at the end. In this work we present a thorough multi-user security analysis of the Ascon mode, where particularly the key blinding is taken into account. Most importantly, our analysis includes an authenticity study in various attack settings. This analysis includes a description of a new security model of authenticity under state recovery, that captures the idea that the mode aims to still guarantee authenticity and security against key recovery even if an inner state is revealed to the adversary in some way, for instance through leakage. We prove that Ascon satisfies this security property, thanks to its unique key blinding technique.
Shun Watanabe, Kenji Yasunaga
Hardness amplification is one of the important reduction techniques in cryptography, and it has been extensively studied in the literature. The standard XOR lemma known in the literature evaluates the hardness in terms of the probability of correct prediction; the hardness is amplified from mildly hard (close to $1$) to very hard $1/2 + \varepsilon$ by inducing $\varepsilon^2$ multiplicative decrease of the circuit size. Translating such a statement in terms of the bit-security framework introduced by Micciancio-Walter (EUROCRYPT 2018) and Watanabe-Yasunaga (ASIACRYPT 2021), it may cause the bit-security loss by the factor of $\log(1/\varepsilon)$. To resolve this issue, we derive a new variant of the XOR lemma in terms of the R\'enyi advantage, which directly characterizes the bit security. In the course of proving this result, we prove a new variant of the hardcore lemma in terms of the conditional squared advantage; our proof uses a boosting algorithm that may output the $\bot$ symbol in addition to $0$ and $1$, which may be of independent interest.
Takanori Isobe, Ryoma Ito, Fukang Liu, Kazuhiko Minematsu, Motoki Nakahashi, Kosei Sakamoto, Rentaro Shiba
In real-world applications, the overwhelming majority of cases require (authenticated) encryption or hashing with relatively short input, say up to 2K bytes. Almost all TCP/IP packets are 40 to 1.5K bytes, and the maximum packet lengths of major protocols, e.g., Zigbee, Bluetooth low energy, and Controller Area Network (CAN), are less than 128 bytes. However, existing schemes are not well optimized for short input. To bridge the gap between real-world needs (in the future) and limited performances of state-of-the-art hash functions and authenticated encryptions with associated data (AEADs) for short input, we design a family of wide-block permutations Areion that fully leverages the power of AES instructions, which are widely deployed in many devices. As for its applications, we propose several hash functions and AEADs. Areion significantly outperforms existing schemes for short input and even competitive to relatively long messages. Indeed, our hash function is surprisingly fast, and its performance is less than three cycles/byte in the latest Intel architecture for any message size. It is significantly much faster than existing state-of-the-art schemes for short messages up to around 100 bytes, which are the most widely-used input size in real-world applications, on both the latest CPU architectures (IceLake, Tiger Lake, and Alder Lake) and mobile platforms (Pixel 7, iPhone 14, and iPad Pro with Apple M2).
Fabio Campos, Jorge Chavez-Saab, Jesús-Javier Chi-Domínguez, Michael Meyer, Krijn Reijnders, Francisco Rodríguez-Henríquez, Peter Schwabe, Thom Wiggers
The isogeny-based scheme CSIDH is considered to be the only efficient post-quantum non-interactive key exchange (NIKE) and poses small bandwidth requirements, thus appearing to be an attractive alternative for classical Diffie--Hellman schemes. A crucial CSIDH design point, still under debate, is its quantum security when using prime fields of 512 to 1024 bits. Most work has focused on prime fields of that size and the practicality of CSIDH with large parameters, 2000 to 9000 bits, has so far not been thoroughly assessed, even though analysis of quantum security suggests these parameter sizes.
We fill this gap by providing two CSIDH instantiations: A deterministic and dummy-free instantiation based on SQALE, aiming at high security against physical attacks, and a speed-optimized constant-time instantiation that adapts CTIDH to larger parameter sizes. We provide implementations of both variants, including efficient field arithmetic for fields of such size, and high-level optimizations. Our deterministic and dummy-free version, dCSIDH, is almost twice as fast as SQALE, and, dropping determinism, CTIDH at these parameters is thrice as fast as dCSIDH. We investigate their use in real-world scenarios through benchmarks of TLS using our software.
Although our instantiations of CSIDH have smaller communication requirements than post-quantum KEM and signature schemes, both implementations still result in too-large handshake latency (tens of seconds), which hinder further consideration of using CSIDH in practice for conservative parameter set instantiations.
We fill this gap by providing two CSIDH instantiations: A deterministic and dummy-free instantiation based on SQALE, aiming at high security against physical attacks, and a speed-optimized constant-time instantiation that adapts CTIDH to larger parameter sizes. We provide implementations of both variants, including efficient field arithmetic for fields of such size, and high-level optimizations. Our deterministic and dummy-free version, dCSIDH, is almost twice as fast as SQALE, and, dropping determinism, CTIDH at these parameters is thrice as fast as dCSIDH. We investigate their use in real-world scenarios through benchmarks of TLS using our software.
Although our instantiations of CSIDH have smaller communication requirements than post-quantum KEM and signature schemes, both implementations still result in too-large handshake latency (tens of seconds), which hinder further consideration of using CSIDH in practice for conservative parameter set instantiations.
Jiangxia Ge, Tianshu Shan, Rui Xue
The Fujisaki-Okamoto (\textsf{FO}) transformation (CRYPTO 1999 and Journal of Cryptology 2013) and its KEM variants (TCC 2017) are used to construct \textsf{IND-CCA}-secure PKE or KEM schemes in the random oracle model (ROM).
In the post-quantum setting, the ROM is extended to the quantum random oracle model (QROM), and the \textsf{IND-CCA} security of \textsf{FO} transformation and its KEM variants in the QROM has been extensively analyzed. Grubbs et al. (EUROCRYPTO 2021) and Xagawa (EUROCRYPTO 2022) then focused on security properties other than \textsf{IND-CCA} security, such as the anonymity aganist chosen-ciphertext attacks (\textsf{ANO-CCA}) of \textsf{FO} transformation in the QROM.
Beyond the post-quantum setting, Boneh and Zhandry (CRYPTO 2013) considered quantum adversaries that can perform the quantum chosen-ciphertext attacks (\textsf{qCCA}). However, to the best of our knowledge, there are few results on the \textsf{IND-qCCA} or \textsf{ANO-qCCA} security of \textsf{FO} transformation and its KEM variants in the QROM.
In this paper, we define a class of security games called the oracle-hiding game, and provide a lifting theorem for it. This theorem lifts the security reduction of oracle-hiding games in the ROM to that in the QROM. With this theorem, we prove the \textsf{IND-qCCA} and \textsf{ANO-qCCA} security of transformation $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$, which are KEM variants of \textsf{FO}, in the QROM.
Moreover, we prove the \textsf{ANO-qCCA} security of the hybrid PKE schemes built via the KEM-DEM paradigm, where the underlying KEM schemes are obtained by $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$. Notably, for those hybrid PKE schemes, our security reduction shows that their anonymity is independent of the security of their underlying DEM schemes. Hence, our result simplifies the anonymity analysis of the hybrid PKE schemes that obtained from the \textsf{FO} transformation.
In the post-quantum setting, the ROM is extended to the quantum random oracle model (QROM), and the \textsf{IND-CCA} security of \textsf{FO} transformation and its KEM variants in the QROM has been extensively analyzed. Grubbs et al. (EUROCRYPTO 2021) and Xagawa (EUROCRYPTO 2022) then focused on security properties other than \textsf{IND-CCA} security, such as the anonymity aganist chosen-ciphertext attacks (\textsf{ANO-CCA}) of \textsf{FO} transformation in the QROM.
Beyond the post-quantum setting, Boneh and Zhandry (CRYPTO 2013) considered quantum adversaries that can perform the quantum chosen-ciphertext attacks (\textsf{qCCA}). However, to the best of our knowledge, there are few results on the \textsf{IND-qCCA} or \textsf{ANO-qCCA} security of \textsf{FO} transformation and its KEM variants in the QROM.
In this paper, we define a class of security games called the oracle-hiding game, and provide a lifting theorem for it. This theorem lifts the security reduction of oracle-hiding games in the ROM to that in the QROM. With this theorem, we prove the \textsf{IND-qCCA} and \textsf{ANO-qCCA} security of transformation $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$, which are KEM variants of \textsf{FO}, in the QROM.
Moreover, we prove the \textsf{ANO-qCCA} security of the hybrid PKE schemes built via the KEM-DEM paradigm, where the underlying KEM schemes are obtained by $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$. Notably, for those hybrid PKE schemes, our security reduction shows that their anonymity is independent of the security of their underlying DEM schemes. Hence, our result simplifies the anonymity analysis of the hybrid PKE schemes that obtained from the \textsf{FO} transformation.
Andrea Basso, Tako Boris Fouotsa
The Supersingular Isogeny Diffie-Hellman (SIDH) protocol has been the main and most efficient isogeny-based encryption protocol, until a series of breakthroughs led to a polynomial-time key-recovery attack. While some countermeasures have been proposed, the resulting schemes are significantly slower and larger than the original SIDH.
In this work, we propose a new countermeasure technique that leads to significantly more efficient and compact protocols. To do so, we introduce the concept of artificially oriented curves, which are curves with an associated pair of subgroups. We show that this information is sufficient to build parallel isogenies and thus obtain an SIDH-like key exchange, while also revealing significantly less information compared to previous constructions.
After introducing artificially oriented curves, we formalize several related computational problems and thoroughly assess their presumed hardness. We then translate the SIDH key exchange to the artificially oriented setting, obtaining the key-exchange protocols binSIDH, or binary SIDH, and terSIDH, or ternary SIDH, which respectively rely on fixed-degree and variable-degree isogenies.
Lastly, we also provide a proof-of-concept implementation of the proposed protocols. Despite being implemented in a high-level, terSIDH has very competitive running times, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.
In this work, we propose a new countermeasure technique that leads to significantly more efficient and compact protocols. To do so, we introduce the concept of artificially oriented curves, which are curves with an associated pair of subgroups. We show that this information is sufficient to build parallel isogenies and thus obtain an SIDH-like key exchange, while also revealing significantly less information compared to previous constructions.
After introducing artificially oriented curves, we formalize several related computational problems and thoroughly assess their presumed hardness. We then translate the SIDH key exchange to the artificially oriented setting, obtaining the key-exchange protocols binSIDH, or binary SIDH, and terSIDH, or ternary SIDH, which respectively rely on fixed-degree and variable-degree isogenies.
Lastly, we also provide a proof-of-concept implementation of the proposed protocols. Despite being implemented in a high-level, terSIDH has very competitive running times, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.
Yaobin Shen, François-Xavier Standaert
We consider the design of a tweakable block cipher from a block cipher whose inputs and outputs are of size $n$ bits. The main goal is to achieve $2^n$ security with a large tweak (i.e., more than $n$ bits). Previously, Mennink at FSE'15 and Wang et al. at Asiacrypt'16 proposed constructions that can achieve $2^n$ security. Yet, these constructions can have a tweak size up to $n$-bit only. As evident from recent research, a tweakable block cipher with a large tweak is generally helpful as a building block for modes of operation, typical applications including MACs, authenticated encryption, leakage-resilient cryptography and full-disk encryption.
We begin with how to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from two block cipher calls. For this purpose, we do an exhaustive search for tweakable block ciphers with $2n$-bit tweaks from two block cipher calls, and show that all of them suffer from birthday-bound attacks. Next, we investigate the possibility to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from three block cipher calls. We start with some conditions to build a such tweakable block cipher and propose a natural construction, called G1, that likely meets them. After inspection, we find a weakness on G1 which leads to a birthday-bound attack. Based on G1, we then propose another construction, called G2, that can avoid this weakness. We finally prove that G2 can achieve $n$-bit security with $2n$-bit tweak.
We begin with how to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from two block cipher calls. For this purpose, we do an exhaustive search for tweakable block ciphers with $2n$-bit tweaks from two block cipher calls, and show that all of them suffer from birthday-bound attacks. Next, we investigate the possibility to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from three block cipher calls. We start with some conditions to build a such tweakable block cipher and propose a natural construction, called G1, that likely meets them. After inspection, we find a weakness on G1 which leads to a birthday-bound attack. Based on G1, we then propose another construction, called G2, that can avoid this weakness. We finally prove that G2 can achieve $n$-bit security with $2n$-bit tweak.
Sahiba Suryawanshi, Dhiman Saha
The current work makes a systematic attempt to describe the effect of the relative order of round constant ( RCon) addition in the round function of an SPN cipher on its algebraic structure. The observations are applied to the SymSum distinguisher, introduced by Saha et al. in FSE 2017 which is one of the best distinguishers on the SHA3 hash function reported in literature. Results show that certain ordering (referred to as Type-LCN) of RCon makes the distinguisher less effective but it still works with some limitations. Results in the form of new SymSum distinguishers are reported on concrete Type-LCN constructions - NIST LWC competition finalist Xoodyak-Hash and its internal permutation Xoodoo. New linear structures are also reported on Xoodoo that augment the distinguisher to penetrate more rounds. Final results include SymSum distinguishers on 7 rounds of Xoodoo and 5 rounds of Xoodyak-Hash with complexity 2^128 and 2^32 , respectively. All practical distinguishers have been verified. The characterization encompassing the algebraic structure
and effect of RCon provided by the current work improves the under-
standing of SymSum in general and constitutes one of the first such result on Xoodyak-Hash and Xoodoo.
02 June 2023
Rockville, USA, 3 October - 4 October 2023
Event date: 3 October to 4 October 2023
Submission deadline: 1 July 2023
Notification: 30 June 2023
Submission deadline: 1 July 2023
Notification: 30 June 2023
31 May 2023
Koç University, İstanbul, Turkey
Cryptography, Security & Privacy Research Group at Koç University has one opening at the post-doctoral researcher level. Accepted applicants may receive competitive salary, housing (accommodation) support, health insurance, computer, travel support, and lunch meal card.
Your duties include performing research on cryptography, security, and privacy in line with our research group's focus, as well as directing graduate and undergraduate students in their research and teaching. The project funding is related to cryptography, game theory and mechanism design, adversarial machine learning, and blockchain technologies.
Applicants are expected to have already obtained their Ph.D. degrees in Computer Science or related discipline with a thesis topic related to the duties above.
For more information about joining our group and projects, visit
https://crypto.ku.edu.tr/work-with-us/
Submit your application via email including
Your duties include performing research on cryptography, security, and privacy in line with our research group's focus, as well as directing graduate and undergraduate students in their research and teaching. The project funding is related to cryptography, game theory and mechanism design, adversarial machine learning, and blockchain technologies.
Applicants are expected to have already obtained their Ph.D. degrees in Computer Science or related discipline with a thesis topic related to the duties above.
For more information about joining our group and projects, visit
https://crypto.ku.edu.tr/work-with-us/
Submit your application via email including
- full CV,
- transcripts of all universities attended,
- 1-3 sample publications where you are the main author,
- a detailed research proposal,
- 2-3 reference letters sent directly by the referees.
Closing date for applications:
Contact: Assoc. Prof. Alptekin Küpçü
https://member.acm.org/~kupcu
More information: https://crypto.ku.edu.tr/work-with-us/
Koç University, İstanbul, Turkey
Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. Accepted Computer Science and Engineering applicants may receive competitive scholarships including monthly stipend, tuition waiver, housing (accommodation) support, health insurance, computer, travel support, and lunch meal card.
Your duties include performing research on cryptography, cyber security, and privacy in line with our research group's focus, including blockchains and adversarial machine learning, assist teaching, as well as collaborating with other graduate and undergraduate students. Computer Science, Mathematics, Cryptography, or related background is necessary.
For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit
https://gsse.ku.edu.tr/en/admissions/application-requirements
All applications must be completed online. Applications with missing documents will not be considered. Applications via e-mail will not be considered. Application Requirements:
We also have a non-thesis paid Cyber Security M.Sc. program:
https://cybersecurity.ku.edu.tr/
For more information about joining our group and projects, visit
https://crypto.ku.edu.tr/work-with-us/
Your duties include performing research on cryptography, cyber security, and privacy in line with our research group's focus, including blockchains and adversarial machine learning, assist teaching, as well as collaborating with other graduate and undergraduate students. Computer Science, Mathematics, Cryptography, or related background is necessary.
For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit
https://gsse.ku.edu.tr/en/admissions/application-requirements
All applications must be completed online. Applications with missing documents will not be considered. Applications via e-mail will not be considered. Application Requirements:
- CV
- Recommendation Letters (2 for MSc, 3 for PhD)
- TOEFL (for everyone whose native language is not English, Internet Based: Minimum Score 80)
- GRE score
- Official transcripts from all the universities attended
- Statement of Purpose
- Area of Interest Form filled online
We also have a non-thesis paid Cyber Security M.Sc. program:
https://cybersecurity.ku.edu.tr/
For more information about joining our group and projects, visit
https://crypto.ku.edu.tr/work-with-us/
Closing date for applications:
Contact: https://gsse.ku.edu.tr/en/admissions/how-to-apply/
More information: https://gsse.ku.edu.tr/en/admissions/how-to-apply/