Identity-Based Encryption (IBE) was introduced in order to reduce the cost associated with Public Key Infrastructure systems. IBE allows users to request a trusted Key Generation Centre (KGC) for a secret key on a given identity, without the need to manage public keys. However, one of the main concerns of IBE is that the KGC has the power to decrypt all ciphertexts as it has access to all (identity, secret key) pairs. To address this issue, Chow (PKC 2009) introduced a new security property against the KGC by employing a new trusted party called the Identity Certifying Authority (ICA). Emura et al. (ESORICS 2019) formalized this notion and proposed construction in the random oracle model. In this work, we first identify several existing IBE schemes where the KGC can decrypt a ciphertext even without knowing the receiver's identity. This paves the way for formalizing new capabilities for the KGC. We then propose a new security definition to capture an adversarial KGC including the newly identified capabilities and we remove the requirement of an additional trusted party. Finally, we propose a new IBE construction that allows users to ask the KGC for a secret key on an identity without leaking any information about the identity to the KGC that is provably secure in the standard model against an adversarial KGC and corrupted users. Our construction is achieved in the composite order pairing groups and requires essentially optimal parameters.

Evaluating the security of LWE-based KEMs involves two crucial metrics: the hardness of the underlying LWE problem and resistance to decryption failure attacks, both significantly influenced by the secret key and error distributions. To mitigate the complexity and timing vulnerabilities of Gaussian sampling, modern LWE-based schemes often adopt either the uniform or centered binomial distribution (CBD). This work focuses on Kyber to evaluate its security under both distributions. Compared with the CBD, the uniform distribution over the same range enhances the LWE hardness but also increases the decryption failure probability, amplifying the risk of decryption failure attacks. We introduce a majority-voting-based key recovery method, and carry out a practical decryption failure attack on Kyber512 in this scenario with a complexity of $2^{37}$. Building on this analysis, we propose uKyber, a variant of Kyber that employs the uniform distribution and parameter adjustments under the asymmetric module-LWE assumption. Compared with Kyber, uKyber maintains comparable hardness and decryption failure probability while reducing ciphertext sizes. Furthermore, we propose a multi-value sampling technique to enhance the efficiency of rejection sampling under the uniform distribution. These properties make uKyber a practical and efficient alternative to Kyber for a wide range of cryptographic applications.

The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem. Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold. For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin. The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials also causes a jump in the security, resulting in parameters that are much bigger than what is needed. In this work, we explore the non-power-of-two instantiations of BGV. Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of ${m=2^s\cdot3^t}$ where $s,t\ge 1$, i.e., cyclotomic polynomials with degree ${n=\phi(m)=2^s\cdot3^{t-1}}$. We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms. We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.

We give a unified syntax, and a hierarchy of definitions of security of increasing strength, for non-interactive threshold signature schemes. They cover both fully non-interactive schemes (these are ones that have a single-round signing protocol, the canonical example being threshold-BLS) and ones, like FROST, that have a prior round of message-independent pre-processing. The definitions in the upper echelon of our hierarchy ask for security that is well beyond any currently defined, let alone proven to be met by the just-mentioned schemes, yet natural, and important for modern applications like securing digital wallets. We prove that BLS and FROST are better than advertised, meeting some of these stronger definitions. Yet, they fall short of meeting our strongest definition, a gap we fill for FROST via a simple enhancement to the scheme. We also surface subtle differences in the security achieved by variants of FROST.

Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Incidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver. With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23) introduced a new variant called non-interactive blind signatures (NIBS). These allow a signer to asynchronously generate partial signatures for any recipient such that only the intended recipient can extract a blinded signature for a random message. This bypasses the two-round barrier for traditional blind signatures, yet enables many known applications. Hanzlik provided new practical designs for NIBS from bilinear pairings. In this work, we propose new enhanced security properties for NIBS as well as provide multiple constructions with varying levels of security and concrete efficiency. We propose a new generic paradigm for NIBS from circuit-private leveled homomorphic encryption achieving optimal-sized signatures (i.e., same as any non-blind signature) at the cost of large public keys. We also investigate concretely efficient NIBS with post-quantum security, satisfying weaker level of privacy as proposed by Hanzlik.

The Deuring correspondence is a correspondence between supersingular elliptic curves and quaternion orders. Under this correspondence, an isogeny between elliptic curves corresponds to a quaternion ideal. This correspondence plays an important role in isogeny-based cryptography and several algorithms to compute an isogeny corresponding to a quaternion ideal (ideal-to-isogeny algorithms) have been proposed. In particular, SQIsign is a signature scheme based on the Deuring correspondence and uses an ideal-to-isogeny algorithm. In this paper, we propose a novel ideal-to-isogeny algorithm using isogenies of dimension $2$. Our algorithm is based on Kani's reducibility theorem, which gives a connection between isogenies of dimension $1$ and $2$. By using the characteristic $p$ of the base field of the form $2^fg - 1$ for a small odd integer $g$, our algorithm works by only $2$-isogenies and $(2, 2)$-isogenies in the operations in $\mathbb{F}_{p^2}$. We apply our algorithm to SQIsign and compare the efficiency of the new algorithm with the existing one. Our analysis shows that the key generation and the signing in our algorithm are at least twice as fast as those in the existing algorithm at the NIST security level 1. This advantage becomes more significant at higher security levels. In addition, our algorithm also improves the efficiency of the verification in SQIsign.

Mercurial signatures are an extension of equivalence class signatures that allow malleability for the public keys, messages, and signatures within the respective classes. Unfortunately, the most efficient construction to date suffers from a weak public key class-hiding property, where the original signer with the signing key can link the public keys in the same class. This is a severe limitation in their applications, where the signer is often considered untrustworthy of privacy. This paper presents two-party and multi-party interactive threshold mercurial signatures that overcome the above limitation by eliminating the single entity who knows the signing key. For the general case, we propose two constructions. The first follows the same interactive structure as the two-party case, avoiding complex distributed computations such as randomness generation, inversion, and multiplication, and even eliminates the need for private communication between parties. The second is based on a blueprint for general multi-party computation using verifiable secret sharing, but adopting optimizations. We show applications in anonymous credential systems that individually fit the two-party and multi-party constructions. In particular, in the two-party case, our approach provides stronger privacy by completely removing the trust in the authorities. We also discuss more applications, from blind signatures to multi-signatures and threshold ring signatures. Finally, to showcase the practicality of our approach, we implement our interactive constructions and compare them against related alternatives.

This paper initiates the study of one-more unforgeability for multi-signatures and threshold signatures as a stronger security goal, ensuring that ℓ executions of a signing protocol cannot result in more than ℓ signatures. This notion is widely used in the context of blind signatures, but we argue that it is a convenient way to model strong unforgeability for other types of distributed signing protocols. We provide formal security definitions for one-more unforgeability (OMUF) and show that the HBMS multi-signature scheme does not satisfy this definition, whereas MuSig and MuSig2 do. We also show that mBCJ multi-signatures do not satisfy OMUF, as well as expose a subtle issue with their existential unforgeability (which does not contradict their original security proof). For threshold signatures, we show that FROST satisfies OMUF, but ROAST does not.

We consider the problem of sampling random supersingular elliptic curves over finite fields of cryptographic size (SRS problem). The currently best-known method combines the reduction of a suitable complex multiplication (CM) elliptic curve and a random walk over some supersingular isogeny graph. Unfortunately, this method is not suitable when the endomorphism ring of the generated curve needs to be hidden, like in some cryptographic applications. This motivates a stricter version of the SRS problem, requiring that the sampling algorithm gives no information about the endomorphism ring of the output curve (cSRS problem). In this work we formally define the SRS and cSRS problems, which are both of theoretical interest. We discuss the relevance of the two problems for cryptographic applications, and we provide a self-contained survey of the known approaches to solve them. Those for the cSRS problem have exponential complexity in the characteristic of the base finite field (since they require computing and finding roots of polynomials of large degree), leaving the problem open. In the second part of the paper, we propose and analyse some alternative techniques – based either on the Hasse invariant or division polynomials – and we explain the reasons why they do not readily lead to efficient cSRS algorithms, but they may open promising research directions.

Multi-input Attribute-Based Encryption (ABE) is a generalization of key-policy ABE where attributes can be independently encrypted across several ciphertexts, and a joint decryption of these ciphertexts is possible if and only if the combination of attributes satisfies the policy of the decryption key. We extend this model by introducing a new primitive that we call Multi-Client ABE (MC-ABE), which provides the usual enhancements of multi-client functional encryption over multi-input functional encryption. Specifically, we separate the secret keys that are used by the different encryptors and consider the case that some of them may be corrupted by the adversary. Furthermore, we tie each ciphertext to a label and enable a joint decryption of ciphertexts only if all ciphertexts share the same label. We provide constructions of MC-ABE for various policy classes based on SXDH. Notably, we can deal with policies that are not a conjunction of local policies, which has been a limitation of previous constructions from standard assumptions. Subsequently, we introduce the notion of Multi-Client Predicate Encryption (MC-PE) which, in contrast to MC-ABE, does not only guarantee message-hiding but also attribute-hiding. We present a new compiler that turns any constant-arity MC-ABE into an MC-PE for the same arity and policy class. Security is proven under the LWE assumption.

We present Scloud+, an LWE-based key encapsulation mechanism (KEM). The key feature of Scloud+ is its use of the unstructured-LWE problem (i.e., without algebraic structures such as rings or modules) and its incorporation of ternary secrets and lattice coding to enhance performance. A notable advantage of the unstructured-LWE problem is its resistance to potential attacks exploiting algebraic structures, making it a conservative choice for constructing high-security schemes. However, a key disadvantage of such schemes is their limited computational and communication efficiency. Scloud+ utilizes ternary secrets and $\text{BW}_{32}$ lattice codes to enhance noise control and ensure robust error correction during decryption, enabling smaller parameters while maintaining low decryption failure probabilities. Equipped with these techniques, Scloud+ exhibits a significant improvement in efficiency. When compared with FrodoKEM for parameter sets targeting 128, 192, and 256 bits of security respectively, \lsc achieves practical performance with a public key size approximately $0.71 \sim 0.87$x and a ciphertext size approximately $0.56 \sim 0.78$x that of FrodoKEM. The encapsulation plus decapsulation time is approximately $0.74 \sim 0.77$x that of FrodoKEM.

One of the most crucial measures to maintain data security is the use of cryptography schemes and digital signatures built upon cryptographic algorithms. The resistance of cryptographic algorithms against conventional attacks is guaranteed by the computational difficulties and the immense amount of computation required to them. In the last decade, with the advances in quantum computing technology and the realization of quantum computers, which have higher computational power compared to conventional computers and can execute special kinds of algorithms (i.e., quantum algorithms), the security of many existing cryptographic algorithms has been questioned. The reason is that by using quantum computers and executing specific quantum algorithms through them, the computational difficulties of conventional cryptographic algorithms can be reduced, which makes it possible to overcome and break them in a relatively short period of time. Therefore, researchers began efforts to find new quantum-resistant cryptographic algorithms that would be impossible to break, even using quantum computers, in a short time. Such algorithms are called post-quantum cryptographic algorithms. In this article, we provide a comprehensive review of the challenges and vulnerabilities of different kinds of conventional cryptographic algorithms against quantum computers. Afterward, we review the latest cryptographic algorithms and standards that have been proposed to confront the threats posed by quantum computers. We present the classification of post-quantum cryptographic algorithms and digital signatures based on their technical specifications, provide examples of each category, and outline the strengths and weaknesses of each category.

In this paper, we present a generalization of Schnorr's digital signature that allows a user to simultaneously sign multiple messages. Compared to Schnorr's scheme that concatenates messages and then signs them, the new protocol takes advantage of multiple threads to process messages in parallel. We prove the security of our novel protocol and discuss different variants of it. Last but not least, we extend Ferradi et al.'s co-signature protocol by exploiting the inherent parallelism of our proposed signature scheme.

In this paper, we discuss what it means for a polynomial system to be random and how hard it is to solve a random polynomial system. We propose an algebraic definition of randomness, that we call algebraic randomness. Using a conjecture from commutative algebra, we produce a sharp upper bound for the degree of regularity, hence the complexity of solving an algebraically random polynomial system by Groebner bases methods. As a proof of concept, we apply our result to Rainbow and GeMSS and show that these systems are far from being algebraically random.

In 2016,Petit et al. first studied the implementation of the index calculus method on elliptic curves in prime finite fields, and in 2018, Momonari and Kudo et al. improved algorithm of Petit et al. This paper analyzes the research results of Petit, Momonari and Kudo, and points out the existing problems of the algorithm. Therefore, with the help of sum polynomial function and index calculus, a pseudo-index calculus algorithm for elliptic curves discrete logarithm problem over prime finite fields is proposed, and its correctness is analyzed and verified. It is pointed out that there is no subexponential time method for solving discrete logarithms on elliptic curves in the finite fields of prime numbers, or at least in the present research background, there is no method for solving discrete logarithms in subexponential time.

Attribute-based encryption (ABE) enables fine-grained control over which ciphertexts various users can decrypt. A master authority can create secret keys $sk_f$ with different functions (circuits) $f$ for different users. Anybody can encrypt a message under some attribute $x$ so that only recipients with a key $sk_f$ for a function such that $f(x)=1$ will be able to decrypt. There are a number of different approaches toward achieving selectively secure ABE, where the adversary has to decide on the challenge attribute $x$ ahead of time before seeing any keys, including constructions via bilinear maps (for NC1 circuits), learning with errors, or witness encryption. However, when it comes adaptively secure ABE, the problem seems to be much more challenging and we only know of two potential approaches: via the ``dual systems'' methodology from bilinear maps, or via indistinguishability obfuscation. In this work, we give a new approach that constructs adaptively secure ABE from witness encryption (along with statistically sound NIZKs and one-way functions). While witness encryption is a strong assumption, it appears to be fundamentally weaker than indistinguishability obfuscation. Moreover, we have candidate constructions of witness encryption from some assumptions (e.g., evasive LWE) from which we do not know how to construct indistinguishability obfuscation, giving us adaptive ABE from these assumptions as a corollary of our work.

This paper proposes a fast, compact key-size, and hardware-friendly bootstrapping using only 16-bit integer arithmetic and fully homomorphic encryption FHE16, which enables gate operations on ciphertexts using only 16-bit integer arithmetic. The proposed bootstrapping consists of unit operations on ciphertexts, such as (incomplete) number theoretic transform (NTT), inverse NTT, polynomial multiplication, gadget decomposition, and automorphism, under a composite modulus constructed from 16-bit primes. Since our bootstrapping does not use any floating-point operations, extra floating-point errors do not occur so that FHE16 can pack more message bits into a single ciphertext than TFHE-rs which utilizes floating-point operations. Furthermore, we propose multiple instruction multiple ciphertext(MIMC) method to accelerate the simultaneous execution of different homomorphic operations across multiple ciphertexts. Finally, experimental results show that the bootstrapping operation completes in 2.89 milliseconds for ciphertext dimension of 512.

Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this work, we provide the first PAKE protocol with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner). We achieve this result by sanitizing the PAKE protocol from oblivious transfer (OT) due to Canetti et al. (PKC'12) via cryptographic reverse firewalls in the UC framework (Chakraborty et al., EUROCRYPT'22). This requires new techniques, which help us uncover new cryptographic primitives with sanitation-friendly properties along the way (such as OT, dual-mode cryptosystems, and signature schemes). As an additional contribution, we delve deeper in the backbone of communication required in the subversion-resilient UC framework, extending it to the unauthenticated setting, in line with the work of Barak et al. (CRYPTO'05).

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2015, Roman'kov introduced an interesting RSA-like cryptosystem that, unlike the classical RSA key equation $ed - k (p-1)(q-1) = 1$, uses the key equation $ed - k r = 1$, where $r | p-1$ and is a large prime number. In this paper, we study if small private key attacks based on lattices can be applied to Roman'kov's cryptosystem. More precisely, we argue that such attacks do not appear to be applicable to this scheme without substantial adaptations.

Isogeny-based schemes often come with special requirements on the field of definition of the involved elliptic curves. For instance, the efficiency of SQIsign, a promising candidate in the NIST signature standardisation process, requires a large power of two and a large smooth integer $T$ to divide $p^2-1$ for its prime parameter $p$. We present two new methods that combine previous techniques for finding suitable primes: sieve-and-boost and XGCD-and-boost. We use these methods to find primes for the NIST submission of SQIsign. Furthermore, we show that our methods are flexible and can be adapted to find suitable parameters for other isogeny-based schemes such as AprèsSQI or POKE. For all three schemes, the parameters we present offer the best performance among all parameters proposed in the literature.

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

In this work, we present a new paradigm for constructing Group Authenticated Key Exchange (GAKE). This result is the first tightly secure GAKE scheme in a strong security model that allows maximum exposure attacks (MEX) where the attacker is allowed to either reveal the secret session state or the long-term secret of all communication partners. Moreover, our protocol features the strong and realistic notion of (full) perfect forward secrecy (PFS), that allows the attacker to actively modify messages before corrupting parties. We obtain our results via a series of tightly secure transformations. Our first transformation is from weakly secure KEMs to unilateral authenticated key exchange (UAKE) with weak forward secrecy (WFS). Next, we show how to turn this into an UAKE with PFS in the random oracle model. Finally, and as one of our major novel conceptual contributions, we describe how to build GAKE protocols from UAKE protocols, also in the random oracle model. We apply our transformations to obtain two practical GAKE protocols with tight security. The first is based on the DDH assumption and features low message complexity. Our second result is based on the LWE assumption. In this way, we obtain the first GAKE protocol from a post-quantum assumption that is tightly secure in a strong model of security allowing MEX attacks.

Any isogeny between two supersingular elliptic curves can be defined over $\mathbb{F}_{p^2}$, however, this does not imply that computing such isogenies can be done with field operations in $\mathbb{F}_{p^2}$. In fact, the kernel generators of such isogenies are defined over extension fields of $\mathbb{F}_{p^2}$, generically with extension degree linear to the isogeny degree. Most algorithms related to isogeny computations are only efficient when the extension degree is small. This leads to efficient algorithms used in isogeny-based cryptographic constructions, but also limits their parameter choices at the same time. In this paper, we consider three computational subroutines regarding isogenies, focusing on cases with large extension degrees: computing a basis of $\ell$-torsion points, computing the kernel polynomial of an isogeny given a kernel generator, and computing the kernel generator of an isogeny given the corresponding quaternion ideal under the Deuring correspondence. We then apply our algorithms to the constructive Deuring correspondence algorithm from Eriksen, Panny, Sotáková and Veroni (LuCaNT'23) in the case of a generic prime characteristic, achieving around 30% speedup over their results.

A union-only signature (UOS) scheme (informally introduced by Johnson et al. at CT-RSA 2002) allows signers to sign sets of messages in such a way that (1) any third party can merge two signatures to derive a signature on the union of the message sets, and (2) no adversary, given a signature on some set, can derive a valid signature on any strict subset of that set (unless it has seen such a signature already). Johnson et al. originally posed building a UOS as an open problem. In this paper, we make two contributions: we give the first formal definition of a UOS scheme, and we give the first UOS constructions. Our main construction uses hashing, regular digital signatures, Pedersen commitments and signatures of knowledge. We provide an implementation that demonstrates its practicality. Our main construction also relies on the hardness of the short integer solution (SIS) problem; we show how that this assumption can be replaced with the use of groups of unknown order. Finally, we sketch a UOS construction using SNARKs; this additionally gives the property that the size of the signature does not grow with the number of merges.

The MPC-in-the-Head (MPCitH) paradigm is widely used for building post-quantum signature schemes, as it provides a versatile way to design proofs of knowledge based on hard problems. Over the years, the MPCitH landscape has changed significantly, with the most recent improvements coming from VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH). While a straightforward application of these frameworks already improve the existing MPCitH-based signatures, we show in this work that we can adapt the arithmetic constraints representing the underlying security assumptions (here called the modeling) to achieve smaller sizes using these new techniques. More precisely, we explore existing modelings for the rank syndrome decoding (RSD) and MinRank problems and we introduce a new modeling, named dual support decomposition, which achieves better sizes with the VOLEitH and TCitH frameworks by minimizing the size of the witnesses. While this modeling is naturally more efficient than the other ones for a large set of parameters, we show that it is possible to go even further and explore new areas of parameters. With these new modeling and parameters, we obtain low-size witnesses which drastically reduces the size of the arithmetic part of the signature. We apply the TCitH and VOLEitH frameworks to our new modeling for both RSD and MinRank and compare our results to the NIST candidates RYDE, MiRitH, and MIRA (MPCitH-based schemes from RSD and MinRank). We also note that recent techniques optimizing the sizes of GGM trees are applicable to our schemes and further reduce the signature sizes by a few hundred bytes. We obtain signature sizes below 3.5 kB for 128 bits of security with N=256 parties (a.k.a. leaves in the GGM trees) and going as low as ≈ 2.8 kB with N=2048, for both RSD and MinRank. This represents an improvement of more than 2 kB compared to the original submissions to the 2023 NIST call for additional signatures.

This work introduces DEFIv2 - an efficient hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. The form is public, but the construction is a trapdoor that depends on the scheme's private key. For polynomial rings over integers and rings of integers of algebraic number fields, the cryptanalysis is reducible to solving a quadratic Diophantine equation over the ring or, equivalently, to solving a system of quadratic Diophantine equations over rational integers. It is still an open problem whether quantum computers will have any advantage in solving Diophantine problems.

We suggest two families of multivariate public keys defined over arbitrary finite commutative ring \(K\) with unity. The first one has quadratic multivariate public rule, this family is an obfuscation of previously defined cryptosystem defined in terms of well known algebraic graphs \(D(n, K)\) with the partition sets isomorphic to \(K^n\). Another family of cryptosystems uses the combination of Eulerian transformation of \(K[x_1, x_2, \ldots, x_n]\) sending each variable \(x_i\) to a monomial term with the quadratic encryption map of the first cryptosystem. The resulting map has unbounded degree and the density \(O(n^4)\) like the cubic multivariate map. The space of plaintexts of the second cryptosystem is the variety \((K^*)^n\) and the space of ciphertexts is the affine space \(K^n\).

Lattices lead to promising practical post-quantum digital signatures, combining asymptotic efficiency with strong theoretical security guarantees. However, tuning their parameters into practical instantiations is a delicate task. On the one hand, NIST round 2 candidates based on Lyubashevsky's design (such as Dilithium and qTesla) allow several tradeoffs between security and efficiency, but at the expense of a large bandwidth consumption. On the other hand, the hash-and-sign falcon signature is much more compact and is still very efficient, but it allows only two security levels, with large compactness and security gaps between them. We introduce a new family of signature schemes based on the Falcon design, which relies on module lattices. Our concrete instantiation enjoys the compactness and efficiency of Falcon, and allows an intermediate security level. It leads to the most compact lattice-based signature achieving a quantum security above 128 bits.

We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning With Errors (LWE) assumption whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et al. (EUROCRYPT 2014) -- we reduce the key size in the latter from $\mathsf{poly}(\mbox{depth},\lambda)$ to $\mathsf{poly}(\lambda)$. The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo (TCC 2022), which achieves $\mathsf{poly}(\lambda)$ key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

The succinct non-interactive argument of knowledge (SNARK) technique has been extensively utilized in blockchain systems to replace the costly on-chain computation with the verification of a succinct proof. However, most existing applications verify each proof independently, resulting in a heavy load on nodes and high transaction fees for users. Currently, the mainstream proof aggregation schemes are based on a generalized inner product argument, which has a logarithmic proof size and verification cost. To improve the efficiency of verifying multiple proofs, we introduce SnarkFold, a novel SNARK-proof aggregation scheme with constant verification time and proof size. SnarkFold is derived from incrementally verifiable computation (IVC) and is optimized further through the folding scheme. By folding multiple instance-proof pairs, SnarkFold defers the expensive SNARK verification (e.g., elliptic curve pairing) to the final step. Additionally, we propose a generic technique to enhance the verifier's efficiency by delegating instance aggregation tasks to the prover. The verifier only needs a simple preprocessing to check the validity of the delegation. We further introduce folding schemes for Groth16 and Plonk proofs. Experimental results demonstrate that SnarkFold offers significant advantages, with an aggregated Plonk proof size of just $0.5$ KB and the verification time of only $4.5$ ms for aggregating 4096 Plonk proofs.

Numerous applications in homomorphic encryption require an operation that moves the slots of a ciphertext to the coefficients of a different ciphertext. For the BGV and BFV schemes, the only efficient algorithms to implement this slot-to-coefficient transformation were proposed in the setting of non-power-of-two cyclotomic rings. In this paper, we devise an FFT-like method to decompose the slot-to-coefficient transformation (and its inverse) for power-of-two cyclotomic rings. The proposed method can handle both fully and sparsely packed slots. Our algorithm brings down the computational complexity of the slot-to-coefficient transformation from a linear to a logarithmic number of FHE operations, which is shown via a detailed complexity analysis. The new procedures are implemented in Microsoft SEAL for BFV. The experiments report a speedup of up to $44\times$ when packing $2^{12}$ elements from $\operatorname{GF}(8191^8)$. We also study a fully packed bootstrapping operation that refreshes $2^{15}$ elements from $\operatorname{GF}(65537)$ and obtain an amortized speedup of $12\times$.

We present an efficient Publicly Verifiable Fully Homomorphic Encryption scheme that, along with being able to evaluate arbitrary boolean circuits over ciphertexts, also generates a succinct proof of correct homomorphic computation. Our scheme is based on FHEW proposed by Ducas and Micciancio (Eurocrypt'15), and we incorporate the GINX homomorphic accumulator (Eurocrypt'16) for improved bootstrapping efficiency. In order to generate the proof efficiently, we generalize the widely used Rank-1 Constraint System (R1CS) to the ring setting and obtain Ring R1CS, to natively express homomorphic computation in FHEW. In particular, we develop techniques to efficiently express in our Ring R1CS the "non-arithmetic" operations, such as gadget decomposition and modulus switching used in the FHEW construction. We further construct a SNARG for Ring R1CS instances, by translating the Ring R1CS instance into a sum-check protocol over polynomials, and then compiling it into a succinct non-interactive proof by incorporating the lattice-based polynomial commitment scheme of Cini, Malavolta, Nguyen, and Wee (Crypto'24). Putting together, our Publicly Verifiable FHE scheme relies on standard hardness assumptions about lattice problems such that it generates a succinct proof of homomorphic computation of circuit $C$ in time $O(|C|^2\cdot poly(\lambda))$ and of size $O(\log^2{|C|}\cdot poly(\lambda))$. Besides, our scheme achieves the recently proposed IND-SA (indistinguishability under semi-active attack) security by Walter (EPrint 2024/1207) that exactly captures client data privacy when a homomorphic computation can be verified.

A crucial ingredient for many cryptographic primitives such as key exchange protocols and advanced signature schemes is a commutative group action where the structure of the underlying group can be computed efficiently. SCALLOP provides such a group action, based on oriented supersingular elliptic curves. We present PEARL-SCALLOP, a variant of SCALLOP that changes several parameter and design choices, thereby improving on both efficiency and security and enabling feasible parameter generation for larger security levels. Within the SCALLOP framework, our parameters are essentially optimal; the orientation is provided by a $2^e$-isogeny, where $2^e$ is roughly equal to the discriminant of the acting class group. As an important subroutine we present a practical algorithm for generating oriented supersingular elliptic curves. To demonstrate our improvements, we provide a proof-of-concept implementation which instantiates PEARL-SCALLOP at all relevant security levels. Our timings are more than an order of magnitude faster than any previous implementation.

This work focuses on concrete cryptanalysis of the isogeny-based cryptosystems SIDH/SIKE under realistic memory/storage constraints. More precisely, we are solving the problem of finding an isogeny of a given smooth degree between two given supersingular elliptic curves. Recent works by Adj et al. (SAC 2018), Costello et al. (PKC 2020), Longa et al. (CRYPTO 2021) suggest that parallel "memoryless" golden collision search by van Oorschot-Wiener (JoC 1999) is the best realistic approach for the problem. We show instead that the classic meet-in-the-middle attack is still competitive due to its very low computational overhead, at least on small parameters. As a concrete application, we apply the meet-in-the-middle attack with optimizations to the $IKEp182 challenge posed by Microsoft Research. The attack was executed on a cluster and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB.

The Brakerski/Fan-Vercauteren (BFV) scheme is a state-of-the-art scheme in Fully Homomorphic Encryption based on the Ring Learning with Errors (RLWE) problem. Thus, ciphertexts contain an error that increases with each homomorphic operation and has to stay below a certain threshold for correctness. This can be achieved by setting the ciphertext modulus big enough. On the other hand, a larger ciphertext modulus decreases the level of security and computational efficiency, making parameter selection challenging. Our work aims to improve the bound on the ciphertext modulus, minimizing it. Our main contributions are the following. Primarily, we perform the first average-case analysis of the error growth for the BFV scheme, significantly improving its estimation. For a circuit with a multiplicative depth of only 5, our bounds are up to 25.2 bits tighter than previous analyses and within 1.2 bits of the experimentally observed values. % Secondly, we give a general way to bound the ciphertext modulus for correct decryption that allows closed formulas. % Finally, we use our theoretical advances and propose the first parameter generation tool for the BFV scheme. Here, we add support for arbitrary but use-case-specific circuits, as well as the ability to generate easy-to-use code snippets, making our theoretical work accessible to both researchers and practitioners.

We present experimental findings on the decoding failure rate (DFR) of BIKE, a fourth-round candidate in the NIST Post-Quantum Standardization process, at the 20-bit security level using graph-theoretic approaches. We select parameters according to BIKE design principles and conduct a series of experiments using Rust to generate significantly more decoding failure instances than in prior work using SageMath. For each decoding failure, we study the internal state of the decoder at each iteration and find that for 97% of decoding failures at block size $r=587$, the decoder reaches a fixed point within 7 iterations. We then consider the corresponding Tanner graphs of each decoding failure instance to determine whether the decoding failures are due to absorbing sets. We find that 81% of decoding failures at $r=587$ were caused by absorbing sets, and of these the majority were $(d,d)$-near codewords.

This paper explores advancements in the Gentry-Sahai-Waters (GSW) fully homomorphic encryption scheme, addressing challenges related to message data range limitations and ciphertext size constraints. We introduce a novel approach utilizing the Chinese Remainder Theorem (CRT) for message decomposition, significantly expanding the allowable message range to the entire plaintext space. This method enables unrestricted message selection and supports parallel homomorphic operations without intermediate decryption. Additionally, we adapt existing ciphertext compression techniques, such as the PVW-like scheme, to reduce memory overhead associated with ciphertexts. Our experimental results demonstrate the effectiveness of the CRT-based decomposition in increasing the upper bound of message values and improving the scheme's capacity for consecutive homomorphic operations. However, compression introduces a trade-off, necessitating a reduced message range due to error accumulation. This research contributes to enhancing the practicality and efficiency of the GSW encryption scheme for complex computational scenarios while managing the balance between expanded message range, computational complexity, and storage requirements.

HFE (that stands for Hidden Field Equations) belongs to multivariate cryptography and was designed by Jacques Patarin in 1996 as a public key trapdoor suitable for encryption or signature. This original basic version is unfortunately known to have a super-polynomial attack, but as imagined since the beginning, it comes with various variants, one can describe as combinations of “modifiers”. In this work, we first present the state of the art of these HFE modifiers, along with their effect on the complexity of the main cryptanalysis techniques against HFE-based schemes. This allows us, in a second time, to identify a combination of two modifiers that has not yet been explored and may still be secure with efficient parameters. Based on our analysis, we propose a new signature scheme that offers extremely short signature sizes, with reasonable public key sizes and performance. In particular, we rely on the classical Feistel-Patarin technique to reduce signature sizes below two times the security parameter.

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared to standard NTRU. To our knowledge, DiTRU (Africacrypt 2024) is the first noncommutative analog of NTRU provided as a complete package. Although DiTRU is practical, it operates at two times slower than NTRU with no decryption failure. Additionally, key generation, encryption, and decryption are 1.2, 1.7, and 1.7 times slower, respectively, with negligible decryption failure. In this work, we introduce a noncommutative version of NTRU that offers comparable performance and key sizes to NTRU while improving upon DiTRU. Our cryptosystem is based on the GR-NTRU framework, utilizing the group ring of a semidirect product of cyclic groups over the ring of Eisenstein integers. This design allows for an efficient construction with key generation speeds approximately two (three) times faster than NTRU (DiTRU). Further, the proposed scheme provides roughly a speed-up by a factor of 1.2 (2) while encrypting/decrypting messages of the same length over NTRU (DiTRU). We provide a reference implementation in C for the proposed cryptosystem to prove our claims.

In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis. First, we obtain a lower bound on the cost of quantum lattice sieving with a bounded size QRAM. We do so in a new query model encompassing a wide range of lattice sieving algorithms similar to those in the classical sieving lower bound by Kirshanova and Laarhoven [CRYPTO 21]. This implies that, under reasonable assumptions, quantum speedups in lattice sieving require the use of QRAM. In particular, no quantum speedup is possible without QRAM. Second, we investigate the trade-off between the size of QRAM and the quantum speedup. We obtain a new interpolation between classical and quantum lattice sieving. Moreover, we show that further improvements require a novel way to use the QRAM by proving the optimality of some subroutines. An important caveat is that this trade-off requires a strong assumption on the efficient replacement of QRAM data, indicating that even speedups with a small QRAM are already challenging. Finally, we provide a circuit for quantum lattice sieving without using QRAM. Our circuit has a better depth complexity than the best classical algorithms but requires an exponential amount of qubits. To the best of our knowledge, this is the first quantum speedup for lattice sieving without QRAM in the standard quantum circuit model. We explain why this circuit does not contradict our lower bound, which considers the query complexity.

Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. Code-based and lattice-based cryptography are two promi- nent approaches, both heavily studied within the NIST standardization project. Code-based cryptography—most prominently exemplified by the McEliece cryptosystem—is based on the hardness of decoding random linear error-correcting codes. Despite the McEliece cryptosystem having been unbroken for several decades, it suffers from large key sizes, which has led to exploring variants using metrics than the Hamming metric, such as the Lee metric. This alternative metric may allow for smaller key sizes, but requires further analysis for potential vulnerabilities to lattice- based attack techniques. In this paper, we consider a generic Lee met- ric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.

In the present work, we establish a new relationship among the Beyond UnForgeability Features (BUFF) introduced by Cremers et al. (SP’21). There, the BUFF notions have been shown to be independent of one another. On the other hand, the analysis by Aulbach et al. (PQCrypto’24) reveals that one of the BUFF notions—message-bound signatures (MBS)—is achieved by most schemes. To achieve BUFF security, there is the generic BUFF transform that achieves all the beyond unforgeability features. The BUFF transform works by signing a hash of the public key and the message (rather than just the message), and appending this hash value to the signature. The need for appending the hash comes from the intuitive notion of weak keys that verify all message-signature pairs. We explain that MBS security effectively rules out the possibility of weak keys. This opens the possibility for a more efficient transform to achieve BUFF. We show that this transform, first introduced by Pornin and Stern (ACNS’05), indeed suffices to achieve BUFF security, if the original signature schemes satisfies MBS. Only in the malicious setting of exclusive ownership, we present an attack on UOV, even after applying the PS-3 transform.

The Multi-Party Computation in the Head (MPCitH) paradigm has proven to be a versatile tool to design proofs of knowledge (PoK) based on variety of computationally hard problems. For instance, many post-quantum signatures have been designed from MPC based proofs combined with the Fiat-Shamir transformation. Over the years, MPCitH has evolved significantly with developments based on techniques such as threshold computing and other optimizations. Recently, Vector Oblivious Linear Evaluation (VOLE) and the VOLE in the Head framework has spurred further advances. In this work, we introduce three VOLE-friendly modelings for generic and communication efficient PoK to prove the knowledge of secret witness in the form of elementary vectors, vectors of Hamming weight at most $\omega$, and permutation matrices. Remarkably, these modelings scale logarithmically with respect to the original witness sizes. Specifically, our modeling for elementary vectors of size $n$ transforms the witness size to $\mathcal{O}(\log_2(n))$, in case of vectors of size $n$ and Hamming weight at most $\omega$ the reduced witness is of size $\mathcal{O}\left(\omega \log_2(n)\right)$ while our modeling for permutation matrix of size $n \times n$ results in an (equivalent) witness of size $\mathcal{O}(n\log_2(n))$, which leads to small proofs in practice. To achieve this, we consider modelings with higher multiplicative depth $d > 2$. Even if this increases the proof size, we show that our approach compares favorably with existing proofs. Such design choices were mostly overlooked in previous comparable works, maybe because prior to the VOLEitH framework, multiplications were often emulated with Beaver's triples causing the proof size to scale poorly with $d$. We also provide several applications for our modelings namely i) post-quantum signature schemes based on the $\mathsf{SD}$ (Syndrome Decoding) problem and $\mathsf{PKP}$ (Permuted Kernel Problem), ii) PoK of secrets key for code-based key encapsulation mechanism (KEM), and iii) ring signatures from $\mathsf{SD}$ and $\mathsf{PKP}$. Our signatures based on $\mathsf{SD}$ over $\mathbb{F}_2$ and $\mathsf{PKP}$ feature sizes of $3.9$ kB and $3.6$ kB for NIST-I security level which is respectively $26\%$ and $38\%$ shorter than state-of-the-art alternatives. Our PoK of secret key of BIKE and HQC are twice shorter than similar PoK for Kyber. In addition, we obtain the smallest ring signature based on $\mathsf{SD}$ and the first ring signature based on $\mathsf{PKP}$.

Fully homomorphic signatures are a significant strengthening of digital signatures, enabling computations on \emph{secretly} signed data. Today, we have multiple approaches to design fully homomorphic signatures such as from lattices, or succinct functional commitments, or indistinguishability obfuscation, or mutable batch arguments. Unfortunately, all existing constructions for homomorphic signatures suffer from one or more limitations. We do not have homomorphic signatures with features such as multi-hop evaluation, context hiding, and fast amortized verification, while relying on standard falsifiable assumptions. In this work, we design homomorphic signatures satisfying all above properties. We construct homomorphic signatures for polynomial-sized circuits from a variety of standard assumptions such as sub-exponential DDH, standard pairing-based assumptions, or learning with errors. We also discuss how our constructions can be easily extended to the multi-key setting.

Delegatable anonymous credentials (DACs) enable a root issuer to delegate credential-issuing power, allowing a delegatee to take a delegator role. To preserve privacy, credential recipients and verifiers should not learn anything about intermediate issuers in the delegation chain. One particularly efficient approach to constructing DACs is due to Crites and Lysyanskaya (CT-RSA '19). In contrast to previous approaches, it is based on mercurial signatures (a type of equivalence-class signature), offering a conceptually simple design that does not require extensive use of zero-knowledge proofs. Unfortunately, current constructions of ``CL-type'' DACs only offer a weak form of privacy-preserving delegation: if an adversarial issuer (even an honest-but-curious one) is part of a user's delegation chain, they can detect when the user shows its credential. This is because the underlying mercurial signature schemes allows a signer to identify his public key in a delegation chain. We propose CL-type DACs that overcome the above limitation based on a new mercurial signature scheme that provides adversarial public key class hiding which ensures that adversarial signers who participate in a user's delegation chain cannot exploit that fact to trace users. We achieve this introducing structured public parameters for each delegation level. Since the related setup produces critical trapdoors, we discuss techniques from updatable structured reference strings in zero-knowledge proof systems (Groth et al. CRYPTO '18) to guarantee the required privacy needs. In addition, we propose a simple way to realize revocation for CL-type DACs via the concept of revocation tokens. While we showcase this approach to revocation using our DAC scheme, it is generic and can be applied to any CL-type DAC system. Revocation is a vital feature that is largely unexplored and notoriously hard to achieve for DACs, thus providing revocation can help to make DAC schemes more attractive in practical applications.

We introduce SQIPrime, a post-quantum digital signature scheme based on the Deuring correspondence and Kani's Lemma. Compared to its predecessors that are SQISign and especially SQISignHD, SQIPrime further expands the use of high dimensional isogenies, already in use in the verification in SQISignHD, to all its subroutines. In doing so, it no longer relies on smooth degree isogenies (of dimension 1). Intriguingly, this includes the challenge isogeny which is also a non-smooth degree isogeny, but has an accessible kernel. The fact that the isogenies do not have rational kernel allows to fit more rational power 2 torsion points which are necessary when computing and representing the response isogeny. SQIPrime operates with prime numbers of the form $p = 2^\alpha f-1$. We describe two variants of SQIPrime. SQIPrime4D which incorporates the novelties described above and uses dimension 4 isogenies to represent the response isogeny. The runtime of higher dimensional isogeny computation is exponential in the dimension, hence the smaller the dimension the better for efficiency. The second variant, SQIPrime2D, solely uses dimension 2 isogenies. This is achieved by setting the degree of the secret isogeny to be equal to that of the challenge isogeny and further exploiting Kani's Lemma. SQIPrime2D is more efficient compared to SQIPrime4D and to SQISignHD, at the cost of being comparatively less compact, but still very compact compared to non isogeny based post-quantum signatures.

The native plaintexts of the Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme are vectors of approximations to complex numbers. Drucker et al. [J. Cryptol.'24] have showed how to use CKKS to efficiently perform computations on bits and small bit-length integers, by relying on their canonical embeddings into the complex plane. For small bit-length integers, Chung et al. [IACR eprint'24] recently suggested to rather rely on an embedding into complex roots of unity, to gain numerical stability and efficiency. Both works use CKKS in a black-box manner. Inspired by the design by Bae et al. [Eurocrypt'24] of a dedicated bootstrapping algorithm for ciphertexts encoding bits, we propose a CKKS bootstrapping algorithm, $\mathsf{SI\mbox{-}BTS}$ (small-integer bootstrapping), for ciphertexts encoding small bit-length integers. For this purpose, we build upon the DM/CGGI-to-CKKS conversion algorithm from Boura et al. [J. Math. Cryptol.'20], to bootstrap canonically embedded integers to integers embedded as roots of unity. $\mathsf{SI\mbox{-}BTS}$ allows functional bootstrapping: it can evaluate an arbitrary function of its input while bootstrapping. It may also be used to batch-(functional-)bootstrap multiple DM/CGGI ciphertexts. For example, its amortized cost for evaluating an 8-bit look-up table on $2^{12}$ DM/CGGI ciphertexts is 3.75ms (single-thread CPU, 128-bit security). We adapt $\mathsf{SI\mbox{-}BTS}$ to simultaneously bootstrap multiple CKKS ciphertexts for bits. The resulting $\mathsf{BB\mbox{-}BTS}$ algorithm (batch-bits bootstrapping) allows to decrease the amortized cost of a binary gate evaluation. Compared to Bae et al., it gives a 2.4x speed-up.

We consider protocols for secure multi-party computation (MPC) built from FHE under honest majority, i.e., for $n=2t+1$ players of which $t$ are corrupt, that are robust. Surprisingly there exists no robust threshold FHE scheme based on BFV to design such MPC protocols. Precisely, all existing methods for generating a common relinearization key can abort as soon as one player deviates. We address this issue, with a new relinearization key (adapted from [CDKS19, CCS'19]) which we show how to securely generate in parallel of the threshold encryption key, in the same broadcast. We thus obtain the first robust threshold BFV scheme, moreover using only one broadcast for the generation of keys instead of two previously. Of independent interest, as an optional alternative, we propose the first threshold FHE decryption enabling simultaneously: (i) robustness over asynchronous channels with honest majority; (ii) tolerating a power-of-small-prime ciphertext modulus, e.g., $2^e$; and (iii) secret shares of sizes quasi-independent of $n$.

The Learning with Errors (LWE) problem with its variants over structured lattices has been widely exploited in efficient post-quantum cryptosystems. Recently, May suggests the Meet-LWE attack, which poses a significant advancement in the line of work on the Meet-in-the-Middle approach to analyze LWE with ternary secrets. In this work, we generalize and extend the idea of Meet-LWE by introducing ternary trees, which result in diverse representations of the secrets. More precisely, we split the secrets into three pieces with the same dimension and expand them into a ternary tree to leverage the increased representations to improve the overall attack complexity. We also suggest the matching criteria for the approximate matching of three lists via locality sensitive hash function accordingly. We carefully analyze and optimize the time and memory costs of our attack algorithm exploiting ternary trees, and compare them to those of the Meet-LWE attack. With asymptotic and non-asymptotic comparisons, we observe that our attack provides improved estimations for all parameter settings, including those of the practical post-quantum schemes, compared to the Meet-LWE attack. We also evaluate the security of the Round 2 candidates of the KpqC competition which aims to standardize post-quantum public key cryptosystems in the Republic of Korea and report that the estimated complexities for our attack applied to SMAUG-T are lower than the claimed for some of the recommended parameters.

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.

The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields (except for the weak small characteristic case). The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. A precomputation, solely dependent on an approximate finite field size and an extension degree, allows to efficiently compute discrete logarithms in a constant proportion of the finite fields of the given approximate size and extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination improves the asymptotic complexity. We also notice that combining our approach with the MNFS variant would be an unnecessary complication as all the potential gain of MNFS is subsumed by our Factory variant anyway. Furthermore, we demonstrate how Chebotarev's density theorem allows to compute the density of finite fields that can be solved with a given precomputation. Finally, we provide experimental data in order to assess the practical reach of our approach.

In Noncommutative Ring Learning With Errors From Cyclic Algebras, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE', was developed, and security reductions similar to those known for the ring and module case were given, as well as a Regev-style encryption scheme. In this work, we make a number of improvements to that work: namely, we describe methods to increase the number of cryptographically useful division algebras, demonstrate the hardness of CLWE from ideal lattices obtained from non-maximal orders, and study Learning with Rounding in cyclic division algebras.

Many messaging platforms have integrated end-to-end (E2E) encryption into their services. This widespread adoption of E2E encryption has triggered a technical tension between user privacy and illegal content moderation. The existing solutions either support only unframeability or deniability, or they are prone to abuse (the moderator can perform content moderation for all messages, whether illegal or not), or they lack mechanisms for retrospective content moderation. To address the above issues, we introduce a new primitive called \emph{mild asymmetric message franking} (MAMF) to establish illegal-messages-only and retrospective content moderation for messaging systems, supporting unframeability and deniability simultaneously. We provide a framework to construct MAMF, leveraging two new building blocks, which might be of independent interest.

Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a ciphertext within pre-specified memory bound $S$ before receiving the secret key. In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the ciphertext to within $S$ bits. An important efficiency measure for incompressible encryption is the ciphertext-rate ( i.e., $\mathsf{rate} = \frac{|m|}{|\mathsf{ct}|}$). We give many new results for incompressible functional encryption for circuits, from minimal assumption of (non-incompressible) functional encryption, with 1. $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys, 2. $\mathsf{ct}$-rate-$1$ and large secret keys. Along the way, we also give a new incompressible attribute-based encryption for circuits from standard assumptions, with $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys. Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with $\mathsf{ct}$-rate-$1$ as well as short secret keys has strong barriers for provable security from standard assumptions. Moreover, our assumptions are minimal as incompressible attribute-based/functional encryption are strictly stronger than their non-incompressible counterparts.

In this work, we provide new, tighter proofs for the $T_{RH}$-transformation by Jiang et al. (ASIACRYPT 2023), which converts OW-CPA secure PKEs into KEMs with IND-1CCA security, a variant of typical IND-CCA security where only a single decapsulation query is allowed. Such KEMs are efficient and have been shown sufficient for real-world applications by Huguenin-Dumittan and Vaudenay at EUROCRYPT 2022. We reprove Jiang et al.'s $T_{RH}$-transformation in both the random oracle model (ROM) and the quantum random oracle model (QROM), for the case where the underlying PKE is rigid deterministic. In both ROM and QROM models, our reductions achieve security loss factors of $\mathcal{O}(1)$, significantly improving Jiang et al.'s results which have security loss factors of $\mathcal{O}(q)$ in the ROM and $\mathcal{O}(q^2)$ in the QROM respectively. Notably, central to our tight QROM reduction is a new tool called ''reprogram-after-measure'', which overcomes the reduction loss posed by oracle reprogramming in QROM proofs. This technique may be of independent interest and useful for achieving tight QROM proofs for other post-quantum cryptographic schemes. We remark that our results also improve the reduction tightness of the $T_{H}$-transformation (which also converts PKEs to KEMs) by Huguenin-Dumittan and Vaudenay (EUROCRYPT 2022), as Jiang et al. provided a tight reduction from $T_H$-transformation to $T_{RH}$-transformation (ASIACRYPT 2023).

Broadcast Encryption (BE) allows a sender to send an encrypted message to multiple receivers. In a typical broadcast encryption scenario, the broadcaster decides the set of users who can decrypt a particular ciphertext (denoted as the privileged set). Gritti et al. (IJIS'16) introduced a new primitive called Broadcast Encryption with Dealership (BrED), where the dealer decides the privileged set. A BrED scheme allows a dealer to buy content from the broadcaster and sell it to users. It provides better flexibility in managing a large user base. To date, quite a few different constructions of BrED schemes have been proposed by the research community. We find that all existing BrED schemes are insecure under the existing security definitions. We demonstrate a concrete attack on all the existing schemes in the purview of the existing security definition. We also find that the security definitions proposed in the state-of-the-art BrED schemes do not capture the real world. We argue about the inadequacy of existing definitions and propose a new security definition that models the real world more closely. Finally, we propose a new BrED construction and prove it to be secure in our newly proposed security model.

We construct a quantum money/quantum lightning scheme from class group actions on elliptic curves over $F_{p}$. Our scheme, which is based on the invariant money construction of Liu-Montgomery-Zhandry (Eurocrypt '23), is simple to describe. We believe it to be the most instantiable and well-defined quantum money construction known so far. The security of our quantum lightning construction is exactly equivalent to the (conjectured) hardness of constructing two uniform superpositions over elliptic curves in an isogeny class which is acted on simply transitively by an exponentially large ideal class group. However, we needed to advance the state of the art of isogenies in order to achieve our scheme. In partcular, we show: 1. An efficient (quantum) algorithm for sampling a uniform superposition over a cryptographically large isogeny class. 2. A method for specifying polynomially many generators for the class group so that polynomial-sized products yield an exponential-sized subset of class group, modulo a seemingly very modest assumption. Achieving these results also requires us to advance the state of the art of the (pure) mathematics of elliptic curves, and we are optimistic that the mathematical tools we developed in this paper can be used to advance isogeny-based cryptography in other ways.

We show that we can break SIDH in classical polynomial time, even with a random starting curve $E_0$.

In the multi-user with corruptions (muc) setting there are $n\geq 1$ users, and the goal is to prove that, even in the face of an adversary that adaptively corrupts users to expose their keys, un-corrupted users retain security. This can be considered for many primitives including signatures and encryption. Proofs of muc security, while possible, generally suffer a factor n loss in tightness, which can be large. This paper gives new proofs where this factor is reduced to the number c of corruptions, which in practice is much smaller than n. We refer to this as corruption-parametrized muc (cp-muc) security. We give a general result showing it for a class of games that we call local. We apply this to get cp-muc security for signature schemes (including ones in standards and in TLS 1.3) and some forms of public-key and symmetric encryption. Then we give dedicated cp-muc security proofs for some important schemes whose underlying games are not local, including the Hashed ElGamal and Fujisaki-Okamoto KEMs and authenticated key exchange. Finally, we give negative results to show optimality of our bounds.

Clustering is a crucial unsupervised learning method extensively used in the field of data analysis. For analyzing big data, outsourced computation is an effective solution but privacy concerns arise when involving sensitive information. Fully homomorphic encryption (FHE) enables computations on encrypted data, making it ideal for such scenarios. However, existing privacy-preserving clustering based on FHE are often constrained by the high computational overhead incurred from FHE, typically requiring decryption and interactions after only one iteration of the clustering algorithm. In this work, we propose a more efficient approach to evaluate the one-hot vector for the index of the minimum in an array with FHE, which fully exploits the parallelism of single-instruction-multiple-data of FHE schemes. By combining this with FHE bootstrapping, we present a practical FHE-based k-means clustering protocol whose required round of interactions between the data owner and the server is optimal, i.e., accomplishing the entire clustering process on encrypted data in a single round. We implement this protocol using the CKKS FHE scheme. Experiments show that our protocol significantly outperforms the state-of-the-art FHE-based k-means clustering protocols on various public datasets and achieves comparable accuracy to plaintext result. Additionally, We adapt our protocol to support mini-batch k-means for large-scale datasets and report its performance.

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition. SQIsign has attracted much attention because of its very short signature and key size among the candidates for the NIST PQC standardization. Recently, a lot of new schemes have been proposed that use high-dimensional isogenies. Among them, the signature scheme called SQIsignHD has an even shorter signature size than SQIsign. However, it requires 4-dimensional isogeny computations for the signature verification. In this paper, we propose a new signature scheme, SQIsign2D-East, which requires only two-dimensional isogeny computations for verification, thus reducing the computational cost of verification. First, we generalized an algorithm called RandIsogImg, which computes a random isogeny of non-smooth degree. Then, by using this generalized RandIsogImg, we construct a new signature scheme SQIsign2D-East.

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 2.4x$\sim$55.1x improvement in bootstrapping throughput, compared to previous works or the naive approach.

Homomorphic Encryption (HE) is a cutting-edge cryptographic technique that enables computations on encrypted data to be mirrored on the original data. This has quickly attracted substantial interest from the research community due to its extensive practical applications, such as in cloud computing and privacy-preserving machine learning. In addition to confidentiality, the importance of authenticity has emerged to ensure data integrity during transmission and evaluation. To address authenticity, various primitives have been developed including Homomorphic Authenticator (HA). Corresponding security notions have also been introduced by extending the existing notions to their homomorphic versions. Despite these advancements, formalizing the security of HE and HA remains challenging due to the novelty of these primitives and complexity of application scenarios involving message evaluation. It is inclusive which definitions in this zoo of notions are insufficient or overly complex. Moreover, HE and HA are designed to be combined to construct a secure communication channel that ensures both confidentiality and authenticity. However, the security of such compositions is not always clear when game-based notions are used to formalize security. To bridge this gap, we conduct a constructive analysis through the lens of com- posable security. This method enables us to examine the security properties of each primitive in isolation and to more effectively evaluate their security when integrated into a larger system. We introduce the concepts of a confidential channel and an au- thenticated channel to specify the security requirements for HE and HA, respectively. We make a comparison with existing game-based notions to determine whether they adequately capture the intended security objectives. We then analyze whether the composition of HE and HA constructs a Homomorphic Authenticated Encryption (HAE) that provides both confidentiality and authenticity in presence of message evaluation. Specifically, we examine a serial composition of HE and HA, corresponding to Encrypt-then-MAC (EtM) composition for constructing classical AE.

We introduce new lattice-based techniques for building ABE for circuits with unbounded attribute length based on the LWE assumption, improving upon the previous constructions of Brakerski and Vaikuntanathan (CRYPTO 16) and Goyal, Koppula, and Waters (TCC 16). Our main result is a simple and more efficient unbounded ABE scheme for circuits where only the circuit depth is fixed at set-up; this is the first unbounded ABE scheme for circuits that rely only on black-box access to cryptographic and lattice algorithms. The scheme achieves semi-adaptive security against unbounded collusions under the LWE assumption. The encryption time and ciphertext size are roughly $3 \times$ larger than the prior bounded ABE of Boneh et al. (EUROCRYPT 2014), substantially improving upon the encryption times in prior works. As a secondary contribution, we present an analogous result for unbounded inner product predicate encryption that satisfies weak attribute-hiding.

We show that under a mild number-theoretic conjecture, recovering an integer from its Jacobi signature modulo $N = p^2 q$, for primes $p$ and $q$, is as hard as factoring $N$. This relates, for the first time, the one-wayness of a pseudorandom generator that Damgård proposed in 1988, to a standard number-theoretic problem. In addition, we show breaking the Jacobi pseudorandom function is no harder than factoring.

The Fast IDentity Online (FIDO) Alliance has developed the widely adopted FIDO2 protocol suite that allows for passwordless online authentication. Cryptographic keys stored on a user's device (e.g. their smartphone) are used as credentials to authenticate to services by performing a challenge-response protocol. Yet, this approach leaves users unable to access their accounts in case their authenticator is lost. The device manufacturer Yubico thus proposed a FIDO2-compliant mechanism that allows to easily create backup authenticators. Frymann et al. (CCS 2020) have first analyzed the cryptographic core of this proposal by introducing the new primitive of Asynchronous Remote Key Generation (ARKG) and accompanying security definitions. Later works instantiated ARKG both from classical and post-quantum assumptions (ACNS 2023, EuroS&P 2023). As we will point out in this paper, the security definitions put forward and used in these papers do not adequately capture the desired security requirements in FIDO2-based authentication and recovery. This issue was also identified in independent and concurrent work by Stebila and Wilson (AsiaCCS 2024), who proposed a new framework for the analysis of account recovery mechanisms, along with a secure post-quantum instantiation from KEMs and key-blinding signature schemes. In this work, we propose alternative security definitions for the primitive ARKG when used inside an account recovery mechanism in FIDO2. We give a secure instantiation from KEMs and standard signature schemes, which may in particular provide post-quantum security. Our solution strikes a middle ground between the compact, but (for this particular use case) inadequate security notions put forward by Frymann et al., and the secure, but more involved and highly tailored model introduced by Stebila and Wilson.

A verifiable random function (VRF) allows one to compute a random-looking image, while at the same time providing a unique proof that the function was evaluated correctly. VRFs are a cornerstone of modern cryptography and, among other applications, are at the heart of recently proposed proof-of-stake consensus protocols. In this work we initiate the formal study of aggregate VRFs, i.e., VRFs that allow for the aggregation of proofs/images into a small digest, whose size is independent of the number of input proofs/images, yet it still enables sound verification. We formalize this notion along with its security properties and we propose two constructions: The first scheme is conceptually simple, concretely efficient, and uses (asymmetric) bilinear groups of prime order. Pseudorandomness holds in the random oracle model and aggregate pseudorandomness is proven in the algebraic group model. The second scheme is in the standard model and it is proven secure against the learning with errors (LWE) problem. As a cryptographic building block of independent interest, we introduce the notion of key homomorphic VRFs, where the verification keys and the proofs are endowed with a group structure. We conclude by discussing several applications of key-homomorphic and aggregate VRFs, such as distributed VRFs and aggregate proof-of-stake protocols.

Jordan-Gauss graphs are bipartite graphs given by special quadratic equations over the commutative ring K with unity with partition sets K^n and K^m , n ≥m such that the neighbour of each vertex is defined by the system of linear equation given in its row-echelon form. We use families of this graphs for the construction of new quadratic and cubic surjective multivariate maps F of K^n onto K^m (or K^n onto K^n) with the trapdoor accelerators T , i. e. pieces of information which allows to compute the reimage of the given value of F in poly-nomial time. The technique allows us to use the information on the quadratic map F from K^s to K^r, s ≥ r with the trapdoor accelerator T for the construction of other map G from K^{s+rs} onto K^{r+rs} with trapdoor accelerator. In the case of finite field it can be used for construc-tion of new cryptosystems from known pairs (F, T). So we can introduce enveloping trapdoor accelerator for Matsumoto-Imai cryptosystem over finite fields of characteristic 2, for the Oil and Vinegar public keys over F_q (TUOV in particular), for quadratic multivariate public keys defined over Jordan-Gauss graphs D(n, K) where K is arbitrary finite commutative ring with the nontrivial multiplicative group.

Equivalence class signatures (EQS; Asiacrypt '14), sign vectors of elements from a bilinear group. Anyone can transform a signature on a vector to a signature on any multiple of that vector; signatures thus authenticate equivalence classes. A transformed signature/message pair is 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, anonymous tokens and contact-tracing schemes, to name a few. The original EQS construction (J. Crypto '19) is proven secure in the generic group model, and the first scheme from standard assumptions (PKC '18) satisfies a weaker model insufficient for most applications. Two works (Asiacrypt '19, PKC '22) propose applicable schemes that assume trusted parameters. Their unforgeability is argued via a security proof from standard (or non-interactive) assumptions. We show that their security proofs are flawed and explain the subtle issue. While the schemes might be provable in the algebraic group model (AGM), we instead show that the original construction, which is more efficient and has found applications in many works, is secure in the AGM under a parametrized non-interactive hardness assumption.

Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag $T$ and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least $k$ different valid signatures w.r.t. $T$ and $k$ different verification keys out of the $n$ keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign predictable messages, such as polling or randomness beacons. However, known SWE schemes without trusted setup have ciphertexts that scale linearly in the number of verification keys. This quickly becomes a major bottleneck as the system gets more distributed and the number of parties increases. Towards showing the feasibility of SWE with ciphertext size sub-linear in the number of keys, we give a construction based on indistinguishability obfuscation (iO) for Turing machines and strongly puncturable signatures (SPS).

Ring-LWE based homomorphic encryption computations in large depth use a combination of two techniques: 1) decomposition of big numbers into small limbs/digits, and 2) efficient cyclotomic multiplications modulo $X^N + 1$. It was long believed that the two mechanisms had to be strongly related, like in the full-RNS setting that uses a CRT decomposition of big numbers over an NTT-friendly family of prime numbers, and NTT over the same primes for multiplications. However, in this setting, NTT was the bottleneck of all large-depth FHE computations. A breakthrough result from Kim et al. (Crypto’2023) managed to overcome this limitation by introducing a second gadget decomposition and showing that it indeed shifts the bottleneck and renders the cost of NTT computations negligible compared to the rest of the computation. In this paper, we extend this result (far) beyond the Full-RNS settings and show that we can completely decouple the big number decomposition from the cyclotomic arithmetic aspects. As a result, we get modulus switching/rescaling for free. We verify both in theory and in practice that the performance of key-switching, external and internal products and automorphisms using our representation are faster than the one achieved by Kim et al., and we discuss the high impact of these results for low-level or hardware optimizations as well as the benefits of the new parametrizations for FHE compilers. We even manage to lower the running time of the gate bootstrapping of TFHE by eliminating one eighth of the FFTs and one sixth of the linear operations, which lowers the running time below 5.5ms on recent CPUs.

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.

This work addresses the long quest for proving full (adaptive) security for attribute-based encryption (ABE). We show that in order to prove full security in a black-box manner, the scheme must be ``irregular'' in the sense that it is impossible to ``validate'' secret keys to ascertain consistent decryption of ciphertexts. This extends a result of Lewko and Waters (Eurocrypt 2014) that was only applicable to straight-line proofs (without rewinding). Our work, therefore, establishes that it is impossible to circumvent the irregularity property using creative proof techniques, so long as the adversary is used in a black-box manner. As a consequence, our work provides an explanation as to why some lattice-based ABE schemes cannot be proven fully secure, even though no known adaptive attacks exist.

Starting from the problem of $d$-Tensor Isomorphism ($d$-TI), we study the relation between various Code Equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric (CE${}_{sr}$) to the rank metric (CE${}_{rk}$). To obtain this result, we investigate reductions between tensor problems. We define the Monomial Isomorphism problem for $d$-tensors ($d$-TI${}^*$), where, given two $d$-tensors, we ask if there are $d-1$ invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied $d$-TI and the TI-completeness of $d$-TI${}^*$ is shown. Due to this result, we obtain a reduction from CE${}_{sr}$ to CE${}_{rk}$. In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on CE${}_{sr}$.

The Paillier cryptosystem is renowned for its applications in electronic voting, threshold ECDSA, multi-party computation, and more, largely due to its additive homomorphism. In these applications, range proofs for the Paillier cryptosystem are crucial for maintaining security, because of the mismatch between the message space in the Paillier system and the operation space in application scenarios. In this paper, we present novel range proofs for the Paillier cryptosystem, specifically aimed at optimizing those for both Paillier plaintext and affine operation. We interpret encryptions and affine operations as commitments over integers, as opposed to solely over $\mathbb{Z}_{N}$. Consequently, we propose direct range proof for the updated cryptosystem, thereby eliminating the need for auxiliary integer commitments as required by the current state-of-the-art. Our work yields significant improvements: In the range proof for Paillier plaintext, our approach reduces communication overheads by approximately $60\%$, and computational overheads by $30\%$ and $10\%$ for the prover and verifier, respectively. In the range proof for Paillier affine operation, our method reduces the bandwidth by $70\%$, and computational overheads by $50\%$ and $30\%$ for the prover and verifier, respectively. Furthermore, we demonstrate that our techniques can be utilized to improve the performance of threshold ECDSA and the DCR-based instantiation of the Naor-Yung CCA2 paradigm.

Forward-Secure Key-Encapsulation Mechanism (FS-KEM; Canetti et al. Eurocrypt 2003) allows Alice to encapsulate a key $k$ to Bob for some time $t$ such that Bob can decapsulate it at any time $t'\leq t$. Crucially, a corruption of Bob's secret key after time $t$ does not reveal $k$. In this work, we generalize and extend this idea by also taking Post-Compromise Security (PCS) into account and call it Interval Key-Encapsulation Mechanism (IKEM). Thus, we do not only protect confidentiality of previous keys against future corruptions but also confidentiality of future keys against past corruptions. For this, Bob can regularly renew his secret key and inform others about the corresponding public key. IKEM enables Bob to decapsulate keys sent to him over an interval of time extending into the past, in case senders have not obtained his latest public key; forward security only needs to hold with respect to keys encapsulated before this interval. This basic IKEM variant can be instantiated based on standard KEM, which we prove to be optimal in terms of assumptions as well as ciphertext and key sizes. We also extend this notion of IKEM for settings in which Bob decapsulates (much) later than Alice encapsulates (e.g., in high-latency or segmented networks): if a third user Charlie forwards Alice's ciphertext to Bob and, additionally, knows a recently renewed public key of Bob's, Charlie could re-encrypt the ciphertext for better PCS. We call this extended notion IKEMR. Our first IKEMR construction based on trapdoor permutations has (almost) constant sized ciphertexts in the number of re-encryptions; and our second IKEMR construction based on FS-PKE has constant sized public keys in the interval size. Finally, to bypass our lower bound on the IKEM(R) secret key size, which must be linear in the interval size, we develop a new Interval RAM primitive with which Bob only stores a constant sized part of his secret key locally, while outsourcing the rest to a (possibly adversarial) server. For all our constructions, we achieve security against active adversaries. For this, we obtain new insights on Replayable CCA security for KEM-type primitives, which might be of independent interest.

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.

Functional encryption (FE) is a cutting-edge research topic in cryptography. The Agr17 FE scheme is a major scheme of FE area. This scheme had the novelty of “being applied for the group of general functions (that is, {\sf P/poly} functions) without IO”. It took the BGG+14 ABE scheme as a bottom structure, which was upgraded into a “partially hiding attribute” scheme, and combined with a fully homomorphic encryp-tion (FHE) scheme. However, the Agr17 FE scheme had a strange operation. For noise cancellation of FHE decryption stage, it used bulky “searching noise” rather than elegant “filtering”. It searched total modulus interval, so that the FHE modulus should be polynomially large. In this paper we discuss the {\sf P/poly} validity of the Agr17 FE scheme. First, we obtain the result that the Agr17 FE scheme is {\sf P/poly} invalid. More detailedly, when the Agr17 FE scheme is applied for the group of randomly chosen {\sf P/poly} Boolean functions, FHE modulus at the “searching” stage cannot be polynomially large. Our analysis is based on three restrictions of the BGG+14 ABE scheme: (1) The modulus of the BGG+14 ABE should be adapted to being super-polynomially large, if it is applied for the group of randomly chosen {\sf P/poly} functions. (2) The modulus of the BGG+14 ABE cannot be switched. (3) If the BGG+14 ABE is upgraded into a “partially hiding attribute” scheme, permitted operations about hidden part of the attribute can only be affine operations. Then, to check whether the {\sf P/poly} validity can be obtained by modifying the scheme, we consider two modified versions. The first modified version is controlling the FHE noise by repeatedly applying bootstrapping, and replacing a modular inner product with an arithmetic inner product. The second modified version is replacing the search for the modulus interval with the search for a public noise interval, hoping such noise interval polynomially large and tolerating the modulus which may be super-polynomially large. The first modified version may be {\sf P/poly} valid, but it is weaker. There is no evidence to support the {\sf P/poly} validity of the second modified version. We also present an additional conclusion that there is no evidence to support the {\sf P/poly} validity of the GVW15 PE scheme. Finally, we present our response to an argument that our work is unnecessary, and show that our work is quite valuable for any interpretation.

Anamorphic encryptions and anamorphic signatures assume a double key pre-shared between two parties so as to enable the transmission of covert messages. How to securely and efficiently distribute a double key under the dictator's surveillance is a central problem for anamorphic cryptography, especially when the users are forced to surrender their long-term secret keys or even the randomness used in the algorithms to the dictator. In this paper, we propose Anamorphic Authentication Key Exchange (AM-AKE) to solve the problem. Similar to anamorphic encryption, AM-AKE contains a set of anamorphic algorithms besides the normal algorithms. With the help of the anamorphic algorithms in AM-AKE, the initiator and the responder are able to exchange not only a session key but also a double key. We define robustness and security notions for AM-AKE, and also prove some impossibility results on plain AM-AKE whose anamorphic key generation algorithm only outputs a key-pair. To bypass the impossibility results, we work on two sides. -- On the one side, for plain AM-AKE, the securities have to be relaxed to resist only passive attacks from the dictator. Under this setting, we propose a generic construction of two-pass plain AM-AKE from a two-pass AKE with partially randomness-recoverable algorithms. -- On the other side, we consider (non-plain) AM-AKE whose key generation algorithm also outputs an auxiliary trapdoor besides the key-pairs. We ask new properties from AKE: its key generation algorithm has secret extractability and other algorithms have separability. Based on such a two-pass AKE, we propose a generic construction of two-pass (non-plain) AM-AKE. The resulting AM-AKE enjoys not only robustness but also the strong security against any dictator knowing both users' secret keys and even the internal randomness of the AKE algorithms and implementing active attacks. Finally, we present concrete AM-AKE schemes from the popular SIG+KEM paradigm and three-KEM paradigm for constructing AKE.

We consider the multi-user security under the adaptive corruptions and key leakages ($\rm{MU^{c\&l}}$ security) for lattice-based signatures. Although there exists an $\rm{MU^{c\&l}}$ secure signature based on a number-theoretic assumption, or a leakage-resilient lattice-based signature in the single-user setting, $\rm{MU^{c\&l}}$ secure lattice-based signature is not known. We examine the existing lattice-based signature schemes from the viewpoint of $\rm{MU^{c\&l}}$ security, and find that the security of the Lyubashevsky's signature, which is proven to have the ordinary single-user security only, can be extended to the multi-user security even if we take the adaptive corruptions and the key leakages into account. Our security proof in the multi-user setting makes use of the feature of the SIS problem so that a SIS instance is set to the public parameter and a reduction algorithm can set a public key with a secret key in order to answer a corruption query. We also show that the entropy of the secret key is kept under the bounded leakage with a high probability and then the leakage resilience of signature holds.

Fully Homomorphic Encryption has known impressive improvements in the last 15 years, going from a technology long thought to be impossible to an existing family of encryption schemes able to solve a plethora of practical use cases related to the privacy of sensitive information. Recent results mainly focus on improving techniques within the traditionally defined framework of GLWE-based schemes, but the recent CPU implementation improvements are mainly incremental. To keep improving this technology, one solution is to modify the aforementioned framework, by using slightly different hardness assumptions. In this paper, we identify two limitations with (T)FHE: (i) there is no fine-grained control over the size of a GLWE secret key, which is traditionally composed of $k$ polynomials with $N=2^\alpha>1$ coefficients; (ii) for security reasons one cannot use a noise variance smaller than a certain $\sigma_{\min}$ so, for all ciphertext modulus $q\in \mathbb{N}$, there exists an integer $n_{\mathsf{plateau}}$ such that, with any secret key of size $k\cdot N \ge n_{\mathsf{plateau}}$, one cannot control their level of security, resulting in unnecessary big security levels. To overcome the aforementioned limitations, we introduce two new types of secret keys for GLWE-based cryptosystems, that can be used separately or together. We explain why these new secret keys are as secure as the traditional ones and we detail all the improvements that they bring to existing FHE algorithms alongside new algorithms especially efficient with these new keys. We provide many comparisons with state-of-the-art TFHE techniques with traditional secret keys, and some benchmarks showing computational speed-ups between $1.3$ and $2.4$ while keeping the same level of security and failure probability (correctness). Furthermore, the size of the key switching and bootstrapping keys is also reduced with this contribution by factors ranging from $1.5$ to $2.7$.

Cryptographic agility, the ability to easily and quickly modify cryptography in a sys- tem, is one of the most important features of any cryptographic system. Any algorithm may be attacked and, at some point in time, be broken. The most obvious solution is to change the cryptographic algorithm, however this has high risk and cost. Another solution is to use agile algorithms. Agile algorithms have security parameters easily changed to increase protection against attacks. In this paper we will show that finite field based algorithms are the most agile of currently used classical cryptography. A critical portion of this will be to show that the bottleneck for the primary costing attack, the number field sieve, is the linear algebra portion of the attack, and not the sieving portion. This paper examines the agility of all three algorithm categories and dispels a few myths about their strengths.

We obfuscate words of a given length in a free monoid on two generators with a simple factorization algorithm (namely $SL_2(\mathbb{N})$) to create a public-key encryption scheme. We provide a reference implementation in Python and suggested parameters. The security analysis is between weak and non-existent, left to future work.

A broadcast encryption scheme allows a user to encrypt a message to $N$ recipients with a ciphertext whose size scales sublinearly with $N$. While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup process that generates a set of public parameters. Thereafter, users can independently generate their own public keys and post them to a public-key directory. Moreover, anyone can broadcast an encrypted message to any subset of user public keys with a ciphertext whose size scales sublinearly with the size of the broadcast set. Unlike traditional broadcast encryption, there are no long-term secrets in distributed broadcast encryption and users can join the system at any time (by posting their public key to the public-key directory). Previously, distributed broadcast encryption schemes were known from standard pairing-based assumptions or from powerful tools like indistinguishability obfuscation or witness encryption. In this work, we provide the first distributed broadcast encryption scheme from a falsifiable lattice assumption. Specifically, we rely on the $\ell$-succinct learning with errors (LWE) assumption introduced by Wee (CRYPTO 2024). Previously, the only lattice-based candidate for distributed broadcast encryption goes through general-purpose witness encryption, which in turn is only known from the /private-coin/ evasive LWE assumption, a strong and non-falsifiable lattice assumption. Along the way, we also describe a more direct construction of broadcast encryption from lattices.

Blind signature schemes enable a user to obtain a digital signature on a message from a signer without revealing the message itself. Among the most fundamental examples of such a scheme is blind Schnorr, but recent results show that it does not satisfy the standard notion of security against malicious users, One-More Unforgeability (OMUF), as it is vulnerable to the ROS attack. However, blind Schnorr does satisfy the weaker notion of sequential OMUF, in which only one signing session is open at a time, in the Algebraic Group Model (AGM) + Random Oracle Model (ROM), assuming the hardness of the Discrete Logarithm (DL) problem. This paper serves as a first step towards characterizing the security of blind Schnorr in the limited concurrency setting. Specifically, we show that blind Schnorr satisfies OMUF when at most two signing sessions can be concurrently open (in the AGM+ROM, assuming DL). Our argument suggests that it is plausible that blind Schnorr satisfies OMUF for up to polylogarithmically many concurrent signing sessions. Our security proof involves interesting techniques from linear algebra and combinatorics.

We present new lattice-based attribute-based encryption (ABE) and laconic function evaluation (LFE) schemes for circuits with *sublinear* ciphertext overhead. For depth $d$ circuits over $\ell$-bit inputs, we obtain * an ABE with ciphertext and secret key size $O(1)$; * a LFE with ciphertext size $\ell + O(1)$ and digest size $O(1)$; * an ABE with public key and ciphertext size $O(\ell^{2/3})$ and secret key size $O(1)$, where $O(\cdot)$ hides $\mbox{poly}(d,\lambda)$ factors. The first two results achieve almost optimal ciphertext and secret key / digest sizes, up to the $\mbox{poly}(d)$ dependencies. The security of our schemes relies on $\ell$-succinct LWE, a falsifiable assumption which is implied by evasive LWE. At the core of our results is a new technique for compressing LWE samples $\mathbf{s}(\mathbf{A}-\mathbf{x} \otimes \mathbf{G})$ as well as the matrix $\mathbf{A}$.

We propose time-memory trade-off algorithms for evaluating look-up table (LUT) in both the leveled homomorphic encryption (LHE) and fully homomorphic encryption (FHE) modes in TFHE. For an arbitrary $n$-bit Boolean function, we reduce evaluation time by a factor of $O(n)$ at the expense of an additional memory of "only" $O(2^n)$ as a trade-off: The total asymptotic memory is also $O(2^n)$, which is the same as that of prior works. Our empirical results demonstrate that a $7.8 \times$ speedup in runtime is obtained with a $3.8 \times$ increase in memory usage for 16-bit Boolean functions in the LHE mode. Additionally, in the FHE mode, we achieve reductions in both runtime and memory usage by factors of $17.9 \times$ and $2.5 \times $, respectively, for 8-bit Boolean functions. The core idea is to decompose the function $f$ into sufficiently small subfunctions and leverage the precomputed results for these subfunctions, thereby achieving significant performance improvements at the cost of additional memory.

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.

We present the first Key Policy Attribute-Based Encryption (KP-ABE) scheme employing isogeny-based cryptography through class group actions, specifically utilizing the Csi-FiSh instantiation and pairing groups. We introduce a new assumption, denoted Isog-DLin, which combines the isogeny and DLin assumptions. We propose the following constructions: a small universe KP-ABE and a large universe KP-ABE under the Isog-DBDH assumption, and a small universe KP-ABE under the Isog-DLin assumption. In these constructions, the master key is designed to be secure against quantum computer attacks, while the ciphertext remains secure against classical computer attacks. This dual-layered approach ensures robust security across classical and quantum computational paradigms, addressing current and potential future cryptographic challenges.

A cryptographic accumulator is a compact data structure for representing a set of elements coming from some domain. It allows for a compact proof of membership and, in the case of a universal accumulator, non-membership of an element x in the data structure. A dynamic accumulator, furthermore, allows elements to be added to and deleted from the accumulator. Previously known RSA-based dynamic accumulators were too slow in practice because they required that an element in the domain be represented as a prime number. Accumulators based on settings other than RSA had other drawbacks such as requiring a prohibitively large common reference string or a trapdoor, or not permitting deletions. In this paper, we construct RSA-based dynamic accumulators that do not require that the accumulated elements be represented as primes. We also show how to aggregate membership and non-membership witnesses and batch additions and deletions. We demonstrate that, for 112-bit, 128-bit, and 192-bit security, the efficiency gains compared to previously known RSA-based accumulators are substantial, and, for the first time, make cryptographic accumulators a viable candidate for a certificate revocation mechanism as part of a WebPKI-type system. To achieve an efficient verification time for aggregated witnesses, we introduce a variant of Wesolowski’s proof of exponentiation (Journal of Cryptology 2020) that does not require hashing into primes.

Bootstrapping stands as a fundamental component of fully homomorphic encryption (FHE) schemes, facilitating an infinite number of operations by recovering the ciphertext modulus. This work is aimed at significantly reducing the consumption of modulus in bootstrapping, thereby enhancing the efficiency of FHE performance, specifically for the Cheon--Kim--Kim--Song (CKKS) scheme proposed by Cheon et al. Building on the EvalRound bootstrapping method proposed by Kim et al., which includes the steps of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, we introduce $\textrm{EvalRound}^{+}$ bootstrapping. This bootstrapping inherits the advantage of EvalRound bootstrapping in CoeffToSlot and resolves its disadvantage in SlotToCoeff. Furthermore, we conduct a set of rigorous and comprehensive analyses to precisely determine the optimal choices of the parameters. The implementation of $\textrm{EvalRound}^{+}$ bootstrapping, along with optimal choices, has achieved a reduction in modulus consumption by over $40\%$ for CoeffToSlot and SlotToCoeff. Additionally, it has increased the number of levels for general multiplication by 2-4 in the most widely used bootstrapping parameter sets.

Blind signatures have garnered significant attention in recent years, with several efficient constructions in the random oracle model relying on well-understood assumptions. However, this progress does not apply to pairing-free cyclic groups: fully secure constructions over cyclic groups rely on pairings, remain inefficient, or depend on the algebraic group model or strong interactive assumptions. To address this gap, Chairattana-Apirom, Tessaro, and Zhu (CTZ, Crypto 2024) proposed a new scheme based on the CDH assumption. Unfortunately, their construction results in large signatures and high communication complexity. In this work, we propose a new blind signature construction in the random oracle model that significantly improves upon the CTZ scheme. Compared to CTZ, our scheme reduces communication complexity by a factor of more than 10 and decreases the signature size by a factor of more than 45, achieving a compact signature size of only 224 Bytes. The security of our scheme is based on the DDH assumption over pairing-free cyclic groups, and we show how to generalize it to the partially blind setting.

Fully homomorphic encryption schemes are methods to perform compu- tations over encrypted data. Since its introduction by Gentry, there has been a plethora of research optimizing the originally inefficient cryptosystems. Over time, different families have emerged. On the one hand, schemes such as BGV, BFV, or CKKS excel at performing coefficient-wise addition or multiplication over vectors of encrypted data. In contrast, accumulator-based schemes such as FHEW and TFHE provide efficient methods to evaluate boolean circuits and means to efficiently compute functions over small plaintext space of up to 4-5 bits in size. In this paper, we focus on the second family. At a high level, accumulator-based schemes encode the range of a function f in the coefficients of a polynomial, which is then encrypted in a homomorphic accumulator. Given an input ciphertext, the coefficients of the encrypted polynomial are homomorphically rotated, such that there is a correspondence between the constant term of the result and the message contained in the ciphertext. In the end, it is possible to derive a ciphertext of the constant term encrypted with regard to the same encryption scheme as the input ciphertext. To summarize, by appropriately encoding the function f on the accumulated polynomial, we can compute f on the plaintext of the input ciphertext, where the output ciphertext has its noise magnitude independent of the input ciphertext. However, by default, it is necessary to impose restrictions on the type of functions we evaluate or drastically limit the plaintext space that can be correctly processed. Otherwise, the procedure’s output will be incorrect and hard to predict. In this work, we describe two novel algorithms that have no such restrictions. Furthermore, we derive an algorithm that enables a user to evaluate an arbitrary amount of functions at a computational cost that differs only by a constant amount compared to a single function. Our methods lead to an evaluation that is between 15 and 31% faster than previous works while also being conceptually simpler.

In this article, we propose a generic hybrid encryption scheme providing entity authentication. The scheme is based on lossy trapdoor functions relying on the hardness of the Learning With Errors problem. The construction can be used on a number of different security requirements with minimal reconfiguration. It ensures entity authentication and ciphertext integrity while providing security against adaptive chosen ciphertext attacks in the standard model. As a desired characteristic of schemes providing entity authentication, we prove the strong unforgeability under chosen message attack for the construction. In addition, the scheme is post-quantum secure based on the hardness of the underlying assumption.

We propose a new NTRU-based Public-Key Encryption (PKE) scheme called $\mathsf{NTRU+}\mathsf{PKE}$, which effectively incorporates the Fujisaki-Okamoto transformation for PKE (denoted as $\mathsf{FO}_{\mathsf{PKE}}$) to achieve chosen-ciphertext security in the Quantum Random Oracle Model (QROM). While $\mathsf{NTRUEncrypt}$, a first-round candidate in the NIST PQC standardization process, was proven to be chosen-ciphertext secure in the Random Oracle Model (ROM), it lacked corresponding security proofs for QROM. Our work extends the capabilities of the recent $\mathsf{ACWC}_{2}$ transformation, proposed by Kim and Park in 2023, by demonstrating that an $\mathsf{ACWC}_{2}$-transformed scheme can serve as a sufficient foundation for applying $\mathsf{FO}_\mathsf{PKE}$. Specifically, we show that the $\mathsf{ACWC}_{2}$-transformed scheme achieves (weak) $\gamma$-spreadness, an essential property for constructing an IND-CCA secure PKE scheme. Moreover, we provide the first proof of the security of $\mathsf{FO}_\mathsf{PKE}$ in the QROM. Finally, we show that $\mathsf{FO}_\mathsf{PKE}$ can be further optimized into a more efficient transformation, $\overline{\mathsf{FO}}_\mathsf{PKE}$, which eliminates the need for re-encryption during decryption. By instantiating an $\mathsf{ACWC}_{2}$-transformed scheme with appropriate parameterizations, we construct $\mathsf{NTRU+}\mathsf{PKE}$, which supports 256-bit message encryption. Our implementation results demonstrate that at approximately a classical 180-bit security level, $\mathsf{NTRU+}\mathsf{PKE}$ is about 2 times faster than \textsc{Kyber} + AES-256-GCM in AVX2 mode.

Due to their simplicity, compactness, and algebraic structure, BLS signatures are among the most widely used signatures in practice. For example, used as multi-signatures, they are integral in Ethereum's proof-of-stake consensus. From the perspective of concrete security, however, BLS (multi-)signatures suffer from a security loss linear in the number of signing queries. It is well-known that this loss can not be avoided using current proof techniques. In this paper, we introduce a new variant of BLS multi-signatures that achieves tight security while remaining fully compatible with regular BLS. In particular, our signatures can be seamlessly combined with regular BLS signatures, resulting in regular BLS signatures. Moreover, it can easily be implemented using existing BLS implementations in a black-box way. Our scheme is also one of the most efficient non-interactive multi-signatures, and in particular more efficient than previous tightly secure schemes. We demonstrate the practical applicability of our scheme by showing how proof-of-stake protocols that currently use BLS can adopt our variant for fully compatible opt-in tight security.

In LWE based cryptosystems, using small (polynomially bounded) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs "simulation security": the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Rényi divergence based analyses that are sufficient for game-based but not simulation security. In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially bounded modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.

In proof-of-stake blockchains, liveness is ensured by repeatedly selecting random groups of parties as leaders, who are then in charge of proposing new blocks and driving consensus forward. The lotteries that elect those leaders need to ensure that adversarial parties are not elected disproportionately often and that an adversary can not tell who was elected before those parties decide to speak, as this would potentially allow for denial-of-service attacks. Whenever an elected party speaks, it needs to provide a winning lottery ticket, which proves that the party did indeed win the lottery. Current solutions require all published winning tickets to be stored individually on-chain, which introduces undesirable storage overheads. In this work, we introduce non-interactive aggregatable lotteries and show how these can be constructed efficiently. Our lotteries provide the same security guarantees as previous lottery constructions, but additionally allow any third party to take a set of published winning tickets and aggregate them into one short digest. We provide a formal model of our new primitive in the universal composability framework. As one of our technical contributions, which may be of independent interest, we introduce aggregatable vector commitments with simulation-extractability and present a concretely efficient construction thereof in the algebraic group model in the presence of a random oracle. We show how these commitments can be used to construct non-interactive aggregatable lotteries. We have implemented our construction, called Jackpot, and provide benchmarks that underline its concrete efficiency.

Vector commitment schemes allow a user to commit to a vector of values $\mathbf{x} \in \{0,1\}^\ell$ and later, open up the commitment to a specific set of positions. Both the size of the commitment and the size of the opening should be succinct (i.e., polylogarithmic in the length $\ell$ of the vector). Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols. We introduce a new framework for constructing non-interactive lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary bounded-depth Boolean circuits. In this scheme, a user commits to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\mathbf{x})$. Both the commitment and the opening are non-interactive and succinct: namely, they have size $\textsf{poly}(\lambda, d, \log \ell)$, where $\lambda$ is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new falsifiable family of "basis-augmented" SIS assumptions (BASIS) we introduce in this work. We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.

Data availability sampling allows clients to verify availability of data on a peer-to-peer network provided by an untrusted source. This is achieved without downloading the full data by sampling random positions of the encoded data. The long-term vision of the Ethereum community includes a comprehensive data availability protocol using polynomial commitments and tensor codes. As the next step towards this vision, an intermediate solution called PeerDAS is about to integrated, to bridge the way to the full protocol. With PeerDAS soon becoming an integral part of Ethereum's consensus layer, understanding its security guarantees is essential. This document aims to describe the cryptography used in PeerDAS in a manner accessible to the cryptographic community, encouraging innovation and improvements, and to explicitly state the security guarantees of PeerDAS.