Threshold public key encryption (ThPKE) is PKE that can be decrypted by collecting "partial decryptions" from t (≤ N) out of N parties. ThPKE based on the learning with errors problem (LWE) is particularly important because it can be extended to threshold fully homomorphic encryption (ThFHE). ThPKE and ThFHE are fundamental tools for constructing multiparty computation (MPC) protocols: In 2023, NIST initiated a project (NIST IR 8214C) to establish guidelines for implementing threshold cryptosystems. Because MPC often requires simulation-security (SS), ThPKE schemes that satisfy SS (SS-ThPKE) are also important. Recently, Micciancio and Suhl (ePrint 2023/1728) presented an efficient SS-ThPKE scheme based on LWE with a polynomial modulus. However, the scheme requires to use a nonstandard problem called “known-norm LWE” for the security proof because the norm ∥e∥ of the error of the public key is leaked from the partial decryptions. This leads to the following two challenges: 1) The construction based on LWE incurs a security loss of approximately 13 bits for 128-bit security. 2) No construction based on (standard) Ring-LWE has been presented. In this paper, we address both of these challenges: we propose an efficient SS-ThPKE scheme whose security is (directly) reduced from standard (Ring-)LWE with a polynomial modulus. The core technique of our construction is what we call "error sharing". We distribute shares of a small error ζ via secret sharing, and use them to prevent leakage of ∥e∥ from partial decryptions.

CRYSTALS-Dilithium is a post-quantum secure digital signature algorithm currently being standardised by NIST. As a result, devices making use of CRYSTALS-Dilithium will soon become generally available and be deployed in various environments. It is thus important to assess the resistance of CRYSTALS-Dilithum implementations to physical attacks. In this paper, we present an attack on a CRYSTALS-Dilithium implementation in hedged mode in ARM Cortex-M4 using fault injection. Voltage glitching is performed to skip computation of a seed during the generation of the signature. We identified settings that consistently skip the desired function without crashing the device. After the successful fault injection, the resulting signature allows for the extraction of the secret key vector. Our attack succeeds with probability 0.582 in a single trace. We also propose countermeasures against the presented attack.

Users bid in a transaction fee mechanism (TFM) to get their transactions included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated the formal treatment of TFMs and proposed three requirements: user incentive compatibility (UIC), miner incentive compatibility (MIC), and a form of collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism satisfies all three properties simultaneously when there is no contention between transactions, but loses the UIC property when there are too many eligible transactions to fit in a single block. Chung and Shi (SODA'23) considered an alternative notion of collusion-resilience, called c-side-constract-proofness (c-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and c-SCP for any c at least 1. OCA-proofness asserts that the users and a miner should not be able to "steal from the protocol" and is intuitively weaker than the c-SCP condition, which stipulates that a coalition of a miner and a subset of users should not be able to profit through strategic deviations (whether at the expense of the protocol or of the users outside the coalition). Our main result is the first proof that, when there is contention between transactions, no (possibly randomized) direct-revelation TFM satisfies UIC, MIC, and OCA-proofness. This result resolves the main open question in Roughgarden(EC'21). We also suggest several relaxations of the basic model that allow our impossibility result to be circumvented.

We show that key exchange and two-party computation are exactly equivalent to monoid actions with certain structural and hardness properties. To the best of our knowledge, this is the first "natural" characterization of the mathematical structure inherent to any key exchange or two-party computation protocol, and the first explicit proof of the necessity of mathematical structure for public-key cryptography. We then utilize these characterizations to show a new black-box separation result, while also achieving a simpler and more general version of an existing black-box separation result. Concretely, we obtain the following results: - Two-Party Key Exchange. We show that that any two-party noninteractive key exchange protocol is equivalent to the existence of an abelian monoid equipped with a natural hardness property, namely (distributional) unpredictability. More generally, we show that any $k$-round (two-party) key exchange protocol is essentially equivalent to the existence of a (distributional) unpredictable monoid with certain commutator-like properties. We then use a generic version of this primitive to show a simpler and more general version of Rudich's (Crypto '91) black-box separation of $k$-round and $(k+1)$-round key exchange. - Two-Party Computation. We show that any maliciously secure two-party computation protocol is also equivalent to a monoid action with commutator-like properties and certain hardness guarantees. We then use a generic version of this primitive to show a black-box separation between $k$-round semi-honest secure two-party computation and $(k+1)$-round maliciously secure two-party computation. This yields the first black-box separation (to our knowledge) between $k$-round and $(k+1)$-round maliciously secure two-party computation protocols. We believe that modeling cryptographic primitives as mathematical objects (and our approach of using such modeling for black-box separations) may have many other potential applications and uses in understanding what sort of assumptions and mathematical structure are necessary for certain cryptoprimitives.

We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key. We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either $2^{O(\sqrt{n})}$-hardness of LPN, or polynomial hardness of LPN and the planted XOR problem at low density. As our primary application of pseudorandom codes, we present an undetectable watermarking scheme for outputs of language models that is robust to cropping and a constant rate of random substitutions and deletions. The watermark is undetectable in the sense that any number of samples of watermarked text are computationally indistinguishable from text output by the original model. This is the first undetectable watermarking scheme that can tolerate a constant rate of errors. Our second application is to steganography, where a secret message is hidden in innocent-looking content. We present a constant-rate stateless steganography scheme with robustness to a constant rate of substitutions. Ours is the first stateless steganography scheme with provable steganographic security and any robustness to errors.

In the past three decades, an impressive body of knowledge has been built around secure and private password authentication. In particular, secure password-authenticated key exchange (PAKE) protocols require only minimal overhead over a classical Diffie-Hellman key exchange. PAKEs are also known to fulfill strong composable security guarantees that capture many password-specific concerns such as password correlations or password mistyping, to name only a few. However, to enjoy both round-optimality and strong security, applications of PAKE protocols must provide unique session and participant identifiers. If such identifiers are not readily available, they must be agreed upon at the cost of additional communication flows, a fact which has been met with incomprehension among practitioners, and which hindered the adoption of provably secure password authentication in practice. In this work, we resolve this issue by proposing a new paradigm for truly password-only yet securely composable PAKE, called bare PAKE. We formally prove that two prominent PAKE protocols, namely CPace and EKE, can be cast as bare PAKEs and hence do not require pre-agreement of anything else than a password. Our bare PAKE modeling further allows us to investigate a novel "reusability" property of PAKEs, i.e., whether $n^2$ pairwise keys can be exchanged from only $n$ messages, just as the Diffie-Hellman non-interactive key exchange can do in a public-key setting. As a side contribution, this add-on property of bare PAKEs leads us to observe that some previous PAKE constructions relied on unnecessarily strong, "reusable" building blocks. By showing that ``non-reusable'' tools suffice for standard PAKE, we open a new path towards round-optimal post-quantum secure password-authenticated key exchange.

Cayley hash functions are based on a simple idea of using a pair of semigroup elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the semigroup. The main advantage of Cayley hash functions compared to, say, hash functions in the SHA family is that when an already hashed document is amended, one does not have to hash the whole amended document all over again, but rather hash just the amended part and then multiply the result by the hash of the original document. Some authors argued that this may be a security hazard, specifically that this property may facilitate finding a second preimage by splitting a long bit string into shorter pieces. In this paper, we offer a way to get rid of this alleged disadvantage and keep the advantages at the same time. We call this method ``Cayley hashing with cookies" using terminology borrowed from the theory of random walks in a random environment. For the platform semigroup, we use $2\times 2$ matrices over $F_p$.

Nova is a new type of recursive proof system that uses folding scheme as its core building block. This brilliant idea of folding relations can significantly reduce recursion overhead. In this paper, we study some issues related to Nova's soundness proof that relies on the soundness of the folding scheme in a recursive manner. First, its proof strategy, due to its recursive nature, inevitably expands the running time of the recursive extractor polynomially for each additional recursive step. This constrains Nova's soundness model to have only logarithmically bounded recursive steps, and so the soundness proof in this limited model does not guarantee the soundness for linear rounds in the security parameter, e.g., 128 rounds for 128 bit security. On the other hand, there are no known attacks on arbitrary depth recursion of Nova, leaving a gap between theoretical security guarantees and real-world attacks. We aim to bridge this gap in two opposite directions. In a negative direction, we present a recursive proof system that is unforgeable in a log-round model but forgeable if used in linear rounds. This shows that the soundness proof in the log-round model might tell nothing about real-world uses that require linearly long rounds. In a positive direction, we show that when Nova uses a specific group-based folding scheme, its knowledge soundness over polynomial rounds can be proven in the algebraic group model with our refinements. To the best of our knowledge, this is the first result to show Nova's polynomial rounds soundness. Second, the folding scheme is converted non-interactively via the Fiat-Shamir transformation and then arithmetized into R1CS. Therefore, the soundness of Nova using the non-interactive folding scheme essentially relies on the heuristic random oracle instantiation in the standard model. In our new soundness proof for Nova in the algebraic group model, we replace this heuristics with a cryptographic hash function with special property. We view this hash function as an independent object of interest and expect it to help further understand the soundness of Nova.

Functional Encryption (FE) is a cutting-edge cryptographic technique that enables a user with a specific functional decryption key to determine a certain function of encrypted data without gaining access to the underlying data. Given its potential and the fact that FE is still a relatively new field, we set out to investigate how it could be applied to resource-constrained environments. This work presents what we believe to be the first lightweight FE scheme explicitly designed for resource-constrained devices. We also propose a use case protocol that demonstrates how our scheme can secure an Internet of Things (IoT) architecture where relevant devices collect data and securely deliver them to a storage server, where an analyst can request access to the encrypted data. Finally, we conduct thorough experiments on two commercially available resource-constrained devices to provide compelling evidence of our approach's practicality and efficiency. Although the results of our evaluations show that there is room for improvement in the proposed scheme, this work represents one of the first attempts to apply FE to the IoT setting that can directly impact people's daily lives and the everyday operations of organizations.

We analyse Layered ROLLO-I, a code-based cryptosystem submitted to the Korean post quantum cryptography competition, of which four versions have been proposed. We show that the first two versions do not provide the claimed security against rank decoding attacks and give reductions to small instances of ROLLO-I for which such attacks are even more effective. Finally, we provide two efficient message recovery attacks, affecting every security level of the first three versions of Layered ROLLO-I and security levels 128 and 192 of the fourth version.

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by a factor of $k$. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for $S$ possible? Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a non-interactive statistical zero-knowledge proof (NISZK) has a non-trivial statistical zero-knowledge batch verification protocol. Their results had two major limitations: (1) to batch verify $k$ inputs of size $n$ each, the communication in their batch protocol is roughly $\textrm{poly}(n,\log{k})+O(k)$, which is better than the naive cost of $k \cdot \textrm{poly}(n)$ but still scales linearly with $k$, and, (2) the batch protocol requires $\Omega(k)$ rounds of interaction. In this work we remove both of these limitations by showing that any problem in $NISZK$ has a non-interactive statistical zero-knowledge batch verification protocol with communication $\textrm{poly}(n,\log{k})$.

Thus far, several papers estimated concrete quantum resources of Shor’s algorithm for solving a binary elliptic curve discrete logarithm problem. In particular, the complexity of computing quantum inversions over a binary field F2n is dominant when running the algorithm, where n is a degree of a binary elliptic curve. There are two major methods for quantum inversion, i.e., the quantum GCD-based inversion and the quantum FLT-based inversion. Among them, the latter method is known to require more qubits; however, the latter one is valuable since it requires much fewer Toffoli gates and less depth. When n = 571, Kim-Hong’s quantum GCD-based inversion algorithm (Quantum Information Processing 2023) and Taguchi-Takayasu’s quantum FLT-based inversion algorithm (CT-RSA 2023) require 3, 473 qubits and 8, 566 qubits, respectively. In contrast, for the same n = 571, the latter algorithm requires only 2.3% of Toffoli gates and 84% of depth compared to the former one. In this paper, we modify Taguchi-Takayasu’s quantum FLT-based inversion algorithm to reduce the required qubits. While Taguchi-Takayasu’s FLT-based inversion algorithm takes an addition chain for n−1 as input and computes a sequence whose number is the same as the length of the chain, our proposed algorithm employs an uncomputation step and stores a shorter one. As a result, our proposed algorithm requires only 3, 998 qubits for n = 571, which is only 15% more than Kim-Hong’s GCD-based inversion algorithm. Furthermore, our proposed algorithm preserves the advantage of FLT-based inversion since it requires only 3.7% of Toffoli gates and 77% of depth compared to Kim-Hong’s GCD-based inversion algorithm for n = 571.

We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class $\mathsf{UP}$ in the reusable designated verifier model. $\mathsf{UP}$ is an expressive subclass of $\mathsf{NP}$ consisting of all $\mathsf{NP}$ languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm. Our main results are as follows. (1) A reusably and adaptively sound zero-knowledge (zk) dvSNARG for $\mathsf{UP}$, from subexponential LWE and evasive LWE (a relatively new but popular variant of LWE). Our SNARGs achieve very short proofs of length $(1 + o(1)) \cdot \lambda$ bits for $2^{-\lambda}$ soundness error. (2) A generic transformation that lifts any ``Sahai-Waters-like'' (zk) SNARG to an adaptively sound (zk) SNARG, in the designated-verifier setting. In particular, this shows that the Sahai-Waters SNARG for $\mathsf{NP}$ is adaptively sound in the designated verifier setting, assuming subexponential hardness of the underlying assumptions. The resulting SNARG proofs have length $(1 + o(1)) \cdot \lambda$ bits for $2^{-\lambda}$ soundness error. Our result sidesteps the Gentry-Wichs barrier for adaptive soundness by employing an exponential-time security reduction. (3) A generic transformation, building on the work of Campanelli, Ganesh, that lifts any adaptively sound (zk) SNARG for $\mathsf{UP}$ to an adaptively sound (zk) SNARK for $\mathsf{UP}$, while preserving zero-knowledge. The resulting SNARK achieves the strong notion of black-box extraction. There are barriers to achieving such SNARKs for all of $\mathsf{NP}$ from falsifiable assumptions, so our restriction to $\mathsf{UP}$ is, in a sense, necessary. Applying (3) to our SNARG for $\mathsf{UP}$ from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for $\mathsf{UP}$ from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size $\mathsf{poly}(\lambda)$. These are the first SNARK constructions (even in the designated-verifier setting) for a non-trivial subset of $\mathsf{NP}$ from (sub-exponentially) falsifiable assumptions.

Keyed homomorphic public key encryption (KHPKE) is a variant of homomorphic public key encryption, where only users who have a homomorphic evaluation key can perform a homomorphic evaluation. Then, KHPKE satisfies the CCA2 security against users who do not have a homomorphic evaluation key, while it satisfies the CCA1 security against users who have the key. Thus far, several KHPKE schemes have been proposed under the standard Diffie-Hellman-type assumptions and keyed fully homomorphic encryption (KFHE) schemes have also been proposed from lattices although there are no KFHE schemes secure solely under the LWE assumption in the standard model. As a natural extension, there is an identity-based variant of KHPKE; however, the security is based on a $q$-type assumption and there are no attribute-based variants. Moreover, there are no identity-based variants of KFHE schemes due to the complex design of the known KFHE schemes. In this paper, we provide two constructions of attribute-based variants. First, we propose an attribute-based KFHE (ABKFHE) scheme from lattices. We start by designing the first KFHE scheme secure solely under the LWE assumption in the standard model. Since the design is conceptually much simpler than known KFHE schemes, we replace their building blocks with attribute-based ones and obtain the proposed ABKFHE schemes. Next, we propose an efficient attribute-based KHPKE (ABKHE) scheme from a pair encoding scheme (PES). Due to the benefit of PES, we obtain various ABKHE schemes that contain the first identity-based KHPKE scheme secure under the standard $k$-linear assumption and the first pairing-based ABKHE schemes supporting more expressive predicates.

Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [BHK13], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, etc. Despite its usefulness, constructing UCE in the standard model is challenging. The only known positive result is given by Brzuska and Mittelbach [BM14], who construct UCE with strongly computationally unpredictable one-query source assuming indistinguishability obfuscation (iO) and the existence of point obfuscators with auxiliary input (AIPO); they also construct UCE with $q$-query sources assuming iO and composable AIPO. On the other hand, Brzuska, Farshim, and Mittelbach [BFM14] show that the most potent version of UCE does not exist, assuming the existence of iO. In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest

In an (α,β)-weak non-interactive zero knowledge (NIZK), the soundness error is at most α and the zero-knowledge error is at most β. Goyal, Jain, and Sahai (CRYPTO 2019) show that if α+β<1 for some constants α,β, then (α,β)-weak NIZK can be turned into fully-secure NIZK, assuming sub-exponentially-secure public-key encryption. We revisit the problem of NIZK amplification: – We amplify NIZK arguments assuming only polynomially-secure public-key encryption, for any constants α+β<1. – We amplify NIZK proofs assuming only one-way functions, for any constants α+β<1. – When the soundness error α is negligible to begin with, we can also amplify NIZK arguments assuming only one-way functions. Our results are based on the hidden-bits paradigm, and can be viewed as a reduction from NIZK amplification to the better understood problem of pseudorandomness amplification.

Cleve's celebrated result (STOC'86) showed that a strongly fair multi-party coin-toss is impossible in the presence of majority-sized coalitions. Recently, however, a fascinating line of work studied a relaxed fairness notion called \emph{game-theoretic fairness}, which guarantees that no coalition should be incentivized to deviate from the prescribed protocol. A sequence of works has explored the feasibility of game-theoretic fairness for \emph{two-sided} coin-toss, and indeed demonstrated feasibility in the dishonest majority setting under standard cryptographic assumptions. In fact, the recent work of Wu, Asharov, and Shi (EUROCRYPT'22) completely characterized the regime where game-theoretic fairness is feasible. However, this line of work is largely restricted to two-sided coin-toss, and more precisely on a \emph{uniform} coin-toss (i.e., Bernoulli with parameter $1/2$). The only exceptions are the works on game-theoretically fair leader election, which can be viewed as a special case of uniform $n$-sided coin-toss where $n$ is the number of parties. In this work, we \emph{initiate} the comprehensive study of game-theoretic fairness for multi-party \emph{sampling from general distributions}. In particular, for the case of $m$-sided \emph{uniform} coin-toss we give a nearly complete characterization of the regime in which game-theoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of game-theoretically fair two-sided coin-toss protocols does not necessarily yield game-theoretically fair multi-sided coins. To circumvent this, we introduce new techniques compatible with game-theoretic fairness. In particular, we give the following results: - We give a protocol from standard cryptographic assumptions that achieves game-theoretic fairness for uniform $m$-sided coin-toss against half- or more-sized adversarial coalitions. - To complement our protocol, we give a general impossibility result that establishes the optimality of our protocol for a broad range of parameters modulo an additive constant. Even in the worst-case, the gap between our protocol and our impossibility result is only a small constant multiplicative factor. - We also present a game-theoretically fair protocol for \emph{any} efficiently sampleable $m$-outcome distribution in the dishonest majority setting. For instance, even for the case of $m=2$ (i.e., two-sided coin-toss), our result implies a game-theoretically fair protocol for an \emph{arbitrary} Bernoulli coin. In contrast, the work of Wu, Asharov, and Shi only focussed on a Bernoulli coin with parameter $1/2$.

This paper focuses on the optimization of the number of logical qubits in Shor's quantum factoring algorithm. As in previous works, we target the implementation of the modular exponentiation, which is the most costly component of the algorithm, both in qubits and operations. In this paper, we show that using only $o(n)$ work qubits, one can obtain the first bit of the modular exponentiation output. We combine this result with May and Schlieper's truncation technique (ToSC 2022) and the Ekerå-Håstad variant of Shor's algorithm (PQCrypto 2017) to obtain a quantum factoring algorithm requiring only $n/2 + o(n)$ qubits in the case of an $n$-bit RSA modulus, while current envisioned implementations require about $2n$ qubits. Our algorithm uses a Residue Number System and succeeds with a parametrizable probability. Being completely classical, we have implemented and tested it. Among possible trade-offs, we can reach a gate count $\mathcal{O}(n^3)$ for a depth $\mathcal{O}(n^2 \log^3 n)$, which then has to be multiplied by $\mathcal{O}(\log n)$ (the number of measurement results required by Ekerå-Håstad). Preliminary logical resource estimates suggest that this circuit could be engineered to use less than 1700 qubits and $2^{36}$ Toffoli gates, and require 60 independent runs to factor an RSA-2048 instance.

Insight into user experience and behavior is critical to the success of large software systems and web services. Yet gaining such insights, while preserving user privacy, is a significant challenge. Recent advancements in multi-party computation have made it practical to compute verifiable aggregates over secret shared data. One important use case for these protocols is heavy hitters, where the servers compute the most popular inputs held by the users without learning the inputs themselves. The Poplar protocol (IEEE S&P 2021) focuses on this use case, but cannot support other aggregation tasks. Another such protocol, Prio (NSDI 2017), supports a wider variety of statistics but is unsuitable for heavy hitters. We introduce Mastic, a flexible protocol for private and verifiable general-purpose statistics based on function secret sharing and zero-knowledge proofs on secret shared data. Mastic is the first to solve the more general problem of weighted heavy-hitters, enabling new use cases, not supported by Prio or Poplar. In addition, Mastic allows grouping general-purpose metrics by user attributes, such as their geographic location or browser version, without sacrificing privacy or incurring high-performance costs, which is a major improvement over Prio. We demonstrate Mastic's benefits with two real-world applications, private network error logging and browser telemetry, and compare our protocol with Prio and Poplar on a wide area network. Overall, we report over one order of magnitude performance improvement over Poplar for heavy hitters and $1.5-2\times$ improvement over Prio for attribute-based metrics.

Symmetric ratchets and one-way key chains play a vital role in numerous important security protocols such as TLS 1.3, DTLS 1.3, QUIC, Signal, MLS, EDHOC, OSCORE, and Apple PQ3. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different ratchet constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions between different types of one-way key chains. Notably, the type of ratchet used by TLS 1.3, Signal, and PQ3 exhibit a significant number of weak keys, an unexpectedly high rate of key collisions surpassing birthday attack expectations, and a predictable shrinking key space susceptible to novel Time-Memory Trade-Off (TMTO) attacks with complexity $\approx N^{1/4}$. Consequently, the security level provided by e.g., TLS 1.3 is significantly lower than anticipated. To address these concerns, we analyze the aforementioned protocols and provide numerous concrete recommendations for enhancing their security, as well as guidance for future security protocol design.

In this work, we study the singular locus of the varieties defined by the public keys of UOV and VOX, two multivariate quadratic signature schemes submitted to the additional NIST call for signature schemes. Singular points do not exist for generic quadratic systems, which enables us to introduce two new algebraic attacks against UOV-based schemes. We show that they can be seen as an algebraic variant of the Kipnis-Shamir attack, which can be obtained in our framework as an enumerative approach of solving a bihomogeneous modeling of the computation of singular points. This allows us to highlight some heuristics implicitly relied on by the Kipnis-Shamir attack. We give new attacks for UOV$^{\hat +}$ and VOX targeting singular points of the public key equations. Our attacks lower the security of the schemes, both asymptotically and in number of gates, showing in particular that the parameters sets proposed for these schemes do not meet the NIST security requirements. More precisely, we show that the security of UOV$^{\hat +}$ was overestimated by factors $2^{22}, 2^{36}, 2^{59}$ for security levels $I, III, V$ respectively. We conclude the attack on VOX by showing that an attacker can perform a full key recovery from one vector obtained in the previous attacks.

In this paper, we propose a leakage-resilient pseudo-random number generator (PRNG) design that leverages the rekeying techniques of the PSV-Enc encryption scheme and the superposition property of the Superposition-Tweak-Key (STK) framework. The random seed of the PRNG is divided into two parts; one part is used as an ephemeral key that changes every two calls to a tweakable block cipher (TBC), and the other part is used as a static long-term key. Using the superposition property, we show that it is possible to eliminate observable leakage by only masking the static key. Thus, our proposal itself can be seen as a superposition of masking and rekeying. We show that our observations can be used to design an unpredictable-with-leakage PRNG as long as the static key is protected, and the ephemeral key cannot be attacked with 2 traces. Our construction enjoys better theoretical security arguments than PSV-Enc; better Time-Data trade-off and leakage assumptions, using the recently popularized unpredictability with leakage. We verify our proposal by performing Test Vector Leakage Assessment (TVLA) on an STK-based TBC (\deoxys) operated with a fixed key and a dynamic random tweak. Our results show that while the protection of the static key is non-trivial, it only requires $\approx 10\%$ overhead for first-order protection in the most conservative setting, unlike traditional masking which may require significant overheads of $300\%$ or more.

Fully Homomorphic Encryption (FHE) enables computation on encrypted data, holding immense potential for enhancing data privacy and security in various applications. Presently, FHE adoption is hindered by slow computation times, caused by data being encrypted into large polynomials. Optimized FHE libraries and hardware acceleration are emerging to tackle this performance bottleneck. Often, these libraries implement the Number Theoretic Transform (NTT) algorithm for efficient polynomial multiplication. Existing implementations mostly focus on the case where the polynomials are defined over a power-of-two cyclotomic ring, allowing to make use of the simpler Cooley-Tukey NTT. However, generalized cyclotomics have several benefits in the BGV FHE scheme, including more SIMD plaintext slots and a simpler bootstrapping algorithm. We present a hardware architecture for the NTT targeting generalized cyclotomics within the context of the BGV FHE scheme. We explore different non-power-of-two NTT algorithms, including the Prime-Factor, Rader, and Bluestein NTTs. Our most efficient architecture targets the 21845-th cyclotomic polynomial --- a practical parameter for BGV --- with ideal properties for use with a combination of the Prime-Factor and Rader algorithms. The design achieves high throughput with optimized resource utilization, by leveraging parallel processing, pipelining, and reusing processing elements. Compared to Wu et al.'s VLSI architecture of the Bluestein NTT, our approach showcases 2$\times$ to 5$\times$ improved throughput and area efficiency. Simulation and implementation results on an AMD Alveo U250 FPGA demonstrate the feasibility of the proposed hardware design for FHE.

Somewhere statistically binding (SSB) hashing allows us to sample a special hashing key such that the digest statistically binds the input at $m$ secret locations. This hash function is said to be somewhere extractable (SE) if there is an additional trapdoor that allows the extraction of the input bits at the $m$ locations from the digest. Devadas, Goyal, Kalai, and Vaikuntanathan (FOCS 2022) introduced a variant of somewhere extractable hashing called rate-1 fully local SE hash functions. The rate-1 requirement states that the size of the digest is $m + \mathsf{poly}(\lambda)$ (where $\lambda$ is the security parameter). The fully local property requires that for any index $i$, there is a "very short" opening showing that $i$-th bit of the hashed input is equal to $b$ for some $b \in \{0,1\}$. The size of this opening is required to be independent of $m$ and in particular, this means that its size is independent of the size of the digest. Devadas et al. gave such a construction from Learning with Errors (LWE). In this work, we give a construction of a rate-1 fully local somewhere extractable hash function from Decisional Diffie-Hellman (DDH) and BARGs. Under the same assumptions, we give constructions of rate-1 BARG and RAM SNARG with partial input soundness whose proof sizes are only matched by prior constructions based on LWE.

In this paper, we study two problems: oblivious compression and decompression of ciphertexts. In oblivious compression, a server holds a set of ciphertexts with a subset of encryptions of zeroes whose positions are only known to the client. The goal is for the server to effectively compress the ciphertexts obliviously, while preserving the non-zero plaintexts and without learning the plaintext values. For oblivious decompression, the client, instead, succinctly encodes a sequence of plaintexts such that the server may decode encryptions of all plaintexts value, but the zeroes may be replaced with arbitrary values. We present solutions to both problems that construct lossless compressions only 5% more than the optimal minimum using only additive homomorphism. The crux of both algorithms involve embedding ciphertexts as random linear systems that are efficiently solvable. Using our compression schemes, we obtain state-of-the-art schemes for batch private information retrieval (PIR) where a client wishes to privately retrieve multiple entries from a server-held database in one query. We show that our compression schemes may be used to reduce communication by up to 30% for batch PIR in both the single- and two-server settings. Additionally, we study labeled private set intersection (PSI) in the unbalanced setting where one party's set is significantly smaller than the other party's set and each entry has associated data. By utilizing our novel compression algorithm, we present a protocol with 65-88% reduction in communication with comparable computation compared to prior works.

The recent surge of distribute technologies caused an increasing interest towards threshold signature protocols, that peaked with the recent NIST First Call for Multi-Party Threshold Schemes. Since its introduction, the Fiat-Shamir Transform has been the most popular way to design standard digital signature schemes. In this work, we translate the Fiat-Shamir Transform into a multi-party setting, building a framework that seeks to be an alternative, easier way to design threshold digital signatures. We do that by introducing the concept of threshold identification scheme and threshold sigma protocol, and showing necessary and sufficient conditions to prove the security of the threshold signature schemes derived from them. Lastly, we show a practical application of our framework providing an alternative security proof for Sparkle, a recent threshold Schnorr signature. In particular, we consider the threshold identification scheme underlying Sparkle and prove the security of the signature derived from it. We show that using our framework the effort required to prove the security of threshold signatures might be drastically lowered. In fact, instead of reducing explicitly its security to the security of a hard problem, it is enough to prove some properties of the underlying threshold sigma protocol and threshold identification scheme. Then, by applying the results that we prove in this paper it is guaranteed that the derived threshold signature is secure.

This note examines a nuance in the methods employed for counting the adversarial online complexity in the security proofs of duplex-based modes, with a focus on authenticated encryption. A recent study by Gilbert et al., reveals an attack on a broad class of duplex-based authenticated encryption modes. In particular, their approach to quantifying the adversarial online complexity, which capture realistic attack scenarios, includes certain queries in the count which are not in the security proofs. This note analyzes these differences and concludes that the attack of Gilbert et al, for certain parameter choices, matches the security bound.

Quantum devices offer a highly useful function - that is generating random numbers in a non-deterministic way since the measurement of a quantum state is not deterministic. This means that quantum devices can be constructed that generate qubits in a uniform superposition and then measure the state of those qubits. If the preparation of the qubits in a uniform superposition is unbiased, then quantum computers can be used to create high entropy, secure random numbers. Typically, preparing and measuring such quantum systems requires more time compared to classical pseudo random number generators (PRNGs) which are inherently deterministic algorithms. Therefore, the typical use of quantum random number generators (QRNGs) is to provide high entropy secure seeds for PRNGs. Quantum annealing (QA) is a type of analog quantum computation that is a relaxed form of adiabatic quantum computation and uses quantum fluctuations in order to search for ground state solutions of a programmable Ising model. Here we present extensive experimental random number results from a D-Wave 2000Q quantum annealer, totaling over 20 billion bits of QA measurements, which is significantly larger than previous D-Wave QA random number generator studies. Current quantum annealers are susceptible to noise from environmental sources and calibration errors, and are not in general unbiased samplers. Therefore, it is of interest to quantify whether noisy quantum annealers can effectively function as an unbiased QRNG. The amount of data that was collected from the quantum annealer allows a comprehensive analysis of the random bits to be performed using the NIST SP 800-22 Rev 1a testsuite, as well as min-entropy estimates from NIST SP 800-90B. The randomness tests show that the generated random bits from the D-Wave 2000Q are biased, and not unpredictable random bit sequences. With no server-side sampling post-processing, the $1$ microsecond annealing time measurements had a min-entropy of $0.824$.

Battery-operated applications have been ubiquitous all over the world ranging from power-intensive electric cars down to low-power smart terminals and embedded devices. Meanwhile, serious incidents around batteries such as swelling, fire, and explosion have been witnessed, which resulted in horribly huge financial and even life loss. People used to attribute such aftermaths to unintentional design mistakes or insufficient quality inspection of original battery manufacturers. However, this is not fair anymore today given the convoluted battery supply chain and the extended cyber-physical attack surface of battery management systems (BMS). In this paper, we will focus on the authenticity and assurance of prevalent (Li-ion) battery instances. We look into battery authenticity by modeling the contemporary battery supply chain and discussing practical concerns such as rewrapping and recycling in-depth at each stage. As for battery assurance, we consider emerging attack vectors that can compromise the confidentiality, integrity, and availability of the microelectronic BMS. Besides, real-world attack examples are highlighted to reflect the capabilities of advanced adversaries. Moreover, promising countermeasures regarding the detection and avoidance of threats on both battery authenticity and assurance are presented, such that researchers will gain insights into how the problem could be addressed/alleviated. We also provide our perspectives on the vulnerabilities of battery systems and their consequent impacts as well as our point of view on potential countermeasure techniques.

We observe that most fixed-party distributed protocols can be rewritten by replacing a party with a ledger (such as a blockchain system) and the authenticated channel communication between parties with cross-chain relayers. This transform is useful because blockchain systems are always online and have battle-tested security assumptions. We provide a definitional framework that captures this analogy. We model the transform formally, and posit and prove a generic metatheorem that allows translating all theorems from the party setting into theorems in the emulated setting, while preserving analogies between party honesty and ledger security. In the heart of our proof lies a reduction-based simulation argument. As an example, our metatheorem can be used to construct a consensus protocol on top of other blockchains, creating a reliable rollup that assumes only the majority of the underlying layer-1s are secure.

Typical results in multi-party computation (in short, MPC) capture faulty parties by assuming a threshold adversary corrupting parties actively and/or fail-corrupting. These corruption types are, however, inadequate for capturing correct parties that might suffer temporary network failures and/or localized faults - these are particularly relevant for MPC over large, global scale networks. Omission faults and general adversary structures have been proposed as more suitable alternatives. However, to date, there is no characterization of the feasibility landscape combining the above ramifications of fault types and patterns. In this work we provide a tight characterization of feasibility of MPC in the presence of general adversaries - characterized by an adversary structure - that combine omission and active corruption. To this front we first provide a tight characterization of feasibility for Byzantine agreement (BA), a key tool in MPC protocols - this BA result can be of its own separate significance. Subsequently, we demonstrate that the common techniques employed in the threshold MPC literature to deal with omission corruptions do not work in the general adversary setting, not even for proving bounds that would appear straightforward, e.g, sufficiency of the well known $Q^3$ condition on omission-only general adversaries. Nevertheless we provide a new protocol that implements general adversary MPC under a surprisingly complex, yet tight as we prove, bound. All our results are for the classical synchronous model of computation. As a contribution of independent interest, our work puts forth, for the first time, a formal treatment of general-adversary MPC with (active and) omission corruptions in Canetti's universal composition framework.

In this work, we introduce a family of asymmetric cryptographic functions based on dynamic number theoretic transformations with multiple rounds of modular arithmetic to enhance diffusion and difficulty of inversion. This function acts as a basic cryptographic building block for a novel communication-efficient zero-knowledge crypto-system. The system as defined exhibits partial homomorphism and behaves as an additive positive accumulator. By using a novel technique to constructively embed lattice problems in a nested fashion, the dimensionality and overall complexity of the lattice structure is increased. This linked lattice framework obscures internal structure and mitigates cryptanalysis by applying a novel ’noisy roots’ technique. By relaxing the need for specifically correct nth ω roots in a given field, we apply offset values to create a framework of consisting of a set of uniquely transforming but arithmetically compatible NTTs. We provide specific parameters for conjectured NIST level V security. Communication costs are extremely low at 288-bytes per public key and 144-bytes per cipher-text or digital signature. Example protocols for key agreement, secure data exchange, additive accumulation, and digital signatures are provided. Peer review is in preliminary stages at time of dissemination. Claims within have not undergone rigorous validation and likely contain inaccuracies, errors, flaws or incomplete analysis. Contents may see significant modification through later iterations.

Trusted setup is commonly used for non-interactive proof and argument systems. However, there is no guarantee that the setup parameters in these systems are generated in a trustworthy manner. Building upon previous works, we conduct a systematic study of non-interactive zero-knowledge arguments in the common reference string model where the authority running the trusted setup might be corrupted. We explore both zero-knowledge and soundness properties in this setting.  - We consider a new notion of NIZK called subversion advice-ZK NIZK that strengthens the notion of zero-knowledge with malicious authority security considered by Ananth, Asharov, Dahari and Goyal (EUROCRYPT'21), and present a construction of a subversion advice-ZK NIZK from the sub-exponential hardness of learning with errors. - We introduce a new notion that strengthens the traditional definition of soundness, called accountable soundness, and present generic compilers that lift any NIZK for interesting languages in NP to additionally achieve accountable soundness. - Finally, we combine our results for both subversion advice-ZK and accountable soundness to achieve a subversion advice-ZK NIZK that also satisfies accountable soundness. This results in the first NIZK construction that satisfies meaningful notions of both soundness and zero-knowledge even for maliciously chosen CRS.

Sharding enhances blockchain scalability by dividing the network into shards, each managing specific unspent transaction outputs or accounts. As an introduced new transaction type, cross-shard transactions pose a critical challenge to the security and efficiency of sharding blockchains. Currently, there is a lack of a generic sharding consensus pattern that achieves both security and low overhead. In this paper, we present Kronos, a secure sharding blockchain consensus achieving optimized overhead. In particular, we propose a new secure sharding consensus pattern, based on a buffer managed jointly by shard members. Valid transactions are transferred to the payee via the buffer, while invalid ones are rejected through happy or unhappy paths. Kronos is proved to achieve security with atomicity under malicious clients with optimal intra-shard overhead $k\mathcal{B}$ ($k$ for involved shard number and $\mathcal{B}$ for a Byzantine fault tolerance (BFT) cost). Efficient rejection even requires no BFT execution in happy paths, and the cost in unhappy paths is still lower than a two-phase commit. Besides, we propose secure cross-shard certification methods based on batch certification and reliable cross-shard transfer. The former combines hybrid trees or vector commitments, while the latter integrates erasure coding. Handling $b$ transactions, Kronos is proved to achieve reliability with low cross-shard overhead $\mathcal{O}(n b \lambda)$ ($n$ for shard size and $\lambda$ for the security parameter). Notably, Kronos imposes no restrictions on BFT and does not rely on time assumptions, offering optional constructions in various modules. Kronos could serve as a universal framework for enhancing the performance and scalability of existing BFT protocols, supporting generic models, including asynchronous networks, increasing the throughput by several orders of magnitude. We implement Kronos using two prominent BFT protocols: asynchronous Speeding Dumbo (NDSS'22) and partial synchronous Hotstuff (PODC'19). Extensive experiments (over up to 1000 AWS EC2 nodes across 4 AWS regions) demonstrate Kronos scales the consensus nodes to thousands, achieving a substantial throughput of 320 ktx/sec with 2.0 sec latency. Compared with the past solutions, Kronos outperforms, achieving up to a 12$\times$ improvement in throughput and a 50% reduction in latency when cross-shard transactions dominate the workload.

In this paper, we propose a novel bi-primality test to determine whether $N=pq$ is the product of two primes on any RSA modulus in which we relaxed the restriction, $p\equiv q \equiv 3 \Mod{4}$, that was assumed in most of current bi-primality tests. Our bi-primality test is generalized from Lucas primality test to the bi-prime case. Our test always accepts when $p$ and $q$ are both prime, and otherwise accepts with probability at most $1/2$. In addition, we also prove that the Boneh-Franklin's bi-primality test accepts composite with probability at most $1/4$ instead of $1/2$, if we add an additional condition $\gcd(N, p+q-1)=1$. Moreover, we design a multiparty protocol against of static semi-honest adversaries in the hybrid model and provide a security proof. We then implement the proposed protocol and run in a single thread on a laptop which turned out with average 224 seconds execution time, given that $N$ is around $2048$-bit.

Anonymous message delivery, as in privacy-preserving blockchain and private messaging applications, needs to protect recipient metadata: eavesdroppers should not be able to link messages to their recipients. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without learning which messages are addressed to whom? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource the message detection and retrieval in a privacy-preserving way, using homomorphic encryption. Their construction exhibits significant costs in computation per message scanned (${\sim}0.1$ second), as well as in the size of the associated messages (${\sim}1$kB overhead) and public keys (${\sim}132$kB). This work constructs more efficient OMR schemes, by replacing the LWE-based clue encryption of prior works with a Ring-LWE variant, and utilizing the resulting flexibility to improve several components of the scheme. We thus devise, analyze, and benchmark two protocols: The first protocol focuses on improving the detector runtime, using a new retrieval circuit that can be homomorphically evaluated $15$x faster than the prior work. The second protocol focuses on reducing the communication costs, by designing a different homomorphic decryption circuit that allows the parameter of the Ring-LWE encryption to be set such that the public key size is about $235$x smaller than the prior work, and the message size is roughly $1.6$x smaller. The runtime of this second construction is ${\sim}40.0$ms per message, still more than $2.5$x faster than prior works.

Fully Homomorphic Encryption (FHE) is a powerful tool for performing privacy-preserving analytics over encrypted data. A promising method for FHE over real and complex numbers is approximate homomorphic encryption, instantiated with the Cheon-Kim-Kim-Song (CKKS) scheme. The CKKS scheme enables efficient evaluation for many privacy-preserving machine learning applications. Despite its high efficiency, there is currently a lot of confusion on how to securely instantiate CKKS for a given application, especially after secret-key recovery attacks were proposed by Li and Micciancio (EUROCRYPT'21) for the $IND-CPA^{D}$ setting, i.e., where decryption results are shared with other parties. On the one hand, the generic definition of $IND-CPA^{D}$ is application-agnostic and often requires impractically large parameters. On the other hand, practical CKKS implementations target specific applications and use tighter parameters. A good illustration are the recent secret-key recovery attacks against a CKKS implementation in the OpenFHE library by Guo et al. (USENIX Security'24). We show that these attacks misuse the library by employing different (incompatible) circuits during parameter estimation and run-time computation, yet they do not violate the generic (application-agnostic) $IND-CPA^{D}$ definition. To address this confusion, we introduce the notion of application-aware homomorphic encryption and devise related security definitions, which correspond more closely to how homomorphic encryption schemes are implemented and used in practice. We then formulate the guidelines for implementing the application-aware homomorphic encryption model to achieve $IND-CPA^{D}$ security for practical applications of CKKS. We also show that our application-aware model can be used for secure, efficient instantiation of exact homomorphic encryption schemes.

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be "linked" to the original input ciphertexts. We formalize the vCCA notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al. in 2012. We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic encryption schemes, namely CCA1, RCCA, FuncCPA, CCVA, and HCCA. We prove that vCCA security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, vCCA is strictly stronger than CCA1. Finally, we provide a general transformation, that takes any CPA-secure FHE scheme and makes it vCCA-secure. Our transformation first turns an FHE scheme into a CCA2-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge (SNARK) to verifiably control the evaluation algorithm. In fact, we obtain four general variation of this transformation. We handle both the asymmetric and the symmetric key FHE schemes, and for each we give two variations differing in whether the ciphertext integrity can be verified publicly or requires the secret key. We use well-known techniques to achieve CCA security in the first step of our transformation. In the asymmetric case, we use the double encryption paradigm, and in the symmetric case, we use Encrypt-then-MAC techniques. Furthermore, our transformation also gives the first CCA-secure FHE scheme based on bootstrapping techniques.

This paper introduces an algorithm to efficiently break the Decisional Diffie-Hellman (DDH) assumption in totally non-maximal imaginary quadratic orders, specifically when $\Delta_1 = 3$, and $f$ is non-prime with knowledge of a single factor. Inspired by Shanks and Dedekind's work on 3-Sylow groups, we generalize their observations to undermine DDH security.

We propose a modification to the fork choice rule of proof-of-work blockchains. Instead of choosing the heaviest chain, we choose the chain with the most intrinsic work. The intrinsic work of a block is roughly the number of zeroes at the front of its hash. This modification allows us to safely decrease the confirmations required, yielding a $28.5\%$ improvement in confirmation delay or, dually, safely increase the block production rate, yielding a $16.3\%$ improvement in throughput, as compared to the vanilla Bitcoin proof-of-work fork choice rule. Our modification is at the level of the proof-of-work inequality, and thus can be composed with any other methods to improve latency or throughput that have been proposed in the literature. We report the experimental findings by measuring them on a production-grade implementation of our system, whose testnet is already deployed in the wild. Lastly, we formally prove the security of our new protocol in the Bitcoin Backbone model.

Masking is one of the most popular countermeasures to side- channel attacks, because it can offer provable security. However, depend- ing on the adversary’s model, useful security guarantees can be hard to provide. At first, masking has been shown secure against t-threshold probing adversaries by Ishai et al. at Crypto’03. It has then been shown secure in the more generic random probing model by Duc et al. at Euro- crypt’14. Prouff and Rivain have introduced the noisy leakage model to capture more realistic leakage at Eurocrypt’13. Reduction from noisy leakage to random probing has been introduced by Duc et al. at Euro- crypt’14, and security guarantees were improved for both models by Prest et al. at Crypto’19, Duc et al. in Eurocrypt’15/J. Cryptol’19, and Masure and Standaert at Crypto’23. Unfortunately, as it turns out, we found that previous proofs in either random probing or noisy leakage models are flawed, and such flaws do not appear easy to fix. In this work, we show that the Doeblin coefficient allows one to over- come these flaws. In fact, it yields optimal reductions from noisy leakage to random probing, thereby providing a correct and usable metric to properly ground security proofs. This shows the inherent inevitable cost of a reduction from the noisy leakages to the random probing model. We show that it can also be used to derive direct formal security proofs using the subsequence decomposition of Prouff and Rivain.

Generating and integrating shared randomness into a blockchain can expand applications and strengthen security. We aim to have validators generating blockchain randomness autonomously, and fresh shared randomness is generated for each block. We focus on proof-of-stake blockchains, where each validator has a different amount of stake (aka weight). Such chains introduce a weighted threshold setting where subset authorization relies on the cumulative weight of validators rather than the subset size. We introduce three cryptographic protocols to enable generating shared randomness in a weighted setting: A publicly verifiable secret sharing scheme (PVSS) which is weighted and aggregatable, a weighted distributed key generation protocol (DKG), and a weighted verifiable unpredictable function (VUF). Importantly, in the VUF protocol, which is the protocol that is run most frequently, the computation and communication costs of participants are independent of their weight. This feature is crucial for scalability. We implemented our schemes on top of Aptos blockchain, which is a proof-of-stake blockchain deployed in production. Our micro-benchmarks demonstrate that the signing and verification time, as well as the signature size, are independent of the total weight of the parties, whereas the signing time and signature size of the baseline (BLS with virtualization) increase significantly. For instance, our VUF reduces the signature size by factors of 7X and 34X for total weights of 821 and 4053, respectively. We also demonstrate the practicability of our design via an end-to-end evaluation.

Over the past decade, cryptocurrencies have garnered attention from academia and industry alike, fostering a diverse blockchain ecosystem and novel applications. The inception of bridges improved interoperability, enabling asset transfers across different blockchains to capitalize on their unique features. Despite their surge in popularity and the emergence of Decentralized Finance (DeFi), trustless bridge protocols remain inefficient, either relaying too much information (e.g., light-client-based bridges) or demanding expensive computation (e.g., zk-based bridges). These inefficiencies arise because existing bridges securely prove a transaction's on-chain inclusion on another blockchain. Yet this is unnecessary as off-chain solutions, like payment and state channels, permit safe transactions without on-chain publication. However, existing bridges do not support the verification of off-chain payments. This paper fills this gap by introducing the concept of Pay2Chain bridges that leverage the advantages of off-chain solutions like payment channels to overcome current bridges' limitations. Our proposed Pay2Chain bridge, named Alba, facilitates the efficient, secure, and trustless execution of conditional payments or smart contracts on a target blockchain based on off-chain events. Alba, besides its technical advantages, enriches the source blockchain's ecosystem by facilitating DeFi applications, multi-asset payment channels, and optimistic stateful off-chain computation. We formalize the security of Alba against Byzantine adversaries in the UC framework and complement it with a game theoretic analysis. We further introduce formal scalability metrics to demonstrate Alba’s efficiency. Our empirical evaluation confirms Alba efficiency in terms of communication complexity and on-chain costs, with its optimistic case incurring only twice the cost of a standard Ethereum transaction of token ownership transfer.

In this note, we show that some of the parameters of the Quotient-Ring transform proposed for VOX are vulnerable. More precisely, they were chosen to defeat an attack in the field extension $\mathbb F_{q^l}$ obtained by quotienting $\mathbb F_q[X]$ by an irreducible polynomial of degree $l$. We observe that we may use a smaller extension $\mathbb F_{q^{l'}}$ for any $l'|l$, in which case the attacks apply again. We also introduce a simple algebraic attack without the use of the MinRank problem to attack the scheme. These attacks concern a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. We estimate the cost of our attack on these parameter sets and find costs of at most $2^{67}$ gates, and significantly lower in most cases. In practice, our attack requires $0.3s, 1.35s, 0.56s$ for parameter sets I,III,V for the initial VOX parameters, and $56.7s, 6.11s$ for parameter sets IIIa, Vb proposed after the rectangular MinRank attack.

As CPU performance is unable to keep up with the dramatic growth of the past few decades, CPU architects are looking into domain-specific architectures to accelerate certain tasks. A recent trend is the introduction of matrix-multiplication accelerators to CPUs by manufacturers such as IBM, Intel and ARM, some of which have not launched commercially yet. Apple's systems-on-chip (SoCs) for its mobile phones, tablets and personal computers include a proprietary, undocumented CPU-coupled matrix multiplication coprocessor called AMX. In this paper, we leverage AMX to accelerate the post-quantum lattice-based cryptosystems Saber and FrodoKEM, and benchmark their performance on Apple M1 and M3 SoCs. We propose a variant of the Toeplitz Matrix-Vector Product algorithm for polynomial multiplication, which sets new speed records for Saber using AMX (up to 13% for the main KEM operations, and 151% for matrix-vector multiplication of polynomials). For FrodoKEM, we set new speed records with our AMX implementation (up to 21% for the main KEM operations, and 124% for matrix multiplication, with even greater improvements for $4 \times$-batching). Such speedups are relative to our optimized NEON implementation, also presented here, which improves upon the state-of-the-art implementation for ARMv8 CPUs.

We introduce Helium, a novel framework that supports scalable secure multiparty computation for lightweight participants and tolerates churn. Helium relies on multiparty homomorphic encryption (MHE) as its core building block. While MHE schemes have been well studied in theory, prior works fall short of addressing critical considerations paramount for adoption such as supporting resource-constrained participants and ensuring liveness and security under network churn. In this work, we systematize the requirements of MHE-based MPC protocols from a practical lens, and we propose a novel execution mechanism, that addresses those considerations. We implement this execution in Helium, which makes it the first implemented solution that effectively supports sub-linear-cost MPC among lightweight participants and under churn. This represents a significant leap in applied MPC, as most previously proposed frameworks require the participants to have high bandwidth and to be consistently online. We show that a Helium network of $30$ parties connected with a $100$Mbits/s link and experiencing a system-wide churn rate of $40$ failures per minute can compute the product of a fixed secret $512\times512$ matrix (e.g., a collectively trained model) with an input secret vector (e.g., a feature vector) $8.3$ times per second. This is $\sim1500$ times faster than a state-of-the art MPC implementation without churn.

The submission of the Triangular Unbalanced Oil and Vinegar (TUOV) digital signature scheme to the NIST competition in 2023 claims that if the Multivariate Quadratic (MQ) problem (with suitable parameters) is hard, then the TUOV problem must also be hard. We show why the proof fails and why the claimed theorem cannot be true in general.

Function secret sharing (FSS) for a class $\cal{F}$ allows to split a secret function $f \in \cal{F}$ into (succinct) secret shares $f_0,f_1$, such that for all $x\in \{0,1\}^n$ it holds $f_0(x)-f_1(x)=f(x)$. FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class $\cal{F}$ translates to richness in the application. Unfortunately, concretely efficient FSS constructions are only known for very limited function classes. In this work we introduce the notion of pseudorandom generators with encoded-output homomorphism (EOH-PRGs), and give direct FSS constructions for bit-fixing predicates, branching programs and more based on this primitive. Further, we give constructions of FSS for deterministic finite automatas (DFAs) from a KDM secure variant of EOH-PRGs. - New abstractions. Following the work of Alamati et al.(EUROCRYPT '19), who classify minicrypt primitives with algebraic structure and their applications, we capture the essence of our FSS constructions in the notion of EOH-PRG, paving the road towards future efficiency improvements via new instantiations of this primitive. The abstraction of EOH-PRG and its instantiations may be of independent interest, as it is an approximate substitution of an ideal homomorphic PRG. - Better efficiency. We show that EOH-PRGs can be instantiated from LWE and a small-exponent variant of the DCR assumption. A theoretical analysis of our instantiations suggest efficiency improvements over the state of the art both in terms of key size and evaluation time: We show that our FSS instantiations lead to smaller key sizes, improving over previous constructions by a factor of $3.5$ and more. While for bit-fixing predicates our FSS constructions show comparable or mildly improved run time (depending on the instantiation), we achieve considerable improvements for branching programs by avoiding the expensive generic transformation via universal circuits, shaving off a factor of $w$ and more in the number of abstract operations, where $w$ corresponds to an upper bound on the width of the underlying class of branching programs. - New constructions. We show that our instantiations of EOH-PRGs additionally support a form of KDM-security, without requiring an additional circular-security assumption. Based on this, we give the first FSS construction for DFAs which supports the evaluation of inputs of a-priori unbounded length without relying on FHE. - Applications. We outline applications of our FSS constructions including pattern matching with wild cards, image matching, nearest neighbor search and regular expression matching.

Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions. Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed how to convert an unreliable CDH oracle into one that is correct with overwhelming probability. However, while a theoretical breakthrough, their reduction is quite inefficient: if the CDH oracle is correct with probability $\epsilon$ then their algorithm to amplify the success requires on the order of $1/\epsilon^{21}$ calls to the CDH oracle. We revisit this line of work and give a much simpler and tighter algorithm. Our method only takes on the order of $1/\epsilon^{4}$ CDH oracle calls and is conceptually simpler than the Montgomery-Zhandry reduction. Our algorithm is also fully black-box, whereas the Montgomery-Zhandry algorithm is slightly non-black-box. Our main tool is a thresholding technique that replaces the comparison of distributions in Montgomery-Zhandry with testing equality of thresholded sets.

The main goal of this work is to construct authenticated encryption (AE) that is both committing and leakage-resilient. As a first approach for this we consider generic composition as a well-known method for constructing AE schemes. While the leakage resilience of generic composition schemes has already been analyzed by Barwell et al. (AC'17), for committing security this is not the case. We fill this gap by providing a separate analysis of the generic composition paradigms with respect to committing security, giving both positive and negative results: By means of a concrete attack, we show that Encrypt-then-MAC is not committing. Furthermore, we prove that Encrypt-and-MAC is committing, given that the underlying schemes satisfy security notions we introduce for this purpose. We later prove these new notions achievable by providing schemes that satisfy them. MAC-then-Encrypt turns out to be more difficult due to the fact that the tag is not outputted alongside the ciphertext as it is done for the other two composition methods. Nevertheless, we give a detailed heuristic analysis of MAC-then-Encrypt with respect to committing security, leaving a definite result as an open task for future work. Our results, in combination with the fact that only Encrypt-then-MAC yields leakage-resilient AE schemes, show that one cannot obtain AE schemes that are both committing and leakage-resilient via generic composition. As a second approach for constructing committing and leakage-resilient AE, we develop a generic transformation that turns an arbitrary AE scheme into one that fulfills both properties. The transformation relies on a keyed function that is both binding, i.e., it is hard to find key-input pairs that result in the same output, and leakage-resilient pseudorandom.

Auctions, a long-standing method of trading goods and services, are a promising use case for decentralized finance. However, due to the inherent transparency property of blockchains, current sealed-bid auction implementations on smart contracts requires a bidder to send at least two transactions to the underlying blockchain: a bidder must first commit their bid in the first transaction during the bidding period and reveal their bid in the second transaction once the revealing period starts. In addition, the smart contract often requires a deposit to incentivize bidders to reveal their bids, rendering unnecessary financial burdens and risks to bidders. We address these drawbacks by enforcing delayed execution in the blockchain execution layer to all transactions. In short, the blockchain only accepts encrypted transactions, and when the blockchain has finalized an encrypted transaction, the consensus group decrypts and executes it. This architecture enables ZeroAuction, a sealed-bid auction smart contract with zero deposit requirement. ZeroAuction relies on the blockchain enhanced with delayed execution to hide and bind the bids within the encrypted transactions and, after a delay period, reveals them automatically by decrypting and executing the transactions. Because a bidder only needs to interact with the blockchain once instead of two times to participate in the auction, ZeroAuction significantly reduces the latency overhead along with eliminating the deposit requirement.

In the realm of privacy-preserving blockchain applications such as Zcash, oblivious message retrieval (OMR) enables recipients to privately access messages directed to them on blockchain nodes (or bulletin board servers). OMR prevents servers from linking a message and its corresponding recipient's address, thereby safeguarding recipient privacy. Several OMR schemes have emerged recently to meet the demands of these privacy-centric blockchains; however, we observe that existing solutions exhibit shortcomings in various critical aspects and may only achieve certain objectives inefficiently, sometimes relying on trusted hardware, thereby impacting their practical utility. This work introduces a novel OMR protocol, HomeRun, that leverages two semi-honest, non-colluding servers to excel in both performance and security attributes as compared to the current state-of-the-art. HomeRun stands out by providing unlinkability across multiple requests for the same recipient's address. Moreover, it does not impose a limit on the number of pertinent messages that can be received by a recipient, which thwarts ``message balance exhaustion'' attacks and enhances system usability. HomeRun also empowers servers to regularly delete the retrieved messages and the associated auxiliary data, which mitigates the constantly increasing computation costs and storage costs incurred by servers. Remarkably, none of the existing solutions offer all of these features collectively. Finally, thanks to its judicious use of highly efficient cryptographic building blocks, HomeRun is highly performant: Specifically, the total runtime of servers in HomeRun is $3830 \times$ less than that in the work by Liu et al. (CRYPTO '22) based on fully-homomorphic encryption, and at least $1459 \times$ less than that in the design by Madathil et al. (USENIX Security '22) based on two semi-honest and non-colluding servers, using a single thread in a WAN setting.

We prove that for $n>1$ the map $\chi:\mathbb{F}_q^n \to \mathbb{F}_q^n$, defined by $y=\chi(x)$ with $y_i = x_i + x_{i+2}\cdot(1+x_{i+1})$ for $1\leq i \leq n$, is bijective if and only if $q=2$ and $n$ is odd, as it was conjectured by Schoone and Daemen in 2023.

High-performance and energy-efficient encryption engines have become crucial components in modern System-On-Chip (SoC) architectures across multiple platforms, including servers, desktops, mobile devices, and IoT edge devices. Alas, the secure operation of cryptographic engines faces a significant obstacle caused by information leakage through various side-channels. Adversaries can exploit statistical analysis techniques on measured (e.g.,) power and timing signatures generated during (e.g.,) encryption process to extract secret material. Countermeasures against such side-channel attacks often impose substantial power, area, and performance overheads. Consequently, designing side-channel secure encryption engines becomes a critical challenge when ensuring high-performance and energy-efficient operations. In this paper we will suggest a novel technique for low cost, high impact, easily scalable protection based on Adaptive Dynamic Voltage and Frequency Scaling (A-DVFS) capabilities in ultra-low-power (ULP) sub-threshold chips. We review the improvement of using integrated voltage regulators and DVFS, normally used for efficient power management, towards increasing side-channel resistance of encryption engines; Pushing known prior-art in the topic to ULP-regime. The hardware measurements were performed on PLS15 test-chip fabricated in ULP 40nm process going down from nominal voltage to 580 mV power-supply. Various results and detailed analysis is presented to demonstrate the impact of power management circuits on side-channel security, performance-impact and comparison to prior-art. Importantly, we highlight security sensitivities DVFS embeds in terms of software side-channels such as timing, and their mitigation with our proposed technique, successfully masking the time signature introduced by DVFS.

A list polynomial commitment scheme (LPC) is a polynomial commitment scheme with a relaxed binding property. Namely, in an LPC setting, a commitment to a function $f(X)$ can be opened to a list of low-degree polynomials close to $f(X)$ (w.r.t. the relative Hamming distance and over a domain $D$). The scheme also allows opening one of the polynomials of the list at an arbitrary point $x$ and convincing a verifier that one of the polynomials in the list evaluates to the purported value. Vortex is a list polynomial commitment, obtained through a modification of Ligero (CCS 2017), inspired by the schemes of Brakedown (Crypto 2023), batch-FRI (FOCS 2020), and RedShift (CCS 2022). Concerning one application of Vortex, for a witness of size $N$, the messages between the prover and the verifier are of size $O(N^{1/2})$. Vortex is a core component of the SNARK used by the prover of Linea (Consensys). This paper provides a complete security analysis for Vortex. We use a general compiler to build an Argument of Knowledge (AoK) by combining our list polynomial commitment and a polynomial-IOP (PIOP). The approach is similar to combining a PIOP with a polynomial commitment scheme and has a soundness loss only linear in the list size. This overcomes a previous limitation in the standard compiler from a generic PIOP and a list polynomial commitment scheme to an interactive argument of knowledge, which suffers from a soundness loss of $\mathcal{O}(|L|^r)$ (where $|L|$ is the list size and $r$ is the number of interactions between the prover and the verifier in the PIOP).

Threshold signatures improve both availability and security of digital signatures by splitting the signing key into $N$ shares handed out to different parties. Later on, any subset of at least $T$ parties can cooperate to produce a signature on a given message. While threshold signatures have been extensively studied in the pre-quantum setting, they remain sparse from quantum-resilient assumptions. We present the first efficient lattice-based threshold signatures with signature size 13 KiB and communication cost 40 KiB per user, supporting a threshold size as large as 1024 signers. We provide an accompanying high performance implementation. The security of the scheme is based on the same assumptions as Dilithium, a signature recently selected by NIST for standardisation which, as far as we know, cannot easily be made threshold efficiently. All operations used during signing are due to symmetric primitives and simple lattice operations; in particular our scheme does not need heavy tools such as threshold fully homomorphic encryption or homomorphic trapdoor commitments as in prior constructions. The key technical idea is to use one-time additive masks to mitigate the leakage of the partial signing keys through partial signatures.

Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC'14), sign vectors of elements from a bilinear group. Signatures can be ``adapted'', meaning that anyone can transform a signature on a vector to a (random) signature on any multiple of that vector. (Signatures thus authenticate equivalence classes.) A transformed signature/message pair is then indistinguishable from a random signature on a random message. EQS have been used to efficiently instantiate (delegatable) anonymous credentials, (round-optimal) blind signatures, ring and group signatures and anonymous tokens. The original EQS construction (J.Crypto'19) is only proven in the generic group model, while the first construction from standard assumptions (PKC'18) only yields security guarantees insufficient for most applications. Two works (AC'19, PKC'22) propose applicable schemes which assume the existence of a common reference string for the anonymity notion. Their unforgeability is argued via a security proof from standard (or non-interactive) assumptions. In this work we show that their security proof is flawed and explain the subtle issue.

Decentralized Storage Network (DSN) is an emerging technology that challenges traditional cloud-based storage systems by consolidating storage capacities from independent providers and coordinating to provide decentralized storage and retrieval services. However, current DSNs face several challenges associated with data privacy and efficiency of the proof systems. To address these issues, we propose FileDES (Decentralized Encrypted Storage), which incorporates three essential elements: privacy preservation, scalable storage proof, and batch verification. FileDES provides encrypted data storage while maintaining data availability, with a scalable Proof of Encrypted Storage (PoES) algorithm that is resilient to Sybil and Generation attacks. Additionally, we introduce a rollup-based batch verification approach to simultaneously verify multiple files using publicly verifiable succinct proofs. We conducted a comparative evaluation on FileDES, Filecoin, Storj and Sia under various conditions, including a WAN composed of up to 120 geographically dispersed nodes. Our protocol outperforms the others in terms of proof generation/verification efficiency, storage costs, and scalability.

Fully Homomorphic Encryption (FHE) enables the computation of an arbitrary function over encrypted data without decrypting them. In particular, bootstrapping is a core building block of FHE which reduces the noise of a ciphertext thereby recovering the computational capability. This paper introduces a new bootstrapping framework for the Fan-Vercauteren (FV) scheme, called the functional bootstrapping, providing more generic and advanced functionality than the ordinary bootstrapping method. More specifically, the functional bootstrapping allows us to evaluate an arbitrary function while removing the error of an input ciphertext. Therefore, we achieve better depth consumption and computational complexity as the evaluation of a circuit can be integrated as part of the functional bootstrapping procedure. In particular, our approach extends the functionality of FV since it is even applicable to functions between different plaintext spaces. At the heart of our functional bootstrapping framework is a homomorphic Look-Up Table (LUT) evaluation method where we represent any LUT using only the operations supported by the FV scheme. Finally, we provide a proof-of-concept implementation and present benchmarks of the functional bootstrapping. In concrete examples, such as delta and sign functions, our functional bootstrapping takes about 46.5s or 171.4s for 9-bit or 13-bit plaintext modulus, respectively.

Embedded Multimedia Cards (eMMCs) provide a protected memory area called the Replay Protected Memory Block (RPMB). eMMCs are commonly used as storage media in modern smartphones. In order to protect these devices from unauthorized access, important data is stored in the RPMB area in an authenticated manner. Modification of the RPMB data requires a pre-shared authentication key. An unauthorized user cannot change the stored data. On modern devices, this pre-shared key is generated and used exclusively within a Trusted Execution Environment (TEE) preventing attackers from access. In this paper, we investigate how the authentication key for RPMB is programmed on the eMMC. We found that this key can be extracted directly from the target memory chip. Once obtained, the authentication key can be used to manipulate stored data. In addition, poor implementation of certain security features, aimed at preventing replay attacks using RPMB on the host system can be broken by an attacker. We show how the authentication key can be extracted and how it can be used to break the anti-rollback protection to enable data restoration even after a data wipe operation has been completed. Our findings show that non-secure RPMB implementations can enable forensic investigators to break security features implemented on modern smartphones.

Traitor-tracing systems allow identifying the users who contributed to building a rogue decoder in a broadcast environment. In a traditional traitor-tracing system, a key authority is responsible for generating the global public parameters and issuing secret keys to users. All security is lost if the \emph{key authority itself} is corrupt. This raises the question: Can we construct a traitor-tracing scheme, without a trusted authority? In this work, we propose a new model for traitor-tracing systems where, instead of having a key authority, users could generate and register their own public keys. The public parameters are computed by aggregating all user public keys. Crucially, the aggregation process is \emph{public}, thus eliminating the need of any trusted authority. We present two new traitor-tracing systems in this model based on bilinear pairings. Our first scheme is proven adaptively secure in the generic group model. This scheme features a transparent setup, ciphertexts consisting of $6\sqrt{L}+4$ group elements, and a public tracing algorithm. Our second scheme supports a bounded collusion of traitors and is proven selectively secure in the standard model. Our main technical ingredients are new registered functional encryption (RFE) schemes for quadratic and linear functions which, prior to this work, were known only from indistinguishability obfuscation. To substantiate the practicality of our approach, we evaluate the performance a proof of concept implementation. For a group of $L = 1024$ users, encryption and decryption take roughly 50ms and 4ms, respectively, whereas a ciphertext is of size 6.7KB.

Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols. In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party's public key. In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k-40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the-art public-key PCFs. As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.

We present a Registered Functional Encryption (RFE) scheme for inner product and a RFE scheme for quadratic functions based on pairings and relying on the Matrix Decision Diffie-Hellman (MDDH) assumption and bilateral MDDH assumption. Previously, RFE is only known to be constructed from indistinguishability obfuscation (iO) in Francati-Friolo-Maitra-Malavolta-Rahimi-Venturi [Asiacrypt '23].

It has been shown that post-quantum key exchange and authentication with ML-KEM and ML-DSA, NIST’s postquantum algorithm picks, will have an impact on TLS 1.3 performance used in the Web or other applications. Studies so far have focused on the overhead of quantum-resistant algorithms on TLS time-to-first-byte (handshake time). Although these works have been important in quantifying the slowdown in connection establishment, they do not capture the full picture regarding real-world TLS 1.3 connections which carry sizable amounts of data. Intuitively, the introduction of an extra 10KB of ML-KEM and ML-DSA exchanges in the connection negotiation will inflate the connection establishment time proportionally more than it will increase the total connection time of a Web connection carrying 200KB of data. In this work, we quantify the impact of ML-KEM and ML-DSA on typical TLS 1.3 connections which transfer a few hundreds of KB from the server to the client. We study the slowdown in the time-to-last-byte of postquantum connections under normal network conditions and in more unstable environments with high packet delay variability and loss probabilities. We show that the impact of ML-KEM and ML-DSA on the TLS 1.3 time-to-last-byte under stable network conditions is lower than the impact on the handshake and diminishes as the transferred data increases. The time-to-last-byte increase stays below 5% for high-bandwidth, stable networks. It goes from 32% increase of the handshake time to under 15% increase of the time-to-last-byte when transferring 50KiB of data or more under low-bandwidth, stable network conditions. Even when congestion control affects connection establishment, the additional slowdown drops below 10% as the connection data increases to 200KiB. We also show that connections under lossy or volatile network conditions could see higher impact from post-quantum handshakes, but these connections’ time-to-lastbyte increase still drops as the transferred data increases. Finally, we show that such connections are already significantly slow and volatile regardless of the TLS handshake.

Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building advanced primitives from code-based assumptions, as the only known such assumption is Learning Parity with Noise (LPN) with an extremely low noise rate $\frac{\log^2 n}{n}$, which is broken in quasi-polynomial time. In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class $\mathcal{BPP}^{\mathcal{SZK}}$ and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece's cryptosystem and random $k\mbox{-}$XOR in average-case complexity. Roughly, the assumption states that \[(\mathbf{T}\, \mathbf{M}, \mathbf{s} \,\mathbf{T}\, \mathbf{M} + \mathbf{e}) \quad \text{is indistinguishable from}\quad (\mathbf{T} \,\mathbf{M}, \mathbf{u}),\] for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$, and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution with inverse polynomial noise probability. We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasi-polynomially secure.

In response to the evolving landscape of quantum computing and the heightened vulnerabilities in classical cryptographic systems, our paper introduces a comprehensive cryptographic framework. Building upon the pioneering work of Kuang et al., we present a unification of two innovative primitives: the Quantum Permutation Pad (QPP) for symmetric key encryption and the Homomorphic Polynomial Public Key (HPPK) for Key Encapsulation Mechanism (KEM) and Digital Signatures (DS). By harnessing matrix representations of the Galois Permutation Group and inheriting its bijective and non-commutative properties, QPP achieves quantum-secure symmetric key encryption, seamlessly extending Shannon’s perfect secrecy to both classical and quantum-native systems. Simultaneously, HPPK, free of NP-hard problems, relies on the security of symmetric encryption for the plain public key. This is accomplished by concealing the mathematical structure through arithmetic representations or modular multiplicative operators (arithmetic QPP) of the Galois Permutation Group over hidden rings, utilizing their partial homomorphic properties. This ensures secure computation on encrypted data during secret encapsulations, thereby enhancing the security of the plain public key. The integration of KEM and DS within HPPK cryptography results in compact key, cipher, and signature sizes, showcasing exceptional performance. This paper organically unifies QPP and HPPK under the Galois Permutation Group, marking a significant advance in laying the groundwork for quantum-resistant cryptographic protocols. Our contribution propels the development of secure communication systems in the era of quantum computing.

We prove that the seminal KZG polynomial commitment scheme (PCS) is black-box extractable under a simple falsifiable assumption ARSDH. To create an interactive argument, we construct a compiler that combines a black-box extractable non-interactive PCS and a polynomial IOP (PIOP). The compiler incurs a minor cost per every committed polynomial. Applying the Fiat-Shamir transformation, we obtain slightly less efficient variants of well-known PIOP-based zk-SNARKs, such as Plonk, that are knowledge-sound in the ROM under the ARSDH assumption. Importantly, there is no need for idealized group models or knowledge assumptions. This results in the first known zk-SNARKs in the ROM from falsifiable assumptions with both an efficient prover and constant-size argument.

BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes, supporting evaluations over a finite field. To evaluate a circuit with arbitrary depth, bootstrapping is needed. However, despite the recent progress, bootstrapping of BGV/BFV still remains relatively impractical, compared to other FHE schemes. In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself. Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function. Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for batched binary gate bootstrapping and a plaintext-space-dependent speed-up for batched functional bootstrapping with plaintext space smaller than $\mathbb{Z}_{512}$.

The computation of step functions over encrypted data is an essential issue in homomorphic encryption due to its fundamental application in privacy-preserving computing. However, an effective method for homomorphically computing general step functions remains elusive in cryptography. This paper proposes two polynomial approximation methods for general step functions to tackle this problem. The first method leverages the fact that any step function can be expressed as a linear combination of shifted sign functions. This connection enables the homomorphic evaluation of any step function using known polynomial approximations of the sign function. The second method boosts computational efficiency by employing a composite polynomial approximation strategy. We present a systematic approach to construct a composite polynomial $f_k \circ f_{k-1} \circ \cdots \circ f_1$ that increasingly approximates the step function as $k$ increases. This method utilizes an adaptive linear programming approach that we developed to optimize the approximation effect of $f_i$ while maintaining the degree and coefficients bounded. We demonstrate the effectiveness of these two methods by applying them to typical step functions such as the round function and encrypted data bucketing, implemented in the HEAAN homomorphic encryption library. Experimental results validate that our methods can effectively address the homomorphic computation of step functions.

Side-Channel Analysis (SCA) is critical in evaluating the security of cryptographic implementations. The search for hyperparameters poses a significant challenge, especially when resources are limited. In this work, we explore the efficacy of a multifidelity optimization technique known as BOHB in SCA. In addition, we proposed a new objective function called $ge_{+ntge}$, which could be incorporated into any Bayesian Optimization used in SCA. We show the capabilities of both BOHB and $ge_{+ntge}$ on four different public datasets. Specifically, BOHB could obtain the least number of traces in CTF2018 when trained in the Hamming weight and identity leakage model. Notably, this marks the first reported successful recovery of the key for the identity leakage model in CTF2018.

Kyber KEM, the NIST selected PQC standard for Public Key Encryption and Key Encapsulation Mechanisms (KEMs) has been subjected to a variety of side-channel attacks, through the course of the NIST PQC standardization process. However, all these attacks targeting the decapsulation procedure of Kyber KEM either require knowledge of the ciphertexts or require to control the value of ciphertexts for key recovery. However, there are no known attacks in a blind setting, where the attacker does not have access to the ciphertexts. While blind side-channel attacks are known for symmetric key cryptographic schemes, we are not aware of such attacks for Kyber KEM. In this paper, we fill this gap by proposing the first blind side-channel attack on Kyber KEM. We target leakage of the pointwise multiplication operation in the decryption procedure to carry out practical blind side-channel attacks resulting in full key recovery. We perform practical validation of our attack using power side-channel from the reference implementation of Kyber KEM taken from the pqm4 library, implemented on the ARM Cortex-M4 microcontroller. Our experiments clearly indicate the feasibility of our proposed attack in recovering the full key in only a few hundred to few thousand traces, in the presence of a suitably accurate Hamming Weight (HW) classifier.

There are long line of researches on the fundamental distributed key generation (DKG) protocols. Unfortunately, all of them suffer from a large cubic total communication, due to the fact that $O(n)$ participants need to {\em broadcast} to all $n$ participants. We introduce the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring $\widetilde{\mathcal{O}}(n^{2.5}\lambda)$ total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element. This property makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. Additionally, both DKG protocols straightforwardly imply an improved (single-shot) common coin protocol. At the core of our techniques, we develop a simple-yet-effective methodology via deterministic sharding that arbitrarily groups nodes into shards; and a new primitive called consortium-dealer secret sharing, to enable a shard of nodes to securely contribute a secret to the whole population only at the cost of one-dealer. We also formalize simulation-based security for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis for DKG. Those might be of independent interest.

In side-channel analysis (SCA), the success of an attack is largely dependent on the dataset sizes and the number of instances in each class. The generation of synthetic traces can help to improve attacks like profiling attacks. However, manually creating synthetic traces from actual traces is arduous. Therefore, automating this process of creating artificial traces is much needed. Recently, diffusion models have gained much recognition after beating another generative model known as Generative Adversarial Networks (GANs) in creating realistic images. We explore the usage of diffusion models in the domain of SCA. We proposed frameworks for a known mask setting and unknown mask setting in which the diffusion models could be applied. Under a known mask setting, we show that the traces generated under the proposed framework preserved the original leakage. Next, we demonstrated that the artificially created profiling data in the unknown mask setting can reduce the required attack traces for a profiling attack. This suggests that the artificially created profiling data from the trained diffusion model contains useful leakages to be exploited.

VOX is a UOV-like signature scheme submitted to Round 1 additional signatures of NIST PQC standardization process. In 2023 Furue and Ikematsu proposed a rectangular MinRank attack on VOX, resulting in the submitters changing their parameters to counter this attack. In this paper we propose a new type of MinRank attack called padded MinRank attack. We show that the attack is highly efficient in its running time, taking less than one minute to break eight of nine parameters and about eight hours for the remaining one. Therefore the parameters of VOX should be reexamined to ensure its safety.

A succinct non-interactive argument (SNARG) for $\mathsf{NP}$ allows a prover to convince a verifier that an $\mathsf{NP}$ statement $x$ is true with a proof of size $o(|x| + |w|)$, where $w$ is the associated $\mathsf{NP}$ witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for $\mathsf{NP}$ in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for $\mathsf{NP}$ from falsifiable assumptions. All previous SNARGs for $\mathsf{NP}$ in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).

Power-of-two cyclotomics is a popular choice when instantiating the BGV scheme because of its efficiency and compliance with the FHE standard. However, in power-of-two cyclotomics, the linear transformations in BGV bootstrapping cannot be decomposed into sub-transformations for acceleration with existing techniques. Thus, they can be highly time-consuming when the number of slots is large, degrading the advantage brought by the SIMD property of the plaintext space. By exploiting the algebraic structure of power-of-two cyclotomics, this paper derives explicit decomposition of the linear transformations in BGV bootstrapping into NTT-like sub-transformations, which are highly efficient to compute homomorphically. Moreover, multiple optimizations are made to evaluate homomorphic linear transformations, including modified BSGS algorithms, trade-offs between level and time, and specific simplifications for thin and general bootstrapping. We implement our method on HElib. With the number of slots ranging from 4096 to 32768, we obtain a 7.35x$\sim$143x improvement in the running time of linear transformations and a 4.79x$\sim$66.4x improvement in bootstrapping throughput, compared to previous works or the naive approach.

We continue the study of blockcipher-based (tweakable) correlation robust hash functions, which are central building blocks of circuit garbling and oblivious-transfer extension schemes. Motivated by Roy (CRYPTO 2022), we first enhance the multi-user tweakable correlation robust notion of Guo et al. (CRYPTO 2020) with a {\it key leaking oracle} that tells the adversary whether a certain user key satisfies the adversarially-chosen predicate. We then investigate the state-of-the-art hash construction of Guo et al. with respect to our new security definition, providing security proof as well as matching attacks. As an application, we exhibit an OT extension protocol with non-trivial multi-user security.

A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present Kaizen, a zkPoT targeted for deep neural networks (DNNs) that achieves the above ideals all at once. In particular, our construction enables a prover to iteratively train their model by the (mini-batch) gradient-descent algorithm where the number of iterations need not be fixed in advance; at the end of each iteration, the prover generates a commitment to the trained model attached with a succinct zkPoT, attesting to the correctness of the entire training process. The proof size and verifier time are independent of the iteration number. Kaizen relies on two essential building blocks to achieve both prover efficiency and verification succinctness. First, we construct an optimized GKR-style (sumcheck-based) proof system for the gradient-descent algorithm with concretely efficient prover cost; this scheme allows the prover to generate a proof for each iteration of the training process. Then, we recursively compose these proofs across multiple iterations to attain succinctness. As of independent interests, we propose a framework for recursive composition of GKR-style proofs and techniques, such as aggregatable polynomial commitment schemes, to minimize the recursion overhead. Benchmarks indicate that Kaizen can handle a large model of VGG-$11$ with $10$ million parameters and batch size $16$. The prover runtime is $22$ minutes (per iteration), which is $\mathbf{43\times}$ faster than generic recursive proofs, while we further achieve at least $\mathbf{224 \times}$ less prover memory overhead. Independent of the number of iterations and, hence, the size of the dataset, the proof size is $1.36$ megabytes, and the verifier runtime is only $103$ milliseconds.

Matrix multiplication is a common operation in applications like machine learning and data analytics. To demonstrate the correctness of such an operation in a privacy-preserving manner, we propose zkMatrix, a zero-knowledge proof for the multiplication of committed matrices. Among the succinct non-interactive zero-knowledge protocols that have an $O(\log n)$ transcript size and $O(\log n)$ verifier time, zkMatrix stands out as the first to achieve $O(n^2)$ prover time and $O(n^2)$ RAM usage for multiplying two $n \times n$ matrices. Significantly, zkMatrix distinguishes itself as the first zk-SNARK protocol specifically designed for matrix multiplication. By batching multiple proofs together, each additional matrix multiplication only necessitates $O(n)$ group operations in prover time.

To improve the throughput of Byzantine Fault Tolerance (BFT) consensus protocols, the Directed Acyclic Graph (DAG) topology has been introduced to parallel data processing, leading to the development of DAG-based BFT consensus. However, existing DAG-based works heavily rely on Reliable Broadcast (RBC) protocols for block broadcasting, which introduces significant latency due to the three communication steps involved in each RBC. For instance, DAGRider, a representative DAG-based protocol, exhibits a best latency of 12 steps, considerably higher than non-DAG protocols like PBFT, which only requires 3 steps. To tackle this issue, we propose LightDAG, which replaces RBC with lightweight broadcasting protocols such as Consistent Broadcast (CBC) and Plain Broadcast (PBC). Since CBC and PBC can be implemented in two and one communication steps, respectively, LightDAG achieves low latency. In our proposal, we present two variants of LightDAG, namely LightDAG1 and LightDAG2, each providing a trade-off between the best latency and the expected worst latency. In LightDAG1, every block is broadcast using CBC, which exhibits a best latency of 5 steps and an expected worst latency of 14 steps. Since CBC cannot guarantee the totality property, we design a block retrieval mechanism in LightDAG1 to assist replicas in retrieving missing blocks. LightDAG2 utilizes a combination of PBC and CBC for block broadcasting, resulting in a best latency of 4 steps and an expected worst latency of $12(t+1)$ steps, where $t$ represents the number of actual Byzantine replicas. Since a Byzantine replica may equivocate through PBC, LightDAG2 prohibits blocks from directly referencing contradictory blocks. To ensure liveness, we propose a mechanism to identify and exclude Byzantine replicas if they engage in equivocation attacks. Extensive experiments have been conducted to evaluate LightDAG, and the results demonstrate its feasibility and efficiency.

Secure merge considers the problem of combining two sorted lists into a single sorted secret-shared list. Merge is a fundamental building block for many real-world applications. For example, secure merge can implement a large number of SQL-like database joins, which are essential for almost any data processing task such as privacy-preserving fraud detection, ad conversion rates, data deduplication, and many more. We present two constructions with communication bandwidth and rounds tradeoff. Logstar, our bandwidth-optimized construction, takes inspiration from Falk and Ostrovsky (ITC, 2021) and runs in $O(n\log^*n)$ time and communication with $O(\log n)$ rounds. In particular, for all conceivable $n$, the $\log^*n$ factor will be equal to the constant $2$, and therefore we achieve a near-linear running time. Median, our rounds-optimized construction, builds on the classic parallel medians-based insecure merge approach of Valiant (SIAM J. Comput., 1975), later explored in the secure setting by Blunk et al. (2022), and requires $O(n \log^c n)$, $1<c<2$, communication with $O(\log \log n)$ rounds. We introduce two additional constructions that merge input lists of different sizes. SquareRootMerge, merges lists of sizes $n^{\frac{1}{2}}$ and $n$, and runs in $O(n)$ time and communication with $O(\log n)$ rounds. CubeRootMerge is closely inspired by Blunk et al.'s (2022) construction and merges lists of sizes $n^{\frac{1}{3}}$ and $n$. It runs in $O(n)$ time and communication with $O(1)$ rounds. We optimize our constructions for concrete efficiency. Today, concretely efficient secure merge protocols rely on standard techniques such as GMW or generic sorting. These approaches require an $O(n \log n)$ size circuit of $O(\log n)$ depth. In contrast, our constructions are more efficient and also achieve superior asymptotics. We benchmark our constructions and obtain significant improvements. For example, Logstar reduces bandwidth costs $\approx 3.3\times$ and Median reduces rounds $\approx2.22\times$.

Threshold symmetric encryption (TSE), introduced by Agrawal et al. [DiSE, CCS 2018], provides scalable and decentralized solution for symmetric encryption by ensuring that the secret-key stays distributed at all times. They avoid having a single point of attack or failure, while achieving the necessary security requirements. TSE was further improved by Christodorescu et al. [ATSE, CCS 2021] to support an amortization feature which enables a “more privileged” client to encrypt records in bulk by interacting only once with the key servers, while decryption must be performed individually for each record, potentially by a “less privileged” client. However, typical enterprises collect or generate data once and query it several times over its lifecycle in various data processing pipelines; i.e., enterprise workloads are often decryption heavy! ATSE does not meet the bar for this setting because of linear interaction / computation (in the number of records to be decrypted) – our experiments show that ATSE provides a sub-par throughput of a few hundred records / sec. We observe that a large class of queries read a subsequence of records (e.g. a time window) from the database. With this access structure in mind, we build a new TSE scheme which allows for both encryption and decryption with flexible granularity, in that a client’s interactions with the key servers is at most logarithmic in the number of records. Our idea is to employ a binary-tree access structure over the data, where only one interaction is needed to decrypt all ciphertexts within a sub-tree, and thus only log-many for any arbitrary size sub-sequence. Our scheme incorporates ideas from binary-tree encryption by Canetti et al. [Eurocrypt 2003] and its variants, and carefully merges that with Merkle-tree commitments to fit into the TSE setting. We formalize this notion as hierarchical threshold symmetric-key encryption (HiSE), and argue that our construction satisfies all essential TSE properties, such as correctness, privacy and authenticity with respect to our definition. Our analysis relies on a well-known XDH assumption and a new assumption, that we call $\ell$-masked BDDH, over asymmetric bilinear pairing in the programmable random oracle model. We also show that our new assumption does hold in generic group model. We provide an open-source implementation of HiSE. For practical parameters, we see 65$\times$ improvement in latency and throughput over ATSE. HiSE can decrypt over 6K records / sec on server-grade hardware, but the logarithmic overhead in HiSE’s encryption (not decryption) only lets us encrypt up to 3K records / sec (about 3-4.5$\times$ slowdown) and incurs roughly 500 bytes of ciphertext expansion per record – while reducing this penalty is an important future work, we believe HiSE can offer an acceptable tradeoff in practice.

Almost all practical cryptographic protocols are based on computational or ad-hoc assumptions. Assessing the strengths of these assumptions is therefore a key factor in evaluating the risks of the systems using them. As a service to (and by) cryptographic researchers and practitioners, we developed Delphi, an online questionnaire to document researchers' opinions and beliefs about the strengths of the most important assumptions. All responses received will be made accessible on our website, ideally non-anonymous (but depending on the contributor's preference). We also intend to consolidate these responses and publish the results. We believe this effort will be of great value when deciding which cryptographic primitives to keep or start using.

In the context of fully-homomorphic-encryption, we consider the representation of large integers by their decomposition over a product of rings (through the Chinese Remainder Theorem) and introduce a new algorithm for the determination of the sign solely through the knowledge of ring-components. We then prove that our algorithm delivers a correct result with a very high probability.

At the core of fully homomorphic encryption lies a procedure to refresh the ciphertexts whose noise component has grown too big. The efficiency of the so-called bootstrap is of paramount importance as it is usually regarded as the main bottleneck towards a real-life deployment of fully homomorphic crypto-systems. In two of the fastest implementations so far, the space of messages is limited to binary integers. If the message space is extended to the discretized torus $T_{p_i}$ or equivalently to $Z_{p_i}$ with values of $p_i$ large as compared to the dimension of the quotient ring in which the operations are realised, the bootstrap delivers incorrect results with far too high probability. As a consequence, the use of a residue numeral system to address large integers modulo $p=p_1 \times \ldots \times p_\kappa$ would be of limited interest in practical situations without the following remedy: rather than increasing the polynomial degree and thus the computational cost, we introduce here a novel and simple technique (hereafter referred to as ``collapsing") which, by grouping the components of the mask, attenuates both rounding errors and computational costs, and greatly helps to sharpen the correctness of the bootstrap. We then rigorously estimate the probability of success as well as the output error and determine practical parameters to reach a given correctness threshold.

The problem of Broadcast Encryption (BE) consists in broadcasting an encrypted message to a large number of users or receiving devices in such a way that the emitter of the message can control which of the users can or cannot decrypt it. Since the early 1990's, the design of BE schemes has received significant interest and many different concepts were proposed. A major breakthrough was achieved by Naor, Naor and Lotspiech (CRYPTO 2001) by partitioning cleverly the set of authorized users and associating a symmetric key to each subset. Since then, while there have been many advances in public-key based BE schemes, mostly based on bilinear maps, little was made on symmetric cryptography. In this paper, we design a new symmetric-based BE scheme, named $\Sigma\Pi$BE, that relies on logic optimization and consensual security assumptions. It is competitive with the work of Naor et al. and provides a different tradeoff: the bandwidth requirement is significantly lowered at the cost of an increase in the key storage.

Numerous algorithms in homomorphic encryption require an operation that moves the slots of a ciphertext to the coefficients of a different ciphertext. We describe an FFT-like method for decomposing this slot-to-coefficient transformation (and its inverse) for BGV and BFV. The proposed method is specific to power-of-two cyclotomic rings and can handle both fully and sparsely packed slots. Previously, such a method was only known for non-power-of-two cyclotomic rings. Our algorithm admits more freedom in the complexity-depth trade-off than prior works. Moreover, it brings down the computational complexity of the slot-to-coefficient transformation from a linear to a logarithmic number of FHE operations in the best case, which is shown via a detailed complexity analysis. We also provide a proof-of-concept implementation in the Magma bootstrapping library.

This paper focuses on equivalences between Generalised Feistel Networks (GFN) of type-II. We introduce a new definition of equivalence which captures the concept that two GFNs are identical up to re-labelling of the inputs/outputs, and give a procedure to test this equivalence relation. Such two GFNs are therefore cryptographically equivalent for several classes of attacks. It induces a reduction of the space of possible GFNs: the set of the $(k!)^2$ possible even-odd GFNs with $2k$ branches can be partitioned into $k!$ different classes. This result can be very useful when looking for an optimal GFN regarding specific computationally intensive properties, such as the minimal number of active S-boxes in a differential trail. We also show that in several previous papers, many GFN candidates are redundant as they belong to only a few classes. Because of this reduction of candidates, we are also able to suggest better permutations than the one of WARP: they reach 64 active S-boxes in one round less and still have the same diffusion round that WARP. Finally, we also point out a new family of permutations with good diffusion properties.

In some linear key recovery attacks, the function which determines the value of the linear approximation from the plaintext, ciphertext and key is replaced by a similar map in order to improve the time or memory complexity at the cost of a data complexity increase. We propose a general framework for key recovery map substitution, and introduce Walsh spectrum puncturing, which consists of removing carefully-chosen coefficients from the Walsh spectrum of this map. The capabilities of this technique are illustrated by describing improved attacks on reduced-round Serpent (including the first 12-round attack on the 192-bit key variant), GIFT-128 and NOEKEON, as well as the full DES.

Learning with Errors (LWE) is a hard math problem underlying post-quantum cryptography (PQC) systems for key exchange and digital signatures, recently standardized by NIST. Prior work [Wenger et al., 2022; Li et al., 2023a;b] proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods—better pre-processing, angular embeddings and model pre-training—to improve these attacks, speeding up preprocessing by 25× and improving model sample efficiency by 10×. We demonstrate for the first time that pre-training improves and reduces the cost of ML attacks on LWE. Our architecture improvements enable scaling to larger-dimension LWE problems: this work is the first instance of ML attacks recovering sparse binary secrets in dimension n = 1024, the smallest dimension used in practice for homomorphic encryption applications of LWE where sparse binary secrets are proposed.

Speculative out-of-order execution is a strategy of masking execution latency by allowing younger instructions to execute before older instructions. While originally considered to be innocuous, speculative out-of-order execution was brought into the spotlight with the 2018 publication of the Spectre and Meltdown attacks. These attacks demonstrated that microarchitectural side channels can leak sensitive data accessed by speculatively executed instructions that are not part of the normal program execution. Since then, a significant effort has been vested in investigating how microarchitectural side channels can leak data from speculatively executed instructions and how to control this leakage. However, much less is known about how speculative out-of-order execution affects microarchitectural side-channel attacks. In this paper, we investigate how speculative out-of-order execution affects the Evict+Time cache attack. Evict+Time is based on the observation that cache misses are slower than cache hits, hence by measuring the execution time of code, an attacker can determine if a cache miss occurred during the execution. We demonstrate that, due to limited resources for tracking out-of-order execution, under certain conditions an attacker can gain more fine-grained information and determine whether a cache miss occurred in part of the executed code. Based on the observation, we design the Evict+Spec+Time attack, a variant of Evict+Time that can learn not only whether a cache miss occurred, but also in which part of the victim code it occurred. We demonstrate that Evict+Spec+Time is an order of magnitude more efficient than Evict+Time when attacking a T-table-based implementation of AES. We further show an Evict+Spec+Time attack on an S-box-based implementation of AES, recovering the key with as little as 14389 decryptions. To the best of our knowledge, ours is the first successful Evict+Time attack on such a victim.

Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.

Fault injection attacks are a serious concern for cryptographic hardware. Adversaries may extract sensitive information from the faulty output that is produced by a cryptographic circuit after actively disturbing its computation. Alternatively, the information whether an output would have been faulty, even if it is withheld from being released, may be exploited. The former class of attacks, which requires the collection of faulty outputs, such as Differential Fault Analysis (DFA), then either exploits some knowledge about the position of the injected fault or about its value. The latter class of attacks, which can be applied without ever obtaining faulty outputs, such as Statistical Ineffective Fault Attacks (SIFA), then either exploits a dependency between the effectiveness of the fault injection and the value to be faulted (e.g., an LSB stuck-at-0 only affecting odd numbers), denoted as SIFA-1, or a conditional propagation of a faulted value based on a sensitive intermediate (e.g., multiplication of a faulted value by 0 prevents propagation), denoted as SIFA-2. The aptitude of additive masking schemes, which were designed to prevent side-channel analysis, to also thwart fault attacks is typically assumed to be limited. Common fault models, such as toggle/bit-flip, stuck-at-0 or stuck-at-1 survive the recombination of Boolean shares well enough for generic attacks to succeed. More precisely, injecting a fault into one or multiple Boolean shares often results in the same, or at least a predictable, error appearing in the sensitive variable after recombination. In this work, we show that additive masking in prime-order fields breaks such relationships, causing frequently exploited biases to decrease exponentially in the number of shares. As a result, prime masking offers surprisingly strong protection against generic statistical attacks, which require a dependency between the effectiveness of an injected fault and the secret variable that is manipulated, such as SIFA-1. Operation-dependent statistical attacks, such as SIFA-2 and Fault Template Attacks (FTA), may still be performed against certain prime-field structures, even if they are masked with many shares. Yet, we analyze the corresponding cases and are able to provide specific guidelines on how to avoid vulnerabilities either at the cipher design or implementation level by making informed decisions about the primes, non-linear mappings and masked gadgets used. Since prime-field masking appears to be one of the rare instances of affordable countermeasures that naturally provide sound protection against sidechannel analysis and certain fault injection attacks, we believe there is a strong incentive for developing new ciphers to leverage these advantages.

This work introduces several algorithms related to the computation of orientations in endomorphism rings of supersingular elliptic curves. This problem boils down to representing integers by ternary quadratic forms, and it is at the heart of several results regarding the security of oriented-curves in isogeny-based cryptography. Our main contribution is to show that there exists efficient algorithms that can solve this problem for quadratic orders of discriminant $n$ up to $O(p^{4/3})$. Our approach improves upon previous results by increasing this bound from $O(p)$ to $O(p^{4/3})$ and removing some heuristics. We introduce several variants of our new algorithm and provide a careful analysis of their asymptotic running time (without heuristic when it is possible). The best proven asymptotic complexity of one of our variant is $O(n^{3/4}/p)$ in average. The best heuristic variant has a complexity of $O(p^{1/3})$ for big enough $n$. We then introduce several results regarding the computation of ideals between oriented orders. The first application of this is a simplification of the known reduction from vectorization to computing the endomorphism ring, removing the assumption on the factorization of the discriminant. As a second application, we relate the problem of computing fixed-degree isogenies between supersingular curves to the problem of computing orientations in endomorphism rings, and we show that for a large range of degree $d$, our new algorithms improve on the state-of-the-art, and in important special cases, the range of degree $d$ for which there exist a polynomial-time algorithm is increased. In the most special case we consider, when both curves are oriented by a small degree endomorphism, we show heuristically that our techniques allow the computation of isogenies of any degree, assuming they exist.

A Proof of Exponentiation (PoE) allows a prover to efficiently convince a verifier that $y=x^e$ in some group of unknown order. PoEs are the basis for practical constructions of Verifiable Delay Functions (VDFs), which, in turn, are important for various higher-level protocols in distributed computing. In applications such as distributed consensus, many PoEs are generated regularly, motivating protocols for secure aggregation of batches of statements into a few statements to improve the efficiency for both parties. Rotem (TCC 2021) recently presented two such generic batch PoEs. In this work, we introduce two batch PoEs that outperform both proposals of Rotem and we evaluate their practicality. First, we show that the two batch PoEs of Rotem can be combined to improve the overall efficiency by at least a factor of two. Second, we revisit the work of Bellare, Garay, and Rabin (EUROCRYPT 1998) on batch verification of digital signatures and show that, under the low order assumption, their bucket test can be securely adapted to the setting of groups of unknown order. The resulting batch PoE quickly outperforms the state of the art in the expected number of group multiplications with the growing number of instances, and it decreases the cost of batching by an order of magnitude already for hundreds of thousands of instances. Importantly, it is the first batch PoE that significantly decreases both the proof size and complexity of verification. Our experimental evaluations show that even a non-optimized implementation achieves such improvements, which would match the demands of real-life systems requiring large-scale PoE processing. Finally, even though our proof techniques are conceptually similar to Rotem, we give an improved analysis of the application of the low order assumption towards secure batching of PoE instances, resulting in a tight reduction, which is important when setting the security parameter in practice.

We give an alternative derivation of (N,N)-isogenies between fast Kummer surfaces which complements existing works based on the theory of theta functions. We use this framework to produce explicit formulae for the case of N = 3, and show that the resulting algorithms are more efficient than all prior (3,3)-isogeny algorithms.

The notion of collaborative zk-SNARK is introduced by Ozdemir and Boneh (USENIX 2022), which allows multiple parties to jointly create a zk-SNARK proof over distributed secrets (also known as the witness). This approach ensures the privacy of the witness, as no corrupted servers involved in the proof generation can learn anything about the honest servers' witness. Later, Garg et al. continued the study, focusing on how to achieve faster proof generation (USENIX 2023). However, their approach requires a powerful server that is responsible for the most resource-intensive computations and communications during the proof generation. This requirement results in a scalability bottleneck, making their protocols unable to handle large-scale circuits. In this work, we address this issue by lifting a zk-SNARK called Libra (Crypto 2019) to a collaborative zk-SNARK and achieve a fully distributed proof generation, where all servers take roughly the same portion of the total workload. Further, our protocol can be adapted to be secure against a malicious adversary by incorporating some verification mechanisms. With 128 consumer machines and a 4Gbps network, we successfully generate a proof for a data-parallel circuit containing $2^{23}$ gates in merely 2.5 seconds and take only 0.5 GB memory for each server. This represents a $19\times$ speed-up, compared to a local Libra prover. Our benchmark further indicates an impressive 877$\times$ improvement in running time and a 992$\times$ enhancement in communication compared to the implementation in previous work. Furthermore, our protocol is capable of handling larger circuits, making it scalable in practice.

To enable parallel processing, the Directed Acyclic Graph (DAG) structure is introduced to the design of asynchronous Byzantine Fault Tolerant (BFT) consensus protocols, known as DAG-based BFT. Existing DAG-based BFT protocols operate in successive waves, with each wave containing three or four Reliable Broadcast (RBC) rounds to broadcast data, resulting in high latency due to the three communication steps required in each RBC. For instance, Tusk, a state-of-the-art DAG-based BFT protocol, has a good-case latency of 7 communication steps and an expected worst latency of 21 communication steps. To reduce latency, we propose GradedDAG, a new DAG-based BFT consensus protocol based on our adapted RBC called Graded RBC (GRBC) and the Consistent Broadcast (CBC), with each wave consisting of only one GRBC round and one CBC round. Through GRBC, a replica can deliver data with a grade of 1 or 2, and a non-faulty replica delivering the data with grade 2 can ensure that more than 2/3 of replicas have delivered the same data. Meanwhile, through CBC, data delivered by different non-faulty replicas must be identical. In each wave, a block in the GRBC round will be elected as the leader. If a leader block has been delivered with grade 2, it and all its ancestor blocks can be committed. GradedDAG offers a good-case latency of 4 communication steps and an expected worst latency of 7.5 communication steps, significantly lower than the state-of-theart. Experimental results demonstrate GradedDAG’s feasibility and efficiency.

We implement a secure platform for statistical analysis over multiple organizations and multiple datasets. We provide a suite of protocols for different variants of JOIN and GROUP-BY operations. JOIN allows combining data from multiple datasets based on a common column. GROUP-BY allows aggregating rows that have the same values in a column or a set of columns, and then apply some aggregation summary on the rows (such as sum, count, median, etc.). Both operations are fundamental tools for relational databases. One example use case of our platform is in data marketing in which an analyst would join purchase histories and membership information, and then obtain statistics, such as "Which products were bought by people earning this much per annum?" Both JOIN and GROUP-BY involve many variants, and we design protocols for several common procedures. In particular, we propose a novel group-by-median protocol that has not been known so far. Our protocols rely on sorting protocols, and work in the honest majority setting and against malicious adversaries. To the best of our knowledge, this is the first implementation of JOIN and GROUP-BY protocols secure against a malicious adversary.

Adaptor signature is a novel cryptographic primitive which ties together the signature and the leakage of a secret value. It has become an important tool for solving the scalability and interoperability problems in the blockchain. Aumayr et al. (Asiacrypt 2021) recently provide the formalization of the adaptor signature and present a provably secure ECDSA-based adaptor signature, which requires zero-knowledge proof in the pre-signing phase to ensure the signer works correctly. However, the number of zero-knowledge proofs is linear with the number of participants. In this paper, we propose efficient ECDSA-based adaptor signature schemes and give security proofs based on ECDSA. In our schemes, the zero-knowledge proofs in the pre-signing phase can be generated in a batch and offline. Meanwhile, the online pre-signing algorithm is similar to the ECDSA signing algorithm and can enjoy the same efficiency as ECDSA. In particular, considering specific verification scenarios, such as (batched) atomic swaps, our schemes can reduce the number of zero-knowledge proofs in the pre-signing phase to one, independent of the number of participants. Last, we conduct an experimental evaluation, demonstrating that the performance of our ECDSA-based adaptor signature reduces online pre-signing time by about 60% compared with the state-of-the-art ECDSA-based adaptor signature.