Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building...

We analyze Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$. Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the...

A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect...

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity-theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following: (1) Any quantum state $2$-design yields...

The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. Wagner's \(k\)-list algorithm (Crypto'02) for $\textsf{GBP}$ has advanced the optimization of solving the syndrome decoding problem and established new cryptanalytic benchmarks for incremental cryptography and blind signatures. $\textsf{Equihash}$ (NDSS'16) underscores the critical advantages of $\textsf{GBP}$ in...

This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel > 1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ≈ log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J. The result formalizes the Invisible Authenticity...

Constrained PRFs are PRFs that allow the generation of constrained keys, which can be used to evaluate the PRF on a subset of the inputs. The PRF is still pseudorandom for an adversary who obtains multiple of these constrained keys on all inputs where none of the constrained keys allow it to evaluate the PRF. Constrained PRFs are known for some simple constraint classes (such as puncturing or intervals) from one-way functions, but for more powerful constraint classes such as bitfixing the...

A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $N$. The breakthrough work of Lin-Mook-Wichs (STOC’23) presented the first DEPIR construction from the Ring-LWE assumption. This...

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect...

Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on...

An $(\epsilon_\mathsf{s},\epsilon_{\mathsf{zk}})$-weak non-interactive zero knowledge (NIZK) argument has soundness error at most $\epsilon_\mathsf{s}$ and zero-knowledge error at most $\epsilon_{\mathsf{zk}}$. We show that as long as $\mathsf{NP}$ is hard in the worst case, the existence of an $(\epsilon_\mathsf{s}, \epsilon_{\mathsf{zk}})$-weak NIZK proof or argument for $\mathsf{NP}$ with $\epsilon_{\mathsf{zk}} + \sqrt{\epsilon_\mathsf{s}} < 1$ implies the existence of one-way...

We present improved definitions and constructions for copy-protected digital signatures and pseudorandom functions (PRFs). Our new security definitions support challenge messages or inputs chosen from arbitrary high min-entropy distributions and allow signing or evaluation queries. This extends prior definitions, which assumed uniformly random challenges and did not consider oracle access. We construct schemes that satisfy these stronger definitions using only polynomially secure...

We study the multi-source randomness extraction and generation properties of the monolithic random oracle (RO), whereby one is tasked with extracting or generating uniform random bits from multiple arbitrary unpredictable sources. We formalize this problem according to the query complexities of the involved parties—sources, distinguishers, and predictors, where the latter are used to define unpredictability. We show both positive and negative results. On the negative side, we rule out...

In 2000, Pliam showed that there does not exist an upper or lower bound in terms of Shannon entropy alone for the number of guesses required in order to guess some randomly sampled element $s$ with certainty $0<q<1$, denoted as marginal guesswork. In comparison, it was shown by Arikan in 1996 that, if the distribution is defined over finite support, the expected guesswork, that is the expected amount of trials it takes to guess some random element $s$ with certainty, is bound in terms...

Quantum copy-protection is a foundational notion in quantum cryptography that leverages the governing principles of quantum mechanics to tackle the problem of software anti-piracy. Despite progress in recent years, precisely characterizing the class of functionalities that can be copy-protected is still not well understood. Two recent works, by [Coladangelo and Gunn, STOC 2024] and [Ananth and Behera, CRYPTO 2024, showed that puncturable functionalities can be copy-protected. Both works...

At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lattice $\mathbb{Z}^n$. Here the search problem asks to find an isometry between $\mathbb{Z}^n$ and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to $\mathbb{Z}^n$. In this work we generalize Szydlo's search to distinguish reduction in two ways. Firstly, we generalize the reduction to any...

Quantum copy-protection (Aaronson, CCC'09) is the problem of encoding a functionality/key into a quantum state to achieve an anti-piracy security notion that guarantees that the key cannot be split into two keys that both still work. Most works so far has focused on constructing copy-protection for specific functionalities. The only exceptions are the work of Aaronson, Liu, Liu, Zhandry, Zhang (CRYPTO'21) and Ananth and Behera (CRYPTO'24). The former constructs copy-protection for all...

Private constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don't know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key...

Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case hardness of $\mathsf{NP}$, is known to imply one-way functions (OWFs) and a range of advanced cryptographic primitives, the cryptographic implications of quantum iO remain poorly understood. In this work, we initiate a study of the power of quantum iO. We define several natural variants of quantum iO, distinguished...

We suggest a generalization of homomorphic encryption (HE) schemes from a purely geometrical and lattice-based perspective. All the current reference HE schemes are based on the ring version of the Learning with Errors (LWE) problem. In this proposal, we first investigate LWE-based cryptosystems from a lattice point of view and present a framework that allows to obtain the same result, in geometrical terms, from any lattice — as long as it contains a sufficiently short trapdoor vector....

Based on a sharpening of Carmichael’s theorem and Euler’s theorem we generalize RSA and CRT-RSA to arbitrary integer moduli $n > 1$, while restricting messages to integers $m$ which are regular modulo $n$, meaning that they have a John-von-Neumann pseudoinverse modulo $n$. We prove the correctness and completeness of our encryption and decryption method for this class of messages, and show that the restriction to regular integers is negligible, since under reasonable assumptions almost all...

One-Time Pad (OTP), introduced by Shannon, is well-known as an unconditionally secure encryption algorithm and has become the cornerstone of modern cryptography. However, the unconditional security of OTP applies solely to confidentiality and does not extend to integrity. Hash functions such as SHA2, SHA3 or SM3 applies only to integrity but not to confidentiality and also can not obtain unconditional security. Encryption and digital signatures based on asymmetric cryptography can provide...

The Learning Parity with Noise (LPN) problem has become a cornerstone for building lightweight, post-quantum secure encryption schemes. Despite its widespread adoption, LPN-based constructions suffer from a fundamental efficiency limitation: the essential noise term that provides security simultaneously requires error correction coding, leading to bandwidth overhead. We introduce a variant of LPN termed Learning Parity with Quantization (LPQ). While maintaining the ``learning from noisy...

Given a sequence of $N$ independent sources $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error...

Inductive reasoning in form of hybrid arguments is prevalent in cryptographic security proofs, but they are not integrated into formalisms used to model cryptographic security proofs, such as, for example, state-separating proofs. In this paper we present an induction principle for hybrid arguments that says that two games are many-steps indistinguishable if they are, respectively, indistinguishable from the end points of an iterated one-step indistinguishability argument. We demonstrate how...

In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of $n$-party AND, the exact complexity is unknown. We improve the upper bound from Couteau and Ros\'en in Asiacrypt 2022 on the (asymptotic) randomness complexity of $n$-party AND from 6 to 5 bits, that is, we give a...

One of the main shortcomings of classical distributed cryptography is its reliance on a certain fraction of participants remaining honest. Typically, honest parties are assumed to follow the protocol and not leak any information, even if behaving dishonestly would benefit them economically. More realistic models used in blockchain consensus rely on weaker assumptions, namely that no large coalition of corrupt parties exists, although every party can act selfishly. This is feasible since, in...

Protocols for State-Machine-Replication (sometimes called 'blockchain' protocols) generally make use of rotating leaders to drive consensus. In typical protocols (henceforth called 'single-sender' protocols), the leader is a single processor responsible for making and disseminating proposals to others. Since the leader acts as a bottleneck, apparently limiting throughput, a recent line of research has investigated the use of 'multi-sender' protocols in which many processors distribute...

In this work, we develop a framework for compiling languages into efficient Interactive Oracle Proofs (IOPs, or ‘circuits’), motivated by applications in verifiable Virtual Machine (zkVM) design. We provide a set of sufficient conditions on a language under which it can be compiled into an efficient IOP, alongside corresponding performance costs. We identify a subclass of languages, which we denote as traversable, and demonstrate how traversable languages can be efficiently compiled as...

We develop a toolbox for modular construction and analysis of succinct, non-interactive commitments and vector commitments in the random oracle model, while guaranteeing universally composable security. To demonstrate its power, we use the toolbox to construct and analyze a modular variant of the Kilian-Micali ZK-SNARK. Along the way we also propose a new UC formulation of a global random oracle, that avoids a weakness in existing formulations and also enables expressing more nuanced,...

Quantum computing is often introduced through the lens of linear algebra with notation that is inherited from quantum mechanics. In this paper, we take an operational view of quantum computing that is easy to demonstrate programmatically. The hope is that this viewpoint will (1) demystify quantum computing and make it more accessible to a wider audience, particularly computer science students and software engineers, and (2) possibly serve as the basis of a formal foundation for automatically...

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis. 1) Obfuscation can serve as a general-purpose worst-case to average-case reduction, reducing the existence of various forms of cryptography to corresponding worst-case assumptions. 2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond $\mathsf{P}\neq \mathsf{NP}$, and...

In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially...

A reduction showing that the hardness of the discrete logarithm ($\mathsf{DL}$) assumption implies the hardness of the computational Diffie-Hellman ($\mathsf{CDH}$) assumption in groups of order $p$, where $p - 1$ is smooth, was first presented by den Boer [Crypto, 88].} We also consider groups of prime order $p$, where $p - 1$ is somewhat smooth (say, every prime $q$ that divides $p - 1$ is less than $2^{100}$). Several practically relevant groups satisfy this condition. 1. ...

As Internet of Things (IoT) systems become increasingly complex, verifying communication protocols is essential to guarantee their security and correctness. This paper introduces a brief introduction to the theoretical concepts of how to use formal techniques, LTL and rewriting logic within the Maude system to verify the security and proper behavior of the protocols. While rewriting logic explains how various events occur over time, LTL explains how a property can be formulated. This...

We make the case for modeling unitary oracles by allowing for controlled access to the oracle as well as its conjugate transpose (inverse), but also its conjugate and transpose. Controlling and conjugate transposes are common if even standard, but conjugates and transposes appear to be non-standard. In order to justify our modeling, we give several formal examples of what goes wrong or is missed when using a more restrictive modeling. We also argue that our model is the "right" level of...

Modular arithmetic is the computational backbone of many cryptographic and scientific algorithms. In particular, modular multiplication in a large prime field is computationally expensive and dictates the runtime of many algorithms. While it is relatively easy to utilize vectorization to accelerate batches of independent modular multiplications, our goal is to reduce the latency of a $\textit{single}$ modular multiplication under a generic prime using vectorization, while maintaining...

We construct $t$-non-malleable extractors---which allow an attacker to tamper with a source $t$ times---for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions. We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against \emph{uniform} adversaries from \emph{uniform} falsifiable...

In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical. We also prove a...

A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as...

Pseudorandom codes (PRCs) are error-correcting codes with the distinguishing feature that their codewords are computationally indistinguishable from random strings. Introduced by Christ and Gunn (CRYPTO 2024), PRCs have found applications in areas such as AI watermarking, where both robustness and pseudorandomness are essential. All known constructions of PRCs rely on coding-theoretic hardness assumptions. In this work, we study how inherent the use of coding-theoretic hardness is in the...

Secret sharing (SS) is a foundational cryptographic primitive with diverse applications, including secure multiparty computation and conditional disclosure of secrets. While traditional schemes have primarily emphasized information-theoretic security, recent advancements have increasingly leveraged computational assumptions to achieve more efficient constructions and support broader access policies. Despite these successes, most existing computational secret sharing (CSS) schemes are limited...

Adaptive trapdoor functions (ATDFs) and tag-based ATDFs (TB-ATDFs) are variants of trapdoor functions proposed by Kiltz, Mohassel, and O’Neill (EUROCRYPT 2010). They are both sufficient for constructing chosen-ciphertext secure public-key encryption (CCA-secure PKE), and their definitions are closely related to CCA-secure PKE. Hohenberger, Koppula, and Waters (CRYPTO 2020) showed that CCA-secure PKE can be constructed from injective TDFs; however, the relations among TDF, ATDF, and TB-ATDF...

A long line of work has investigated the design of scalable secure multiparty computation (MPC) protocols with computational and communication complexity independent of the number of parties (beyond any dependence on the circuit size). We present the first unconditionally-secure MPC protocols for arithmetic circuits over {\em large fields} with total computation $\mathcal{O}(|C|\log|F|)$, where $|C|$ and $|F|$ denote the circuit and field size, respectively. Prior work could either...

Secure multiparty computation allows multiple parties to jointly compute a function while maintaining security even in the presence of malicious adversaries. There are two types of adversaries in the literature: static adversaries, which choose the parties to corrupt before the protocol begins; and adaptive adversaries, which can corrupt parties during the execution of the protocol based on the messages exchanged by the parties. While adaptive security provides a more robust security...

Secret sharing is a foundational cryptographic primitive for sharing secret keys in distributed systems. In a classical threshold setting, it involves a dealer who has a secret, a set of $n$ users to whom shares of the secret are sent, and a threshold $t$ which is the minimum number of shares required to recover the secret. These schemes offer an all-or-nothing security approach where less than $t$ shares reveal no information about the secret. But these guarantees are threatened by...

The smoothing parameter is a cornerstone concept in lattice-based cryptography. Traditionally defined using the \( L^{\infty} \) distance, this standard formulation can be overly stringent compared to the \( L^1 \) (or statistical) distance more commonly employed in cryptographic contexts. Recent work has proposed relaxed definitions based on Kullback-Leibler (KL) divergence and \( L^1 \) distance, thereby loosening the constraints required for the distance to vanish. However, the additive...

Recently, the concept of incompressible encryption has emerged as a powerful enhancement to key-leakage resilience. In an incompressible encryption scheme, an adversary who intercepts ciphertexts is forced to dedicate a significant amount of memory to store them in full if they wish to extract any information about the plaintext later when the secret key becomes available. Given two messages, the security game involves two adversaries: the first adversary receives an encryption of one of the...

Some of the most valuable applications of homomorphic encryption, such as encrypted machine learning inference, require efficient large-scale plaintext-ciphertext and ciphertext-ciphertext matrix multiplications. Current state-of-the-art techniques for matrix multiplications all build on the ability to pack many ciphertexts into a ciphertext and compute on them in a Single Instruction, Multiple Data (SIMD) manner. However, to fit the operation of matrix multiplication into this computational...

In TCC 2018, Boneh, Ishai, Passelègue, Sahai, and Wu propose candidates of weak and strong PRFs by evaluating linear functions over coprime moduli alternatively. Such PRFs can be evaluated by low-depth circuits and are MPC-friendly. However, they have not been able to base the security of their PRFs on well-formed assumptions other than assuming that the PRF constructions themselves are secure. In this paper, we formalize a new assumption called Learning with Alternating Moduli (LAM)....

In this paper, we propose a new block cipher primitive, based on ring-LWE, which allows key rotation with a possible security update. This makes it possible to double the security of the ciphertext with each key rotation. Our scheme could therefore be used for long-term secret storage, allowing the security of the ciphertext to be adapted to the attacker's computing power, without the need for decryption. We propose an implementation of our cryptographic scheme and prove its security.

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied $\textit{in the classical setting}$ due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, $\textit{post-quantum}$...

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the *BCS transformation* is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding. Prior work established the post-quantum security of Kilian's succinct interactive argument, a special case of the BCS transformation for...

Witness encryption allows one to encrypt a message to an $\mathsf{NP}$ relation $\mathcal{R}$ and a statement $x$. The corresponding decryption key is any valid $\mathsf{NP}$ witness $w$. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the $\mathsf{NP}$ relation. Currently, all realizations of succinct witness encryption for $\mathsf{NP}$ rely on strong assumptions such as pseudorandom obfuscation, extractable witness...

The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under ``resource variability'', i.e., if the total hashing power...

Logic locking is an obfuscation technique designed to protect the intellectual property of hardware designs and has attracted considerable attention for over a decade. However, most logic locking schemes have been developed heuristically, leading the field into a cat-and-mouse game between attackers and defenders. Indeed, several proposed schemes have already been broken. While recent works have introduced provably secure logic locking, they often incur impractical overhead or fail to...

Introduced by Canetti in 2001, Universal Composability (UC) is a widely adopted security model that enables the specification and proof of security for a broad range of protocols, offering strong security guarantees. At its core lies the universal composition theorem (UC theorem), which ensures that protocols proven secure within the framework remain secure even when deployed in real-world environments with multiple instances of them. In this work, we present two key contributions....

In this paper, we show two simple variations of a data availability scheme which enable it to act as a multilinear polynomial commitment scheme over the data in a block. The first variation enables commitments over all of the block's data with zero prover overhead: the data availability construction simply serves both purposes. The second variation allows commitments over subsets of data with nonzero but still concretely small proving costs, since most work is already done during data...

We study the security of a popular paradigm for constructing SNARGs, closing a key security gap left open by prior work. The paradigm consists of two steps: first, construct a public-coin succinct interactive argument by combining a functional interactive oracle proof (FIOP) and a functional commitment scheme (FC scheme); second, apply the Fiat–Shamir transformation in the random oracle model. Prior work did not consider this generalized setting nor prove the security of this second step...

Fully Homomorphic Encryption (FHE) enables computations on encrypted data without requiring decryption. However, each computation increases the noise level, which can eventually cause decryption failures once a certain threshold is reached. In particular, homomorphic multiplication significantly amplifies noise in the ciphertext. In this work, we revisit Ring-learning-With-Error (RLWE) based encryption proposed by Fan et al. and present an optimized noise growth approach by swapping the...

We give new constructions of pseudorandom functions (PRFs) computable in $\mathsf{NC}^1$ from (variants of the) Learning Parity with Noise (LPN) assumption. Prior to our work, the only $\mathsf{NC}^1$-computable PRF from LPN-style assumptions was due to Boyle et al. (FOCS 2020) who constructed a weak PRF from a new heuristic variant of LPN called variable-density LPN. We give the following three results: (1) A weak PRF computable in $\mathsf{NC}^1$ from standard LPN. (2) A...

Directed Acyclic Graph (DAG)-based BFT consensus protocols often suffer from limited throughput and scalability due to bandwidth-intensive data replication to all participants. However, it is sufficient to replicate data to a smaller sub-committee of parties that holds an honest majority with high probability. In this work, we introduce tribe-assisted reliable broadcast, a novel primitive that ensures reliable broadcast (RBC) properties within a smaller honest-majority...

Proximity testing for linear codes is a fundamental problem in coding theory with critical applications in cryptographic protocols, blockchain, and distributed storage systems. This work addresses the proximity gaps for linear codes, a crucial aspect for efficiently verifying whether a batch of codewords is close to a given code. We present a general framework for deriving proximity gaps from the list-decodability properties of the underlying linear code. Our main result shows that if a...

Secret sharing is a cornerstone of modern cryptography, underpinning the secure distribution and reconstruction of secrets among authorized participants. In these schemes, succinctness—measured by the size of the distributed shares—has long been an area of both great theoretical and practical interest, with large gaps between constructions and best known lower bounds. In this paper, we present a novel computational secret sharing scheme for monotone Boolean circuits that achieves...

We introduce a new class of addition chains and show the numbers for which these chains are optimal satisfy the Scholz conjecture, precisely the inequality $$\iota(2^n-1)\leq n-1+\iota(n).$$

Nowadays, the notion of semi-regular sequences, originally proposed by Fröberg, becomes very important not only in Mathematics, but also in Information Science, in particular Cryptology. For example, it is highly expected that randomly generated polynomials form a semi-regular sequence, and based on this observation, secure cryptosystems based on polynomial systems can be devised. In this paper, we deal with a semi regular sequence and its variant, named a generalized cryptographic...

Distributed Key Generation (DKG) protocols are fundamental components of threshold cryptography, enabling key generation in a trustless manner for a range of cryptographic operations such as threshold encryption and signing. Of particular widespread use are DKG protocols for discrete-logarithm based cryptosystems. In this Systematization of Knowledge (SoK), we present a comprehensive analysis of existing DKG protocols in the discrete-logarithm setting, with the goal of identifying...

The literature on computational differential privacy (CDP) has focused almost exclusively on definitions that are computational analogs of `pure' $(\epsilon,0)$-DP. We initiate the formal study of computational versions of approximate DP, i.e. $(\epsilon, \delta)$-DP with non-negligible $\delta$. We focus on IND-CDP and SIM$_{\forall\exists}$-CDP and show that the hierarchy between them when $\delta > 0$ potentially differs substantially from when $\delta = 0$. In one direction, we show that...

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: 1) For...

One approach to solving polynomial systems is to multiply each equation by monomials, which creates a larger system with the coefficient matrix known as the Macaulay matrix. The eXtended Linearization (XL) method, introduced by Courtois, Klimov, Patarin, and Shamir in 2000, is one such approach and includes a sub-algorithm that performs Gaussian elimination on the Macaulay matrix. Due to the simplicity of the method, several improvements and variations have been proposed since its...

The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time. Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of $N$ elements. The classical `baby-step giant-step' algorithm for the...

In the $k$-Orthogonal Vectors ($k$-OV) problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^{o(1)}$, and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require $n^{k-o(1)}$ time in the worst case. We propose a way to plant a solution among vectors with i.i.d. $p$-biased entries, for appropriately chosen $p$, so that the planted solution...

One-way functions (OWFs) form the foundation of modern cryptography, yet their unconditional existence remains a major open question. In this work, we study this question by exploring its relation to lossy reductions, i.e., reductions $R$ for which it holds that $I(X;R(X)) \ll n$ for all distributions $X$ over inputs of size $n$. Our main result is that either OWFs exist or any lossy reduction for any promise problem $\Pi$ runs in time $2^{\Omega(\log\tau_\Pi / \log\log n)}$, where...

We study the problem of how to find the inverse of shift invariant (SI) transformations proposed in Daemen's thesis. In particular, two of them have been used in practice: $y_i=x_i\oplus \overline{x_{i+1}}x_{i+2}$ and $y_i=x_i\oplus \overline{x_{i+1}}x_{i+2}x_{i+3}$. The first one is the well-known $\chi$ transformation used in \textsf{SHA-3}, \textsf{Subterranean 2.0} and \textsf{Rasta}, while the second one is used in a recently proposed ZK-friendly hash function called Monolith. While the...

AES-GCM has seen great adoption for the last 20 years to protect data in various use-cases because of its optimal performance. It has also posed some challenges to modern applications due to its nonce, block size, and lack of key commitment. Nonce-derived schemes address these challenges by deriving a different key from random values and using GCM with the derived key. In this work, we explore efficient key commitment methods for nonce-derived schemes. For concreteness, we focus on expanding...

Secure rate-distortion-perception (RDP) trade-offs arise in critical applications, such as semantic compression and privacy-preserving generative coding, where preserving perceptual quality while minimizing distortion is vital. This paper studies a framework for secure RDP over noiseless and noisy broadcast channels under strong secrecy constraints. We first characterize the exact secure RDP region for noiseless transmission channels. We then develop an inner bound on the secure RDP region...

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum...

While one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no...

The sponge is a cryptographic construction that turns a public permutation into a hash function. When instantiated with the Keccak permutation, the sponge forms the NIST SHA-3 standard. SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption. While one can consider many security properties for the sponge, the ultimate one is \emph{indifferentiability from a random oracle}, or simply \emph{indifferentiability}. The sponge was proved...

Quantum fire was recently formalized by Bostanci, Nehoran and Zhandry (STOC’25). This notion considers a distribution of quantum states that can be efficiently cloned, but cannot be converted into a classical string. Previously, work of Nehoran and Zhandry (ITCS’24) showed how to construct quantum fire relative to an inefficient unitary oracle. Later, the work of Bostanci, Nehoran, Zhandry gave a candidate construction based on group action assumptions, and proved the correctness of their...

Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [BCCK22]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected $2^k$ different inputs one will find an output that starts with $k$ zeros. Using such truncation one can for example save substantial gas fees on Blockchains where...

In this paper, we investigate the Extended Gabidulin (EG) codes and the Interleaved EG (IEG) codes, develop more powerful attacks on the variants of the Rank Decoding (RD) problem, and enhance rank-based cryptosystems such as RQC and ROLLO. First, we develop a general decoding algorithm for the (I)EG codes by solving the Linear Reconstruction (LR) problem. We find that the (I)EG codes can be probabilistically decoded by Welch-Berlekamp like algorithm, can achieve an arbitrarily small...

Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for $n > m$, a scaled random projection $\mathbf{A}$ from $\mathbb{R}^n$ to $\mathbb{R}^m$ is an approximate isometry on any set $S$ of size at most exponential in $m$. If $S$ is larger, however, its points can contract arbitrarily under $\mathbf{A}$. In particular, the hypergrid $([-B, B] \cap \mathbb{Z})^n$ is expected to contain a point that is contracted by a factor of $\kappa_{\mathsf{stat}} = \Theta(B)^{-1/\alpha}$,...

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of...

We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner, resolving a long-standing open question in quantum cryptography. Specifically, in the quantum random oracle model (QROM), no perfect-complete QPKE scheme with classical keys, and classical/quantum ciphertext can be secure. This improves the previous works which require either unproven conjectures or...

When Nakamoto invented Bitcoin, the first generation of cryptocurrencies followed it in applying POW (Proof of Work) consensus mechanism; due to its excessive energy consumption and heavy carbon footprints, new innovations evolved like Proof of Space, POS (Proof of Stake), and a lot more with many variants for each. Furthermore, the emergence of more blockchain applications and kinds beyond just cryptocurrencies needed more consensus mechanisms that is optimized to fit requirements of each...

In this paper, we present an improved framework for proving query bounds in the Quantum Random Oracle Model (QROM) for algorithms with both quantum and classical query interfaces, where the classical input is partially controlled by the adversary. By extending existing techniques, we develop a method to bound the progress an adversary can make with such partial-control classical queries. While this framework is applicable to different hash function properties, we decided to demonstrate the...

Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator, even if some processes (possibly including the initiator) are Byzantine. In asynchronous settings, it is known since the prominent work of Bracha \cite{Bracha87} that Byzantine reliable broadcast can be implemented deterministically if the total number of processes, denoted by...

A set of unacquainted parties, some of which may misbehave, communicate with each other over an unauthenticated and unreliable gossip network. They wish to jointly replicate a state machine $\Pi$ so that each one of them has fair access to its operation. Specifically, assuming parties' computational power is measured as queries to an oracle machine $H(\cdot)$, parties can issue symbols to the state machine in proportion to their queries to $H(\cdot)$ at a given fixed rate. Moreover, if such...

Semantic communication systems, which focus on transmitting the semantics of data rather than its exact reconstruction, redefine the design of communication networks for transformative efficiency in bandwidth-limited and latency-critical applications. Addressing these goals, we tackle the rate-distortion-perception (RDP) problem for image compression, a critical challenge in achieving perceptually realistic reconstructions under rate constraints. Formulated within the randomized distributed...

A Random Oracle Combiner (ROC), introduced by Dodis et al. (CRYPTO ’22), takes two hash functions $h_1, h_2$ from m bits to n bits and outputs a new hash function $C$ from $m$' to $n$' bits. This function C is guaranteed to be indifferentiable from a fresh random oracle as long as one of $h_1$ and $h_2$ (say, $h_1$) is a random oracle, while the other h2 can “arbitrarily depend” on $h_1$. The work of Dodis et al. also built the first length-preserving ROC, where $n$′ = $n$. Unfortunately,...

This paper presents new results that establish connections between isogeny graphs and nonlinear recurrences over finite fields. Specifically, we prove several theorems that link these two areas, offering deeper insights into the structure of isogeny graphs and their relationship with nonlinear recurrence sequences. We further provide two related conjectures which may be worth of further research. These findings contribute to a better understanding of the endomorphism ring of a curve,...

Physically Unclonable Constants (PUCs) are a special type of Physically Unclonable Constants and they can be used to embed secret bit-strings in chips. Most PUCs are an array of cells where each cell is a digital circuit that evolve spontaneously toward one of two states, the chosen state being function of random manufacturing process variations. In this paper we propose an Analog Physically Unclonable Constant (APUC) whose output is an analog value to be transformed in digital by a...

In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on three representative models: \emph{Garay's}, \emph{Bonnet's} and \emph{Buhrman's} models. In \emph{Garay's model} when a process has been left by the Byzantine, it is in the \emph{cured} state and it is aware of its condition and thus can remain silent for a round to prevent the dissemination of wrong information. In...

State-separating proofs are a powerful tool to structure cryptographic arguments, so that they are amenable for mechanization, as has been shown through implementations, such as SSProve. However, the treatment of separation for heaps has never been satisfactorily addressed. In this work, we present the first comprehensive treatment of nominal state separation in state-separating proofs using nominal sets. We provide a Rocq library, called Nominal-SSProve, that builds on nominal state...

Abstract The Singularity Random Number Generator (SRNG) represents a groundbreaking advancement in the generation of random numbers by integrating two key properties - computational irreducibility and seed independence - into a deterministic algorithm. Unlike conventional pseudorandom number generators (PRNGs) whose randomness is intrinsically linked to seed quality or chaotic sensitivity, SRNG transforms even low-entropy seeds into complex, unpredictable outputs. SRNG demonstrates...

Formal methods are becoming an important tool for ensuring correctness and security of cryptographic constructions. However, the support for certain advanced proof techniques, namely rewinding, is scarce among existing verification frameworks, which hinders their application to complex schemes such as multi-party signatures and zero-knowledge proofs. We expand the support for rewinding in EasyCrypt by implementing a version of the general forking lemma by Bellare and Neven. We demonstrate...

A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed offline into a data structure, which then allows the server to answer any client query efficiently in sub-linear online time. Constructing DEPIR is a notoriously difficult problem, and this difficulty even extends to a weaker...

In order to compute a multiple of a point on an elliptic curve in Weierstrass form one can use formulas in only one of the two coordinates of the points. These $x$-only formulas can be seen as an arithmetic on the Kummer line associated to the curve. In this paper, we look at models of Kummer lines, and define an intrinsic notion of isomorphisms of Kummer lines. This allows us to give conversion formulas between Kummer models in a unified manner. When there is one rational point $T$ of...

We introduce deniable secret sharing (DSS), which, analogously to deniable encryption, enables shareholders to produce fake shares that are consistent with a target “fake message”, regardless of the original secret. In contrast to deniable encryption, in a DSS scheme an adversary sees multiple shares, some of which might be real, and some fake. This makes DSS a more difficult task, especially in situations where the fake shares need to be generated by individual shareholders, without...