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:
21 August 2023
Cas Cremers, Eyal Ronen, Mang Zhao
Video conferencing apps like Zoom have hundreds of millions of daily users, making them a high-value target for surveillance and subversion. While such apps claim to achieve some forms of end-to-end encryption, they usually assume an incorruptible server that is able to identify and authenticate all the parties in a meeting. Concretely this means that, e.g., even when using the “end-to-end encrypted” setting, malicious Zoom servers could eavesdrop or impersonate in arbitrary groups.
In this work, we show how security against malicious servers can be improved by changing the way in which such protocols use passwords (known as passcodes in Zoom) and integrating a password-authenticated key exchange (PAKE) protocol.
To formally prove that our approach achieves its goals, we formalize a class of cryptographic protocols suitable for this setting, and define a basic security notion for them, in which group security can be achieved assuming the server is trusted to correctly authorize the group members. We prove that Zoom indeed meets this notion. We then propose a stronger security notion that can provide security against malicious servers, and propose a transformation that can achieve this notion. We show how we can apply our transformation to Zoom to provably achieve stronger security against malicious servers, notably without introducing new security elements.
In this work, we show how security against malicious servers can be improved by changing the way in which such protocols use passwords (known as passcodes in Zoom) and integrating a password-authenticated key exchange (PAKE) protocol.
To formally prove that our approach achieves its goals, we formalize a class of cryptographic protocols suitable for this setting, and define a basic security notion for them, in which group security can be achieved assuming the server is trusted to correctly authorize the group members. We prove that Zoom indeed meets this notion. We then propose a stronger security notion that can provide security against malicious servers, and propose a transformation that can achieve this notion. We show how we can apply our transformation to Zoom to provably achieve stronger security against malicious servers, notably without introducing new security elements.
Nilanjan Datta, Shreya Dey, Avijit Dutta, Sougata Mondal
In CRYPTO'02, Liskov et al. have introduced a new symmetric key primitive called tweakable block cipher. They have proposed two constructions of designing a tweakable block cipher from block ciphers. The first proposed construction is called $\mathsf{LRW1}$ and the second proposed construction is called $\mathsf{LRW2}$. Although, $\mathsf{LRW2}$ has been extended in later works to provide beyond birthday bound security (e.g., cascaded $\mathsf{LRW2}$ in CRYPTO'12 by Landecker et al.), but extension of the $\mathsf{LRW1}$ has received no attention until the work of Bao et al. in EUROCRYPT'20, where the authors have shown that one round extension of $\mathsf{LRW1}$, i.e., masking the output of $\mathsf{LRW1}$ with the given tweak and then re-encrypting it with the same block cipher, gives security up to $2^{2n/3}$ queries. Recently, Khairallah has shown a birthday bound distinguishing attack on the construction and hence invalidated the security claim of Bao et al. This has led to the open research question, that how many round are necessary for cascading $\mathsf{LRW1}$ to achieve beyond birthday bound security ?
In this paper, we have shown that cascading $\mathsf{LRW1}$ up to four rounds are necessary for ensuring beyond the birthday bound security. In particular, we have shown that $\mathsf{CLRW1}^4$ provides security up to $2^{2n/3}$ queries. Security analysis of our construction is based on the recent development of the mirror theory technique for tweakable random permutations under the H-Coefficient framework.
In this paper, we have shown that cascading $\mathsf{LRW1}$ up to four rounds are necessary for ensuring beyond the birthday bound security. In particular, we have shown that $\mathsf{CLRW1}^4$ provides security up to $2^{2n/3}$ queries. Security analysis of our construction is based on the recent development of the mirror theory technique for tweakable random permutations under the H-Coefficient framework.
Dan Boneh, Aditi Partap, Lior Rotem
A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group.
In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
Sriram Sridhar, Yinuo Zhang
Modern SNARK designs typically feature a frontend-backend paradigm: The frontend compiles a user's program into some equivalent circuit representation, while the backend calls for a SNARK specifically made for proving satisfiability of the circuit. While the circuit may be defined over small fields, the backend prover often needs to lift the computation to much larger fields for achieving soundness. This gap results in concrete overheads, for example, when representing a SHA-256 program as a circuit with pairing-based backend SNARKs.
For a class of computations that are $\textit{highly repetitive}$, we propose an improved frontend that partially bridges this gap. Compared with existing works, our frontend yields circuit representations defined over larger fields but of smaller size. Our implementation shows that for SIMD computation with $\approx 180$ SHA-256 instances, our improved frontend improves prover runtime by over $2.6 \times$ and reduces memory usage by over $1.3 \times$.
Central to our result and of independent interest, is an efficient technique for proving non-native modulo arithmetic.
For a class of computations that are $\textit{highly repetitive}$, we propose an improved frontend that partially bridges this gap. Compared with existing works, our frontend yields circuit representations defined over larger fields but of smaller size. Our implementation shows that for SIMD computation with $\approx 180$ SHA-256 instances, our improved frontend improves prover runtime by over $2.6 \times$ and reduces memory usage by over $1.3 \times$.
Central to our result and of independent interest, is an efficient technique for proving non-native modulo arithmetic.
Shuichi Katsumata, Yi-Fu Lai, Jason T. LeGrow, Ling Qin
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme.
While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure.
Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct Schnorr-like blind signatures based on modules such as classical groups and lattices.
Consequently, our scheme is provably-secure in the poly-logarithmic (in the number of security parameter) concurrent execution and does not seem susceptible to the recent efficient ROS attack exploiting the linear nature of the underlying mathematical tool.
In more detail, our blind signature exploits the "quadratic twist" of an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size $128$~B and signature size $8$~KB under the CSIDH-512 parameter sets---these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a new "ring" variant of the group action inverse problem rGAIP, we can halve the signature size to 4~KB while increasing the public key size to 512~B. We provide preliminary cryptanalysis of rGAIP and show that for certain parameter settings, it is essentially as secure as the standard GAIP. Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key---constructing such a hash function in the isogeny setting remains an open problem.
In more detail, our blind signature exploits the "quadratic twist" of an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size $128$~B and signature size $8$~KB under the CSIDH-512 parameter sets---these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a new "ring" variant of the group action inverse problem rGAIP, we can halve the signature size to 4~KB while increasing the public key size to 512~B. We provide preliminary cryptanalysis of rGAIP and show that for certain parameter settings, it is essentially as secure as the standard GAIP. Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key---constructing such a hash function in the isogeny setting remains an open problem.
Andreas Wiemers, Stephan Ehlen
Ducas and Pulles in "Does the Dual-Sieve Attack on Learning with Errors even Work?" especially report on experiments they made comparing the distributions of scores for random targets and BDD targets. They discovered that the distribution of scores for BDD targets deviate from the predictions made under the independence heuristic. Here, we want to derive approximations for the distributions which take into
account the dependency that occur in the scores. These approximations lead to new formulas that seem to describe the result in Table 1 of the article quite accurately.
haolei, Jiahui He, Kai Hu, Meiqin Wang
The key step of the cube attack is to recover the special polynomial, the superpoly, of the target cipher. In particular, the balanced superpoly, in which there exists at least one secret variable as a single monomial and none of the other monomials contain this variable, can be exploited to reveal one-bit information about the key bits. However, as the number of rounds grows, it becomes increasingly difficult to find such balanced superpolies. Consequently, traditional methods of searching for balanced superpolies soon hit a bottleneck. Aiming at performing a cube attack on more rounds of Trivium with a practical complexity, in this paper, we present three techniques to obtain sufficient balanced polynomials.
1. Based on the structure of Trivium, we propose a variable substitution technique to simplify the superpoly.
2. Obtaining the additional balanced polynomial by combining two superpolies to cancel the two-degree terms.
3. We propose an experimental approach to construct high-quality large cubes which may contain more subcubes with balanced superpolies and a heuristic search strategy for their subcubes whose superpolies are balanced.
To illustrate the power of our techniques, we search for balanced polynomials for 810- and 825-round Trivium. As a result, we can mount cube attacks against 810- and 825-round Trivium with the time complexity of $2^{44.17}$ and $2^{53.17}$ round-reduced Trivium initializations, respectively, which can be verified in 48 minutes and 18 days on a PC with one A100 GPU. For the same level of time complexity, this improves the previous best results by $2$ and $5$ rounds, respectively.
15 August 2023
Sajin Sasy, Aaron Johnson, Ian Goldberg
As more privacy-preserving solutions leverage trusted execution environments (TEEs) like Intel SGX, it becomes pertinent that these solutions can by design thwart TEE side-channel attacks that research has brought to light. In particular, such solutions need to be fully oblivious to circumvent leaking private information through memory or timing side channels.
In this work, we present fast fully oblivious algorithms for shuffling and sorting data. Oblivious shuffling and sorting are two fundamental primitives that are frequently used for permuting data in privacy-preserving solutions. We present novel oblivious shuffling and sorting algorithms in the offline/online model such that the bulk of the computation can be done in an offline phase that is independent of the data to be permuted. The resulting online phase provides performance improvements over state-of-the-art oblivious shuffling and sorting algorithms both asymptotically ($O(\beta n\log n)$ vs. $O(\beta n \log^2n)$) and concretely ($>5\times$ and $>3\times$ speedups), when permuting $n$ items each of size $\beta$.
Our work revisits Waksman networks, and it uses the key observation that setting the control bits of a Waksman network for a uniformly random shuffle is independent of the data to be shuffled. However, setting the control bits of a Waksman network efficiently and fully obliviously poses a challenge, and we provide a novel algorithm to this end. The total costs (inclusive of offline computation) of our WaksShuffle shuffling algorithm and our WaksSort sorting algorithm are lower than all other fully oblivious shuffling and sorting algorithms when the items are at least moderately sized (i.e., $\beta$ > 1400 B), and the performance gap only widens as the item sizes increase. Furthermore, WaksShuffle improves the online cost of oblivious shuffling by $>5\times$ for shuffling $2^{20}$ items of any size; similarly WaksShuffle+QS, our other sorting algorithm, provides $>2.7\times$ speedups in the online cost of oblivious sorting.
In this work, we present fast fully oblivious algorithms for shuffling and sorting data. Oblivious shuffling and sorting are two fundamental primitives that are frequently used for permuting data in privacy-preserving solutions. We present novel oblivious shuffling and sorting algorithms in the offline/online model such that the bulk of the computation can be done in an offline phase that is independent of the data to be permuted. The resulting online phase provides performance improvements over state-of-the-art oblivious shuffling and sorting algorithms both asymptotically ($O(\beta n\log n)$ vs. $O(\beta n \log^2n)$) and concretely ($>5\times$ and $>3\times$ speedups), when permuting $n$ items each of size $\beta$.
Our work revisits Waksman networks, and it uses the key observation that setting the control bits of a Waksman network for a uniformly random shuffle is independent of the data to be shuffled. However, setting the control bits of a Waksman network efficiently and fully obliviously poses a challenge, and we provide a novel algorithm to this end. The total costs (inclusive of offline computation) of our WaksShuffle shuffling algorithm and our WaksSort sorting algorithm are lower than all other fully oblivious shuffling and sorting algorithms when the items are at least moderately sized (i.e., $\beta$ > 1400 B), and the performance gap only widens as the item sizes increase. Furthermore, WaksShuffle improves the online cost of oblivious shuffling by $>5\times$ for shuffling $2^{20}$ items of any size; similarly WaksShuffle+QS, our other sorting algorithm, provides $>2.7\times$ speedups in the online cost of oblivious sorting.
Dengguo Feng, Lin Jiao, Yonglin Hao, Qunxiong Zheng, Wenling Wu, Wenfeng Qi, Lei Zhang, Liting Zhang, Siwei Sun, Tian Tian
In this paper, we propose LOL, a general framework for designing blockwise stream ciphers, to achieve ultrafast software implementations for the ubiquitous virtual networks in 5G/6G environments and high-security level for post-quantum cryptography. The LOL framework is structurally strong, and all its components as well as the LOL framework itself enjoy high flexibility with various extensions. Following the LOL framework, we propose new stream cipher designs named LOL-MINI and LOL-DOUBLE with the support of the AES-NI and SIMD instructions: the former applies the basic LOL single mode while the latter uses the extended parallel-dual mode. Both LOL-MINI and LOL-DOUBLE support 256-bit key length and, according to our thorough evaluations, have 256-bit security margins against all existing cryptanalysis methods including differential, linear, integral, etc. The software performances of LOL-MINI and LOL-DOUBLE can reach 89 Gbps and 135 Gbps. In addition to pure encryptions, the LOL-MINI and LOL-DOUBLE stream ciphers can also be applied in a stream-cipher-then-MAC strategy to make an AEAD scheme.
Nikolaos Makriyannis, Oren Yomtov
Multi-Party Computation (MPC) has become a major tool for protecting hundreds of billions of dollars in cryptocurrency wallets. MPC protocols are currently powering the wallets of Coinbase, Binance, Zengo, BitGo, Fireblocks and many other fintech companies servicing thousands of financial institutions and hundreds of millions of end-user consumers.
We present four novel key-extraction attacks on popular MPC signing protocols showing how a single corrupted party may extract the secret in full during the MPC signing process. Our attacks are highly practical (the practicality of the attack depends on the number of signature-generation ceremonies the attacker participates in before extracting the key). Namely, we show key-extraction attacks against different threshold-ECDSA protocols/implementations requiring $10^6$, $256$, $16$, and *one signature*, respectively. In addition, we provide proof-of-concept code that implements our attacks.
We present four novel key-extraction attacks on popular MPC signing protocols showing how a single corrupted party may extract the secret in full during the MPC signing process. Our attacks are highly practical (the practicality of the attack depends on the number of signature-generation ceremonies the attacker participates in before extracting the key). Namely, we show key-extraction attacks against different threshold-ECDSA protocols/implementations requiring $10^6$, $256$, $16$, and *one signature*, respectively. In addition, we provide proof-of-concept code that implements our attacks.
Ashwin Jha, Mridul Nandi, Abishanka Saha
In a recent paper, Khairallah demonstrated a birthday-bound attack on TNT, thereby invalidating its (beyond-the-birthday-bound) CCA security claims. In this short note, we reestablish a birthday-bound CCA security bound for TNT. Furthermore, using a minor variant of Khairallah's attack, we show that our security bound is tight. We provide a rigorous and complete attack advantage calculations to further enhance the confidence in Khairallah's proposed attack strategy.
Tarek Galal, Anja Lehmann
Digital Covid certificates are the first widely deployed end-user cryptographic certificates. For service providers, such as airlines or event ticket vendors, that needed to check that their (global) customers satisfy certain health policies, the verification of such Covid certificates was challenging though - not because of the cryptography involved, but due to the multitude of issuers, different certificate types and the evolving nature of country-specific policies that had to be supported. As Covid certificates contain sensitive health information, their (online) presentation to non-health related entities also poses clear privacy risk. To address both challenges, the EU proposed a specification for outsourcing the verification process to a validator service, that executes the process and informs service providers of the result. The WHO announced to adopt this approach for general vaccination credentials beyond Covid-19. While being beneficial to improve security and privacy for service providers, their solution requires strong trust assumption for the (central) validation service that learns all health-related details of the users.
In our work, we propose and formally model a privacy-preserving variant of such an outsourced validation service. Therein the validator learns the attributes it is supposed to verify, but not the users identity. Still, the validator's assertion is blindly bound to the user's identity to ensure the desired user-binding. We analyze the EU specification in our model and show that it only meets a subset of those goals. Our analysis further shows that the EU protocol is unnecessarily complex and can be significantly simplified while maintaining the same (weak) level of security. Finally, we propose a new construction for privacy-preserving certificate validation that provably satisfies all desired goals.
In our work, we propose and formally model a privacy-preserving variant of such an outsourced validation service. Therein the validator learns the attributes it is supposed to verify, but not the users identity. Still, the validator's assertion is blindly bound to the user's identity to ensure the desired user-binding. We analyze the EU specification in our model and show that it only meets a subset of those goals. Our analysis further shows that the EU protocol is unnecessarily complex and can be significantly simplified while maintaining the same (weak) level of security. Finally, we propose a new construction for privacy-preserving certificate validation that provably satisfies all desired goals.
Fangan Yssouf Dosso, Alexandre Berzati, Nadia El Mrabet, Julien Proy
The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$.
The PMNS is a redundant number system. In~\cite{rando-pmns-arith26}, Didier et al. used this redundancy property to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM).
In this paper, we refine the results on redundancy and propose several new results on PMNS. More precisely, we study a generalisation of the Montgomery-like internal reduction method proposed by Negre and Plantard, along with some improvements on parameter bounds for smaller memory cost to represent elements in this system. We also show how to perform equality test in the PMNS.
Shuai Han, Shengli Liu, Zhedong Wang, Dawu Gu
In this work, we construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of the number of users, signatures or ciphertexts. Previously, such schemes were only known to exist under number-theoretic assumptions or in classical random oracle model, thus vulnerable to quantum adversaries.
To obtain our schemes from LWE, we propose new frameworks for constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). As a new variant of HPS, our pr-QA-HPS provides probabilistic public and private evaluation modes that may toss coins. This is in stark contrast to the traditional HPS [Cramer and Shoup, Eurocrypt 2002] and existing variants like approximate HPS [Katz and Vaikuntanathan, Asiacrypt 2009], whose public and private evaluations are deterministic in their inputs. Moreover, we formalize a new property called evaluation indistinguishability by requiring statistical indistinguishability of the two probabilistic evaluation modes, even in the presence of the secret key. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof of our frameworks under adaptive corruptions.
As for instantiations, we construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which admit almost tightly secure LWE-based SIG and PKE schemes under our frameworks. Along the way, we also provide new almost-tight reductions from LWE to multi-secret LWE, which may be of independent interest.
To obtain our schemes from LWE, we propose new frameworks for constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). As a new variant of HPS, our pr-QA-HPS provides probabilistic public and private evaluation modes that may toss coins. This is in stark contrast to the traditional HPS [Cramer and Shoup, Eurocrypt 2002] and existing variants like approximate HPS [Katz and Vaikuntanathan, Asiacrypt 2009], whose public and private evaluations are deterministic in their inputs. Moreover, we formalize a new property called evaluation indistinguishability by requiring statistical indistinguishability of the two probabilistic evaluation modes, even in the presence of the secret key. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof of our frameworks under adaptive corruptions.
As for instantiations, we construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which admit almost tightly secure LWE-based SIG and PKE schemes under our frameworks. Along the way, we also provide new almost-tight reductions from LWE to multi-secret LWE, which may be of independent interest.
Francesco Sica
We fix an omission in [Petit17] on torsion point attacks of isogeny-based cryptosystems akin to SIDH, also reprised in [dQuehen-etal21]. In these works, their authors represent certain integers using a norm equation to derive a secret isogeny. However, this derivation uses as a crucial ingredient ([Petit17] Section 4.3), which we show to be incorrect. We then state sufficient conditions allowing to prove a modified version this lemma.
A further idea of parametrizing solutions of the norm equation will show that these conditions can be fulfilled under the same heuristics of these previous works. Our contribution is a theoretical one. It doesn't invalidate the attack, which works as well in practice, but gives a correct mathematical justification for it.
We also simplify the argument of Theorem 3 in [dQuehen-etal21] to show that the requirement that $m$ be small is unnecessary.
A further idea of parametrizing solutions of the norm equation will show that these conditions can be fulfilled under the same heuristics of these previous works. Our contribution is a theoretical one. It doesn't invalidate the attack, which works as well in practice, but gives a correct mathematical justification for it.
We also simplify the argument of Theorem 3 in [dQuehen-etal21] to show that the requirement that $m$ be small is unnecessary.
Elizabeth Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro, Chenzhi Zhu
Both threshold and blind signatures have, individually, received a considerable amount of attention. However little is known about their combination, i.e., a threshold signature which is also blind, in that no coalition of signers learns anything about the message being signed or the signature being produced. Several applications of blind signatures (e.g., anonymous tokens) would benefit from distributed signing as a means to increase trust in the service and hence reduce the risks of key compromise. This paper builds the first blind threshold signatures in pairing-free groups. Our main contribution is a construction that transforms an underlying blind non-threshold signature scheme with a suitable structure into a threshold scheme, preserving its blindness. The resulting signing protocol proceeds in three rounds, and produces signatures consisting of one group element and two scalars. The underlying non-threshold blind signature schemes are of independent interest, and improve upon the current state of the art (Tessaro and Zhu, EUROCRYPT ’22) with shorter signatures (three elements, instead of four) and simpler proofs of security. All of our schemes are proved secure in the Random Oracle and Algebraic Group Models, assuming the hardness of the discrete logarithm problem.
Kosei Sakamoto, Ryoma Ito, Takanori Isobe
The most crucial but time-consuming task for differential cryptanalysis is to find a differential with a high probability. To tackle this task, we propose a new SAT-based automatic search framework to efficiently figure out a differential with the highest probability under a specified condition. As the previous SAT methods (e.g., the Sun et al’s method proposed at ToSC 2021(1)) focused on accelerating the search for an optimal single differential characteristic, these are not optimized for evaluating a clustering effect to obtain a tighter differential probability of differentials. In contrast, our framework takes advantage of a method to solve incremental SAT problems in parallel using a multi-threading technique, and consequently, it offers the following advantages compared with the previous methods: (1) speedy identification of a differential with the highest probability under the specified conditions; (2) efficient construction of the truncated differential with the highest probability from the obtained multiple differentials; and (3) applicability to a wide class of symmetric-key primitives. To demonstrate the effectiveness of our framework, we apply it to the block cipher PRINCE and the tweakable block cipher QARMA. We successfully figure out the tight differential bounds for all variants of PRINCE and QARMA within the practical time, thereby identifying the longest distinguisher for all the variants, which improves existing ones by one to four more rounds. Besides, we uncover notable differences between PRINCE and QARMA in the behavior of differential, especially for the clustering effect. We believe that our findings shed light on new structural properties of these important primitives. In the context of key recovery attacks, our framework allows us to derive the key-recovery-friendly truncated differentials for all variants of QARMA. Consequently, we report key recovery attacks based on (truncated) differential cryptanalysis on QARMA for the first time and show these key recovery attacks are competitive with existing other attacks.
Huayi Qi, Minghui Xu, Dongxiao Yu, Xiuzhen Cheng
The privacy concern in smart contract applications continues to grow, leading to the proposal of various schemes aimed at developing comprehensive and universally applicable privacy-preserving smart contract (PPSC) schemes. However, the existing research in this area is fragmented and lacks a comprehensive system overview. This paper aims to bridge the existing research gap on PPSC schemes by systematizing previous studies in this field. The primary focus is on two categories: PPSC schemes based on cryptographic tools like zero-knowledge proofs, as well as schemes based on trusted execution environments. In doing so, we aim to provide a condensed summary of the different approaches taken in constructing PPSC schemes. Additionally, we also offer a comparative analysis of these approaches, highlighting the similarities and differences between them. Furthermore, we shed light on the challenges that developers face when designing and implementing PPSC schemes. Finally, we delve into potential future directions for improving and advancing these schemes, discussing possible avenues for further research and development.
Yuval Ishai, Mahimna Kelkar, Varun Narayanan, Liav Zafar
Correlated secret randomness is a useful resource for secure computation protocols, often enabling dramatic speedups compared to protocols in the plain model. This has motivated a line of work on identifying and securely generating useful correlations.
Different kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are much more costly to generate. Thus, it is highly desirable to develop efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation, especially when the former are cheaper to generate than the latter.
In this work, we initiate a systematic study of such conversions that only involve a single uni-directional message. We refer to such a conversion as a one-message secure reduction (OMSR). Recent works (Agarwal et al, Eurocrypt 2022; Khorasgani et al, Eurocrypt 2022) studied a similar problem when no communication is allowed; this setting is quite restrictive, however, with few non-trivial conversions being feasible. The OMSR setting substantially expands the scope of feasible results, allowing for direct applications to existing MPC protocols.
We obtain the following positive and negative results. - OMSR constructions. We present a general rejection-sampling based technique for OMSR with OT source correlations. We apply it to substantially improve in the communication complexity of optimized protocols for distributed symmetric cryptography (Dinur et al., Crypto 2021).
- OMSR lower bounds. We develop general techniques for proving lower bounds on the communication complexity of OMSR, matching our positive results up to small constant factors.
Different kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are much more costly to generate. Thus, it is highly desirable to develop efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation, especially when the former are cheaper to generate than the latter.
In this work, we initiate a systematic study of such conversions that only involve a single uni-directional message. We refer to such a conversion as a one-message secure reduction (OMSR). Recent works (Agarwal et al, Eurocrypt 2022; Khorasgani et al, Eurocrypt 2022) studied a similar problem when no communication is allowed; this setting is quite restrictive, however, with few non-trivial conversions being feasible. The OMSR setting substantially expands the scope of feasible results, allowing for direct applications to existing MPC protocols.
We obtain the following positive and negative results. - OMSR constructions. We present a general rejection-sampling based technique for OMSR with OT source correlations. We apply it to substantially improve in the communication complexity of optimized protocols for distributed symmetric cryptography (Dinur et al., Crypto 2021).
- OMSR lower bounds. We develop general techniques for proving lower bounds on the communication complexity of OMSR, matching our positive results up to small constant factors.
Kirill Vedenev, Yury Kosolapov
In this paper, we study the decoding failure rate (DFR) of non-binary QC-MDPC codes using theoretical tools, extending the results of previous binary QC-MDPC code studies. The theoretical estimates of the DFR are particularly significant for cryptographic applications of QC-MDPC codes. Specifically, in the binary case, it is established that exploiting decoding failures makes it possible to recover the secret key of a QC-MDPC cryptosystem. This implies that to attain the desired security level against adversaries in the CCA2 model, the decoding failure rate must be strictly upper-bounded to be negligibly small. In this paper, we observe that this attack can also be extended to the non--binary case as well, which underscores the importance of DFR estimation. Consequently, we study the guaranteed error-correction capability of non-binary QC-MDPC codes under one-step majority logic (OSML) decoder and provide a theoretical analysis of the 1-iteration parallel symbol flipping decoder and its combination with OSML decoder. Utilizing these results, we estimate the potential public-key sizes for QC-MDPC cryptosystems over $\mathbb{F}_4$ for various security levels. We find that there is no advantage in reducing key sizes when compared to the binary case.