In this note we explain how to compute n KZG proofs for a polynomial of degree d in time superlinear of (n+d). Our technique is used in lookup arguments and vector commitment schemes.

Polynomial commitment schemes (PCS) have recently been in the spotlight for their key role in building SNARKs. A PCS provides the ability to commit to a polynomial over a finite field and prove its evaluation at points. A succinct PCS has commitment and evaluation proof size sublinear in the degree of the polynomial. An efficient PCS has sublinear proof verification. Any efficient and succinct PCS can be used to construct a SNARK with similar security and efficiency characteristics (in the random oracle model).

Proof-carrying data (PCD) enables a set of parties to carry out an indefinitely long distributed computation where every step along the way is accompanied by a proof of correctness. It generalizes incrementally verifiable computation and can even be used to construct SNARKs. Until recently, however, the only known method for constructing PCD required expensive SNARK recursion. A system called Halo first demonstrated a new methodology for building PCD without SNARKs, exploiting an aggregation property of the Bulletproofs innerproduct argument. The construction was heuristic because it makes non-black-box use of a concrete instantiation of the Fiat-Shamir transform. We expand upon this methodology to show that PCD can be (heuristically) built from any homomorphic polynomial commitment scheme (PCS), even if the PCS evaluation proofs are neither succinct nor efficient. In fact, the Halo methodology extends to any PCS that has an even more general property, namely the ability to aggregate linear combinations of commitments into a new succinct commitment that can later be opened to this linear combination. Our results thus imply new constructions of SNARKs and PCD that were not previously described in the literature and serve as a blueprint for future constructions as well.

An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs and give a construction from constant-sized polynomial commitments. Our construction is unique in that it has linear-sized public parameters, it can compute all constant-sized proofs in quasilinear time, it updates proofs in constant time and it can aggregate multiple proofs into a constant-sized subvector proof. Furthermore, our concrete proof sizes are small due to our use of pairing-friendly groups. We use our aSVC to obtain a payments-only stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block's proof overhead to a single group element, which is optimal. Furthermore, our subvector proofs speed up block verification and our smaller public parameters further reduce block size.

We present an enhanced version of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG10] where a single group element can be an opening proof for multiple polynomials each evaluated at a different arbitrary subset of points.

As a sample application we “plug in” this scheme into the PLONK proving system[GWC19] to obtain improved proof size and prover run time at the expense of additional verifier G2 operations and pairings, and additional G2 SRS elements.

We also present a second scheme where the proof consists of two group elements and the verifier complexity is better than previously known batched verification methods for [KZG10].

We present Origami verifiable delay function, build from the MinRoot hash and our dedicated plonk proof system that utilizes a tailored custom gate and a folding scheme. MinRoot VDF is the leading candidate for Ethereum adoption. For N iterations of MinRoot hash function, the overall cost of Origami is N +o(N ) group operations; improving the previous best known result of 6N from a Nova based solution. The proof size is 128k + 224 bytes if we fold the proofs for k times; and may be further reduce to around 960 bytes, regardless of k, via a standard recursive prover.

We present $\mathsf{Bingo}$, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets with a total communication complexity of $O(\lambda n^2)$ words, where $\lambda$ is the security parameter and $n$ is the number of parties.

Using $\mathsf{Bingo}$, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time, which we in turn use to construct an adaptively secure high-threshold asynchronous distributed key generation (ADKG) protocol that uses $O(\lambda n^3)$ expected words and constant expected time.

To the best of our knowledge, our ADKG is the first to allow for an adaptive adversary while matching the asymptotic complexity of the best known static ADKGs.

We present a candidate sequential function for a VDF protocol to be used within the Ethereum ecosystem. The new function, called MinRoot, is an optimized iterative algebraic transformation and is a strict improvement over competitors VeeDo and Sloth++. We analyze various attacks on sequentiality and suggest weakened versions for public scrutiny. We also announce bounties on certain research directions in cryptanalysis.

We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand $f \leq n/3$ faulty parties), has a constant expected number of rounds, has $\tilde{\mathcal{O}}(n^3)$ expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required $\Omega(n)$ expected number of rounds, and $\Omega(n^4)$ expected communication.

Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $\mathcal{O}(n^2)$ to $\mathcal{O}(n \log n)$, where n denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. Finally, we experimentally evaluate our DKG and show that the perparty overheads scale linearly and are practical. For 64 parties, it takes 71 ms to share and 359 ms to verify the overall transcript, while for 8192 parties, it takes 8 s and 42.2 s respectively.

We present two new Verifiable Delay Functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and some drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.

Verifiable Random Functions (VRFs) play a key role in Proof-of-Stake blockchains such as Algorand to achieve highly scalable consensus, but currently deployed VRFs lack post-quantum security, which is crucial for future-readiness of blockchain systems. This work presents the first quantum-safe VRF scheme based on symmetric primitives. Our main proposal is a practical many-time quantum-safe VRF construction, X-VRF, based on the XMSS signature scheme. An innovation of our work is to use the state of the blockchain to counter the undesired stateful nature of XMSS by constructing a blockchain-empowered VRF. While increasing the usability of XMSS, our technique also enforces honest behavior when creating an X-VRF output so as to satisfy the fundamental uniqueness property of VRFs. We show how X-VRF can be used in the Algorand setting to extend it to a quantum-safe blockchain and provide four instances of X-VRF with different key life-time. Our extensive performance evaluation, analysis and implementation indicate the effectiveness of our proposed constructions in practice. Particularly, we demonstrate that X-VRF is the most efficient quantum-safe VRF with a maximum proof size of 3 KB and a possible TPS of 449 for a network of thousand nodes.

We present "Baloo", the first protocol for lookup tables where the prover work is linear on the amount of lookups and independent of the size of the table. "Baloo" is built over the lookup arguments of Caulk and Caulk+, and the framework for linear relations of Ràfols and Zapico.

Our protocol supports commit-and-prove expansions: the prover selects the subtable containing the elements used in the lookup, that is unknown to the verifier, commits to it and later prove relation with the committed element. This feature makes "Baloo" especially suitable for prover input-output relations on hash functions, and in particular to instantiate the Ethereum Virtual Machine (EVM).

We provide an implementation of Baloo, as well as benchmarks for comparison with existing protocols.

We present two protocols for checking the values of a committed polynomial $\phi (X)$ over a mutliplicative subgroup $H \subset \mathbb{F}$ of size $m$ are contained in a table $T\in \mathbb{F}^N$. After a preprocessing step, the prover algorithm runs in time $O(m\log ^2 m)$. This improves a recent result of Caulk+[PK22] for the same problem with run time $O(m^2)$, that in turn improved another recent result with run time $O(m^2+m\log N)$ Caulk[ZBK+22]. We pose further improving this complexity to $O(m\log m)$ as the next important milestone for efficient zk-SNARK lookups.

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or $m$ values that comprise commitment $\textsf{cm}$ all belong to the vector of size $N$ committed to in $\C$. Our construction $\textsf{Caulk}$ can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude.

For both single- and multi-membership proofs the $\textsf{Caulk}$ protocol beats SNARKed Merkle proofs by the factor of 100 even if the latter is instantiated with Poseidon hash. Asymptotically our prover needs $O(m^2 + m\log N)$ time to prove a batch of $m$ openings, whereas proof size is $O(1)$ and verifier time is $O(\log(\log N))$.

As a lookup argument, $\textsf{Caulk}$ is the first scheme with prover time sublinear in the table size, assuming $O(N\log N)$ preprocessing time and $O(N)$ storage. It can be used as a subprimitive in verifiable computation schemes in order to drastically decrease the lookup overhead.

Our scheme comes with a reference implementation and benchmarks.

Zero-knowledge blocklists allow cross-platform blocking of users but, counter-intuitively, do not link users identities inter- or intra-platform, or to the fact they were blocked. Unfortunately, existing approaches (Tsang et al. '10) require that servers do work linear in the size of the blocklist for each verification of a non-membership proof.

We design and implement $\mathsf{SNARKBlock}$, a new protocol for zero-knowledge blocklisting with server-side verification that is logarithmic in the size of the blocklist. $\mathsf{SNARKBlock}$ is also the first approach to support ad-hoc, federated blocklisting: websites can mix and match their own blocklists from other blocklists and dynamically choose which identity providers they trust.

Our core technical advance, of separate interest, is the $\mathsf{HICIAP}$ zero-knowledge proof system, which addresses a common problem in privacy-preserving protocols: using zero-knowledge proofs for repeated but unlinkable interactions. Rerandomzing a Groth16 proof achieves unlinkability without the need to recompute the proof for every interaction. But this technique does not apply to applications where each interaction includes multiple Groth16 proofs over a common hidden input (e.g., the user's identity). Here, the best known approach is to commit to the hidden input and feed it to each proof, but this creates a persistent identifier, forcing recomputation. $\mathsf{HICIAP}$ resolves this problem by aggregating $n$ Groth16 proofs into one $O(\log n)$-sized, $O(\log n)$-verification time proof which also shows that the input proofs share a hidden input. Because $\mathsf{HICIAP}$ is zero-knowledge, repeated shows of the same aggregate or an updated aggregate are unlinkable even though the underlying Groth16 proofs are never recomputed.

Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and efficiently verifiable proofs that do not reveal anything more than the correctness of the statement. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns.

A major drawback of such proof systems in practice is the requirement to run a trusted setup for the public parameters. Moreover, these parameters set an upper bound to the size of the computations or statements to be proven, which results in new scalability problems.

We design and implement SnarkPack, a new argument that further reduces the size of SNARK proofs by means of aggregation. Our goal is to provide an off-the-shelf solution that is practical in the following sense: (1) it is compatible with existing deployed SNARK systems, (2) it does not require any extra trusted setup. SnarkPack is designed to work with Groth16 scheme and has logarithmic size proofs and a verifier that runs in logarithmic time in the number of proofs to be aggregated. Most importantly, SnarkPack reuses the public parameters from Groth16 system.

SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 163ms, yielding a verification mechanism that is exponentially faster than other solutions. SnarkPack can be used in blockchain applications that rely on many SNARK proofs such as Proof-of-Space or roll-up solutions.

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of n source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by 6 log n target group exponentiations. Proofs are of size 6 log n target group elements, computed using 6n pairings and 4n exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification,$\mathcal{O}(\sqrt{d})$ prover complexity for degree $d$ polynomials (not including the cost to evaluate the polynomial), and a CRS of size $\mathcal{O}(\sqrt{d})$. Concretely, this means that for d = 228, producing an evaluation proof in our protocol is 76$\times$ faster than doing so in the KZG [KZG10] commitment scheme, and the CRS in our protocol is 1,000$\times$ smaller: 13MB vs 13GB for KZG. This gap only grows as the degree increases. Our polynomial commitment scheme is applicable to both univariate and bivariate polynomials.

As a second application, we introduce an argument for aggregating n Groth16 zkSNARKs into an $\mathcal{O}(\log n)$ sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition [BCGMMW20]: we can aggregate about 130,000 proofs in 25min, while in the same time recursive composition aggregates just 90 proofs.

Finally, we show how to apply our aggregation protocol to construct a low-memory SNARK for machine computations. For a computation that requires time T and space S, our SNARK produces proofs in space $\tilde{\mathcal{O}}(S + T)$, which is significantly more space efficient than a monolithic SNARK, which requires space $\tilde{\mathcal{O}}(S \cdot T)$.

Succinct non-interactive arguments of knowledge (SNARKs) have found numerous applications in the blockchain setting and elsewhere. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). Our contributions are two-fold:

– We give a security framework for non-interactive zero-knowledge arguments with a ceremony protocol.

– We revisit the ceremony protocol of Groth's SNARK [Bowe et al., 2017]. We show that the original construction can be simplified and optimized, and then prove its security in our new framework. Importantly, our construction avoids the random beacon model used in the original work.

The rising popularity of computational integrity protocols has led to an increased focus on efficient domain-specific hash functions, which are one of the core components in these use cases. For example, they are used for polynomial commitments or membership proofs in the context of Merkle trees. Indeed, in modern proof systems the computation of hash functions is a large part of the entire proof's complexity.

In the recent years, authors of these hash functions have focused on components which are verifiable with low-degree constraints. This led to constructions like Poseidon, Rescue, Griffin, Reinforced Concrete, and Tip5, all of which showed significant improvements compared to classical hash functions such as SHA-3 when used inside the proof systems.

In this paper, we focus on lookup-based computations, a specific component which allows to verify that a particular witness is contained in a lookup table. We work over 31-bit and 64-bit finite fields $\mathbb{F}_p$, both of which are used in various modern proof systems today and allow for fast implementations. We propose a new 2-to-1 compression function and a SAFE hash function, instantiated by the Monolith permutation. The permutation is significantly more efficient than its competitors, both in terms of circuit friendliness and plain performance, which has become one of the main bottlenecks in various use cases. This includes Reinforced Concrete and Tip5, the first two hash functions using lookup computations internally. Moreover, in Monolith we instantiate the lookup tables as functions defined over $\mathbb{F}_2$while ensuring that the outputs are still elements in $\mathbb{F}_p$. Contrary to Reinforced Concrete and Tip5, this approach allows efficient constant-time plain implementations which mitigates the risk of side-channel attacks potentially affecting competing lookup-based designs. Concretely, our constant time 2-to-1 compression function is faster than a constant time version of Poseidon2 by a factor of 7. Finally, it is also the first arithmetization-oriented function with a plain performance comparable to SHA3-256, essentially closing the performance gap between circuit-friendly hash functions and traditional ones.

We provide security foundations for SAFE, a recently introduced API framework for sponge-based hash functions tailored to prime-field-based protocols. SAFE aims to provide a robust and foolproof interface, has been implemented in the Neptune hash framework and some zero-knowledge proof projects, but currently lacks any security proof.

In this work we identify the SAFECore as versatile variant sponge construction underlying SAFE, we prove indifferentiability of SAFECore for all (binary and prime) fields up to around $|\mathbb{F}_p|^{c/2}$ queries, where $\mathbb{F}_p$ is the underlying field and $c$ the capacity, and we apply this security result to various use cases.

We show that the SAFE-based protocols of plain hashing, authenticated encryption, verifiable computation, non-interactive proofs, and commitment schemes are secure against a wide class of adversaries, including those dealing with multiple invocations of a sponge in a single application. Our results pave the way of using SAFE with the full taxonomy of hash functions, including SNARK-, lattice-, and x86-friendly hashes.

From hashing and commitment schemes to Fiat-Shamir and encryption, hash functions are everywhere in zero-knowledge proofsystems (ZKPs), and minor performance changes in ``vanilla'' implementations can translate in major discrepancies when the hash is processed as a circuit within the proofsystem.

Protocol designers have resorted to a number of techniques and custom modes to optimize hash functions for ZKPs settings, but so far without a single established, well-studied construction. To address this need, we define the Sponge API for Field Elements (SAFE), a unified framework for permutation-based schemes (including AEAD, Sigma, PRNGs, and so on). SAFE eliminates the performance overhead, is pluggable in any field-oriented protocol, and is suitable for any permutation algorithm.

SAFE is implemented in Filecoin's Neptune hash framework, which is our reference implementation (in Rust). SAFE is also being integrated in other prominent ZKP projects. This report specifies SAFE and describes some use cases.

Among other improvements, our construction is among the first to store the protocol metadata in the sponge inner part in a provably secure way, which may be of independent interest to the sponge use cases outside of ZKP.

Zero-knowledge proof systems for computational integrity have seen a rise in popularity in the last couple of years. One of the results of this development is the ongoing effort in designing so-called arithmetization-friendly hash functions in order to make these proofs more efficient. One of these new hash functions, Poseidon, is extensively used in this context, also thanks to being one of the first constructions tailored towards this use case. Many of the design principles of Poseidon have proven to be efficient and were later used in other primitives, yet parts of the construction have shown to be expensive in real-word scenarios.

In this paper, we propose an optimized version of Poseidon, called Poseidon2. The two versions differ in two crucial points. First, Poseidon is a sponge hash function, while Poseidon2 can be either a sponge or a compression function depending on the use case. Secondly, Poseidon2 is instantiated by new and more efficient linear layers with respect to Poseidon. These changes allow to decrease the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%. This makes Poseidon2 the currently fastest arithmetization-oriented hash function without lookups.

Besides that, we address a recently proposed algebraic attack and propose a simple modification that makes both Poseidon and Poseidon2 secure against this approach.

Note: Updated cryptanalysis results for the original Poseidon.

We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.

The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

We prove that this construction matches Stam’s bound, by providing $\tilde{\mathcal{O}}(q^2 / 2^n)$ collision security and $\mathcal{O}(q^3 / 2^{2n} + nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q \leq 2^{n/2}$). In particular, it provides birthday security for hashing 5 inputs using three 2n-to-n compression calls, instead of only 4 inputs in prior constructions.

Thus, we get a sequential variant of the Merkle-Damgard (MD) hashing, where t message blocks are hashed using only $3t/4$ calls to the 2n-to-n compression functions; a 25% saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using 3 (resp. 2) parallel execution units; saving a factor of 4 (resp. 2) over the traditional MD-hashing, where parallelism does not help to process one message.

We also get a novel variant of a Merkle tree, where t message blocks can be processed using 0.75($t$ − 1) compression function calls and depth $0.86 \log_2 t$, thereby saving 25% in the number of calls and 14% in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree.

For the aggressive variant, we reduce the proof length to a 29% overhead compared to Merkle trees ($1.29 \log_2 t$ vs $\log_2 t$), but the verification time is now 14% faster ($0.86 \log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid t-block message.

We prove adaptive security of a simple three-round threshold Schnorr signature scheme, which we call Sparkle. The standard notion of security for threshold signatures considers a static adversary – one who must declare which parties are corrupt at the beginning of the protocol. The stronger adaptive adversary can at any time corrupt parties and learn their state. This notion is natural and practical, yet not proven to be met by most schemes in the literature.

In this paper, we demonstrate that Sparkle achieves several levels of security based on different corruption models and assumptions. To begin with, Sparkle is statically secure under minimal assumptions: the discrete logarithm assumption (DL) and the random oracle model (ROM). If an adaptive adversary corrupts fewer than t/2 out of a threshold of t + 1 signers, then Sparkle is adaptively secure under a weaker variant of the one-more discrete logarithm assumption (AOMDL) in the ROM. Finally, we prove that Sparkle achieves full adaptive security, with a corruption threshold of t, under AOMDL in the algebraic group model (AGM) with random oracles. Importantly, we show adaptive security without requiring secure erasures. Ours is the first proof achieving full adaptive security without exponential tightness loss for any threshold Schnorr signature scheme; moreover, the reduction is tight.

Both threshold and blind signatures have, individually, received a considerable amount of attention. However, little is known about their combination, i.e., a threshold signature which is also blind, in that no coalition of signers learns anything about the message being signed or the signature being produced. Several applications of blind signatures (e.g., anonymous tokens) would benefit from distributed signing as a means to increase trust in the service and hence reduce the risks of key compromise. This paper builds the first blind threshold signatures in pairing-free groups. Our main contribution is a construction that transforms an underlying blind non-threshold signature scheme with a suitable structure into a threshold scheme, preserving its blindness.

The resulting signing protocol proceeds in three rounds, and produces signatures consisting of one group element and two scalars. The underlying non-threshold blind signature schemes are of independent interest, and improve upon the current state of the art (Tessaro and Zhu, EUROCRYPT ’22) with shorter signatures (three elements, instead of four) and simpler proofs of security. All of our schemes are proved secure in the Random Oracle and Algebraic Group Models, assuming the hardness of the discrete logarithm problem.

Given $\ell$ parties with sets $X_1, \ldots, X_{\ell}$ of size $n$, we would like to securely compute the intersection $\cap_{i=1}^{\ell} X_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $t$.

In this work, we construct protocols with a quasilinear dependency on $t$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $n-t$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $\mathcal{O}(\lambda \ell \cdot \mathsf{poly}(t))$, where $\lambda$ is the security parameter, and transforms it into a protocol with communication complexity $\mathcal{O}(\lambda^2 \ell t \cdot \mathsf{polylog}(t))$.

Threshold secret sharing allows a dealer to split a secret $s$ into $n$ shares, such that any $t$ shares allow for reconstructing $s$, but no $t-1$ shares reveal any information about $s$. Leakage-resilient secret sharing requires that the secret remains hidden, even when an adversary additionally obtains a limited amount of leakage from every share.

Benhamouda et al. (CRYPTO'18) proved that Shamir's secret sharing scheme is one bit leakage-resilient for reconstruction threshold $r \geq 0.85n$ and conjectured that the same holds for $t = cn$ for any constant $0 \leq c \leq 1$. Nielsen and Simkin (EUROCRYPT'20) showed that this is the best one can hope for by proving that Shamir's scheme is not secure against one-bit leakage when $t = c n / \log n$.

In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakage-resilience, where a random subset of leakages is replaced by uniformly random noise. We prove a lower bound for Shamir's secret sharing, similar to that of Nielsen and Simkin, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient sharing scheme. We then use this lower bound to show that there exist universal constants $c_1$, $c_2$, such that for infinitely many n, it holds that Shamir's secret sharing scheme is not noisy-leakage-resilient for $t \leq c_1 n / \log n$, even when a $c_2$ fraction of leakages are replaced by random noise.

We give a unified syntax, and a hierarchy of definitions of security of increasing strength, for non-interactive threshold signature schemes. These are schemes having a single-round signing protocol, possibly with one prior round of message-independent pre-processing.

We fit FROST1 and BLS, which are leading practical schemes, into our hierarchy, in particular showing they meet stronger security definitions than they have been shown to meet so far. We also fit in our hierarchy a more efficient version FROST2 of FROST1 that we give.

These definitions and results, for simplicity, all assume trusted key generation. Finally, we prove the security of FROST2 with key generation performed by an efficient distributed key generation protocol.

In this paper, we present new techniques for proving the security of multi- and threshold signature schemes under discrete logarithm assumptions in the random oracle model. The purpose is to provide a simple framework for analyzing the relatively complex interactions of these schemes in a concurrent model, thereby reducing the risk of attacks. We make use of proofs of possession and prove that a Schnorr signature suffices as a proof of possession in the algebraic group model without any tightness loss. We introduce and prove the security of a simple, three-round multisignature SimpleMuSig.

Using our new techniques, we prove the concurrent security of a variant of the MuSig2 multisignature scheme that includes proofs of possession as well as the FROST threshold signature scheme. These are currently the most efficient schemes in the literature for generating Schnorr signatures in a multiparty setting. Our variant of MuSig2, which we call SpeedyMuSig, has faster key aggregation due to the proofs of possession.

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

Property-preserving hash functions allow for compressing long inputs $x_0$ and $x_1$ into short hashes $h(x_0)$ and $h(x_1)$ in a manner that allows for computing a predicate $P(x_0, x_1)$ given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick $x_0$ and $x_1$ after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result.

In this work, we construct robust property-preserving hash functions for the hamming-distance predicate which distinguishes inputs with a hamming distance at least some threshold $t$. The security of the construction is based on standard lattice hardness assumptions. Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin (Eurocrypt 2021). Our construction relies on a single well-studied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions.

In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas the work of Fleischhacker and Simkin required several exponentiations per bit as well as the interpolation and evaluation of high-degree polynomials over large fields. An additional benefit of our construction is that the description of the hash function can be compressed to $\lambda$. Previous work has descriptions of length $\mathcal{O}(\ell \lambda)$ bits for input bit-length $\ell$.

We prove a lower bound on the output size of any property-preserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.

In this paper, we study the hybrid dual attack over Learning with Errors (LWE) problems for any secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that for most cryptographic use cases a hybrid dual attack outperforms a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of all LWE related proposals in round 3 of NIST's post-quantum cryptography process, and improve the state-of-the-art cryptanalysis results by 2-14 bits, under the BKZ-core-SVP model.

In [BS22], the authors proposed a lattice based hash function that is useful for building zero-knowledge proofs with superior performance. In this short note we analysis the underlying lattice problem with the classic shortest vector problem, and show that 2 out of 15 proposed parameter sets for this hash function do not achieve the claimed security.

Tensor core is a specially designed hardware included in new NVIDIA GPU chips, aimed at accelerating deep learning applications. With the introduction of tensor core, the matrix multiplication at low precision can be computed much faster than using conventional integer and floating point units in NVIDIA GPU. In the past, applications of tensor core were mainly restricted to machine learning and mixed precision scientific computing. In this paper, we show that for the first time, tensor core can be used to accelerate state-of-the-art lattice-based cryptosystems. In particular, we employed tensor core to accelerate NTRU, one of the finalists in NIST post-quantum standardization. Towards our aim, several parallel algorithms are proposed to allow the tensor core to handle flexible matrix sizes and ephemeral key pair. Experimental results show that the polynomial convolution using tensor core is 2.79× (ntruhps2048509) and 2.72× (ntruhps2048677) faster than the version implemented with conventional integer units of NVIDIA GPU. The proposed tensor core based polynomial convolution technique was applied to NTRU public key scheme (TensorTRU). It achieved 1.94×/1.95× (encryption) and 1.97×/2.02× (decryption) better performance for the two parameter sets, compared to the conventional integer based implementations in GPU. TensorTRU is also more than 20× faster than the reference implementation in CPU and 2× faster than the AVX2 implementation, for both encryption and decryption. To demonstrate the flexibility of the proposed technique, we have extended the implementation to other lattice-based cryptosystems that have a small modulus (LAC and two variant parameter sets in FrodoKEM). Experimental results show that the tensor core based polynomial convolution is flexible and useful in accelerating lattice-based cryptosystems that cannot utilize number theoretic transform in performing polynomial multiplication.

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega( n( \frac{ \log 1/\delta}{\log n} + 1) )$ space and they crucially rely on fully random hash functions.

We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}( n + \log(1 / \delta) \log\log(1 / \delta) )$ space and $\mathcal{O}( \log( \log( n ) / \delta ) )$-wise independent hash functions.

As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h: U \mapsto [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n / 2$ keys will have a unique hash value. Proving this is highly non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest.

A recent work of Fleischhacker, Larsen, and Simkin (Eurocrypt 2023) shows how to efficiently compress encrypted sparse vectors. Subsequently, Fleischhacker, Larsen, Obremski, and Simkin (Eprint 2023) improve upon their work and provide more efficient constructions solving the same problem. Being able to efficiently compress such vectors is very useful in a variety of applications, such as private information retrieval, searchable encryption, and oblivious message retrieval.

Concretely, assume one is given a vector $(m_1, \ldots, m_n)$ with at most $t$ distinct indices $i \in [n]$, such that $m_i \neq 0$ and assume $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ is an additively homomorphic encryption scheme. The authors show that one can compress $(\mathsf{Enc}(k, m_1), \ldots, \mathsf{Enc}(k, m_n))$, without knowing the secret key $k$, into a digest with size dependent on the upper bound on the sparsity $t$, but not on the total vector length $n$.

Unfortunately, all existing constructions either only work for encryption schemes that have sufficiently large plaintext spaces or require additional encrypted auxiliary information about the plaintext vector.

In this work, we show how to generalize the results of Fleischhacker, Larsen, and Simkin to encryption schemes with arbitrarily small plaintext spaces. Our construction follows the same general ideas laid out in previous works but modifies them in a way that allows compressing the encrypted vectors correctly with high probability, independently of the size of the plaintext space.

We study the task of obliviously compressing a vector comprised of $n$ ciphertexts of size $\xi$ bits each, where at most $t$ of the corresponding plaintexts are non-zero. This problem commonly features in applications involving encrypted outsourced storages, such as searchable encryption or oblivious message retrieval. We present two new algorithms with provable worst-case guarantees, solving this problem by using only homomorphic additions and multiplications by constants. Both of our new constructions improve upon the state of the art asymptotically and concretely.

Our first construction, based on sparse polynomials, is perfectly correct and the first to achieve an asymptotically optimal compression rate by compressing the input vector into $\mathcal{O}(t \xi)$. Compression can be performed homomorphically by performing $\mathcal{O}( n \log n)$ homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of $\Omega(\sqrt{n})$.

Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability $1 - 2^{-\kappa}$. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into $\mathcal{O}(\xi\kappa t / \log t)$ bits, where $\kappa \geq \log t$. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by $\mathcal{O}(n \kappa / \log t)$ homomorphic additions and multiplications by constants. The decompression complexity is dominated by $\mathcal{O}(\kappa t / \log t )$ decryption operations and equally many inversions of a pseudorandom permutation.

In this short note we explore a particular behaviour of the CSIDH key exchange that leads to a very special form of (shared) key control via the use of the quadratic twists. This peculiarity contained in CSIDH with regard to quadratic twists was already noted in the original CSDIH work and used in several subsequent papers but we believe spelling out this in the form of an attack might be useful to the wider community.

We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt'20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

In this short note, we introduce Bandersnatch, a new elliptic curve built over the BLS12-381 scalar field. The curve is equipped with an efficient endomorphism, allowing a fast scalar multiplication algorithm. Our benchmark shows that the multiplication is 42% faster, compared to another curve, called Jubjub, having similar properties. Nonetheless, Bandersnatch does not provide any performance improvement for either rank 1 constraint systems (R1CS) or multi scalar multiplications, compared to the Jubjub curve.

In this short note we analyze the low order assumption in the imaginary quadratic number fields. We show how this assumption is broken for Mersenne primes. We also provide a description on how to possible attack this assumption for other class of prime numbers leveraging some new mathematical tool coming from higher (cubic) number fields.