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
Matthias Geihs, Hart Montgomery
We initiate the study of lattice-based pseudo-random functions (PRFs) for use in multi-party computation protocols, motivated by their application to distributed key management. We show that the LWE-based PRF of Boneh et al. (CRYPTO'13) can be turned into a distributed PRF protocol that runs in only 8 online rounds, improving over the state-of-the-art by an order of magnitude. The resulting protocol can be used as a method for distributed key derivation and reduces the amount of managed key material in distributed key management systems from linear in the number of users to constant. Finally, we support our findings by implementing and evaluating our protocol using the MP-SPDZ framework (CCS'20).
Aggelos Kiayias, Nikos Leonardos, Yu Shen
An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a deep connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were investigated in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize the input transactions, a natural objective is to minimize the distance (in terms of injected number of transactions) between any pair of unfairly ordered transactions in the output ledger — a concept we call bounded unfairness. In state machine replication (SMR) parlance this asks for minimizing the number of unfair state updates occurring before the processing of any transaction. This unfairness minimization objective gives rise to a natural class of parametric order fairness definitions that has not been studied before. As we observe, previous realizable relaxations of order fairness do not yield good unfairness bounds.
Achieving optimal order fairness in the sense of bounded unfairness turns out to be connected to the graph theoretic properties of the underlying transaction dependency graph and specifically the bandwidth metric of strongly connected components in this graph. This gives rise to a specific instance of the definition that we call ``directed bandwidth order-fairness'' which we show that it captures the best possible that any protocol can achieve in terms of bounding unfairness. We prove ordering transactions in this fashion is NP-hard and non-approximable for any constant ratio. Towards realizing the property, we put forth a new distributed ledger protocol called Taxis that achieves directed bandwidth order-fairness in the permissionless setting. We present two variants of our protocol, one that matches the property perfectly but (necessarily) lacks in performance and liveness, and a second variant that achieves liveness and better complexity while offering a slightly relaxed version of the directed bandwidth definition. Finally, we comment on applications of our work to social choice theory, a direction which we believe to be of independent interest.
Achieving optimal order fairness in the sense of bounded unfairness turns out to be connected to the graph theoretic properties of the underlying transaction dependency graph and specifically the bandwidth metric of strongly connected components in this graph. This gives rise to a specific instance of the definition that we call ``directed bandwidth order-fairness'' which we show that it captures the best possible that any protocol can achieve in terms of bounding unfairness. We prove ordering transactions in this fashion is NP-hard and non-approximable for any constant ratio. Towards realizing the property, we put forth a new distributed ledger protocol called Taxis that achieves directed bandwidth order-fairness in the permissionless setting. We present two variants of our protocol, one that matches the property perfectly but (necessarily) lacks in performance and liveness, and a second variant that achieves liveness and better complexity while offering a slightly relaxed version of the directed bandwidth definition. Finally, we comment on applications of our work to social choice theory, a direction which we believe to be of independent interest.
Fabian Schmid, Shibam Mukherjee, Stjepan Picek, Marc Stöttinger, Fabrizio De Santis, Christian Rechberger
Side-channel analysis certification is a process designed to certify the resilience of cryptographic hardware and software implementations against side-channel attacks.
In certain cases, third-party evaluations by external companies or departments are necessary due to limited budget, time, or even expertise with the penalty of a significant exchange of sensitive information during the evaluation process.
In this work, we investigate the potential of Homomorphic Encryption (HE) in performing side-channel analysis on HE-encrypted measurements. With HE applied to side-channel analysis (SCA), a third party can perform SCA on encrypted measurement data and provide the outcome of the analysis without gaining insights about the actual cryptographic implementation under test. To this end, we evaluate its feasibility by analyzing the impact of AI-based side-channel analysis using HE (private SCA) on accuracy and execution time and compare the results with an ordinary AI-based side-channel analysis (plain SCA).
Our work suggests that both unprotected and protected cryptographic implementations can be successfully attacked already today with standard server equipment and modern HE protocols/libraries, while the traces are HE-encrypted.
Antonin Leroux
In this paper, we introduce the family $\mathsf{DeuringVRF}_{y,z}$ of Verifiable Random Function (VRF) protocols. Based on isogenies between supersingular curves, the random function at the heart of our scheme is the one that computes the codomain of an isogeny of big prime degree from its kernel.
In $\mathsf{DeuringVRF}_{y,z}$, the evaluation is done with algorithms for the Deuring correspondence that make use of isogenies in dimension $z$, and the verification is based on the isogeny representation obtained from isogenies in dimension $y$.
The main advantage of the $\mathsf{DeuringVRF}_{y,z}$ family is its compactness, with proof sizes of a few hundred bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions.
We describe four variants of our scheme with $(y,z) \in \lbrace (2,1),(2,2),(4,1), (4,2) \rbrace$ each offering different tradeoffs between compactness, evaluation efficiency and verification efficiency.
In the process, we introduce several new algorithms that might be of independent interest. In particular, for the variants with $z=2$, we introduce the first algorithm to translate an ideal into the corresponding isogeny of dimension $1$ using isogenies between abelian variety of dimension $2$ as a tool. The main advantage of this new algorithm compared to existing solution is the relaxation of the constraints on the prime characteristic: our new algorithm can run efficiently with ``SIDH primes" that are very easy to generate unlike ``SQIsign primes" that are currently required by the state of the art appoach. We believe that this algorithm opens a promising research direction to speed-up other schemes based on the Deuring correspondence such as the SQIsign signature scheme.
In $\mathsf{DeuringVRF}_{y,z}$, the evaluation is done with algorithms for the Deuring correspondence that make use of isogenies in dimension $z$, and the verification is based on the isogeny representation obtained from isogenies in dimension $y$.
The main advantage of the $\mathsf{DeuringVRF}_{y,z}$ family is its compactness, with proof sizes of a few hundred bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions.
We describe four variants of our scheme with $(y,z) \in \lbrace (2,1),(2,2),(4,1), (4,2) \rbrace$ each offering different tradeoffs between compactness, evaluation efficiency and verification efficiency.
In the process, we introduce several new algorithms that might be of independent interest. In particular, for the variants with $z=2$, we introduce the first algorithm to translate an ideal into the corresponding isogeny of dimension $1$ using isogenies between abelian variety of dimension $2$ as a tool. The main advantage of this new algorithm compared to existing solution is the relaxation of the constraints on the prime characteristic: our new algorithm can run efficiently with ``SIDH primes" that are very easy to generate unlike ``SQIsign primes" that are currently required by the state of the art appoach. We believe that this algorithm opens a promising research direction to speed-up other schemes based on the Deuring correspondence such as the SQIsign signature scheme.
Bharath Namboothiry
A revealable functional commitment allows a prover to commit to a secret polynomial size function $f$. Later, the prover has the ability to (1) prove that $y = f(x)$ for public $x, y$ and (2) open a small window into $f$'s machinery, via an encoded set of constraints - all without divulging any other information about $f$. In this way, revealable functional commitments allow the operator of a proprietary function to prove desired predicate about the function. For example, a government can commit to a bail decision algorithm, and prove that the same algorithm is being used for all defendants. They can also quell concerns about bias, and increase transparency processes by revealing windows into what their function does - while keeping most of their function secret to prevent exploitation. To build a revealable functional commitment, we introduce a 'proof of reveal', to show that a set of constraints, combined with a set of guarantees about those constraints, is consistent with a committed secret function. We show that combining a algebraic holomorphic proof (AHP), a 'proof of function relation' (PFR), and a proof of reveal yields a secure revealable functional commitment scheme. Additionally, we construct proof of reveals for two popular PFR-equipped AHPs, and obtain two instantiations of revealable functional commitments. Towards that end, we also develop interactive protocols that prove properties of committed polynomials, which may have independent value.
Kyosuke Yamashita, Keisuke Hara
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general.
However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model).
The impossibility stems from the difference between the definitions of unforgeability.
To the best of our knowledge, existing works demonstrating the constructions do not provide formal reduction from an MDVS scheme to a ring signature scheme, and thus the impossibility has been overlooked for a long time.
Zhengjun Cao, Lihua Liu
We show that the key agreement scheme [IEEE Trans. Veh. Technol. 71(4): 3470-3479, 2022] fails to keep user anonymity, not as claimed.
Giuseppe D'Alconzo, Antonio J. Di Scala
Cryptographic group actions provide a flexible framework that allows the instantiation of several primitives, ranging from key exchange protocols to PRFs and digital signatures. The security of such constructions is based on the intractability of some computational problems. For example, given the group action $(G,X,\star)$, the weak unpredictability assumption (Alamati et al., Asiacrypt 2020) requires that, given random $x_i$'s in $X$, no probabilistic polynomial-time algorithm can compute, on input $\{(x_i,g\star x_i)\}_{i=1,\dots,Q}$, the group element $g$.
In this work, we study such assumptions, aided by the definition of group action representations and a new metric, the linear dimension, that estimates the "linearity" of a group action, or in other words, how much it is far from being linear.
We show that under some hypotheses on the group action representation, and if the linear dimension is polynomial in the security parameter, then the weak unpredictability and other related assumptions cannot hold.
This technique is applied to some actions from cryptography, like the ones arising from the equivalence of linear codes; as a result, we obtain the impossibility of using such actions for the instantiation of certain primitives.
As an additional result, some bounds on the linear dimension are given for classical groups, such as $\mathcal{S}_n$, $\mathrm{GL}(\mathbb{F}^n)$ and the cyclic group $\mathbb{Z}_n$ acting on itself.
Cas Cremers, Alexander Dax, Charlie Jacomme, Mang Zhao
Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent protocol-level attacks exploit subtle behaviors that differ among real-world AEAD schemes.
We provide the first automated analysis method for protocols that use AEADs that can systematically find attacks that exploit the subtleties of the specific type of AEAD used. This can then be used to analyze specific protocols with a fixed AEAD choice, or to provide guidance on which AEADs might be (in)sufficient to make a protocol design secure. We develop generic symbolic AEAD models, which we instantiate for the Tamarin prover. Our approach can automatically and efficiently discover protocol attacks that could previously only be found using manual inspection, such as the Salamander attack on Facebook’s message franking, and attacks on SFrame and YubiHSM. Furthermore, our analysis reveals undesirable behaviors of several other protocols.
Muzhou Li, Nicky Mouha, Ling Sun, Meiqin Wang
The related-key statistical saturation (RKSS) attack is a cryptanalysis method proposed by Li et al. at FSE 2019. It can be seen as the extension of previous statistical saturation attacks under the related-key setting. The attack takes advantage of a set of plaintexts with some bits fixed, while the other bits take all possible values, and considers the relation between the value distributions of a part of the ciphertext bits generated under related keys. Usually, RKSS distinguishers exploit the property that the value distribution stays invariant under the modification of the key. However, this property can only be deterministically verified if the plaintexts cover all possible values of a selection of bits. In this paper, we propose the probabilistic RKSS cryptanalysis which avoids iterating over all non-fixed plaintext bits by applying a statistical method on top of the original RKSS distinguisher. Compared to the RKSS attack, this newly proposed attack has a significantly lower data complexity and has the potential of attacking more rounds. As an illustration, for reduced-round Piccolo, we obtain the best key recovery attacks (considering both pre- and post-whitening keys) on both versions in terms of the number of rounds. Note that these attacks do not threaten the full-round security of Piccolo.
Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, Jai Hyun Park, Damien Stehlé
Most of the current fully homomorphic encryption (FHE) schemes are based on either the learning-with-errors (LWE) problem or on its ring variant (RLWE) for storing plaintexts. During the homomorphic computation of FHE schemes, RLWE formats provide high throughput when considering several messages, and LWE formats provide a low latency when there are only a few messages. Efficient conversion can bridge the advantages of each format. However, converting LWE formats into RLWE format, which is called ring packing, has been a challenging problem.
We propose an efficient solution for ring packing for FHE. The main improvement of this work is twofold. First, we accelerate the existing ring packing methods by using bootstrapping and ring switching techniques, achieving practical runtimes. Second, we propose a new method for efficient ring packing, HERMES, by using ciphertexts in Module-LWE (MLWE) formats, to also reduce the memory. To this end, we generalize the tools of LWE and RLWE formats for MLWE formats.
On a single-thread implementation, HERMES consumes $10.2$s for the ring packing of $2^{15}$ LWE-format ciphertexts into an RLWE-format ciphertext. This gives $41$x higher throughput compared to the state-of-the-art ring packing for FHE, PEGASUS [S&P'21], which takes $51.7$s for packing $2^{12}$ LWE ciphertexts with similar homomorphic capacity. We also illustrate the efficiency of HERMES by using it for transciphering from LWE symmetric encryption to CKKS fully homomorphic encryption, significantly outperforming the recent proposals HERA [Asiacrypt'21] and Rubato [Eurocrypt'22].
We propose an efficient solution for ring packing for FHE. The main improvement of this work is twofold. First, we accelerate the existing ring packing methods by using bootstrapping and ring switching techniques, achieving practical runtimes. Second, we propose a new method for efficient ring packing, HERMES, by using ciphertexts in Module-LWE (MLWE) formats, to also reduce the memory. To this end, we generalize the tools of LWE and RLWE formats for MLWE formats.
On a single-thread implementation, HERMES consumes $10.2$s for the ring packing of $2^{15}$ LWE-format ciphertexts into an RLWE-format ciphertext. This gives $41$x higher throughput compared to the state-of-the-art ring packing for FHE, PEGASUS [S&P'21], which takes $51.7$s for packing $2^{12}$ LWE ciphertexts with similar homomorphic capacity. We also illustrate the efficiency of HERMES by using it for transciphering from LWE symmetric encryption to CKKS fully homomorphic encryption, significantly outperforming the recent proposals HERA [Asiacrypt'21] and Rubato [Eurocrypt'22].
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.