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 introduces an overhead factor of $(\pi/2)^\ell$ in the complexity (for $\ell$ layers). 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 a generic complexity formula that improves the state-of-the-art both for concrete instantiations and in the asymptotic setting. For concrete instances, we show that numerical optimizations enable further improvements over this formula, which results in a further decrease in the gap to an exact quadratic speedup. We demonstrate our framework with applications in cryptanalysis and improve the complexity 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 authentication and coercion-resistant properties of government elections do not apply, a prime example being social media platforms. These systems are often iterative and have no trusted authority, in contrast to the centrally organised, single-shot elections on which most of the literature is focused. Moreover, they require a continuous flow of aggregation to take place and become available even as input is still collected from the participants which is in contrast to "fairness" in classical elections where partial results should never be revealed. In this work, we explore opinion aggregation in a decentralised, iterative setting by proposing a novel protocol in which randomly-chosen participants take turns to act in an incentive-driven manner as decryption authorities. Our construction provides public verifiability, robust vote privacy and liveness guarantees, while striving to minimise the resources each participant needs to contribute.

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 exponential speedups when the attacker is allowed to issue superposition queries. Our results do not constitute a quantum break of the Milenage algorithms, but they do show that Milenage suffers from structural weaknesses making it susceptible to quantum attacks.

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.

Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then “open” some of its positions efficiently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic. In this work, we examine the demands on the properties that an ideal vector commitment should satisfy in the light of the emerging plethora of practical applications and propose new constructions that improve the state-of-the-art in several dimensions and offer new tradeoffs. We also propose a unifying framework that captures several constructions and show how to generically achieve some properties from more basic ones. On the practical side, we focus on building efficient schemes that do not require new trusted setup (we can reuse existing ceremonies for pairing-based “powers of tau” run by real-world systems such as ZCash or Filecoin). Our (in-progress) implementation demonstrates that our work over-performs in efficiency prior schemes with same properties.

In theory, Fully Homomorphic Encryption schemes allow users to compute any operation over encrypted data. However in practice, one of the major difficulties lies into determining secure cryptographic parameters that minimize the computational cost of evaluating a circuit. In this paper, we propose a solution to solve this open problem. Even though it mainly focuses on TFHE, the method is generic enough to be adapted to all the current FHE schemes. TFHE is particularly suited, for small precision messages, from Boolean to 5-bit integers. It is possible to instantiate bigger integers with this scheme, however the computational cost quickly becomes unpractical. By studying the parameter optimization problem for TFHE, we observed that if one wants to evaluate operations on larger integers, the best way to do it is by encrypting the message into several ciphertexts, instead of considering bigger parameters for a single ciphertext. In the literature, one can find some constructions going in that direction, which are mainly based on radix and CRT representations of the message. However, they still present some limitations, such as inefficient algorithms to evaluate generic homomorphic lookup tables and no solution to work with arbitrary modulus for the message space. We overcome these limitations by proposing two new ways to evaluate homomorphic modular reductions for any modulo in the radix approach, by introducing on the one hand a new hybrid representation, and on the other hand by exploiting a new efficient algorithm to evaluate generic lookup tables on several ciphertexts. The latter is not only a programmable bootstrapping but does not require any padding bit, as needed in the original TFHE bootstrapping. We additionally provide benchmarks to support our results in practice. Finally, we formalize the parameter selection as an optimization problem, and we introduce a framework based on it enabling easy and efficient translation of an arithmetic circuit into an FHE graph of operation along with its optimal set of cryptographic parameters. This framework offers a plethora of features: fair comparisons between FHE operators, study of contexts that are favorable to a given FHE strategy/algorithm, failure probability selection for the entire use case, and so on.

Certificate authorities in public key infrastructures typically require entities to prove possession of the secret key corresponding to the public key they want certified. While this is straightforward for digital signature schemes, the most efficient solution for public key encryption and key encapsulation mechanisms (KEMs) requires an interactive challenge-response protocol, requiring a departure from current issuance processes. In this work we investigate how to non-interactively prove possession of a KEM secret key, specifically for lattice-based KEMs, motivated by the recently proposed KEMTLS protocol which replaces signature-based authentication in TLS 1.3 with KEM-based authentication. Although there are various zero-knowledge (ZK) techniques that can be used to prove possession of a lattice key, they yield large proofs or are inefficient to generate. We propose a technique called verifiable generation, in which a proof of possession is generated at the same time as the key itself is generated. Our technique is inspired by the Picnic signature scheme and uses the multi-party-computation-in-the-head (MPCitH) paradigm; this similarity to a signature scheme allows us to bind attribute data to the proof of possession, as required by certificate issuance protocols. We show how to instantiate this approach for two lattice-based KEMs in Round 3 of the NIST post-quantum cryptography standardization project, Kyber and FrodoKEM, and achieve reasonable proof sizes and performance. Our proofs of possession are faster and an order of magnitude smaller than the previous best MPCitH technique for knowledge of a lattice key, and in size-optimized cases can be comparable to even state-of-the-art direct lattice-based ZK proofs for Kyber. Our approach relies on a new result showing the uniqueness of Kyber and FrodoKEM secret keys, even if the requirement that all secret key components are small is partially relaxed, which may be of independent interest for improving efficiency of zero-knowledge proofs for other lattice-based statements.

We introduce a new efficient, transparent setup, polynomial commitment scheme that runs on efficient groups with logarithmic verifier and communication costs. Existing group based polynomial commitment schemes must run on costly groups such as class groups with unknown order or pairing based groups to achieve transparency (no trusted setup), making them slow in practice, and non-group based schemes such as Reed-Soloman based schemes has its own set of pros and cons compared to group based schemes. We offer the first group based polynomial commitment scheme that does not rely on expensive pairing based groups or class groups with unknown order to achieve transparency while still providing logarithmic verifier and communication costs. While the asymptotic performance of our protocol is comparable to the current state of art, its concrete verifier and communication costs are about one order of magnitude more efficient than the current state of art schemes. The asymptotic costs of our new transparent scheme is dominated by $3n \,\mathbb{G}$ exponential prover cost, 3 log $n \, \mathbb{G}$ exponential verifier cost and 3 log $n \, \mathbb{G}$ communication cost. Running with one thread and evaluating a polynomial of $n=2^{20}$ degree terms, the verifier cost of our protocol is $\approx 2.5 ms$, and the communication cost is $\approx 2 KB$, giving approximately 11X and 9X improvement over the current state of art.

The boomerang attack is a cryptanalysis technique that combines two short differentials instead of using a single long differential. It has been applied to many primitives, and results in the best known attacks against several AES-based ciphers (Kiasu-BC, Deoxys-BC). In this paper, we introduce a general framework for boomerang attacks with truncated differentials. While the underlying ideas are already known, we show that a careful analysis provides a significant improvement over the best boomerang attacks in the literature. In particular, we take into account structures on the plaintext and ciphertext sides, and include an analysis of the key recovery step. On 6-round AES, we obtain a structural distinguisher with complexity $2^{87}$ and a key recovery attack with complexity $2^{61}$. The truncated boomerang attacks is particularly effective against tweakable AES variants. We apply it to 8-round Kiasu-BC, resulting in the best known attack with complexity $2^{83}$ (rather than $2^{103}$). We also show an interesting use of the 6-round distinguisher on TNT-AES, a tweakable block-cipher using 6-round AES as a building block. Finally, we apply this framework to Deoxys-BC, using a MILP model to find optimal trails automatically. We obtain the best attacks against round-reduced versions of all variants of Deoxys-BC.

Atomic Swaps enable exchanging crypto-assets without trusting a third party. To enable these swaps, both parties lock funds and let their counterparty withdraw them in exchange for a secret. This leads to the so-called griefing attack, or the emergence of an American Call option, where one party stops participating in the swap, thereby making their counterparty wait for a timelock to expire before they can withdraw their funds. The standard way to mitigate this attack is to make the attacker pay a premium for the emerging American Call option. In these premium-paying approaches, the premium itself ends up being locked for possibly an even longer duration than the swap amount itself. We propose a new Atomic Swap construction, where neither party exposes itself to a griefing attack by their counterparty. Notably, unlike previous constructions, ours can be implemented in Bitcoin as is. Our construction also takes fewer on-chain transactions and has a lower worst-case timelock.

The OCB mode of operation for block ciphers has three variants, OCB1, OCB2 and OCB3. OCB1 and OCB3 can be used as secure authenticated encryption schemes whereas OCB2 has been shown to be classically insecure (Inoue et al., Crypto 2019). Even further, in the presence of quantum queries to the encryption functionality, a series of works by Kaplan et al. (Crypto 2016), Bhaumik et al. (Asiacrypt 2021) and Bonnetain et al. (Asiacrypt 2021) have shown how to break the existential unforgeability of the OCB modes. However, these works did not consider the confidentiality of OCB in the presence of quantum queries. We fill this gap by presenting the first formal analysis of the IND-qCPA security of OCB. In particular, we show the first attacks breaking the IND-qCPA security of the OCB modes. Surprisingly, we are able to prove that OCB2 is IND-qCPA secure when used without associated data, while relying on the assumption that the underlying block cipher is a quantum-secure pseudorandom permutation. Additionally, we present new quantum attacks breaking the universal unforgeability of OCB. Our analysis of OCB has implications for the post-quantum security of XTS, a well-known disk encryption standard, that was considered but mostly left open by Anand et al. (PQCrypto 2016).

Protocols for state machine replication (SMR) are typically designed for synchronous or asynchronous networks, with a lower corruption threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or an asynchronous network. We propose two new constructions of network-agnostic SMR protocols that improve on existing protocols in terms of either the adversarial model or communication complexity: 1. an adaptively secure protocol with optimal corruption thresholds and quadratic amortized communication complexity per transaction; 2. a statically secure protocol with near-optimal corruption thresholds and linear amortized communication complexity per transaction. We further explore SMR protocols run in a network that may change between synchronous and asynchronous arbitrarily often; parties can be uncorrupted (as in the proactive model), and the protocol should remain secure as long as the appropriate corruption thresholds are maintained. We show that purely asynchronous proactive secret sharing is impossible without some form of synchronization between the parties, ruling out a natural approach to proactively secure network-agnostic SMR protocols. Motivated by this negative result, we consider a model where the adversary is limited in the total number of parties it can corrupt over the duration of the protocol and show, in this setting, that our SMR protocols remain secure even under arbitrarily changing network conditions.

Incompressible encryption, recently proposed by Guan, Wichs and Zhandry (EUROCRYPT'22), is a novel encryption paradigm geared towards providing strong long-term security guarantees against adversaries with bounded long-term memory. Given that the adversary forgets just a small fraction of a ciphertext, this notion provides strong security for the message encrypted therein, even if, at some point in the future, the entire secret key is exposed. This comes at the price of having potentially very large ciphertexts. Thus, an important efficiency measure for incompressible encryption is the message-to-ciphertext ratio (also called the rate). Guan et al. provided a low-rate instantiation of this notion from standard assumptions and a rate-1 instantiation from indistinguishability obfuscation (iO). In this work, we propose a simple framework to build rate-1 incompressible encryption from standard assumptions. Our construction can be realized from, e.g. the DDH and additionally the DCR or the LWE assumptions.

Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, algebraic constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known. In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize. Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.

This work presents new advances in algebraic cryptanalysis of small scale derivatives of AES. We model the cipher as a system of polynomial equations over GF(2), which involves only the variables of the initial key, and we subsequently attempt to solve this system using Gröbner bases. We show, for example, that one of the attacks can recover the secret key for one round of AES-128 under one minute on a contemporary CPU. This attack requires only two known plaintexts and their corresponding ciphertexts. We also compare the performance of Gröbner bases to a SAT solver, and provide an insight into the propagation of diffusion within the cipher.

The focus of this work are multi-signatures schemes in the synchronized setting. A multi-signature scheme allows multiple signatures for the same message but from independent signers to be compressed into one short aggregated signature, which allows verifying all of the signatures simultaneously. In the synchronized setting, the signing algorithm takes the current time step as an additional input. It is assumed that no signer signs more than one message per time step and we aim to aggregate signatures for the same message and same time step. This setting is particularly useful in the context of blockchains, where validators are naturally synchronized by the blocks they sign. We present Squirrel, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that works for a bounded number of $2^{\tau}$ time steps and allows for aggregating up to $\rho$ signatures at each step, where both $\tau$ and $\rho$ are public parameters upon which the efficiency of our scheme depends. Squirrel allows for non-interactive aggregation of independent signatures and is proven secure in the random oracle model in the presence of rogue-key attacks assuming the hardness of the short integer solution problem in a polynomial ring. We provide a careful analysis of all parameters and show that Squirrel can be instantiated with good concrete efficiency. For $\tau = 24$ and $\rho = 4096$, a signer could sign a new message every 10 seconds for 5 years non-stop. Assuming the signer has a cache of 112 MB, signing takes 68 ms and verification of an aggregated signature takes 36 ms. The size of the public key is 1 KB, the size of an individual signature is 52 KB, and the size of an aggregated signature is 771 KB.

A theoretical framework of the bit security of cryptographic primitives/games was first introduced in a pioneering work by Micciancio and Walter (Eurocrypt 2018), and an alternative framework was introduced by the authors (Asiacrypt 2021). First, we observe that quantitative results in the latter framework are preserved even if adversaries are allowed to output the failure symbol. With this slight modification, we show that the notion of bit security in the latter framework is equivalent to that in the former framework up to constant bits. Also, we demonstrate that several existing notions of advantages can be captured in a unified way. Based on this equivalence, we show that the reduction algorithm of Hast (J. Cryptology, 2004) gives a tight reduction of the Goldreich-Levin hard-core predicate to the hardness of one-way functions. These two results resolved open problems that remained. Furthermore, in the latter framework, we show that all games we need to care about are decision games. Namely, for every search game G, there is the corresponding decision game G′ such that G has λ-bit security if and only if G′ has λ-bit security. The game G′ consists of the real and the ideal games, where attacks in the ideal game are never approved. Such games often appear in game-hopping security proofs. The result justifies such security proofs because they lose no security. Finally, we provide a distribution replacement theorem. Suppose a game using distribution Q in a black-box manner is λ-bit secure, and two distributions P and Q are computationally λ-bit secure indistinguishable. In that case, the game where Q is replaced by P is also λ-bit secure.

We propose a new Diffie-Hellman-like Non-Interactive Key Exchange that uses the Lattice Isomorphisms as a building block. Our proposal also relies on a group action structure, implying a similar security setup as in the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) protocol where Kuperberg's algorithm applies. We short label our scheme as LIKE. As with the original Diffie-Hellman protocol, our proposed scheme is also passively secure. We provide a proof-of-concept constant-time C-code implementation of LIKE, and conservatively propose LIKE-1, LIKE-3, and LIKE-5 instances with equivalent asymptotic Kuperberg's algorithm complexity than CSIDH-4096, CSIDH-6144, and CSIDH-8192. Our experiments illustrate that LIKE-1 is about 3.8x faster than CTIDH-512 (the current fastest variant of CSIDH-512), and it is about 641.271x faster than CSIDH-4096 when deriving shared keys (while LIKE-1 key generation is about 2.16x faster than CSIDH-4096); oppositely, LIKE-1 public keys are 32.25x larger than CSIDH-4096.

Privacy and security challenges due to the outsourcing of data storage and processing to third-party cloud providers are well known. With regard to data privacy, Oblivious RAM (ORAM) schemes provide strong privacy guarantees by not only hiding the contents of the data (by encryption) but also obfuscating the access patterns of the outsourced data. But most existing ORAM datastores are not fault tolerant in that if the external storage server (which stores encrypted data) or the trusted proxy (which stores the encryption key and other meta- data) crashes, an application loses all of its data. To achieve fault-tolerance, we propose QuORAM, the first ORAM datastore to replicate data with a quorum-based replication protocol. QuORAM’s contributions are three-fold: (i) it obfuscates access patterns to provide obliviousness guarantees, (ii) it replicates data using a novel lock-free and decentralized replication protocol to achieve fault-tolerance, and (iii) it guarantees linearizable semantics. Experimentally evaluating QuORAM highlights counter-intuitive results: QuORAM in- curs negligible cost to achieve obliviousness when compared to an insecure fault-tolerant replicated system; QuORAM’s peak throughput is 2.4x of its non-replicated baseline; and QuORAM performs 33.2x better in terms of throughput than an ORAM datastore that relies on CockroachDB, an open- source geo-replicated database, for fault tolerance.

We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size $n$. The adversary also operates as a streaming algorithm, but has a much larger memory size $m \gg n$. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In this work, we construct message authentication and signatures in the BSM. First, we consider the symmetric-key setting, where Alice and Bob share a small secret key. Alice can authenticate arbitrarily many messages to Bob by streaming long authentication tags of size $k \gg m$, while ensuring that the tags can be generated and verified using only $n$ bits of memory. We show a solution using local extractors (Vadhan; JoC '04), which allows for up to exponentially large adversarial memory $m = 2^{O(n)}$, and has tags of size $k= O(m)$. Second, we consider the same setting as above, but now additionally require each individual tag to be small, of size $k \leq n$. We show a solution is still possible when the adversary's memory is $m = O(n^2)$, which is optimal. Our solution relies on a space lower bound for leaning parities (Raz; FOCS '16). Third, we consider the public-key signature setting. A signer Alice initially streams a long verification key over an authentic channel, while only keeping a short signing key in her memory. A verifier Bob receives the streamed verification key and generates some short verification digest that he keeps in his memory. Later, Alice can sign arbitrarily many messages using her signing key by streaming the signatures to Bob, who can verify them using his verification digest. We show a solution for $m= O(n^2)$, which we show to be optimal. Our solution relies on a novel entropy lemma, of independent interest. We show that, if a sequence of blocks has sufficiently high min-entropy, then a large fraction of individual blocks must have high min-entropy. Naive versions of this lemma are false, but we show how to patch it to make it hold.

In CRYPTO'21, Shen et al. have proved in the ideal cipher model that $\textsf{Two-Keyed-DbHtS}$ construction is secure up to $2^{2n/3}$ queries in the multi-user setting independent of the number of users, where the underlying double-block hash function $\textsf{H}$ of the \textsf{Two-Keyed-DbHtS} construction is realized as the concatenation of two independent $n$-bit keyed hash functions $(\textsf{H}_{K_h,1}, \textsf{H}_{K_h, 2})$ such that each of the $n$-bit keyed hash function is $O(2^{-n})$ universal and regular. They have also demonstrated the applicability of their result to the key-reduced variants of \textsf{DbHtS} MACs, including \textsf{2K-SUM-ECBC}, $\textsf{2K-PMAC_Plus}$ and $\textsf{2K-LightMAC_Plus}$ without requiring domain separation technique and proved $2n/3$-bit multi-user security of these constructions in the ideal cipher model. Recently, Guo and Wang have invalidated the security claim of Shen et al.'s result by exhibiting three constructions, which are the instantiations of the $\textsf{Two-Keyed-DbHtS}$ framework, such that each of their $n$-bit keyed hash functions being $O(2^{-n})$ universal and regular, while the constructions themselves are secure only up to the birthday bound. In this work, we show a sufficient condition on the underlying Double-block Hash ($\textsf{DbH}$) function, under which we prove $3n/4$-bit multi-user security of the $\textsf{Two-Keyed-DbHtS}$ construction in the ideal-cipher model. As an instantiation, we show that two-keyed Polyhash-based $\textsf{DbHtS}$ construction is multi-user secure up to $2^{3n/4}$ queries in the ideal-cipher model. Furthermore, due to the generic attack on $\textsf{DbHtS}$ constructions by Ga\"etan et al. in CRYPTO'18, our derived bound for the construction is tight.

The LowMC family of block ciphers was first proposed by Albrecht et al. in [ARS+15], specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3-bit S-box as the sole non-linear transformation in the algorithm. In contrast, both the linear layer and round key generation are achieved through multiplications of full rank matrices over GF(2). The cipher is instantiable using a diverse set of default configurations, some of which have partial non-linear layers i.e., in which the S-boxes are not applied over the entire internal state of the cipher. The significance of cryptanalysing LowMC was elevated by its inclusion into the NIST PQC digital signature scheme PICNIC in which a successful key recovery using a single plaintext/ciphertext pair is akin to retrieving the secret signing key. The current state-of-the-art attack in this setting is due to Dinur [Din21a], in which a novel way of enumerating the roots of a Boolean system of equation is morphed into a key recovery procedure that undercuts an ordinary exhaustive search in terms of time complexity for the variants of the cipher up to five rounds. In this work, we demonstrate that this technique can efficiently be enriched with a specific linearization strategy that reduces the algebraic degree of the non-linear layer as put forward by Banik et al. [BBDV20]. This amalgamation yields a drastic reduction in terms of memory complexity across all instantiations of LowMC up to six rounds with a quasi-equivalent time complexity.

Single Secret Leader Election protocols (SSLE, for short) allow a group of users to select a random leader so that the latter remains secret until she decides to reveal herself. Thanks to this feature, SSLE can be used to build an election mechanism for proof-of-stake based blockchains. In particular, a recent work by Azouvi and Cappelletti (ACM AFT 2021) shows that in comparison to probabilistic leader election methods, SSLE-based proof-of-stake blockchains have significant security gains, both with respect to grinding attacks and with respect to the private attack. Yet, as of today, very few concrete constructions of SSLE are known. In particular, all existing protocols are only secure in a model where the adversary is supposed to corrupt participants before the protocol starts -- an assumption that clashes with the highly dynamic nature of decentralized blockchain protocols. In this paper we make progress in the study of SSLE by proposing new efficient constructions that achieve stronger security guarantees than previous work. In particular, we propose the first SSLE protocol that achieves adaptive security. Our scheme is proven secure in the universal composability model and achieves efficiency comparable to previous, less secure, realizations in the state of the art.

In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1, \ldots, P_{q}) \in (\{0, 1\}^{n})^{q}$ satisfying a system of equations of the form $X_i \oplus X_j = \lambda_{i,j}$ such that $P_1, P_2, \ldots$, $P_{q}$ are pairwise distinct. This result is known as \emph{``$P_i \oplus P_j$ Theorem for any $\xi_{\max}$''} or alternatively as \emph{Mirror Theory for general $\xi_{\max}$}, which was later proved by Patarin in ICISC'05. Mirror theory for general $\xi_{\max}$ stands as a powerful tool to provide a high-security guarantee for many blockcipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps that are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ theorem for a wide range of $\xi_{\max}$, typically up to order $O(2^{n/4}/\sqrt{n})$. Furthermore, our proof approach is made simpler by using a new type of equation, dubbed link-deletion equation, that roughly corresponds to half of the so-called orange equations from earlier works. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and $n$-bit security proof for six round Feistel cipher, and provide updated security bounds.

Timing attack is a class of side-channel attacks that aims to leak secret information based on the time it takes to perform different operations. The biggest advantage of a timing attack is that it does not require sophisticated or expensive equipment to be carried out. Side Channels on FHE schemes have been reported on the client side which has the secret key. But the present project aims to delve into the counter intuitive question, can an analysis be performed on the server end which ideally has no information of the secret key. In this report, we investigate when homomorphic operations are performed on the ciphertexts stored in the server, can timing reveal information of the error used to mask the ciphertexts? Finally, can this be utilized to determine the secret key of the ciphering technique?

In recent years, Bitcoin and Ethereum have emerged as the two largest and most popular blockchain networks. While Bitcoin provides the most secure digital asset, Ethereum provides the smart contract execution platform with the richest application ecosystem. In this paper, we present RSK, a sidechain that extends Bitcoin with Ethereum-compatible and stateful smart contract functionality. RSK's goal is to bring Ethereum's advantages to Bitcoin, allowing Bitcoin users to fully benefit from decentralized finance without having to exchange their bitcoin for other assets or having to renounce Bitcoin's consensus security. As a sidechain, RSK does not define a currency of its own, and thus, RSK does not compete with Bitcoin as store of value. Instead, RSK extends Bitcoin with new capabilities without taking resources from the Bitcoin network. Among other features, RSK provides a highly secure mechanism to transfer bitcoins from Bitcoin and back, and implements a merged mining protocol that provides Bitcoin miners with additional fees without adding significant overhead.

Quantum computing is considered among the next big leaps in computer science. While a fully functional quantum computer is still in the future, there is an ever-growing need to evaluate the security of the symmetric key ciphers against a potent quantum adversary. Keeping this in mind, our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 20 implementations per AES variant (thus totaling in 60), by taking the state-of-the-art advancements in the relevant fields into account. In a nutshell, we present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 86 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in details, fix the bugs (arising from some problem of the quantum computing tool used and not related to their coding) and report corrected benchmarks. To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun and the Asiacrypt'23 paper by Liu et al.) in terms of various quantum circuit complexity metrics (Toffoli depth, full depth, Toffoli/full depth - qubit count product, full depth - gate count product, etc.). Also, our bug-fixing of Jaques et al.'s Eurocrypt'20 implementations seem to improve from the authors' own bug-fixing, thanks to our architecture consideration. Equipped with the basic AES implementations, we further investigate the prospect of the Grover's search. We also propose three new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt’20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, T-depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect, that offers the best performance in terms of metrics for circuit complexity (like, depth-squared - qubit count product, depth - gate count product).

We consider a foundational unsupervised learning task of k-means data clustering, in a federated learning (FL) setting consisting of a central server and many distributed clients. We develop SecFC, which is a secure federated clustering algorithm that simultaneously achieves 1) universal performance: no performance loss compared with clustering over central- ized data, regardless of data distribution across clients; 2) data privacy: each client’s private data and the cluster centers are not leaked to other clients and the server. In SecFC, the clients perform Lagrange encoding on their local data and share the coded data in an information-theoretically private manner; then leveraging the algebraic structure of the coding, the FL network exactly executes the Lloyd’s k-means heuristic over the coded data to obtain the final clustering. Experiment results on synthetic and real datasets demonstrate the universally superior performance of SecFC for different data distributions across clients, and its computational practicality for various combinations of system parameters. Finally, we propose an extension of SecFC to further provide membership privacy for all data points.