Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if $n>2f$ for $f$ Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if $n>3f+2k$ for $f$ Byzantine faults and $k$ crash faults. Currently, the only known synchronous protocol for consensus with a resilience of $n>2f+k$ is a binary consensus protocol. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated multivalued consensus protocol in synchronous networks resilient to $f$ Byzantine faults and $k$ crash faults if $n>2f+k$. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that $n>2f+k$ is optimally resilient for consensus and state machine replication protocols.

One of the main challenges cryptography needs to deal with is balancing the performances of a cryptographic primitive with its security. That is why in 2015, the National Institute of Standards and Technologies (NIST) has begun a standardization process to solicit the creation of new lightweight cryptographic algorithms. We then wondered which of this standardization finalists would suit the best to a white-box implementation. To this end, we studied different algorithms structures on their encodability to later develop our white-box encoding solution. Afterwards, we reviewed the standardization finalists on the applicability of our solution to those algorithms, and finally apply it to GIFT, the permutation of GIFT-COFB.

Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when deniability (also known as non-transferability) is desired. In the lattice-based setting, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen. While repetitions due to aborts are acceptable in theory, in some practical applications it is desirable to avoid re-runs for usability reasons. In this work we present a generic technique that departs from an interactive zero-knowledge system (that might require multiple re-runs to complete the protocol) and obtains a 3-moves zero-knowledge system (without re-runs). The transformation combines the well-known Fiat-Shamir technique with a couple of initially exchanged messages. The resulting 3-moves system enjoys honest-verifier zero-knowledge and can be easily turned into a fully deniable proof using standard techniques. We show some practical scenarios where our transformation can be beneficial and we also discuss the results of an implementation of our transformation.

Traditional blockchain systems execute program state transitions on-chain, requiring each network node participating in state-machine replication to re-compute every step of the program when validating transactions. This limits both scalability and privacy. Recently, Bowe et al. introduced a primitive called decentralized private computation (DPC) and provided an instantiation called ZEXE, which allows users to execute arbitrary computations off-chain without revealing the program logic to the network. Moreover, transaction validation takes only constant time, independent of the off-chain computation. However, ZEXE required a separate trusted setup for each application, which is highly impractical. Prior attempts to remove this per-application setup incurred significant performance loss. We propose a new DPC instantiation VERI-ZEXE that is highly efficient and requires only a single universal setup to support an arbitrary number of applications. Our benchmark improves the state-of-the-art by 9x in transaction generation time and by 3.4x in memory usage. Along the way, we also design efficient gadgets for variable-base multi-scalar multiplication and modular arithmetic within the plonk constraint system, leading to a Plonk verifier gadget using only ∼ 21k plonk constraints.

Having access to the scan chain of Integrated Circuits (ICs) is an integral requirement of the debug/testability process within the supply chain. However, the access to the scan chain raises big concerns regarding the security of the chip, particularly when the secret information, such as the key of logic obfuscation, is embedded/stored inside the chip. Hence, to relieve such concerns, numerous secure scan chain architectures have been proposed in the literature to show not only how to prevent any unauthorized access to the scan chain but also how to keep the availability of the scan chain for debug/testability. In this paper, we first provide a holistic overview of all secure scan chain architectures. Then, we discuss the key leakage possibility and some substantial architectural drawbacks that moderately affect both test flow and design constraints in the state-of-the-art published design-for-security (DFS) architectures. Then, we propose a new key-trapped DFS (kt-DFS) architecture for building a secure scan chain architecture while addressing the potential of key leakage. The proposed kt-DFS architecture allows the designer to perform the structural test with no limitation, enabling an untrusted foundry to utilize the scan chain for manufacturing fault testing without needing to access the scan chain. Finally, we evaluate and compare the proposed architecture with state-of-the-art ones in terms of security, testability time and complexity, and area/power/delay overhead.

Recent advances in function secret sharing (FSS) have led to new possibilities in multi-party computation in the pre-processing model. Silent Pseudorandom Correlation Generators (Crypto '19, CCS '19, CCS '19, CCS '20) have demonstrated the ability to generate large quantities of pre-processing material such as oblivious transfers and Beaver triples through a non-interactive offline phase (with an initial set-up). However, there has been limited protocols for pre-processing material such as doubly authenticated bits (daBits, IndoCrypt'19) and extended doubly authenticated bits (edaBits, Crypto '20) which are critical for state-of-the-art secure comparison protocols over arithmetic secret sharing. In this work, we propose new protocols in a 3-party computation model for these two cryptographic primitives -- daBits and edaBits. We explore how advances in silent PCGs can be used to construct efficient protocols for daBits and edaBits. Our protocols are secure against a single corruption in both the semi-honest and malicious security models. Our contributions can be summarized as follows: (1) New constant round protocols for generating daBits and edaBits. We achieve this by constructing an efficient 3-party oblivious transfer protocol (using just 2 rounds of computation) and using it to build efficient protocols for daBit and edaBit generation. (2) We extend the above semi-honest protocol to achieve malicious security against an honest majority. We use a standard cut-and-choose approach for this. This improves the round complexity of prior edaBit protocols from O(log2 l) to a constant, where l is the bit-length of the inputs. (3) Finally, to understand when the above protocols provide concrete efficiency, we implement and benchmark the performance of our protocols against state-of-the-art implementation of these primitives in MP-SDPZ. Our protocols improve the throughput of daBit generation by up to 10x in the LAN setting and 5x in the WAN setting. Comparing the performance of edaBit generation, our protocols achieve 4x higher throughput in the LAN setting and 32x higher throughput in the WAN setting. It is known that silent PCGs are compute intense and thus the performance of these new protocols can further be improved using works such as CryptGPU (S\&P '21), Piranha (USENIX '22) that significantly improve the local computation in MPC protocols.

We revisit the question of minimizing the randomness complexity of protocols for secure multiparty computation (MPC) in the setting of perfect information-theoretic security. Kushilevitz and Mansour (SIAM J. Discret. Math., 1997) studied the case of $n$-party semi-honest MPC for the XOR function with security threshold $t<n$, showing that $O(t^2\log(n/t))$ random bits are sufficient and $\Omega(t)$ random bits are necessary. Their positive result was obtained via a non-explicit protocol, whose existence was proved using the probabilistic method. We essentially close the question by proving an $\Omega(t^2)$ lower bound on the randomness complexity of XOR, matching the previous upper bound up to a logarithmic factor (or constant factor when $t=\Omega(n)$). We also obtain an explicit protocol that uses $O(t^2\cdot\log^2n)$ random bits, matching our lower bound up to a polylogarithmic factor. We extend these results from XOR to general symmetric Boolean functions and to addition over a finite Abelian group, showing how to amortize the randomness complexity over multiple additions. Finally, combining our techniques with recent randomness-efficient constructions of private circuits, we obtain an explicit protocol for evaluating a general circuit $C$ using only $O(t^2\cdot\log |C|)$ random bits, by employing additional ``helper parties'' who do not contribute any inputs. This upper bound too matches our lower bound up to a logarithmic factor.

Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label. Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation and feed the resulting cleartext value back into the MPC. Such techniques are not known to work for GC. We show that it is, in fact, possible to improve GC efficiency, while keeping its round complexity, by exposing masked private values to the evaluator. Our improvements use garbled one-hot encodings of values. By using this encoding we improve a number of interesting functions, e.g., matrix multiplication, integer multiplication, field element multiplication, field inverses and AES S-Boxes, integer exponents, and more. We systematize our approach by providing a framework for designing such GC modules. Our constructions are concretely efficient. E.g., we improve binary matrix multiplication inside GC by more than $6\times$ in terms of communication and by more than $4\times$ in terms of WAN wall-clock time. Our improvement circumvents an important GC lower bound and may open GC to further improvement.

Arecentlineofwork, Stacked Garbled Circuit(SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor $\log b$ extra work as compared to standard GC. We extend the sublinearity of SGC to also include the work performed by the GC evaluator E; thus we achieve a fully sublinear E, which is essential when optimizing for the online phase. We formalize our approach as a garbling scheme called GCWise: GC WIth Sublinear Evaluator. We show one attractive and immediate application, Garbled PIR, a primitive that marries GC with Private Information Retrieval. Garbled PIR allows the GC to non-interactively and sublinearly access a privately indexed element from a publicly known database, and then use this element in continued GC evaluation.

Nakamoto's consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.

Katz et al., CCS 2018 (KKW) is a popular and efficient MPC-in-the-head non-interactive ZKP (NIZK) scheme, which is the technical core of the post-quantum signature scheme Picnic, currently considered for standardization by NIST. The KKW approach simultaneously is concretely efficient, even on commodity hardware, and does not rely on trusted setup. Importantly, the approach scales linearly in the circuit size with low constants with respect to proof generation time, proof verification time, proof size, and RAM consumption. However, KKW works with Boolean circuits only and hence incurs significant cost for circuits that include arithmetic operations. In this work, we extend KKW with a suite of efficient arithmetic operations over arbitrary rings and Boolean conversions. Rings $\mathbb{Z}_{2^k}$ are important for NIZK as they naturally match the basic operations of modern programs and CPUs. In particular, we: * present a suitable ring representation consistent with KKW, * construct efficient conversion operators that translate between arith- metic and Boolean representations, and * demonstrate how to efficiently operate over the arithmetic representation, including a vector dot product of length-n vectors with cost equal to that of a single multiplication. These improvements substantially improve KKW for circuits with arithmetic. As one example, we can multiply 100 × 100 square matrices of 32-bit numbers using a 3200x smaller proof size than standard KKW (100x improvement from our dot product construction and 32x from moving to an arithmetic representation). We discuss in detail proof size and resource consumption and argue the practicality of running large proofs on commodity hardware.

This article develops a novel method of generating ``independent'' points on an ordinary elliptic curve over a finite field of large characteristic. Such points are actively used, e.g., in the Pedersen vector commitment scheme and its modifications. The conventional generation consists in sampling points successively via a hash function to the elliptic curve. The new generation method equally satisfies the NUMS (Nothing Up My Sleeve) principle, but it works faster on average. In other words, instead of finding each point separately, it is suggested to sample several points at once with a non-small success probability. This means that in practice the new method finishes in polynomial time, unless one is mysteriously unlucky. More precisely, some explicit formulas are represented in the article for deriving up to four ``independent'' points on any curve of $j$-invariant $0$. Such curves are known to be very popular in elliptic curve cryptography.

Secure machine learning (ML) inference can provide meaningful privacy guarantees to both the client (holding sensitive input) and the server (holding sensitive weights of the ML model) while realizing inference-as-a-service. Although many specialized protocols exist for this task, including those in the preprocessing model (where a majority of the overheads are moved to an input independent offline phase), they all still suffer from large online complexity. Specifically, the protocol phase that executes once the parties know their inputs, has high communication, round complexity, and latency. Function Secret Sharing (FSS) based techniques offer an attractive solution to this in the trusted dealer model (where a dealer provides input independent correlated randomness to both parties), and 2PC protocols obtained based on these techniques have a very lightweight online phase. Unfortunately, current FSS-based 2PC works (AriaNN, PoPETS 2022; Boyle et al. Eurocrypt 2021; Boyle et al. TCC 2019) fall short of providing a complete solution to secure inference. First, they lack support for math functions (e.g., sigmoid, and reciprocal square root) and hence, are insufficient for a large class of inference algorithms (e.g. recurrent neural networks). Second, they restrict all values in the computation to be of the same bitwidth and this prevents them from benefitting from efficient float-to-fixed converters such as Tensorflow Lite that crucially use low bitwidth representations and mixed bitwidth arithmetic. In this work, we present LLAMA -- an end-to-end, FSS based, secure inference library supporting precise low bitwidth computations (required by converters) as well as provably precise math functions; thus, overcoming all the drawbacks listed above. We perform an extensive evaluation of LLAMA and show that when compared with non-FSS based libraries supporting mixed bitwidth arithmetic and math functions (SIRNN, IEEE S&P 2021), it has at least an order of magnitude lower communication, rounds, and runtimes. We integrate LLAMA with the EzPC framework (IEEE EuroS&P 2019) and demonstrate its robustness by evaluating it on large benchmarks (such as ResNet-50 on the ImageNet dataset) as well as on benchmarks considered in AriaNN -- here too LLAMA outperforms prior work.

As the most dominant authentication mechanism, password-based authentication suffers catastrophic offline password guessing attacks once the authentication server is compromised and the password database is leaked. Password hardening (PH) service, an external/third-party crypto service, has been recently proposed to strengthen password storage and reduce the damage of authentication server compromise. However, all existing schemes are unreliable because they overlook the important restorable property: PH service opt-out. In existing PH schemes, once the authentication server has subscribed to a PH service, it must adopt this service forever, even if it wants to stop the external/third-party PH service and restore its original password storage (or subscribe to another PH service). To fill the gap, we propose a new PH service called PW-Hero that equips its PH service with an option to terminate its use (i.e., opt-out). In PW-Hero, password authentication is strengthened against offline attacks by adding external secret spices to password records. With the opt-out property, authentication servers can proactively request to end the PH service after successful authentications. Then password records can be securely migrated to their traditional salted hash state, ready for subscription to other PH services. Besides, PW-Hero achieves all existing desirable properties, such as comprehensive verifiability, rate limits against online attacks, and user privacy. We define PW-Hero as a suite of protocols that meet desirable properties and build a simple, secure, and efficient instance. Moreover, we develop a prototype implementation and evaluate its performance, which shows the practicality of our PW-Hero service.

It is well-known that in the presence of majority coalitions, strongly fair coin toss is impossible. A line of recent works have shown that by relaxing the fairness notion to game theoretic, we can overcome this classical lower bound. In particular, Chung et al. (CRYPTO'21) showed how to achieve approximately (game-theoretically) fair leader election in the presence of majority coalitions, with round complexity as small as $O(\log \log n)$ rounds. In this paper, we revisit the round complexity of game-theoretically fair leader election. We construct $O(\log^* n)$ rounds leader election protocols that achieve $(1-o(1))$-approximate fairness in the presence of $(1-O(1)) n$-sized coalitions. Our protocols achieve the same round-fairness trade-offs as Chung et al.'s and have the advantage of being conceptually simpler. Finally, we also obtain game-theoretically fair protocols for committee election which might be of independent interest.

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing succinct arguments. In this work, we study the limitations of IOPs, as well as their relation to those of PCPs. We present a versatile toolbox of IOP-to-IOP transformations containing tools for: (i) length and round reduction; (ii) improving completeness; and (iii) derandomization. We use this toolbox to establish several barriers for IOPs: -- Low-error IOPs can be transformed into low-error PCPs. In other words, interaction can be used to construct low-error PCPs; alternatively, low-error IOPs are as hard to construct as low-error PCPs. This relates IOPs to PCPs in the regime of the sliding scale conjecture for inverse-polynomial soundness error. -- Limitations of quasilinear-size IOPs for 3SAT with small soundness error. -- Limitations of IOPs where query complexity is much smaller than round complexity. -- Limitations of binary-alphabet constant-query IOPs. We believe that our toolbox will prove useful to establish additional barriers beyond our work.

Designing symmetric ciphers for particular applications becomes a hot topic. At EUROCRYPT 2020, Naito, Sasaki and Sugawara invented the threshold implementation friendly cipher SKINNYe-64-256 to meet the requirement of the authenticated encryption PFB_Plus. Soon, Thomas Peyrin pointed out that SKINNYe-64-256 may lose the security expectation due the new tweakey schedule. Although the security issue of SKINNYe-64-256 is still unclear, Naito et al. decided to introduce SKINNYe-64-256 v2 as a response. In this paper, we give a formal cryptanalysis on the new tweakey schedule of SKINNYe-64-256 and discover unexpected differential cancellations in the tweakey schedule. For example, we find the number of cancellations can be up to 8 within 30 consecutive rounds, which is significantly larger than the expected 3 cancellations. Moreover, we take our new discoveries into rectangle, MITM and impossible differential attacks, and adapt the corresponding automatic tools with new constraints from our discoveries. Finally, we find a 41-round related-tweakey rectangle attack on SKINNYe-64-256 and leave a security margin of 3 rounds only. As STK accepts arbitrary tweakey size, but SKINNY and SKINNYe-64-256 v2 only support up to 4n tweakey size. We introduce a new design of tweakey schedule for SKINNY-64 to further extend the supported tweakey size. We give a formal proof that our new tweakey schedule inherits the security requirement of STK and SKINNY. We also discuss possible ways to extend the tweakey size for SKINNY-128.

This paper provides improved preimage analysis on round-reduced Keccak-384/512. Unlike low-capacity versions, Keccak-384/512 outputs from two parts of its state: an entire 320-bit plane and a 64/192-bit truncation of a second plane. Due to lack of degrees of freedom, most existing preimage analysis can only control the first 320-bit plane and achieve limited results. By thoroughly analyzing the algebraic structure of Keccak, this paper proposes a technology named ``extra linear dependence'', which can construct linear relations between corresponding bits from two planes. To apply the technology, this paper inherits pioneers' attack thoughts that convert output bits to linear or quadratic equations of input variables. When solving the final equation system, those linear relations can lead to extra restricting equations of output, exceeding the limit of matrix rank. As a result, the complexity of preimage attacks on 2-round and 3-round Keccak-384/512 can be decreased to $2^{39}$/$2^{204}$ and $2^{270}$/$2^{424}$ Keccak calls respectively, which are all the best known results so far. To support the theoretical analysis, this paper provides the first preimage of all `0' digest for 2-round Keccak-384, which can be obtained in one day with single core on an ordinary PC.

The protection of confidential information is a global issue and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on "Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a ciphertext. The actual strength of the block ciphers against several attacks is entirely based on its substitution characteristic, which is gained by using the substitution box(S-Box). In the current literature, algebraic structure-based and chaos-based techniques are highly used for the construction of S-boxes because both these techniques have favourable features for S-box construction, but also various attacks of these techniques have been identified including SAT solver,Linear and differential attacks,Gröbner-based attacks,XSL attacks,Interpolation attacks,XL based-attacks,Finite precision effect, chaotic systems degradation, predictability,weak randomness, chaotic discontinuity, Limited control parameters. The main objective of this research is to design a novel technique for the dynamic generation of S-boxes that are safe against the cryptanalysis techniques of algebraic structure-based and chaos-based approaches. True randomness has been universally recognized as the ideal method for cipher primitives design because true random numbers are unpredictable, irreversible, and unreproducible. The biggest challenge we faced during this research was how can we generate the true random numbers and how can true random numbers utilized for strengthening the s-box construction technique. The basic concept of the proposed technique is the extraction of true random bits from underwater acoustic waves and to design a novel technique for the dynamic generation of S-boxes using the chain of knight’s tour. Rather than algebraic structure and chaos-based, our proposed technique depends on inevitable high-quality randomness which exists in underwater acoustics waves. The proposed method satisfies all standard evaluation tests of S-boxes construction and true random numbers generation. Two million bits have been analyzed using the NIST randomness test suite, and the results show that underwater sound waves are an impeccable entropy source for true randomness. Additionally, our dynamically generated S-boxes have better or equal strength, over the latest published S-boxes (2020 to 2021). According to our knowledge first time, this type of research has been done, in which natural randomness of underwater acoustic waves has been used for the construction of block cipher's Substitution Box.

Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.

Lattice-based digital signature schemes following the hash-and-sign design paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer an attractive level of efficiency, particularly when instantiated with structured compact trapdoors. In particular, NIST postquantum finalist Falcon is both quite fast for signing and verification and quite compact: NIST notes that it has the smallest bandwidth (as measured in combined size of public key and signature) of all round 2 digital signature candidates. Nevertheless, while Falcon--512, for instance, compares favorably to ECDSA--384 in terms of speed, its signatures are well over 10 times larger. For applications that store large number of signatures, or that require signatures to fit in prescribed packet sizes, this can be a critical limitation. In this paper, we explore several approaches to further improve the size of hash-and-sign lattice-based signatures, particularly instantiated over NTRU lattices like Falcon and its recent variant Mitaka. In particular, while GPV signatures are usually obtained by sampling lattice points according to some \emph{spherical} discrete Gaussian distribution, we show that it can be beneficial to sample instead according to a suitably chosen \emph{ellipsoidal} discrete Gaussian: this is because only half of the sampled Gaussian vector is actually output as the signature, while the other half is recovered during verification. Making the half that actually occurs in signatures shorter reduces signature size at essentially no security loss (in a suitable range of parameters). Similarly, we show that reducing the modulus $q$ with respect to which signatures are computed can improve signature size as well as verification key size almost ``for free''; this is particularly true for constructions like Falcon and Mitaka that do not make substantial use of NTT-based multiplication (and rely instead on transcendental FFT). Finally, we show that the Gaussian vectors in signatures can be represented in a more compact way with appropriate coding-theoretic techniques, improving signature size by an additional 7 to 14%. All in all, we manage to reduce the size of, e.g., Falcon signatures by 30--40% at the cost of only 4--6 bits of Core-SVP security.

We consider a federated representation learning framework, where with the assistance of a central server, a group of $N$ distributed clients train collaboratively over their private data, for the representations (or embeddings) of a set of entities (e.g., users in a social network). Under this framework, for the key step of aggregating local embeddings trained at the clients in a private manner, we develop a secure embedding aggregation protocol named SecEA, which provides information-theoretical privacy guarantees for the set of entities and the corresponding embeddings at each client $simultaneously$, against a curious server and up to $T < N/2$ colluding clients. As the first step of SecEA, the federated learning system performs a private entity union, for each client to learn all the entities in the system without knowing which entities belong to which clients. In each aggregation round, the local embeddings are secretly shared among the clients using Lagrange interpolation, and then each client constructs coded queries to retrieve the aggregated embeddings for the intended entities. We perform comprehensive experiments on various representation learning tasks to evaluate the utility and efficiency of SecEA, and empirically demonstrate that compared with embedding aggregation protocols without (or with weaker) privacy guarantees, SecEA incurs negligible performance loss (within 5%); and the additional computation latency of SecEA diminishes for training deeper models on larger datasets.

We propose a new paradigm for justifying the security of random oracle-based protocols, which we call the Augmented Random Oracle Model (AROM). We show that the AROM captures a wide range of important random oracle impossibility results. Thus a proof in the AROM implies some resiliency to such impossibilities. We then consider three ROM transforms which are subject to impossibilities: Fiat-Shamir (FS), Fujisaki-Okamoto (FO), and Encrypt-with-Hash (EwH). We show in each case how to obtain security in the AROM by strengthening the building blocks or modifying the transform. Along the way, we give a couple other results. We improve the assumptions needed for the FO and EwH impossibilities from indistinguishability obfuscation to circularly secure LWE; we argue that our AROM still captures this improved impossibility. We also demonstrate that there is no "best possible" hash function, by giving a pair of security properties, both of which can be instantiated in the standard model separately, which cannot be simultaneously satisfied by a single hash function.

In this paper we deepen our understanding of how to apply Simon’s algorithm to break symmetric cryptographic primitives. On the one hand, we automate the search for new attacks. Using this approach we automatically find the first efficient key-recovery attacks against constructions like 5-round MISTY L-FK or 5-round Feistel-FK (with internal permutation) using Simon’s algorithm. On the other hand, we study generalizations of Simon’s algorithm using non-standard Hadamard matrices, with the aim to expand the quantum symmetric cryptanalysis toolkit with properties other than the periods. Our main conclusion here is that none of these generalizations can ac- complish that, and we conclude that exploiting non-standard Hadamard matrices with quantum computers to break symmetric primitives will require fundamentally new attacks.

The SPDZ multiparty computation protocol allows $n$ parties to securely compute arithmetic circuits over a finite field, while tolerating up to $n − 1$ active corruptions. A line of work building upon SPDZ have made considerable improvements to the protocol’s performance, typically focusing on concrete efficiency. However, the communication complexity of each of these protocols is $\Omega(n^2 |C|)$. In this paper, we present a protocol that achieves $O(n|C|)$ communication. Our construction is very similar to those in the SPDZ family of protocols, but for one modular sub-routine for computing a verified sum. There are a handful of times in the SPDZ protocols in which the $n$ parties wish to sum $n$ public values. Rather than requiring each party to broadcast their input to all other parties, clearly it is cheaper to use some designated "dealer" to compute and broadcast the sum. In prior work, it was assumed that the cost of verifying the correctness of these sums is $O(n^2 )$, erasing the benefit of using a dealer. We show how to amortize this cost over the computation of multiple sums, resulting in linear communication complexity whenever the circuit size is $|C| > n$.

We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $t$-out-of-$N$-threshold access-structure that is efficient and does not require a trusted dealer in the common random-string model. We construct this scheme from the ring-learning-with-error (RLWE) assumptions, and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted share re-sharing procedure, this extension can be used to relax the $N$-out-of-$N$-threshold access structure of the original scheme into a $t$-out-of-$N$-threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least $t$ parties can compute a $t$-out-of-$t$ additive sharing of the secret key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.

This work proposes a new two-stage lattice two-stage sampling technique, generalizing the prior two-stage sampling method of Gentry, Peikert, and Vaikuntanathan (STOC '08). By using our new technique as a key building block, we can significantly improve security and efficiency of the current state of the arts of simulation-based functional encryption. Particularly, our functional encryption achieves $(Q,\poly)$ simulation-based semi-adaptive security that allows arbitrary pre- and post-challenge key queries, and has succinct ciphertexts with only an additive $O(Q)$ overhead. Additionally, our two-stage sampling technique can derive new feasibilities of indistinguishability-based adaptively-secure $\IB$-$\FE$ for inner products and semi-adaptively-secure $\AB$-$\FE$ for inner products, breaking several technical limitations of the recent work by Abdalla, Catalano, Gay, and Ursu (Asiacrypt '20).

SPHINCS+~[CCS '19] is one of the selected post-quantum digital signature schemes of NIST's post-quantum standardization process. The scheme is a hash-based signature and is considered one of the most secure and robust proposals. The proposal includes a fast (but large) variant and a small (but costly) variant for each security level. The main problem that might hinder its adoption is its large signature size. Although SPHINCS+ supports a trade-off between signature size and the computational cost of signing, further reducing the signature size (below the small variants) results in a prohibitively high computational cost for the signer. This paper presents several novel methods for further compressing the signature size while requiring negligible added computational costs for the signer and further reducing verification time. Moreover, our approach enables a much more efficient trade-off curve between signature size and the computational costs of the signer. In many parameter settings, we achieve small signatures and faster running times simultaneously. For example, for $128$-bit security, the small signature variant of SPHINCS+ is $7856$ bytes long, while our variant is only $6304$ bytes long: a compression of approximately $20$% while still reducing the signer's running time. However, other trade-offs that focus, e.g., on verification speed, are possible. The main insight behind our scheme is that there are predefined specific subsets of messages for which the WOTS+ and FORS signatures (that SPHINCS+ uses) can be compressed, and generation can be made faster while maintaining the same security guarantees. Although most messages will not come from these subsets, we can search for suitable hashed values to sign. We sign a hash of the message concatenated with a counter that was chosen such that the hashed value is in the subset. The resulting signature is both smaller and faster to sign and verify. Our schemes are simple to describe and implement. We provide an implementation, a theoretical analysis of speed and security, as well as benchmark results.

Orbis Labs presents a method for compiling (“arithmetizing”) relations, expressed as Σ¹₁ formulas in the language of rings, into Halo 2 arithmetic circuits. This method offers the possibility of creating arithmetic circuits without laborious and error-prone manual circuit design and implementation, by instead expressing the relation to be arithmetized in a concise mathematical notation and generating the circuit based on that expression.

This paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for $n$ nodes and input message $M$ that has communication cost $O(n|M|+n^2\log n)$, which is near-optimal due to the lower bound of $\Omega(n|M|+n^2)$. The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation: We propose a new construction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message $M$ while other nodes only needs to multicast coded fragments of size $O(|M|/n + \log n)$. The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.

We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is $O(|M|+\kappa n^2)$, and the retrieval cost per client is $O(|M|+\kappa n)$. Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of $O(|M|+\kappa n)$ in comparison to $O(|M|+\kappa n\log n)$ of prior best. Moreover, each node in our AVID protocol incurs a storage cost of $O(|M|/n+\kappa)$ bits, in comparison to $O(|M|/n+\kappa \log n)$ bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs -- only a factor of $O(\kappa)$ gap from the lower bounds.

Due to the adoption of the horizontal business model with the globalization of semiconductor manufacturing, the overproduction of integrated circuits (ICs) and the piracy of intellectual properties (IPs) have become a significant threat to the semiconductor supply chain. Logic locking has emerged as a primary design-for-security measure to counter these threats. In logic locking, ICs become fully functional after fabrication only when unlocked with the correct key. However, Boolean satisfiability-based attacks have rendered most locking schemes ineffective. This gives rise to the numerous defenses and new locking methods to achieve SAT resiliency. This paper provides a unique perspective on the SAT attack efficiency based on conjunctive normal form (CNF) stored in the SAT solver. First, we show that the attack learns a new relation between key bits upon every distinguishing pattern. After each iteration, these additional clauses appended to the solver could significantly decrease the key search complexity. Second, we demonstrate that the SAT attack can break the locking scheme within the linear complexity of key size. The deviation away from linear search can be explained by the oracle's output and different logic gate types. This helps to answer how different distinguishing input eliminates fewer or more incorrect keys. Moreover, we show how key constraints on point functions affect the complexity of SAT attack. The proper key constraint on AntiSAT locking can effectively reduce the SAT attack complexity to constant 1. The same constraint minimizes the complexity of breaking CAS-Lock down to the linear range. Our analysis provides fresh perspectives on the capabilities of SAT attack, and we offer new directions to achieve SAT resiliency.

In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow-up in query complexity for each oracle individually, and causes a very mild blow-up only. In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure. Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in order to deal with adaptivity.

Private Set Intersection (PSI) allows a set of mutually distrustful parties, each holds a private data set, to compute the intersection of all sets, such that no information is revealed except for the intersection. The state-of-the-art PSI protocol (Garimella et al., CRYPTO'21) in the multi-party setting tolerating any number of malicious corruptions requires the communication bandwidth of $O(n\ell|\mathbb{F}|)$ bits for the central party $P_0$ due to the star architecture, where $n$ is the number of parties, $\ell$ is the size of each set and $|\mathbb{F}|$ is the size of an exponentially large field $\mathbb{F}$. When $n$ and $\ell$ are large, this forms an efficiency bottleneck (especially for networks with restricted bandwidthes). In this paper, we present a new multi-party PSI protocol in dishonest-majority malicious setting, which reduces the communication bandwidth of the central party $P_0$ from $O(n\ell|\mathbb{F}|)$ bits to $O(\ell|\mathbb{F}|)$ bits using a tree architecture. Furthermore, our PSI protocol reduces the expensive LPN encoding operations performed by $P_0$ by a factor of $n$ as well as the computational cost by $2n\ell$ hash operations in total. Additionally, while the multi-party PSI protocol (Garimella et al., CRYPTO'21) with a single output is secure, we present a simple attack against its multi-output extension, which allows an adversary to learn more information on the sets of honest parties beyond the intersection of all sets.

Fully homomorphic encryption~(FHE) has flourished since it was first constructed by Gentry~(STOC 2009). Single instruction multiple data~(SIMD) gave rise to efficient homomorphic operations on vectors in \((\mathbb{F}_{t^d})^\ell\), for prime \(t\). RLWE instantiated with cyclotomic polynomials of the form \(X^{2^N}+1\) dominate implementations of FHE due to highly efficient fast Fourier transformations. However, this choice yields very short SIMD plaintext vectors and high degree extension fields, e.g. \(\ell < 100, d > 100\) for small primes~(\(t = 3, 5, \dots\)). In this work, we describe a method to encode more data on top of SIMD, \emph{Field Instruction Multiple Data}, applying reverse multiplication friendly embedding~(RMFE) to FHE. With RMFE, length-\(k\) \(\mathbb{F}_{t}\) vectors can be encoded into \(\mathbb{F}_{t^d}\) and multiplied once. The results have to be recoded~(decoded and then re-encoded) before further multiplications can be done. We introduce an FHE-specific technique to additionally evaluate arbitrary linear transformations on encoded vectors for free during the FHE recode operation. On top of that, we present two optimizations to unlock high degree extension fields with small \(t\) for homomorphic computation: \(r\)-fold RMFE, which allows products of up to \(2^r\) encoded vectors before recoding, and a three-stage recode process for RMFEs obtained by composing two smaller RMFEs. Experiments were performed to evaluate the effectiveness of FIMD from various RMFEs compared to standard SIMD operations. Overall, we found that FIMD generally had \(>2\times\) better (amortized) multiplication times compared to FHE for the same amount of data, while using almost \(k/2 \times\) fewer ciphertexts required.

We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in the security analysis of our PAKE protocols. Despite the resemblance, the translation of Diffie-Hellman based PAKE protocols to group actions either does not work with known techniques or is insecure ("How not to create an isogeny-based PAKE", Azarderakhsh et al., ACNS 2020). We overcome the difficulties mentioned in previous work by using a "bit-by-bit" approach, where each password bit is considered separately. Our first protocol $\mathsf{X\text{-}GA\text{-}PAKE}_\ell$ can be executed in a single round. Both parties need to send two set elements for each password bit in order to prevent offline dictionary attacks. The second protocol $\mathsf{Com\text{-}GA\text{-}PAKE}_\ell$ requires only one set element per password bit, but one party has to send a commitment on its message first. We also discuss different optimizations that can be used to reduce the computational cost. We provide comprehensive security proofs for our base protocols and deduce security for the optimized versions.

Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the $\beta$-Weil pairing on curves with odd embedding degree which involve vertical line functions useful for sparse multiplications. For computations we used Miller's algorithm combined with storage and multifunction methods. Applying our framework to BLS-$27$, BLS-$15$ and BLS-$9$ curves at respectively the $256$ bit, the $192$ bit and the $128$ bit security level, we obtain faster $\beta$-Weil pairings than the previous state-of-the-art constructions. The correctness of all the formulas and bilinearity of pairings obtained in this work is verified by a SageMath code.

A software watermarking scheme can embed a message into a program while preserving its functionality. The embedded message can be extracted later by an extraction algorithm, and no one could remove it without significantly changing the functionality of the program. A watermarking scheme is public key if neither the marking procedure nor the extraction procedure needs a watermarking secret key. Prior constructions of watermarking schemes mainly focus on watermarking pseudorandom functions (PRFs), and the major open problem in this direction is to construct a public-key watermarkable PRF. In this work, we solve the open problem via constructing public-key watermarkable PRFs with different trade-offs from various assumptions, ranging from standard lattice assumptions to the existence of indistinguishability obfuscation. To achieve the results, we first construct watermarking schemes in a weaker model, where the extraction algorithm is provided with a “hint” about the watermarked PRF key. Then we upgrade the constructions to standard watermarking schemes using a robust unobfuscatable PRF. We also provide the first construction of robust unobfuscatable PRF in this work, which is of independent interest.

Non-malleable zero-knowledge, originally introduced in the context of man-in-the-middle attacks, serves as an important building block to protect against concurrent attacks where different protocols may coexist and interleave. While this primitive admits almost optimal constructions in the plain model, they are several orders of magnitude slower in practice than standalone zero-knowledge. This is in sharp contrast to non-malleable commitments where practical constructions (under the DDH assumption) have been known for a while. We present a new approach for constructing efficient non-malleable zero-knowledge for all languages in NP, based on a new primitive called instance-based non-malleable commitment (IB-NMC). We show how to construct practical IB-NMC by leveraging the fact that simulators of sub-linear zero-knowledge protocols can be much faster than the honest prover algorithm. With an efficient implementation of IB-NMC, our approach yields the first general-purpose non-malleable zero-knowledge protocol that achieves practical efficiency in the plain model. All of our protocols can be instantiated from symmetric primitives such as block-ciphers and hash functions, have reasonable efficiency in practice, and are general-purpose. Our techniques also yield the first efficient non-malleable commitment scheme without public-key assumptions.

In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element $x$, an integer $T$, and an RSA modulus $N$, it is hard to compute $x^{2^T} \mod N$---or even decide whether $y\stackrel{?}{=}x^{2^T} \mod N$---in parallel time less than the trivial approach of computing $T$ sequential squarings. This rise has been driven by efficient interactive proofs for repeated squaring, opening the door to more efficient constructions of verifiable delay functions, various secure computation primitives, and proof systems for more general languages. In this work, we study the complexity of statistically-sound interactive proofs for the repeated squaring relation. Technically, we consider interactive proofs where the prover sends at most $k \ge 0$ elements per round and the verifier performs generic group operations over the group $\mathbb{Z}_N^\star$. As our main contribution, we show that for any one-round proof with a randomized verifier (i.e., an MA proof) the verifier either runs in parallel time $\Omega(T/(k+1))$ with high probability, or is able to factor $N$ given the proof provided by the prover. This shows that either the prover essentially sends $p,q$ such that $N = p\cdot q$ (which is infeasible or undesirable in most applications), or a variant of Pietrzak's proof of repeated squaring (ITCS 2019) has optimal verifier complexity $O(T/(k+1))$. In particular, it is impossible to obtain a statistically-sound one-round proof of repeated squaring with efficiency on par with the computationally-sound protocol of Wesolowski (EUROCRYPT 2019), with a generic group verifier. We further extend our one-round lower bound to a natural class of recursive (multi-round) interactive proofs for repeated squaring.

The rotational differential-linear attacks, proposed at EUROCRYPT 2021, is a generalization of differential-linear attacks by replacing the differential part of the attacks with rotational differentials. At EUROCRYPT 2021, Liu et al. presented a method based on Morawiecki et al.’s technique (FSE 2013) for evaluating the rotational differential-linear correlations for the special cases where the output linear masks are unit vectors. With this method, some powerful (rotational) differential-linear distinguishers with output linear masks being unit vectors against Friet, Xoodoo, and Alzette were discovered. However, how to compute the rotational differential-linear correlations for arbitrary output masks was left open. In this work, we partially solve this open problem by presenting an efficient algorithm for computing the (rotational) differential-linear correlation of modulo additions for arbitrary output linear masks, based on which a technique for evaluating the (rotational) differential-linear correlation of ARX ciphers is derived. We apply the technique to Alzette, Siphash, Chacha, and Speck. As a result, significantly improved (rotational) differential-linear distinguishers including deterministic ones are identified. All results of this work are practical and experimentally verified to confirm the validity of our methods. In addition, we try to explain the experimental distinguishers employed in FSE 2008, FSE 2016, and CRYPTO 2020 against Chacha. The predicted correlations are close to the experimental ones.

Proofs of Retrievability (PoR) protocols ensure that a client can fully retrieve a large outsourced file from an untrusted server. Good PoRs should have low communication complexity, small storage overhead and clear security guarantees. We design a good PoR based on a family of graph codes called expander codes. We use expander codes based on graphs derived from point-line incidence relations of finite affine planes. Høholdt et al. showed that, when using Reed-Solomon codes as inner codes, these codes have good dimension and minimum distance over a relatively small alphabet. Moreover, expander codes possess very efficient unique decoding algorithms. We take advantage of these results to de- sign a PoR scheme that extracts the outsourced file in quasi-linear time and features better concrete parameters than state-of-the-art schemes w.r.t storage overhead and size of the outsourced file. Using the Con- structive Cryptography framework of Maurer, we get sharper and more rigourous security guarantees for our scheme than the ones given by the usual epsilon-adversary model. We follow an unbounded-use audit procedure to ensure that the extraction of the outsourced file will succeed w.h.p.. The properties of our expander codes yield an audit with communication complexity comparable to other code-based PoRs.

In recent years, cryptocurrencies have increasingly been used in cybercrime and have become the key means of payment in darknet marketplaces, partly due to their alleged anonymity. Furthermore, the research attacking the anonymity of even those cryptocurrencies that claim to offer anonymity by design is growing and is being applied by law enforcement agencies in the fight against cybercrime. Their investigative measures require a certain degree of suspicion and it is unclear whether findings resulting from attacks on cryptocurrencies' anonymity can indeed establish that required degree of suspicion. The reason for this is that these attacks are partly based upon uncertain assumptions which are often not properly addressed in the corresponding papers. To close this gap, we extract the assumptions in papers that are attacking Bitcoin, Monero and Zcash, major cryptocurrencies used in darknet markets which have also received the most attention from researchers. We develop a taxonomy to capture the different nature of those assumptions in order to help investigators to better assess whether the required degree of suspicion for specific investigative measures could be established. We found that assumptions based on user behaviour are in general the most unreliable and thus any findings of attacks based on them might not allow for intense investigative measures such as pre-trial detention. We hope to raise awareness of the problem so that in the future there will be fewer unlawful investigations based upon uncertain assumptions and thus fewer human rights violations.

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions. In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.

In this paper we study search problems that arise very often in cryptanalysis: nested search problems, where each search layer has known degrees of freedom and/or constraints. A generic quantum solution for such problems consists of nesting Grover's quantum search algorithm or amplitude amplification (QAA) by Brassard et al., obtaining up to a square-root speedup on classical algorithms. However, the analysis of nested Grover or QAA is complex and introduces technicalities that in previous works are handled in a case-by-case manner. Moreover, straightforward nesting of $\ell$ layers multiplies the complexity by a constant factor $(\pi/2)^\ell$. In this paper, we aim to remedy both these issues and introduce a generic framework and tools to transform a classical nested search into a quantum procedure. It improves the state-of-the-art in three ways: 1) our framework results in quantum procedures that are significantly simpler to describe and analyze; 2) it reduces the overhead factor from $(\pi/2)^\ell$ to $\sqrt{\ell}$; 3) it is simpler to apply and optimize, without needing manual quantum analysis. We give generic complexity formulas and show that for concrete instances, numerical optimizations enable further improvements, reducing even more the gap to an exact quadratic speedup. We demonstrate our framework by giving a tighter analysis of quantum attacks on reduced-round AES.

There are numerous settings in which people’s preferences are aggregated outside of formal elections, and where privacy and verification are important but the stringent coercion-resistant properties of government elections do not apply, a prime example being social media platforms. In contrast to the centrally organised, single-shot elections on which most of the literature is focused, our settings of interest often have no trusted authority and are iterative, i.e., publish partial tallies before all votes are received. In this work, we explore opinion aggregation in a decentralised, iterative setting. In our novel protocol,randomly-chosen parties take turns to decrypt aggregated votes in an incentive-driven manner. Our simple construction leverages homomorphic encryption and secret sharing in a novel manner to provide security of the tally, public and individual verifiability, as well as vote privacy and liveness guarantees. Contrary to existing voting schemes, our protocol is ideal for the iterative setting.

Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions, and a number of techniques have been proposed to do so over the years. One of the first ones was due to Shallue and van de Woestijne (ANTS-VII), and it had the interesting property of applying to essentially all elliptic curves over finite fields. It did not, however, have the desirable property of being indifferentiable from a random oracle when composed with a random oracle to the base field. Various approaches have since been considered to overcome this limitation, starting with the foundational work of Brier et al. (CRYPTO 2011). For example, if $f\colon \mathbb{F}_q\to E(\mathbb{F}_q)$ is the Shallue--van de Woestijne (SW) map and $\mathfrak{h}_1,\mathfrak{h}_2$ are two independent random oracles to $\mathbb{F}_q$, we now know that $m\mapsto f\big(\mathfrak{h}_1(m)\big)+f\big(\mathfrak{h}_2(m)\big)$ is indifferentiable from a random oracle. Unfortunately, this approach has the drawback of being twice as expensive to compute than the straightforward, but not indifferentiable, $m\mapsto f\big(\mathfrak{h}_1(m)\big)$. Most other solutions so far have had the same issue: they are at least as costly as two base field exponentiations, whereas plain encoding maps like $f$ cost only one exponentiation. Recently, Koshelev (DCC 2022) provided the first construction of indifferentiable hashing at the cost of one exponentiation, but only for a very specific class of curves (some of those with $j$-invariant $0$), and using techniques that are unlikely to apply more broadly. In this work, we revisit this long-standing open problem, and observe that the SW map actually fits in a one-parameter family $(f_u)_{u\in\mathbb{F}_q}$ of encodings, such that for independent random oracles $\mathfrak{h}_1, \mathfrak{h}_2$ to $\mathbb{F}_q$, $F\colon m\mapsto f_{\mathfrak{h}_2(m)}\big(\mathfrak{h}_1(m)\big)$ is indifferentiable. Moreover, on a very large class of curves (essentially those that are either of odd order or of order divisible by 4), the one-parameter family admits a rational parametrization, which let us compute $F$ at almost the same cost as small $f$, and finally achieve indifferentiable hashing to most curves with a single exponentiation. Our new approach also yields an improved variant of the Elligator Squared technique of Tibouchi (FC 2014) that represents points of arbitrary elliptic curves as close-to-uniform random strings.

Adaptive security is a highly desirable property in the design of secure protocols. It tolerates adversaries that corrupt parties as the protocol proceeds, as opposed to static security where the adversary corrupts the parties at the onset of the execution. The well-accepted folklore is that static and adaptive securities are equivalent for perfectly secure protocols. Indeed, this folklore is backed up by a transformation by Canetti et al. (EUROCRYPT'01), showing that any perfectly secure protocol that is statically secure and satisfies some basic requirements is also adaptively secure. Yet, the transformation results in an adaptively secure protocol with inefficient simulation (i.e., where the simulator might run in super-polynomial time even if the adversary runs just in polynomial time). Inefficient simulation is problematic when using the protocol as a sub-routine in the computational setting. Our main question is whether an alternative efficient transformation from static to adaptive security exists. We show an inherent difficulty in achieving this goal generically. In contrast to the folklore, we present a protocol that is perfectly secure with efficient static simulation (therefore also adaptively secure with inefficient simulation), but for which efficient adaptive simulation does not exist (assuming the existence of one-way permutations). In addition, we prove that the seminal protocol of Ben-Or, Goldwasser, and Wigderson (STOC'88) is secure against adaptive, semi-honest corruptions with efficient simulation. Previously, adaptive security of the protocol, as is, was only known either for a restricted class of circuits or for all circuits but with inefficient simulation.

Machine learning as a service scenario typically requires the client to trust the server and provide sensitive data in plaintext. However, with the recent improvements in fully homomorphic encryption (FHE) schemes, many such applications can be designed in a privacy preserving way. In this work, we focus on such a problem, private decision tree evaluation (PDTE) --- where a server has a decision tree classification model, and a client wants to use the model to classify her private data without revealing the data or the classification result to the server. We present an efficient non-interactive design of PDTE, that we call SortingHat, based on FHE techniques. As part of our design, we solve multiple cryptographic problems related to FHE: (1) we propose a fast homomorphic comparison function where one input can be in plaintext format; (2) we design an efficient binary decision tree evaluation technique in the FHE setting, which we call homomorphic traversal, and apply it together with our homomorphic comparison to evaluate private decision tree classifiers, obtaining running times orders of magnitude faster than the state of the art; (3) we improve both the communication cost and the time complexity of transciphering, by applying our homomorphic comparison to the FiLIP stream cipher. Through a prototype implementation, we demonstrate that our improved transciphering solution runs around 400 times faster than previous works. We finally present a choice in terms of PDTE design: we present a version of SortingHat without transciphering that achieves significant improvement in terms of computation cost comparing to prior works; and another version with transciphering that has a communication cost about 20 thousand times smaller but comparable running time.

In this work we improve upon the state of the art for practical zero-knowledge for set membership, a building block at the core of several privacy-aware applications, such as anonymous payments, credentials and whitelists. This primitive allows a user to show knowledge of an element in a large set without leaking the specific element. One of the obstacles to its deployment is efficiency. Concretely efficient solutions exist, e.g., those deployed in Zcash Sapling, but they often work at the price of a strong trust assumption: an underlying setup that must be generated by a trusted third party. To find alternative approaches we focus on a common building block: accumulators, a cryptographic data structure which compresses the underlying set. We propose novel, more efficient and fully transparent constructions (i.e., without a trusted setup) for accumulators supporting zero-knowledge proofs for set membership. Technically, we introduce new approaches inspired by ``commit-and-prove'' techniques to combine shallow Merkle trees and 2-cycles of elliptic curves into a highly practical construction. Our basic accumulator construction---dubbed Curve Trees---is completely transparent (does not require a trusted setup) and is based on simple and widely used assumptions (DLOG and Random Oracle Model). Ours is the first fully transparent construction that obtains concretely small proof/commitment sizes for large sets and a proving time one order of magnitude smaller than proofs over Merkle Trees with Pedersen hash. For a concrete instantiation targeting 128 bits of security we obtain: a commitment to a set of any size is 256 bits; for $|S| = 2^{40}$ a zero-knowledge membership proof is 2.9KB, its proving takes $2$s and its verification $40$ms on an ordinary laptop. Using our construction as a building block we can design a simple and concretely efficient anonymous cryptocurrency with full anonymity set, which we dub $\mathbb{V}$cash. Its transactions can be verified in $\approx 80$ms or $\approx 5$ms when batch-verifying multiple ($> 100$) transactions; transaction sizes are $4$KB. Our timings are competitive with those of the approach in Zcash Sapling and trade slightly larger proofs (transactions in Zcash Sapling are 2.8KB) for a completely transparent setup.

The verifiable delay function (VDF), as a kind of cryptographic primitives, has recently been adopted quite often in decentralized systems. Highly correlated to the security of VDFs, the fastest implementation for VDF evaluation is generally desired to be publicly known. In this paper, for the first time, we propose a low-latency hardware implementation for the complete VDF evaluation in the class group by joint exploiting optimizations. On one side, we reduce the required computational cycles by decreasing the hardware-unfriendly divisions and increase the parallelism of computations by reducing the data dependency. On the other side, well-optimized low-latency architectures for large-number divisions, multiplications, and additions are developed, respectively, while those operations are generally very hard to be accelerated. Based on these basic operators, we devise the architecture for the complete VDF evaluation with possibly minimal pipeline stalls. Finally, the proposed design is coded and synthesized under the TSMC 28-nm CMOS technology. The experimental results show that our design can achieve a speedup of 3.6x compared to the optimal C++ implementation for the VDF evaluation over an advanced CPU. Moreover, compared to the state-of-the-art hardware implementation for the squaring, a key step of VDF, we achieve about 2x speedup.

In this paper we propose the first efficient quantum version of key-recovery attacks on block ciphers based on impossible differentials, which was left as an open problem in previous work. These attacks work in two phases. First, a large number of differential pairs are collected, by solving a limited birthday problem with the attacked block cipher considered as a black box. Second, these pairs are filtered with respect to partial key candidates. We show how to translate the pair filtering step into a quantum procedure, and provide a complete analysis of its complexity. If the path of the attack can be properly reoptimized, this procedure can reach a significant speedup with respect to classical attacks. We provide two applications on SKINNY-128-256 and AES-192/256. These results do not threaten the security of these ciphers but allow us to better understand their (post-quantum) security margin.

Nowadays, MILP is a very popular tool to help cryptographers search for various distinguishers, in particular for integral distinguishers based on the division property. However, cryptographers tend to use MILP in a rather naive way, modeling problems in an exact manner and feeding them to a MILP solver. In this paper, we show that a proper use of some features of MILP solvers such as lazy constraints, along with using simpler but less accurate base models, can achieve much better solving times, while maintaining the precision of exact models. In particular, we describe several new modelization techniques for division property related models as well as a new variant of the Quine-McCluskey algorithm for this specific setting. Moreover, we positively answer a problem raised in [DF20] about handling the large sets of constraints describing valid transitions through Super S-boxes into a MILP model. As a result, we greatly improve the solving times to recover the distinguishers from several previous works ([DF20], [HWW20], [SWW17], [Udo21], [EY21]) and we were able to search for integral distinguishers on 5-round ARIA which was out of reach of previous modeling techniques.

Division property is an effective method for finding integral distinguishers for block ciphers, performing cube attacks on stream ciphers, and studying the algebraic degree of boolean functions. One of the main problems in this field is how to provably find the smallest input multiset leading to a balanced output. In this paper, we propose a new method based on division property for finding integral distinguishers with a provably minimum data complexity on permutation functions and block ciphers, in the conventional division property model. The new method is based on efficiently analyzing the algebraic normal form of the target output boolean function. We examine the proposed method on LBlock, TWINE, SIMON, Present, Gift, and Clyde-128 block ciphers. Although in most cases, the results are compliant with the distinguishers reported in the previous work, the proposed method proves the optimality of these results, in the conventional division property model. However, the proposed method can find distinguishers for 8-round Clyde-128 with a data complexity less than the previously reported one, based on conventional division property. The new method is also capable of determining the maximum number of balanced output bits in an integral distinguisher with a specified number of active bits. We propose an algorithm to exploit this capability and apply it to the studied ciphers. As a result, we determine the maximum number of balanced bits on integral distinguishers with minimum and non-minimum data complexities on the studied ciphers and report improved results on Gift-64, Present and SIMON64 in the conventional model.

The recently proposed YOSO model is a groundbreaking approach to MPC, executable on a public blockchain, circumventing adaptive player corruption by hiding the corruption targets until they are worthless. Players are selected unpredictably from a large pool to perform MPC subtasks, in which each selected player sends a single message (and reveals their identity). While YOSO MPC has attractive asymptotic complexity, unfortunately, it is concretely prohibitively expensive due to the cost of its building blocks. We propose a modification to the YOSO model that preserves resilience to adaptive server corruption, but allows for much more efficient protocols. In SCALES (Small Clients And Larger Ephemeral Servers) only the servers facilitating the MPC computation are ephemeral (unpredictably selected and ``speak once''). Input providers (clients) publish problem instances and collect the output, but do not otherwise participate in computation. SCALES offers attractive features, and improves over YOSO protocols in outsourcing MPC to a large pool of servers under adaptive corruption. We build SCALES from rerandomizable garbling schemes, which is a contribution of independent interest, with additional applications.

A Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, when we design scalable two-party PSU protocols, we follow the so-called ``split-execute-assemble'' paradigm, and also use Oblivious Transfer as a building block. Recently, Kolesnikov et al. (ASIACRYPT 2019) pointed out that security issues could be introduced when we design PSU protocols following the ``split-execute-assemble'' paradigm. Surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage. In this work, to enable a better understanding of the security for PSU, we provide a systematic treatment of the typical PSU protocols, which may shed light on the design of practical and secure PSU protocols in the future. More specifically, we define different versions of PSU functionalities to properly capture the subtle security issues arising from protocols following the ``split-execute-assemble'' paradigm and using Oblivious Transfer as subroutines. Then, we survey the typical PSU protocols, and categorize these protocols into three design frameworks, and prove what PSU functionality the protocols under each framework can achieve at best, in the semi-honest setting.

Draco is a lightweight stream cipher designed by Hamann et al. in IACR ToSC 2022. It has a Grain-like structure with two state registers of size 95 and 33 bits. In addition, the cipher uses a 128-bit secret key and a 96-bit IV. The first 32 bits of the key and the IV forms a non-volatile internal state that does not change during the time that the cipher produces keystream bits. The authors claim that the cipher is provably secure against Time Memory Data (TMD) Tradeoff attacks. However in this paper, we first present two TMD tradeoff attacks against Draco. Both attacks leverage the fact that for certain judiciously chosen IVs, the state update function of the cipher depend on only a small fraction of the non-volatile internal state. This makes the state update function in Draco essentially a one way function over a much smaller domain and range. The first attack requires around $2^{114.2}$ Draco iterations and requires that the adversary has access to $2^{32}$ chosen IVs. The second attack is such that the attack parameters can be tuned as per the requirements of the attacker. If the attacker prioritizes that the number of different chosen IVs is limited to $2^{20}$ say, then the attack can be done in around time proportional to $2^{126}$ Draco rounds. However if the total attack complexity is to be optimized, then the attack can be performed in $2^{107}$ time using around $2^{40}$ chosen IVs.

We revisit and improve performance of arithmetic in the binary GLS254 curve by introducing the 2DT-GLS scalar multiplication algorithm. The algorithm includes theoretical and practice-oriented contributions of potential independent interest: (i) for the first time, a proof that the GLS scalar multiplication algorithm does not incur exceptions, such that faster incomplete formulas can be used; (ii) faster dedicated atomic formulas that alleviate the cost of precomputation; (iii) a table compression technique that reduces the storage needed for precomputed points; (iv) a refined constant-time scalar decomposition algorithm that is more robust to rounding. We also present the first GLS254 implementation for Armv8. With our contributions, we set new speed records for constant-time scalar multiplication by $34.5\%$ and $6\%$ on 64-bit Arm and Intel platforms, respectively.

Lightweight cryptography ensures cryptography applications to devices with limited resources. Low-area implementations of linear layers usually play an essential role in lightweight cryptography. The previous works have provided plenty of methods to generate low-area implementations using 2-input xor gates for various linear layers. However, it is still challenging to search for smaller implementations using two or more inputs xor gates. This paper, inspired by Banik et al., proposes a novel approach to construct a quantity of lower area implementations with (n+1)-input gates based on the given implementations with n-input gates. Based on the novel algorithm, we present the corresponding search algorithms for n=2 and n=3, which means that we can efficiently convert an implementation with 2-input xor gates and 3-input xor gates to lower-area implementations with 3-input xor gates and 4-input xor gates, respectively. We improve the previous implementations of linear layers for many block ciphers according to the area with these search algorithms. For example, we achieve a better implementation with 4-input xor gates for AES MixColumns, which only requires 243 GE in the STM 130 nm library, while the previous public result is 258.9 GE. Besides, we obtain better implementations for all 5500 lightweight matrices proposed by Li et al. at FSE 2019, and the area for them is decreased by about 21% on average.

Recently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages. In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for $k$ out of $\ell$ statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of $\Sigma$-protocols and a corresponding threshold relation $\mathcal{R}_\mathsf{k,\ell}$, provides an efficient $\Sigma$-protocol for $\mathcal{R}_\mathsf{k,\ell}$ with improved communication complexity w.r.t. prior results. Moreover, our transformation preserves statistical/perfect honest-verifier zero knowledge.

Automatic tools to search for boomerang distinguishers have seen significant advances over the past few years. However, most previous work has focused on ciphers based on a Substitution Permutation Network (SPN), while analyzing the Feistel structure is of great significance. Boukerrou et al. recently provided a theoretical framework to formulate the boomerang switch over multiple Feistel rounds, but they did not provide an automatic tool to find distinguishers. In this paper, by enhancing the recently proposed method by Hadipour et al., we provide an automatic tool to search for boomerang distinguishers and apply it to block ciphers following the Generalized Feistel Structure (GFS). Applying our tool to a wide range of GFS ciphers, we show that it significantly improves the best previous results on boomerang analysis. In particular, we improve the best previous boomerang distinguishers for 20 and 21 rounds of WARP by a factor of $2^{38.28}$ and $2^{36.56}$, respectively. Thanks to the effectiveness of our method, we can extend the boomerang distinguishers of WARP by two rounds and distinguish 23 rounds of this cipher from a random permutation. Applying our method to the internationally-standardized cipher CLEFIA, we achieve a 9-round boomerang distinguisher which improves the best previous boomerang distinguisher by one round. Based on this distinguisher, we build a key-recovery attack on 11 rounds of CLEFIA, which improves the best previous sandwich attack on this cipher by one round. We also apply our method to LBlock, LBlock-s, and TWINE and improve the best previous boomerang distinguisher of these ciphers.

We propose MoNet, the first bi-directional payment channel network with unlimited lifetime for Monero. It is fully compatible with Monero without requiring any modification of the current Monero blockchain. MoNet preserves transaction fungibility, i.e., transactions over MoNet and Monero are indistinguishable, and guarantees anonymity of Monero and MoNet users by avoiding any potential privacy leakage introduced by the new payment channel network. We also propose a new crypto primitive, named Verifiable Consecutive One-way Function (VCOF). It allows one to generate a sequence of statement-witness pairs in a consecutive and verifiable way, and these statement-witness pairs are one-way, namely it is easy to compute a statement-witness pair by knowing any of the pre-generated pairs, but hard in an opposite flow. By using VCOF, a signer can produce a series of consecutive adaptor signatures CAS. We further propose the generic construction of consecutive adaptor signature as an important building block of MoNet. We develop a proof-of-concept implementation for MoNet, and our evaluation shows that MoNet can reach the same transaction throughput as Lightning Network, the payment channel network for Bitcoin. Moreover, we provide a security analysis of MoNet under the Universal Composable (UC) security framework.

Replay attacks are among the most well-known attacks against vote privacy. Many e-voting systems have been proven vulnerable to replay attacks, including systems like Helios that are used in real practical elections. Despite their popularity, it is commonly believed that replay attacks are inefficient but the actual threat that they pose to vote privacy has never been studied formally. Therefore, in this paper, we precisely analyze for the first time how efficient replay attacks really are. We study this question from commonly used and complementary perspectives on vote privacy, showing as an independent contribution that a simple extension of a popular game-based privacy definition corresponds to a strong entropy-based notion. Our results demonstrate that replay attacks can be devastating for a voter's privacy even when an adversary's resources are very limited. We illustrate our formal findings by applying them to a number of real-world elections, showing that a modest number of replays can result in significant privacy loss. Overall, our work reveals that, contrary to a common belief, replay attacks can be very efficient and must therefore be considered a serious threat.

In this paper, we propose a new approach to the study of lattice problems used in cryptography. We specifically focus on module lattices of a fixed rank over some number field. An essential question is the hardness of certain computational problems on such module lattices, as the additional structure may allow exploitation. The fundamental insight is the fact that the collection of those lattices are quotients of algebraic manifolds by arithmetic subgroups. Functions on these spaces are studied in mathematics as part of number theory. In particular, those form a module over the Hecke algebra associated with the general linear group. We use results on these function spaces to define a class of distributions on the space of lattices. Using the Hecke algebra, we define Hecke operators associated with collections of prime ideals of the number field and show a criterion on distributions to converge to the uniform distribution, if the Hecke operators are applied to the chosen distribution. Our approach is motivated by the work of de Boer, Ducas, Pellet-Mary, and Wesolowski (CRYPTO'20) on self-reduction of ideal lattices via Arakelov divisors.

Symbolic security protocol verifiers have reached a high degree of automation and maturity. Today, experts can model real-world protocols, but this often requires model-specific encodings and deep insight into the strengths and weaknesses of each of those tools. With Sapic+ , we introduce a protocol verification platform that lifts this burden and permits choosing the right tool for the job, at any development stage. We build on the existing compiler from Sapic to Tamarin, and extend it with automated translations from Sapic+ to ProVerif and DeepSec, as well as powerful, protocol-independent optimizations of the existing translation. We prove each part of these translations sound. A user can thus, with a single Sapic+ file, verify reachability and equivalence properties on the specified protocol, either using ProVerif, Tamarin or DeepSec. Moreover, the soundness of the translation allows to directly assume results proven by another tool which allows to exploit the respective strengths of each tool. We demonstrate our approach by analyzing various existing models. This includes a large case study of the 5G authentication protocols, reviously analyzed in Tamarin. Encoding this model in Sapic+ we demonstrate the effectiveness of our approach. Moreover, we study four new case studies: the LAKE and the Privacy-Pass [20] protocols, both under standardization, the SSH protocol with the agent-forwarding feature, and the recent KEMTLS [45] protocol, a post-quantum version of the main TLS key exchange.

Public-key authentication in SSH reveals more information about the participants' keys than is necessary. (1) The server can learn a client's entire set of public keys, even keys generated for other servers. (2) The server learns exactly which key the client uses to authenticate, and can further prove this fact to a third party. (3) A client can learn whether the server recognizes public keys belonging to other users. Each of these problems lead to tangible privacy violations for SSH users. In this work we introduce a new public-key authentication method for SSH that reveals essentially the minimum possible amount of information. With our new method, the server learns only whether the client knows the private key for some authorized public key. If multiple keys are authorized, the server does not learn which one the client used. The client cannot learn whether the server recognizes public keys belonging to other users. Unlike traditional SSH authentication, our method is fully deniable. Our new method also makes it harder for a malicious server to intercept first-use SSH connections on a large scale. Our method supports existing SSH keypairs of all standard flavors — RSA, ECDSA, EdDSA. It does not require users to generate new key material. As in traditional SSH authentication, clients and servers can use a mixture of different key flavors in a single authentication session. We integrated our new authentication method into OpenSSH, and found it to be practical and scalable. For a typical client and server with at most 10 ECDSA/EdDSA keys each, our protocol requires 9 kB of communication and 12.4 ms of latency. Even for a client with 20 keys and server with 100 keys, our protocol requires only 12 kB of communication and 26.7 ms of latency.

Updatable Encryption (UE) allows to rotate the encryption key in the outsourced storage setting while minimizing the bandwith used. The server can update ciphertexts to the new key using a token provided by the client. UE schemes should provide strong confidentiality guarantees against an adversary that can corrupt keys and tokens. This paper studies the problem of building UE in the group action framework. We introduce a new notion of Mappable Effective Group Action (MEGA) and show that we can build CCA secure UE from a MEGA by generalizing the SHINE construction of Boyd etal at Crypto 2020. Unfortunately, we do not know how to instantiate this new construction in the post-quantum setting. Doing so would solve the open problem of building a CCA secure post-quantum UE scheme. Isogeny-based group actions are the most studied post-quantum group actions. Unfortunately, the resulting group actions are not mappable. We show that we can still build UE from isogenies by introducing a new algebraic structure called Effective Triple Orbital Group Action (ETOGA). We prove that UE can be built from an ETOGA and show how to instantiate this abstract structure from isogeny-based group actions. This new construction solves two open problems in ciphertext-independent post-quantum UE. First, this is the first post-quantum UE scheme that supports an unbounded number of updates. Second, our isogeny-based UE scheme is the first post-quantum UE scheme not based on lattices. The security of this new scheme holds under an extended version of the weak pseudorandomness of the standard isogeny group action.

Homomorphic Encryption (HE) is a very attractive solution to ensure privacy when outsourcing confidential data to the cloud, as it enables computation on the data without decryption. As the next step, searching this homomorphic data becomes necessary to navigate it in the server. In this paper, we propose a novel algorithm to search homomorphically encrypted data outsourced to an untrusted server and shared with multiple users. We optimize the steps involved in the process to reduce the number of rounds of communication. We use an order-preserving encoding to batch the data with multi-key HE cryptosystems to reduce the multiplicative depth of the equality circuits and enable direct comparison. Further, we use LEAF to retrieve indices securely, and SealPIR to retrieve the values obliviously to the user. Overall, we provide an efficient end-to-end framework for searching shared data in a semi-honest server.

In this work, we present a systematic study of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA) on structured lattice-based schemes, with a focus on Kyber Key Encapsulation Mechanism (KEM) and Dilithium signature scheme, which are leading candidates in the NIST standardization process for Post-Quantum Cryptography (PQC). Through our study, we attempt to understand the underlying similarities and differences between the existing attacks, while classifying them into different categories. Given the wide variety of reported attacks, simultaneous protection against all the attacks requires to implement customized protections/countermeasures for both Kyber and Dilithium. We therefore present a range of customized countermeasures, capable of providing defenses/mitigations against existing SCA/FIA, and incorporate several SCA and FIA countermeasures within a single design of Kyber and Dilithium. Among the several countermeasures discussed in this work, we present novel countermeasures that offer simultaneous protection against several SCA and FIA-based chosen-ciphertext attacks for Kyber KEM. We implement the presented countermeasures within the well-known pqm4 library for the ARM Cortex-M4 based microcontroller. Our performance evaluation reveals that the presented custom countermeasures incur reasonable performance overheads, on the ARM Cortex-M4 microcontroller. We therefore believe our work argues for the usage of custom countermeasures within real-world implementations of lattice-based schemes, either in a standalone manner or as reinforcements to generic countermeasures such as masking.

This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weakness in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks. The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds.

We describe a new paradigm for multi-party private set intersection cardinality (\psica) that allows $n$ parties to compute the intersection size of their datasets without revealing any additional information. We explore a variety of instantiations of this paradigm. Our protocols avoid computationally expensive public-key operations and are secure in the presence of a semi-honest adversary. We demonstrate the practicality of our \psica\ with an implementation. For $n=16$ parties with data-sets of $2^{20}$ items each, our server-aided variant takes 71 seconds. Interestingly, in the server-less setting, the same task takes only 7 seconds. To the best of our knowledge, this is the first `special purpose' implementation of a multi-party \psica\ from symmetric-key techniques (i.e., an implementation that does not rely on a generic underlying MPC). We study two interesting applications -- heatmap computation and associated rule learning (ARL) -- that can be computed securely using a dot-product as a building block. We analyse the performance of securely computing heatmap and ARL using our protocol and compare that to the state-of-the-art.

The cryptographic sponge is a popular method for hash function design. The construction is in the ideal permutation model proven to be indifferentiable from a random oracle up to the birthday bound in the capacity of the sponge. This result in particular implies that, as long as the attack complexity does not exceed this bound, the sponge construction achieves a comparable level of collision, preimage, and second preimage resistance as a random oracle. We investigate these state-of-the-art bounds in detail, and observe that while the collision and second preimage security bounds are tight, the preimage bound is not tight. We derive an improved and tight preimage security bound for the cryptographic sponge construction. The result has direct implications for various lightweight cryptographic hash functions. For example, the NIST Lightweight Cryptography finalist Ascon-Hash does not generically achieve $2^{128}$ preimage security as claimed, but even $2^{192}$ preimage security. Comparable improvements are obtained for the modes of Spongent, PHOTON, ACE, Subterranean 2.0, and QUARK, among others.

The potential advent of large-scale quantum computers in the near future poses a threat to contemporary cryptography. One ubiquitous usage of cryptography is currently present in the vibrant field of cellular networks. The cryptography of cellular networks is centered around seven secret-key algorithms $f_1, \ldots, f_5, f_1^{*}, f_5^{*}$, aggregated into an authentication and key agreement algorithm set. Still, to the best of our knowledge, these secret key algorithms have not yet been subject to quantum cryptanalysis. Instead, many quantum security considerations for telecommunication networks argue that the threat posed by quantum computers is restricted to public-key cryptography. However, various recent works have presented quantum attacks on secret key cryptography that exploit quantum period finding to achieve more than a quadratic speedup compared to the best known classical attacks. Motivated by this quantum threat to symmetric cryptography, this paper presents a quantum cryptanalysis for the Milenage algorithm set, the prevalent instantiation of the seven secret-key $f_1, \ldots, f_5, f_1^{*}, f_5^{*}$ algorithms that underpin cellular security. Building upon recent quantum cryptanalytic results, we show attacks that go beyond a quadratic speedup. Concretely, we provide quantum attack scenarios for all Milenage algorithms, including a polynomial time quantum existential forgery attack in the $Q_2$ model. Our comprehensive attack overview can serve as a basis for further research into the resilience of Milenage against quantum adversaries.

The dream of software obfuscation is to take programs, as they are, and then generically compile them into obfuscated versions that hide their secret inner workings. In this work we investigate notions of obfuscations weaker than virtual black-box (VBB) but which still allow obfuscating cryptographic primitives preserving their original functionalities as much as possible. In particular we propose two new notions of obfuscations, which we call oracle-differing-input obfuscation (odiO) and oracle-indistinguishability obfuscation (oiO). In a nutshell, odiO is a natural strengthening of differing-input obfuscation (diO) and allows obfuscating programs for which it is hard to find a differing-input when given only oracle access to the programs. An oiO obfuscator allows to obfuscate programs that are hard to distinguish when treated as oracles. We then show applications of these notions, as well as positive and negative results around them. A few highlights include: – Our new notions are weaker than VBB and stronger than diO. – As it is the case for VBB, we show that there exist programs that cannot be obfuscated with odiO or oiO. – Our new notions allow to generically compile several flavours of secret-key primitives (e.g., SKE, MAC, designated verifier NIZK) into their public-key equivalent (e.g., PKE, signatures, publicly verifiable NIZK) while preserving one of the algorithms of the original scheme (function-preserving), or the structure of their outputs (format-preserving).

The rebound attack was introduced by Mendel et al. at FSE 2009 to fulfill a heavy middle round of a differential path for free, utilizing the degree of freedom from states. The inbound phase was extended to 2 rounds by the Super-Sbox technique invented by Lamberger et al. at ASIACRYPT 2009 and Gilbert and Peyrin at FSE 2010. In ASIACRYPT 2010, Sasaki et al. further reduced the requirement of memory by introducing the non-full-active Super-Sbox. In this paper, we further develop this line of research by introducing Super-Inbound, which is able to connect multiple 1-round or 2-round (non-full-active) Super-Sbox inbound phases by utilizing fully the degrees of freedom from both states and key, yet without the use of large memory. This essentially extends the inbound phase by up to 3 rounds. We applied this technique to find classic or quantum collisions on several AES-like hash functions, and improved the attacked round number by 1 to 5 in targets including AES-128 and SKINNY hashing modes, Saturnin-Hash, and Grostl-512. To demonstrate the correctness of our attacks, the semi-free-start collision on 6-round AES-128-MMO/MP with estimated time complexity $2^{24}$ in classical setting was implemented and an example pair was found instantly on a standard PC.

In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-$m$ Crusader Broadcast, in which up to $m$ parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.

WARP is a 128-bit block cipher published by Banik et al. at SAC 2020 as a lightweight alternative to AES. It is based on a generalized Feistel network and achieves the smallest area footprint among 128-bit block ciphers in many settings. Previous analysis results include integral key-recovery attacks on 21 out of 41 rounds. In this paper, we propose integral key-recovery attacks on up to 32 rounds by improving both the integral distinguisher and the key-recovery approach substantially. For the distinguisher, we show how to model the monomial prediction technique proposed by Hu et al. at ASIACRYPT 2020 as a SAT problem and thus create a bit-oriented model of WARP taking the key schedule into account. Together with two additional observations on the properties of WARP's construction, we extend the best previous distinguisher by 2 rounds (as a classical integral distinguisher) or 4 rounds (for a generalized integral distinguisher). For the key recovery, we create a graph-based model of the round function and demonstrate how to manipulate the graph to obtain a cipher representation amenable to FFT-based key recovery.

The performance of Side-Channel Attacks (SCAs) decays rapidly when considering more sub-keys, making the full-key recovery a very challenging problem. Limited to independent collision information utilization, collision attacks establish the relationship among sub-keys but do not significantly slow down this trend. To solve it, we first exploit the samples from the previously attacked S-boxes to assist attacks on the targeted S-box under an assumption that similar leakage occurs in program loop or code reuse scenarios. The later considered S-boxes are easier to be recovered since more samples participate in this assist attack, which results in the ``snowball'' effect. We name this scheme as Snowball, which significantly slows down the attenuation rate of attack performance. We further introduce confusion coefficient into the collision attack to construct collision confusion coefficient, and deduce its relationship with correlation coefficient. Based on this relationship, we give two optimizations on our Snowball exploiting the ``values'' information and ``rankings'' information of collision correlation coefficients named Least Deviation from Pearson correlation coefficient (PLD) and Least Deviation from confusion coefficient (CLD). Experiments show that the above optimizations significantly improve the performance of our Snowball.

Regev's Learning with Errors (LWE) problem (STOC 2005) is a fundamental hardness assumption for modern cryptography. The Learning with Rounding (LWR) Problem was put forth by Banarjee, Peikert and Rosen (Eurocrypt 2012) as an alternative to LWE, for use in cryptographic situations which require determinism. The only method we currently have for proving hardness of LWR is the so-called "rounding reduction" which is a specific reduction from an analogous LWE problem. This reduction works whenever the LWE error is small relative to the noise introduced by rounding, but it fails otherwise. For this reason, all prior work on establishing hardness of LWR forces the LWE error to be small, either by setting other parameters extremely large (which hurts performance), or by limiting the number of LWR samples seen by the adversary (which rules out certain applications). Hardness of LWR is poorly understood when the LWE modulus ($q$) is polynomial and when the number of LWE samples ($m$) seen by the adversary is an unbounded polynomial. This range of parameters is the most relevant for practical implementations, so the lack of a hardness proof in this situation is not ideal. In this work, we identify an obstacle for proving the hardness of LWR via a reduction from LWE in the above parameter regime. Specifically, we show that any "point-wise" reduction from LWE to LWR can be used to directly break the corresponding LWE problem. A reduction is "point-wise" if it maps LWE samples to LWR samples one at a time. Our argument goes roughly as follows: first we show that any point-wise reduction from LWE to LWR must have good agreement with some affine map; then we use a Goldreich-Levin-type theorem to extract the LWE secret given oracle access to a point-wise reduction with good affine agreement. Both components may be of independent interest.

The lattice-based cryptography is considered a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possess a time-consuming operation of polynomial multiplication. As it is relatively the highest time-consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In this paper, we focus on and develop a radix-3 NTT polynomial multiplication and compute its computational complexity. In addition, utilizing the ring structure, we propose two parameter sets of CRYSTALS-KYBER, one of the four round-three finalists in the NIST Post-Quantum Competition.

In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on AES-192 with $2^{124}$ time, $2^{124}$ data, and $2^{79.8}$ memory complexities, which is better than the one presented by Biryukov and Khovratovich at ASIACRYPT 2009 with complexities $2^{176}/2^{123}/2^{152}$ respectively. This represents a huge improvement for the time and memory complexity, illustrating the power of MILP in cryptanalysis.

The code-based post-quantum algorithm Hamming Quasi-Cyclic (HQC) is a fourth round candidate in the NIST standardization project. Since their third round version the authors utilize a new combination of error correcting codes, namely a combination of a Reed-Muller and a Reed-Solomon code, which requires an adaption of published attacks. We identify that the power side-channel attack by Uneo et al. from CHES 2021 does not work in practice as they miss the fact that the implemented Reed-Muller decoder does not have a fixed decoding boundary. In this work we provide a novel attack strategy that again allows for a successful attack. Our attack does not rely on simulation to verify its success but is proven with high probability for the HQC parameter sets. In contrast to the timing side-channel attack by Guo et al. we are able to reduce the required attack queries by a factor of 12 and are able to eliminate the inherent uncertainty of their used timing oracle. We show practical attack results utilizing a power side-channel of the used Reed-Solomon decoder on an ARM Cortex-M4 microcontroller. In addition, we provide a discussion on how or whether our attack strategy is usable with the side-channel targets of mentioned related work. Finally, we use information set decoding to evaluate the remaining attack complexity for partially retrieved secret keys. This work again emphasizes the need for a side-channel secure implementation of all relevant building blocks of HQC.

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance vary from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we investigate the rectangle key recovery in depth and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Notably, it not only covers the four previous rectangle key recovery algorithms, but also unveils five types of new attacks which were missed previously. Along with the new key recovery algorithm, we propose a framework for automatically finding the best attacking parameters, with which the time complexity of the rectangle attack will be minimized using the new algorithm. To demonstrate the efficiency of the new key recovery algorithm, we apply it to Serpent, CRAFT, SKINNY and Deoxys-BC-256 based on existing distinguishers and obtain a series of improved rectangle attacks.

Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can efficiently complete key negotiation while ensuring key correctness and security. SER exploits the properties of the approximate secret values σ1 and σ2 shared by the two parties, and simultaneously reconciles the most and least significant bits of the secret value, and a two-bit key can be obtained by one coordination. By sharing g-bit auxiliary information between two entities, SER expands the fault tolerance interval during reconciliation and improves the success rate of consensus. To test the actual performance of SER, we integrate it into key ex- change protocols based on LWE, RLWE, and MLWE, such as Frodo and NewHope. By comparing parameters such as failure rate, security strength, and the number of CPU rounds, we find that SER performs well in various modes, especially in RLWE-based protocol. Since SER doubles the error to reconcile the least significant bit, which in turn leads to a relatively large error in SER; while the RLWE-based key ex- change scheme adopts a polynomial ring and selects a large parameter q, which is very suitable for SER. Compared with Frodo and NewHope, SER improves the reconciliation efficiency of the per-bit key by 61.6% and 797.6%, respectively.

Today, our society produces massive amounts of data, part of which are strictly private. So, a long line of research has worked to design protocols that perform functions on such private data without revealing them. One function that has attracted significant interest is a multi-party private set operation, where each party's input is a set. The parties commonly intend to compute these sets' collective intersection (MPSI) or union (MPSU), which finds uses in various applications, including private scheduling and threat intelligence. Most current protocols use integer-based homomorphic encryption, with large elements and expensive operations, or oblivious transfers, which require communicationally-expensive pairwise interactions between all parties. Thus, existing solutions introduce significant overhead that hinders practical use. This paper considers a certain class of previously-proposed MPSI and MPSU protocols. We propose to express them in terms of new private AND or OR operations among all parties and use elliptic curves to realize these operations efficiently. We achieve a significant performance gain: Firstly, our protocols take only three rounds of communication. Secondly, our constant-time open-source implementation is two orders of magnitude faster than the state-of-the-art MPSI for small universes and outperforms the state-of-the-art MPSI for large universes for three parties or more.

In this paper, we focus on constructing an automatic search model that greatly improves efficiency with little loss of accuracy and obtains some better results in the construction of integral distinguishers for block ciphers. First, we define a new notion named BDPT Trail, which divides BDPT propagation into three parts: the division trail for K, division trail for L, and Key-Xor operation. Secondly, we improve the insufficiency of the previous methods of calculating division trails and propose an effective algorithm that can obtain more valid division trails for L of the S-box operation. Third, we propose a new algorithm that models each Key-Xor operation based on the MILP technique for the first time. Based on this, we can accurately characterize the Key-Xor operation by solving these MILP models. After that, by selecting the appropriate initial BDPT and stopping rules, we construct an automatic search model. As a result, our automatic search model is applied to search for integral distinguishers for some block ciphers. For GIFT-64, we find a 11-round integral distinguisher, which is one more round than the previous best results. For Rectangle, we find a better $10$-round integral distinguisher with 9 balanced bits, which has eight more bits than the previous best results. For Simon64, we can find more balanced bits than the previous longest distinguishers.

The fair exchange problem has faced for a long time the bottleneck of a required trusted third party. The recent development of blockchains introduces a new type of party to this problem, whose trustworthiness relies on a public ledger and distributed computation. The challenge in this setting is to reconcile the minimalistic and public nature of blockchains with elaborate fair exchange requirements, from functionality to privacy. Zero-knowledge contingent payments (ZKCP) are a class of protocols that are promising in this direction, allowing the fair exchange of data for payment. We propose a new ZKCP protocol that, when compared to others, requires less computation from the blockchain and less interaction between parties. The protocol is based on two-party (weak) adaptor signatures, which we show how to instantiate from state of the art multiparty signing protocols. We improve the symbolic definition of ZKCP security and, for automated verification with Tamarin, we propose a general security reduction from the theory of abelian groups to the theory of exclusive or.

In this paper, for the first time, we consider a four-party scenario, where a \textit{customer} holding a smart card wants to authenticate herself to a \textit{server}, which employs a \textit{cloud database} to verify the customer. The customers initially register with the \textit{manager}. The manager outsources the processed registration data to a cloud database. Then, the customer only interacts with the server for authentication purposes. The server employs the help of the cloud database during authentication. In addition to the security of the authentication, privacy is another goal, where the cloud should not learn which customer is interacting with which server. We consider several different threat models and provide secure and efficient generic solutions as well as a post-quantum secure solution.

A Hash Time Lock Contract (HTLC) is a protocol that is commonly used to exchange payments across different blockchains. Using HTLC as a building block for cross blockchain atomic swaps has its drawbacks: The notion of time is handled differently in each blockchain, be it private or public. Additionally, if the swap ends up aborted, the funds are locked in escrow until the safety timeout expires. In this work we formulate a new cryptographic primitive: Attribute Verifiable Timed Commitment which enables to prove that a timed commitment commits to a value which possesses certain attributes. Using our cryptographic primitive, we describe a new cross chain atomic swap protocol that operates without blockchain derived time and unlike the state of the art, all parties can instantly abort the swap without waiting for the safety timeouts to expire. In order to prove in zero knowledge that a secret committed to using a timed commitment has a claimed hash value, we employ the "MPC in the head" technique by Ishai et al. and implement our zero-knowledge proof protocol and evaluate its performance. As part of our techniques, we develop a novel and efficient procedure for integer Lower-Than validation in arithmetic circuits which may be of independent interest.

The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group $\mathbb{G}$ of points of the elliptic curve is more predominant. At $128$-bit security level two curves $BW13-P310$ and $BW19-P286$ with odd embedding degrees $13$ and $19$ suitable for super optimal pairing have been recommended for such pairing based protocols . But a prime embedding degree ($k=13;19$) eliminates some important optimisation for the pairing computation. However The Miller loop length of the superoptimal pairing is the half of that of the optimal ate pairing but involve more exponentiations that affect its efficiency. In this work, we successfully develop methods and construct algorithms to efficiently evaluate and avoid heavy exponentiations that affect the efficiency of the superoptimal pairing. This leads to the definition of new bilinear and non degenerate pairing on $BW13-P310$ and $BW19-P286$ called $x$-superoptimal pairing wchich is about $27.3\%$ and $49\%$ faster than the optimal ate pairing previousely computed on $BW13-P310$ and $BW19-P286$ respectively.

In this paper we revisit the Spectre v1 vulnerability and software-only countermeasures. Specifically, we systematically investigate the performance penalty and security properties of multiple variants of speculative load hardening (SLH). As part of this investigation we implement the “strong SLH” variant by Patrignani and Guarnieri (CCS 2021) as a compiler extension to LLVM. We show that none of the existing variants, including strong SLH, is able to protect against all Spectre v1 attacks in practice. We do this by demonstrating, for the first time, that variable-time arithmetic instructions leak secret information even if they are executed only speculatively. We extend strong SLH to include protections also against this kind of leakage, implement the resulting full protection in LLVM, and use the SPEC2017 benchmarks to compare its performance to the existing variants of SLH and to code that uses fencing instructions to completely prevent speculative execution. We show that our proposed countermeasure offers full protection against Spectre v1 attacks at much better performance than code using fences. In fact, for several benchmarks our approach is more than twice as fast.

This work introduces MicroSecAgg, a framework that addresses the intricacies of secure aggregation in the single-server landscape, specifically tailored to situations where distributed trust among multiple non-colluding servers presents challenges. Our protocols are purpose-built to handle situations featuring multiple successive aggregation phases among a dynamic pool of clients who can drop out during the aggregation. Our different protocols thrive in three distinct cases: firstly, secure aggregation within a small input domain; secondly, secure aggregation within a large input domain; and finally, facilitating federated learning for the cases where moderately sized models are considered. Compared to the prior works of Bonawitz et al. (CCS 2017), Bell et al. (CCS 2020), and the recent work of Ma et al. (S&P 2023), our approach significantly reduces the overheads. In particular, MicroSecAgg halves the round complexity to just 3 rounds, thereby offering substantial improvements in communication cost efficiency. Notably, it outperforms Ma et al. by a factor of n on the user side, where n represents the number of users. Furthermore, in MicroSecAgg the computation complexity of each aggregation per user exhibits a logarithmic growth with respect to $n$, contrasting with the linearithmic or quadratic growth observed in Ma et al. and Bonawitz et al., respectively. We also require linear (in n) computation work from the server as opposed to quadratic in Bonawitz et al., or linearithmic in Ma et al. and Bell et al. In the realm of federated learning, a delicate tradeoff comes into play: our protocols shine brighter as the number of participating parties increases, yet they exhibit diminishing computational efficiency as the sheer volume of weights/parameters increases significantly. We report an implementation of our system and compare the performance against prior works, demonstrating that MicroSecAgg significantly reduces the computational burden and the message size.

We study the problem of private set union in the two-party setting, providing several new constructions. We consider the case where one party is designated to receive output. In the semi-honest setting, we provide a four-round protocol and two-round protocol, each with two variants. Our four-round protocol focusing on runtime out-performs the state-of-the-art in runtime for the majority of the medium bandwidth settings ($100$Mbps) and the large set size ($\geq 2^{20}$) settings, with a runtime that is 1.04X-1.25X faster than existing protocols. Our other four-round variant focusing on communication outperforms the state-of-the-art in communication by up to a factor of 1.43 when the set size $\geq 2^{18}$. On the other hand, our two-round protocol is only slightly more expensive but has the property that the receiver message can be re-used across multiple executions. All our semi-honest protocols are post-quantum secure if post-quantum primitives (OKVS and OT) are used. In the setting where the sender is malicious, we provide the first protocols that avoid using expensive zero-knowledge proofs. Our four-round protocol costs less than double in both communication and computation compared to all other semi-honest constructions, showcasing great efficiency. As in the semi-honest setting, we also give a more expensive protocol that allows the receiver message to be re-used. Our work draws on several techniques from the literature on private set intersection and helps clarify how these techniques generalize (and don't generalize) to the problem of private set union.

Learning parity with noise (LPN) has been widely studied and used in cryptography. It was recently brought to new prosperity since Boyle et al. (CCS'18), putting LPN to a central role in designing secure multi-party computation, zero-knowledge proofs, private set intersection, and many other protocols. In this paper, we thoroughly studied the security of LPN problems in this particular context. We found that some important aspects have long been ignored and many conclusions from classical LPN cryptanalysis do not apply to this new setting, due to the low noise rates, extremely high dimensions, various types (in addition to $\mathbb{F}_2$) and noise distributions. 1. For LPN over a field, we give a parameterized reduction from exact-noise LPN to regular-noise LPN. Compared to the recent result by Feneuil, Joux and Rivain (Crypto'22), we significantly reduce the security loss by paying only a small additive price in dimension and number of samples. 2. We analyze the security of LPN over a ring $\mathbb{Z}_{2^\lambda}$. Existing protocols based on LPN over integer rings use parameters as if they are over fields, but we found an attack that effectively reduces the weight of a noise by half compared to LPN over fields. Consequently, prior works that use LPN over $\mathbb{Z}_{2^\lambda}$ overestimate up to 40 bits of security. 3. We provide a complete picture of the hardness of LPN over integer rings by showing: 1) the equivalence between its search and decisional versions; 2) an efficient reduction from LPN over $\mathbb{F}_2$ to LPN over $\mathbb{Z}_{2^\lambda}$; and 3) generalization of our results to any integer ring. Finally, we provide an all-in-one estimator tool for the bit security of LPN parameters in the context of PCG, incorporating the recent advanced attacks.

We present a new abstraction based on crusader agreement called $\textit{Binding Crusader Agreement}$ (BCA) for solving binary consensus in the $\textit{asynchronous}$ setting against an $\textit{adaptive}$ adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called $\textit{binding}$. Binding states that before the first non-faulty party terminates, there is a value $v \in \{0,1\}$ such that no non-faulty party can output the value $v$ in any continuation of the execution. We believe that reasoning about binding explicitly, as a first order goal, greatly helps algorithm design, clarity, and analysis. Using our framework, we solve several versions of asynchronous binary agreement against an adaptive adversary in a simple and modular manner that either improves or matches the efficiency of state of the art solutions. We do this via new BCA protocols, given a strong common coin, and via new Graded BCA protocols given an $\epsilon$-good common coin. For crash failures, we reduce the expected time to terminate and we provide termination bounds that are linear in the goodness of the common coin. For Byzantine failures, we improve the expected time to terminate in the computational setting with threshold signatures, and match the state of the art in the information theoretic setting, both with a strong common coin and with an $\epsilon$-good common coin.

The LESS signature scheme, introduced in 2020, represented a fresh start for code-based signatures. In this paper we explore advanced functionalities for signature schemes, stemming from the work of LESS. First, we adapt a recent protocol of Beullens et al. to obtain a construction for (linkable) ring signatures. Then, we realize an identity-based signature scheme following the traditional approach by Joye and Neven. Our performance numbers confirm that signature schemes based on the code equivalence problem have considerable potential for practical applications.

In this article, we generalize the works of Pan et al. (Eurocrypt’21) and Porter et al. (ArXiv’21) and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we generalize it to any ideal (whose prime factors are not ramified) of any number field. We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time. As a proof of concept, we implemented our attack and managed to solve those particular instances for concrete parameter settings proposed in the literature. For random instances, we can halve the lattice dimension with non-negligible probability.

The Multivariate Quadratic ($\mathcal{MQ}$) problem consists in finding the solutions of a given system of $m$ quadratic equations in $n$ unknowns over a finite field, and it is an NP-complete problem of fundamental importance in computer science. In particular, the security of some cryptosystems against the so-called algebraic attacks is usually given by the hardness of this problem. Many algorithms to solve the $\mathcal{MQ}$ problem have been proposed and studied. Estimating precisely the complexity of all these algorithms is crucial to set secure parameters for a cryptosystem. This work collects and presents the most important classical algorithms and the estimates of their computational complexities. Moreover, it describes a software that we wrote and that makes possible to estimate the hardness of a given instance of the $\mathcal{MQ}$ problem.

Physical side-channel analysis poses a huge threat to post-quantum cryptographic schemes implemented on embedded devices. Still, secure implementations are missing for many schemes. In this paper, we present an efficient solution for masked polynomial inversion, a main component of the key generation of multiple post-quantum KEMs. For this, we introduce a polynomial-multiplicative masking scheme with efficient arbitrary order conversions from and to additive masking. Furthermore, we show how to integrate polynomial inversion and multiplication into the masking schemes to reduce costs considerably. We demonstrate the performance of our algorithms for two different post-quantum cryptographic schemes on the Cortex-M4. For NTRU, we measure an overhead of 35% for the first-order masked inversion compared to the unmasked inversion while for BIKE the overhead is as little as 11%. Lastly, we verify the security of our algorithms for the first masking order by measuring and performing a TVLA based side-channel analysis.

Fully Homomorphic Encryption (FHE) is a groundbreaking technology that allows for arbitrary computations to be performed on encrypted data. State-of-the-art schemes such as Brakerski Gentry Vaikuntanathan (BGV) are based on the Learning with Errors over rings (RLWE) assumption, and each ciphertext has an associated error that grows with each homomorphic operation. For correctness, the error needs to stay below a certain threshold, requiring a trade-off between security and error margin for computations in the parameters. Choosing the parameters accordingly, for example, the polynomial degree or the ciphertext modulus, is challenging and requires expert knowledge specific to each scheme. In this work, we improve the parameter generation process across all steps of its process. We provide a comprehensive analysis for BGV in the Double Chinese Remainder Theorem (DCRT) representation providing more accurate and better bounds than previous work on the DCRT, and empirically derive a closed formula linking the security level, the polynomial degree, and the ciphertext modulus. Additionally, we introduce new circuit models and combine our theoretical work in an easy-to-use parameter generator for researchers and practitioners interested in using BGV for secure computation. Our formula results in better security estimates than previous closed formulas, while our DCRT analysis results in reduced prime sizes of up to 42% compared to previous work.