This paper offers a mathematical introduction to fully homomorphic encryption, a concept that enables computation on encrypted data. We trace the historical development of FHE, describe Fully Homomorphic Encryption over the Torus (TFHE) and how it performs certain mathematical operations, and explore bootstrapping and the possibility for adjusting computational depth. This paper equips readers with a brief understanding of FHE's evolution and the essential mechanisms facilitating practical implementation.

In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a quadratic gap between the query complexity of the honest parties and the eavesdropper. This quadratic gap is known to be optimal, by the works of Impagliazzo and Rudich [STOC ’89] and Barak and Mahmoody [Crypto ’09]. When the oracle function is injective or a permutation, Merkle’s Puzzles has perfect completeness. That is, it is certain that the protocol results in agreement between the parties. However, without such an assumption on the random function, there is a small error probability, and the parties may end up holding different keys. This fact raises the question: Is there a key-agreement protocol with perfect completeness and super-linear security in the ROM? In this paper we give a positive answer to the above question, showing that changes to the query distribution of the parties in Merkle’s Puzzles, yield a protocol with perfect completeness and roughly the same security.

Threshold secret sharing allows a dealer to split a secret $s$ into $n$ shares, such that any $t$ shares allow for reconstructing $s$, but no $t-1$ shares reveal any information about $s$. Leakage-resilient secret sharing requires that the secret remains hidden, even when an adversary additionally obtains a limited amount of leakage from every share. Benhamouda et al. (CRYPTO'18) proved that Shamir's secret sharing scheme is one bit leakage-resilient for reconstruction threshold $t\geq0.85n$ and conjectured that the same holds for $t=c\cdot n$ for any constant $0\leq c\leq1$. Nielsen and Simkin (EUROCRYPT'20) showed that this is the best one can hope for by proving that Shamir's scheme is not secure against one-bit leakage when $t=c\cdot n/\log(n)$. In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakage-resilience, where a random subset of leakages is replaced by uniformly random noise. We prove a lower bound for Shamir's secret sharing, similar to that of Nielsen and Simkin, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient sharing scheme. We then use this lower bound to show that there exist universal constants $c_1,c_2$, such that for infinitely many $n$, it holds that Shamir's secret sharing scheme is not noisy-leakage-resilient for $t\leq c_1\cdot n/\log(n)$, even when a $c_2$ fraction of leakages are replaced by random noise.

Homomorphic encryption is a central object in modern cryptography, with far-reaching applications. Constructions supporting homomorphic evaluation of arbitrary Boolean circuits have been known for over a decade, based on standard lattice assumptions. However, these constructions are leveled, meaning that they only support circuits up to some a-priori bounded depth. These leveled constructions can be bootstrapped into fully homomorphic ones, but this requires additional circular security assumptions, which are construction-dependent, and where reductions to standard lattice assumptions are no longer known. Alternative constructions are known based on indistinguishability obfuscation, which has been recently constructed under standard assumptions. However, this alternative requires subexponential hardness of the underlying primitives. We prove a new bootstrapping theorem relying on functional encryption, which is known based on standard polynomial hardness assumptions. As a result we obtain the first fully homomorphic encryption scheme that avoids both circular security assumptions and super-polynomial hardness assumptions. The construction is secure against uniform adversaries, and can be made non-uniformly secure, under a widely-believed worst-case complexity assumption (essentially that non-uniformity does not allow arbitrary polynomial speedup). At the heart of the construction is a new proof technique based on cryptographic puzzles. Unlike most cryptographic reductions, our security reduction does not fully treat the adversary as a black box, but rather makes explicit use of its running time (or circuit size).

Latin squares are a classical and well-studied topic of discrete mathematics, and recently Takeuti and Adachi (IACR ePrint, 2023) proposed (2,n)-threshold secret sharing based on mutually orthogonal Latin squares (MOLS). Hence efficient constructions of as large sets of MOLS as possible are also important from practical viewpoints. In this letter, we determine the maximum number of MOLS among a known class of Latin squares defined by weighted sums. We also mention some known property of Latin squares interpreted via the relation to secret sharing and a connection of Takeuti-Adachi's scheme to Shamir's secret sharing scheme.

We study the relationship between notions of pseudorandomness in the quantum and classical worlds. Pseudorandom quantum state generator (PRSG), a pseudorandomness notion in the quantum world, is an efficient circuit that produces states that are computationally indistinguishable from Haar random states. PRSGs have found applications in quantum gravity, quantum machine learning, quantum complexity theory, and quantum cryptography. Pseudorandom generators, on the other hand, a pseudorandomness notion in the classical world, is ubiquitous to theoretical computer science. While some separation results were known between PRSGs, for some parameter regimes, and PRGs, their relationship has not been completely understood. In this work, we show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs. Our result along with the previous separations gives a better picture regarding the relationship between the two notions. We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes. Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.

The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO'10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below $d^{O(d)}$ for cyclotomic fields, here $d$ refers to the field degree). De Boer et al. [CRYPTO'20] obtained another random self-reducibility result for an average-case distribution involving integral ideals of norm $2^{O(d^2)}$. In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry's reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of \emph{small-norm prime ideals}. Using the reduction from Pellet-Mary and Stehl\'e [ASIACRYPT'21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.

Correlation intractability is an emerging cryptographic paradigm that enabled several recent breakthroughs in establishing soundness of the Fiat-Shamir transform and, consequently, basing non-interactive zero-knowledge proofs and succinct arguments on standard cryptographic assumptions. In a nutshell, a hash family is said to be \emph{correlation intractable} for a class of relations $\mathcal{R}$ if, for any relation $R\in\mathcal{R}$, it is hard given a random hash function $h\gets H$ to find an input $z$ s.t. $(z,h(z))\in R$, namely a correlation. Despite substantial progress in constructing correlation intractable hash functions, all constructions known to date are based on highly-structured hardness assumptions and, further, are of complexity scaling with the circuit complexity of the target relation class. In this work, we initiate the study of the barriers for building correlation intractability. Our main result is a lower bound on the complexity of any black-box construction of CIH from collision resistant hash (CRH), or one-way permutations (OWP), for any sufficiently expressive relation class. In particular, any such construction for a class of relations with circuit complexity $t$ must make at least $\Omega(t)$ invocations of the underlying building block. We see this as a first step in developing a methodology towards broader lower bounds.

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches the key-agreement protocol proposed by Merkle (CACM 78), known as Merkle's Puzzles. Besides query complexity, the communication complexity of key-agreement protocols in the ROM is also an interesting question in the realm of find-grained cryptography, even though only limited security is achievable. Haitner et al. (ITCS 2019) first observed that in Merkle's Puzzles, to obtain secrecy against an eavesdropper with $O(\ell^2)$ queries, the honest parties must exchange $\Omega(\ell)$ bits. Therefore, they conjectured that high communication complexity is unavoidable, i.e., any $\ell$-query protocols with $c$ bits of communication could be attacked by an $O(c\cdot \ell)$-query adversary. This, if true, will suggest that Merkle's Puzzle is also optimal regarding communication complexity. Building upon techniques from communication complexity, Haitner et al. (ITCS 2019) confirmed this conjecture for two types of key agreement protocols with certain natural properties. This work affirms the above conjecture for all non-adaptive protocols with perfect completeness. Our proof uses a novel idea called density increment argument. This method could be of independent interest as it differs from previous communication lower bounds techniques (and bypasses some technical barriers).

Time-lock puzzles, introduced by May, Rivest, Shamir and Wagner, is a mechanism for sending messages ``to the future''. A sender can quickly generate a puzzle with a solution $s$ that remains hidden until a moderately large amount of time $t$ has elapsed. The solution $s$ should be hidden from any adversary that runs in time significantly less than $t$, including resourceful parallel adversaries with polynomially many processors. While the notion of time-lock puzzles has been around for 22 years, there has only been a *single* candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an ``inherently sequential'' computation. We show that various flavors of {\em randomized encodings} give rise to time-lock puzzles of varying strengths, whose security can be shown assuming *the existence* of non-parallelizing languages, which are languages that require circuits of depth at least $t$ to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles. We instantiate the construction with different randomized encodings from the literature, where increasingly better efficiency is obtained based on increasingly stronger cryptographic assumptions, ranging from one-way functions to indistinguishability obfuscation. We also observe that time-lock puzzles imply one-way functions, and thus the reliance on some cryptographic assumption is necessary. Finally, generalizing the above, we construct other types of puzzles such as *proofs of work* from randomized encodings and a suitable worst-case hardness assumption (that is necessary for such puzzles to exist).

Existing proofs of adaptive security (e.g., in settings in which decryption keys are adaptively revealed) often rely on guessing arguments. Such guessing arguments can be simple (and, e.g., just involve guessing which keys are revealed), or more complex "partitioning'' arguments. Since guessing directly and negatively impacts the loss of the corresponding security reduction, this leads to black-box lower bounds for a number of cryptographic scenarios that involve adaptive security. In this work, we provide an alternative to such guessing arguments: instead of guessing in a security reduction which adaptive choices an adversary A makes, we rewind A many times until we can successfully embed a given computational challenge. The main benefit of using rewindings is that these rewindings can be arranged sequentially, and the corresponding reduction loss only accumulates additively (instead of multiplicatively, as with guessing). The main technical challenge is to show that A's success is not negatively affected after (potentially many) rewindings. To this end, we develop a machinery for "undirected'' rewindings that preserve A's success across (potentially many) rewindings. We use this strategy to show - security of the "Logical Key Hierarchy'' protocol underlying the popular TreeKEM key management protocol, and - security of the Goldreich-Goldwasser-Micali (GGM) pseudorandom function (PRF) as a prefix-constrained PRF. In both cases, we provide the first polynomial reductions to standard assumptions (i.e., to IND-CPA and PRG security, respectively), and in case of the GGM PRF, we also circumvent an existing lower bound.

While cryptographic protocols are often analyzed in isolation, they are typically deployed within a stack of protocols, where each layer relies on the security guarantees provided by the protocol layer below it, and in turn provides its own security functionality to the layer above. Formally analyzing the whole stack in one go is infeasible even for semi-automated verification tools, and impossible for pen-and-paper proofs. The DY$^\star$ protocol verification framework offers a modular and scalable technique that can reason about large protocols, specified as a set of F$^\star$ modules. However, it does not support the compositional verification of layered protocols since it treats the global security invariants monolithically. In this paper, we extend DY$^\star$ with a new methodology that allows analysts to modularly analyze each layer in a way that compose to provide security for a protocol stack. Importantly, our technique allows a layer to be replaced by another implementation, without affecting the proofs of other layers. We demonstrate this methodology on two case studies. We also present a verified library of generic authenticated and confidential communication patterns that can be used in future protocol analyses and is of independent interest.

In many occasions, the knowledge error $\kappa$ of an interactive proof is not small enough, and thus needs to be reduced. This can be done generically by repeating the interactive proof in parallel. While there have been many works studying the effect of parallel repetition on the {\em soundness error} of interactive proofs and arguments, the effect of parallel repetition on the {\em knowledge error} has largely remained unstudied. Only recently it was shown that the $t$-fold parallel repetition of {\em any} interactive protocol reduces the knowledge error from $\kappa$ down to $\kappa^t +\nu$ for any non-negligible term $\nu$. This generic result is suboptimal in that it does not give the knowledge error $\kappa^t$ that one would expect for typical protocols, and, worse, the knowledge error remains non-negligible. In this work we show that indeed the $t$-fold parallel repetition of any $(k_1,\dots,k_{\mu})$-special-sound multi-round public-coin interactive proof optimally reduces the knowledge error from $\kappa$ down to $\kappa^t$. At the core of our results is an alternative, in some sense more fine-grained, measure of quality of a dishonest prover than its success probability, for which we show that it characterizes when knowledge extraction is possible. This new measure then turns out to be very convenient when it comes to analyzing the parallel repetition of such interactive proofs. While parallel repetition reduces the knowledge error, it is easily seen to {\em increase} the {\em completeness error}. For this reason, we generalize our result to the case of $s$-out-of-$t$ threshold parallel repetition, where the verifier accepts if $s$ out of $t$ of the parallel instances are accepting. An appropriately chosen threshold $s$ allows both the knowledge error and completeness error to be reduced simultaneously.

Fine-grained cryptography is constructing cryptosystems in a setting where an adversary’s resource is a-prior bounded and an honest party has less resource than an adversary. Currently, only simple form of encryption schemes, such as secret-key and public-key encryption, are constructed in this setting. In this paper, we enrich the available tools in fine-grained cryptography by proposing the first fine-grained secure attribute-based encryption (ABE) scheme. Our construction is adaptively secure under the widely accepted worst-case assumption, NC1$\subsetneq \oplus$L/poly, and it is presented in a generic manner using the notion of predicate encodings (Wee, TCC’14). By properly instantiating the underlying encoding, we can obtain different types of ABE schemes, including identity-based encryption. Previously, all of these schemes were unknown in fine-grained cryptography. Our main technical contribution is constructing ABE schemes without using pairing or the Diffie-Hellman assumption. Hence, our results show that, even if one-way functions do not exist, we still have ABE schemes with meaningful security. For more application of our techniques, we construct an efficient (quasi-adaptive) non-interactive zero-knowledge (QA-NIZK) proof system.

Whether one-way functions (OWF) exist is arguably the most important problem in Cryptography, and beyond. While lots of candidate constructions of one-way functions are known, and recently also problems whose average-case hardness characterize the existence of OWFs have been demonstrated, the question of whether there exists some \emph{worst-case hard problem} that characterizes the existence of one-way functions has remained open since their introduction in 1976. In this work, we present the first ``OWF-complete'' promise problem---a promise problem whose worst-case hardness w.r.t. $\BPP$ (resp. $\Ppoly$) is \emph{equivalent} to the existence of OWFs secure against $\PPT$ (resp. $\nuPPT$) algorithms. The problem is a variant of the Minimum Time-bounded Kolmogorov Complexity problem ($\mktp[s]$ with a threshold $s$), where we condition on instances having small ``computational depth''. We furthermore show that depending on the choice of the threshold $s$, this problem characterizes either ``standard'' (polynomially-hard) OWFs, or quasi polynomially- or subexponentially-hard OWFs. Additionally, when the threshold is sufficiently small (e.g., $2^{O(\sqrt{n})}$ or $\poly\log n$) then \emph{sublinear} hardness of this problem suffices to characterize quasi-polynomial/sub-exponential OWFs. While our constructions are black-box, our analysis is \emph{non- black box}; we additionally demonstrate that fully black-box constructions of OWF from the worst-case hardness of this problem are impossible. We finally show that, under Rudich's conjecture, and standard derandomization assumptions, our problem is not inside $\coAM$; as such, it yields the first candidate problem believed to be outside of $\AM \cap \coAM$, or even ${\bf SZK}$, whose worst case hardness implies the existence of OWFs.

In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature (IMDVS), and prove that (i) IMDVS is equivalent to PKE, and (ii) it is impossible to construct IMDVS from a ring signature scheme in a generic way. Our result suggests an essential gap between ring signature and group signature, as it is known that group signature implies PKE.

Most of the current lattice-based cryptosystems rely on finding Gaussian Samples from a lattice that are close to a given target. To that end, two popular distributions have been historically defined and studied: the Rounded Gaussian distribution and the Discrete Gaussian distribution. The first one is nearly trivial to sample: simply round the coordinates of continuous Gaussian samples to their nearest integer. Unfortunately, the security of resulting cryptosystems are not as well understood. In the opposite, the second distribution is only implicitly defined by a restriction of the support of the continuous Gaussian distribution to the discrete lattice points. Thus, algorithms to achieve such distribution are more involved, even in dimension one. The justification for exerting this computational effort is that the resulting lattice-based cryptographic schemes are validated by rigorous security proofs, often by leveraging the fact that the distribution is radial and discrete Gaussians behave well under convolutions, enabling arithmetic between samples, as well as decomposition across dimensions. In this work, we unify both worlds. We construct out of infinite series, the cumulative density function of a new continuous distribution that acts as surrogate for the cumulative distribution of the discrete Gaussian. If $\mu$ is a center and $x$ a sample of this distribution, then rounding $\mu+x$ yields a faithful Discrete Gaussian sample. This new sampling algorithm naturally splits into a pre-processing/offline phase and a very efficient online phase. The online phase is simple and has a trivial constant time implementation. Modulo the offline phase, our algorithm offers both the efficiency of rounding and the security guarantees associated with discrete Gaussian sampling.

We initiate the study of software watermarking against quantum adversaries. A quantum adversary generates a quantum state as a pirate software that potentially removes an embedded message from a classical marked software. Extracting an embedded message from quantum pirate software is difficult since measurement could irreversibly alter the quantum state. In software watermarking against classical adversaries, a message extraction algorithm crucially uses the (input-output) behavior of a classical pirate software to extract an embedded message. Even if we instantiate existing watermarking PRFs with quantum-safe building blocks, it is not clear whether they are secure against quantum adversaries due to the quantum-specific property above. Thus, we need entirely new techniques to achieve software watermarking against quantum adversaries. In this work, we define secure watermarking PRFs and PKE for quantum adversaries (unremovability against quantum adversaries). We also present two watermarking PRFs and one watermarking PKE as follows. - We construct a privately extractable watermarking PRF against quantum adversaries from the quantum hardness of the learning with errors (LWE) problem. The marking and extraction algorithms use a public parameter and a private extraction key, respectively. The watermarking PRF is unremovable even if adversaries have (the public parameter and) access to the extraction oracle, which returns a result of extraction for a queried quantum circuit. - We construct a publicly extractable watermarking PRF against quantum adversaries from indistinguishability obfuscation (IO) and the quantum hardness of the LWE problem. The marking and extraction algorithms use a public parameter and a public extraction key, respectively. The watermarking PRF is unremovable even if adversaries have the extraction key (and the public parameter). - We construct a publicly extractable watermarking PKE against quantum adversaries from standard PKE. The marking algorithm can directly generate a marked decryption from a decryption key, and the extraction algorithm uses a public key of the PKE scheme for extraction. We develop a quantum extraction technique to extract information (a classical string) from a quantum state without destroying the state too much. We also introduce the notions of extraction-less watermarking PRFs and PKE as crucial building blocks to achieve the results above by combining the tool with our quantum extraction technique.

Regev's Learning with Errors (LWE) problem (STOC 2005) is a fundamental hardness assumption for modern cryptography. The Learning with Rounding (LWR) Problem was put forth by Banarjee, Peikert and Rosen (Eurocrypt 2012) as an alternative to LWE, for use in cryptographic situations which require determinism. The only method we currently have for proving hardness of LWR is the so-called "rounding reduction" which is a specific reduction from an analogous LWE problem. This reduction works whenever the LWE error is small relative to the noise introduced by rounding, but it fails otherwise. For this reason, all prior work on establishing hardness of LWR forces the LWE error to be small, either by setting other parameters extremely large (which hurts performance), or by limiting the number of LWR samples seen by the adversary (which rules out certain applications). Hardness of LWR is poorly understood when the LWE modulus ($q$) is polynomial and when the number of LWE samples ($m$) seen by the adversary is an unbounded polynomial. This range of parameters is the most relevant for practical implementations, so the lack of a hardness proof in this situation is not ideal. In this work, we identify an obstacle for proving the hardness of LWR via a reduction from LWE in the above parameter regime. Specifically, we show that any "point-wise" reduction from LWE to LWR can be used to directly break the corresponding LWE problem. A reduction is "point-wise" if it maps LWE samples to LWR samples one at a time. Our argument goes roughly as follows: first we show that any point-wise reduction from LWE to LWR must have good agreement with some affine map; then we use a Goldreich-Levin-type theorem to extract the LWE secret given oracle access to a point-wise reduction with good affine agreement. Both components may be of independent interest.

Gadget decomposition is widely used in lattice based cryptography, especially homomorphic encryption (HE) to keep the noise growth slow. If it is randomized following a subgaussian distribution, it is called subgaussian (gadget) decomposition which guarantees that we can bound the noise contained in ciphertexts by its variance. This gives tighter and cleaner noise bound in average case, instead of the use of its norm. Even though there are few attempts to build efficient such algorithms, most of them are still not practical enough to be applied to homomorphic encryption schemes due to somewhat high overhead compared to the deterministic decomposition. Furthermore, there has been no detailed analysis of existing works. Therefore, HE schemes use the deterministic decomposition algorithm and rely on a Heuristic assumption that every output element follows a subgaussian distribution independently. In this work, we introduce a new practical subgaussian gadget decomposition algorithm which has the least overhead (less than 14\%) among existing works for certain parameter sets, by combining two previous works. In other words, we bring an existing technique based on an uniform distribution to a simpler and faster design (PKC' 22) to exploit parallel computation, which allows to skip expensive parts due to pre-computation, resulting in even simpler and faster algorithm. When the modulus is large (over 100-bit), our algorithm is not always faster than the other similar work. Therefore, we give a detailed comparison, even for large modulus, with all the competitive algorithms for applications to choose the best algorithm for their choice of parameters.

Two-source extractors are deterministic functions that, given two independent weak sources of randomness, output a (close to) uniformly random string of bits. Cheraghchi and Guruswami (TCC 2015) introduced two-source non-malleable extractors that combine the properties of randomness extraction with tamper resilience. Two-source non-malleable extractors have since then attracted a lot of attention, and have very quickly become fundamental objects in cryptosystems involving communication channels that cannot be fully trusted. Various applications of two-source non-malleable extractors include in particular non-malleable codes, non-malleable commitments, non-malleable secret sharing, network extraction, and privacy amplification with tamperable memory. The best known constructions of two-source non-malleable extractors are due to Chattopadhyay, Goyal, and Li (STOC 2016), Li (STOC 2017), and Li (CCC 2019). All of these constructions require both sources to have min-entropy at least $0.99 n$, where $n$ is the bit-length of each source. In this work, we introduce collision-resistant randomness extractors. This allows us to design a compiler that, given a two-source non-malleable extractor, and a collision-resistant extractor, outputs a two-source non-malleable extractor that inherits the non-malleability property from the non-malleable extractor, and the entropy requirement from the collision-resistant extractor. Nested application of this compiler leads to a dramatic improvement of the state-of-the-art mentioned above. We obtain a construction of a two-source non-malleable extractor where one source is required to have min-entropy greater than $0.8n$, and the other source is required to have only $\text{polylog} (n)$ min-entropy. Moreover, the other parameters of our construction, i.e., the output length, and the error remain comparable to prior constructions.

This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties. For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives). Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$. Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.

Let $(A,t)$ be an instance of the search-LWE problem, where $A$ is a matrix and $t$ is a vector. This paper constructs an integer programming problem using $A$ and $t$, and shows that it is possible to derive a solution of the instance $(A,t)$ (perhaps with high probability) using its optimal solution or its tentative solution of small norm output by an integer programming solver. In other words, the LWE-search problem can be reduced to an integer programming problem. In the reduction, only basic linear algebra and finite field calculation are required. The computational complexity of the integer programming problem obtained is still unknown.

Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general Maiorana-McFarland class. We employ a method first proposed by Ding et al. [7] to construct minimal codes violating the Ashikhmin-Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal codes. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. This study provides insights into the scope of this method.

The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived. Furthermore, the lower bound on the valence of the cryptograms of entire ciphers is derived in this paper. The obtained parameters allow to assess the resistance of cryptograms, resp. ciphers against brute force attack. The model is general, illustrative and uses a simpler mathematical apparatus than existing theory. Therefore, it can also be used as an introduction to the theory of resistance of ciphers to brute force attack.

Consider the problem of efficiently evaluating isogenies $\phi: \mathcal{E} \to \mathcal{E}/H$ of elliptic curves over a finite field $\mathbb{F}_q$, where the kernel \(H = \langle{G}\rangle\) is a cyclic group of odd (prime) order: given \(\mathcal{E}\), \(G\), and a point (or several points) $P$ on $\mathcal{E}$, we want to compute $\phi(P)$. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu's formul\ae{} give an efficient solution to this problem when the kernel generator $G$ is defined over $\mathbb{F}_q$. However, for general isogenies, \(G\) is only defined over some extension $\mathbb{F}_{q^k}$, even though $\langle{G}\rangle$ as a whole (and thus \(\phi\)) is defined over the base field $\mathbb{F}_q$; and the performance of Vélu-style algorithms degrades rapidly as $k$ grows. In this article, we revisit the isogeny-evaluation problem with a special focus on the case where $1 \le k \le 12$. We improve Vélu-style isogeny evaluation for many cases where \(k = 1\) using special addition chains, and combine this with the action of Galois to give greater improvements when \(k > 1\).

Zero-knowledge and succinctness are two important properties that arise in the study of non-interactive arguments. Previously, Kitagawa et al. (TCC 2020) showed how to obtain a non-interactive zero-knowledge (NIZK) argument for NP from a succinct non-interactive argument (SNARG) for NP. In particular, their work demonstrates how to leverage the succinctness property from an argument system and transform it into a zero-knowledge property. In this work, we study a similar question of leveraging succinctness for zero-knowledge. Our starting point is a batch argument for NP, a primitive that allows a prover to convince a verifier of $T$ NP statements $x_1, \ldots, x_T$ with a proof whose size scales sublinearly with $T$. Unlike SNARGs for NP, batch arguments for NP can be built from group-based assumptions in both pairing and pairing-free groups and from lattice-based assumptions. The challenge with batch arguments is that the proof size is only amortized over the number of instances, but can still encode full information about the witness to a small number of instances. We show how to combine a batch argument for NP with a local pseudorandom generator (i.e., a pseudorandom generator where each output bit only depends on a small number of input bits) and a dual-mode commitment scheme to obtain a NIZK for NP. Our work provides a new generic approach of realizing zero-knowledge from succinctness and highlights a new connection between succinctness and zero-knowledge.

This paper introduces CycleFold, a new and conceptually simple approach to instantiate folding-scheme-based recursive arguments over a cycle of elliptic curves, for the purpose of realizing incrementally verifiable computation (IVC). Existing approach to solve this problem originates from BCTV (CRYPTO'14) who describe their approach for a SNARK-based recursive argument, and it was adapted by Nova (CRYPTO'22) to a folding-scheme-based recursive argument. A downside of this approach is that it represents a folding scheme verifier as a circuit on both curves in the cycle. (e.g., with Nova, this requires $\approx$10,000 multiplication gates on both curves in the cycle). CycleFold’s starting point is the observation that folding-scheme-based recursive arguments can be efficiently instantiated without a cycle of elliptic curves—except for a few scalar multiplications in their verifiers (2 in Nova, 1 in HyperNova, and 3 in ProtoStar). Accordingly, CycleFold uses the second curve in the cycle to merely represent a single scalar multiplication ($\approx$1,000--1,500 multiplication gates). CycleFold then folds invocations of that tiny circuit on the first curve in the cycle. This is nearly an order of magnitude improvement over the prior state-of-the-art in terms of circuit sizes on the second curve. CycleFold is particularly beneficial when instantiating folding-scheme-based recursive arguments over “half pairing” cycles (e.g., BN254/Grumpkin) as it keeps the circuit on the non-pairing-friendly curve minimal. The running instance in a CycleFold-based recursive argument consists of an instance on the first curve and a tiny instance on the second curve. Both instances can be proven using a zkSNARK defined over the scalar field of the first curve. On the conceptual front, with CycleFold, an IVC construction and nor its security proof has to explicitly reason about the cycle of elliptic curves. Finally, due to its simplicity, CycleFold-based recursive argument can be more easily be adapted to support parallel proving with the so-called "binary tree" IVC.

Applied cryptographic protocols have to meet a rich set of security requirements under diverse environments and against diverse adversaries. However, currently used security specifications, based on either simulation (e.g., `ideal functionality' in UC) or games, are monolithic, combining together different aspects of protocol requirements, environment and assumptions. Such security specifications are complex, error-prone, and foil reusability, modular analysis and incremental design. We present the Modular Security Specifications (MoSS) framework, which cleanly separates the security requirements (goals) which a protocol should achieve, from the models (assumptions) under which each requirement should be ensured. This modularity allows us to reuse individual models and requirements across different protocols and tasks, and to compare protocols for the same task, either under different assumptions or satisfying different sets of requirements. MoSS is flexible and extendable, e.g., it can support both asymptotic and concrete definitions for security. So far, we confirmed the applicability of MoSS to two applications: secure broadcast protocols and PKI schemes.

Fully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow for fully secure MPC is an important goal. Cleve (STOC'86) showed that full security cannot be obtained in general without an honest majority. Conversely, by Rabin and Ben-Or (STOC'89), assuming a broadcast channel and an honest majority enables a fully secure computation of any function. Our goal is to characterize the set of functionalities that can be computed with full security, assuming an honest majority, but no broadcast. This question was fully answered by Cohen et al. (TCC'16) -- for the restricted class of symmetric functionalities (where all parties receive the same output). Instructively, their results crucially rely on agreement and do not carry over to general asymmetric functionalities. In this work, we focus on the case of three-party asymmetric functionalities, providing a variety of necessary and sufficient conditions to enable fully secure computation. An interesting use-case of our results is server-aided computation, where an untrusted server helps two parties to carry out their computation. We show that without a broadcast assumption, the resource of an external non-colluding server provides no additional power. Namely, a functionality can be computed with the help of the server if and only if it can be computed without it. For fair coin tossing, we further show that the optimal bias for three-party (server-aided) $r$-round protocol remains $\Theta(1/r)$ (as in the two-party setting).

One of the central questions in cryptology is how efficient generic constructions of cryptographic primitives can be. Gennaro, Gertner, Katz, and Trevisan [SIAM J. Compt. 2005] studied the lower bounds of the number of invocations of a (trapdoor) oneway permutation in order to construct cryptographic schemes, e.g., pseudorandom number generators, digital signatures, and public-key and symmetric-key encryption. Recently quantum machines have been explored to _construct_ cryptographic primitives other than quantum key distribution. This paper studies the efficiency of _quantum_ black-box constructions of cryptographic primitives when the communications are _classical_. Following Gennaro et al., we give the lower bounds of the number of invocations of an underlying quantumly-computable quantum-oneway permutation (QC-qOWP) when the _quantum_ construction of pseudorandom number generator (PRG) and symmetric-key encryption (SKE) is weakly black-box. Our results show that the quantum black-box constructions of PRG and SKE do not improve the number of invocations of an underlying QC-qOWP.

We consider the fundamental problem of designing classical consensus-related distributed abstractions for large-scale networks, where the number of parties can be huge. Specifically, we consider tasks such as Byzantine Agreement, Broadcast, and Committee Election, and our goal is to design scalable protocols in the sense that each honest party processes and sends a number of bits which is sub-linear in $n$, the total number of parties. In this work, we construct the first such scalable protocols for all of the above tasks. In our protocols, each party processes and sends $\tilde O (\sqrt n)$ bits throughout $\tilde O (1)$ rounds of communication, and correctness is guaranteed for at most $1/3-\epsilon$ fraction of static byzantine corruptions for every constant $\epsilon>0$ (in the full information model). All previous protocols for the considered agreement tasks were non-scalable, either because the communication complexity was linear or because the computational complexity was super polynomial. We complement our result with a matching lower bound showing that any Byzantine Agreement protocol must have $\Omega(\sqrt n)$ complexity in our model. Previously, the state of the art was the well-known $\tilde\Omega(\sqrt[3]{n})$ lower bound of Holtby, Kapron, and King (Distributed Computing, 2008).

Recent works showed how Mutual Information Neural Estimation (MINE) could be applied to side-channel analysis in order to evaluate the amount of leakage of an electronic device. One of the main advantages of MINE over classical estimation techniques is to enable the computation between high dimensional traces and a secret, which is relevant for leakage assessment. However, optimally exploiting this information in an attack context in order to retrieve a secret remains a non-trivial task especially when a profiling phase of the target is not allowed. Within this context, the purpose of this paper is to address this problem based on a simple idea: there are multiple leakage sources in side-channel traces and optimal attacks should necessarily exploit most/all of them. To this aim, a new mathematical framework, designed to bridge classical Mutual Information Analysis (MIA) and the multidimensional aspect of neural-based estimators, is proposed. One of the goals is to provide rigorous proofs consolidating the mathematical basis behind MIA, thus alleviating inconsistencies found in the state of the art. This framework allows to derive a new attack called Neural Estimated Mutual Information Analysis (NEMIA). To the best of our knowledge, it is the first unsupervised attack able to benefit from both the power of deep learning techniques and the valuable theoretical properties of MI. Simulations and experiments show that NEMIA outperforms classical and more recent deep learning based unsupervised side-channel attacks, especially in low-information contexts.

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only $2$ times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction works with fewer LWE samples compared to the classical reduction that has a high success probability. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over $\mathbb{Z}_q$ where $q$ is prime. In short, this theorem states that, if a hardcore predicate $a\cdot s \pmod q$ can be predicted with probability distinctly greater than $1/q$ with respect to a uniformly random $a\in\mathbb{Z}_q^n$, then it is possible to determine $s\in\mathbb{Z}_q^n$.

In 2002, Barak and Goldreich introduced the notion of a universal argument and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of non-interactive succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under sub-exponential assumptions. Assuming polynomially hard fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.

Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for \emph{stochastic} constraint satisfaction problems (SCSPs). An SCSP with $k$ alternations is a list of constraints over variables grouped into $2k$ blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints. In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For $k \leq O(\log n)$, we prove that it is $AM[k]$-hard to approximate, to within a constant, the value of SCSPs with $k$ alternations and constant arity. Before, this was known only for $k = O(1)$. Furthermore, we introduce a natural class of $k$-round interactive proofs, denoted $IR[k]$ (for \emph{interactive reducibility}), and show that several protocols (e.g., the sumcheck protocol) are in $IR[k]$. Using this notion, we extend our inapproximability to all values of $k$: we show that for every $k$, approximating an SCSP instance with $O(k)$ alternations and constant arity is $IR[k]$-hard. While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in $AM[k \leq O(\log n)]$ or in $IR[k]$ has an $O(k)$-round IOP whose verifier has \emph{constant} query complexity (\emph{regardless} of the number of rounds $k$). In particular, we derive a ``sumcheck protocol'' whose verifier reads $O(1)$ bits from the entire interaction transcript.

The celebrated result of Yao (FOCS'82) shows that concatenating $n\cdot p(n)$ copies of a weak one-way function (OWF) $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, yields a strong OWF $g$, showing that weak and strong OWFs are black-box equivalent. Yao's transformation is not security-preserving, i.e., the input to $g$ needs to be much larger than the input to $f$. Understanding whether a larger input is inherent is a long-standing open question. In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of a strong OWF $g$ from a weak OWF $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, the input size of $g$ must grow as $\Omega(p(n))$. Here, direct product refers to the following structure: the construction $g$ executes some arbitrary pre-processing function (independent of $f$) on its input $s$, obtaining a vector $(x_1, \cdots, x_l)$, and outputs $f(x_1), \cdots, f(x_l)$. When setting the pre-processing to be the identity, one recovers thus Yao's construction. Our result generalizes to functions $g$ with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong OWF hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense that post-processing of the outputs of $f$ is very lossy). On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak OWFs by evaluating the OWF along a random walk on an expander graph – the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak OWF.

Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS). We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT). The factoring of SIM-EXT into KS + WUR + TLZK is becoming a cornerstone of the analysis of non-malleable SNARK systems. We show how to prove WUR and TLZK for PIOP compiled SNARKs under mild falsifiable assumptions on the polynomial commitment scheme. This means that the analysis of knowledge soundness from PIOP properties that inherently relies on non-falsifiable or idealized assumption such as the algebraic group model (AGM) or generic group model (GGM) need not be repeated. While the proof of WUR requires only mild assumptions on the PIOP, TLZK is a different matter. As perfectly hiding polynomial commitments sometimes come at a substantial performance premium, SNARK designers prefer to employ deterministic commitments with some leakage. This results in the need for a stronger zero-knowledge property for the PIOP. The modularity of our approach implies that any analysis improvements, e.g. in terms of tightness, credibility of the knowledge assumption and model of the KS analysis, or the precision of capturing real-world optimizations for TLZK also benefits the SIM-EXT guarantees.

The analysis of real-life incidents has revealed that state-level efforts are made to camouflage the intentional flaws in the mathematical layer of an S-Box to exploit the information-theoretic properties, i.e., Kuznyechik. To extract and investigate the common features in the backdoored S-Box(es), this research thoroughly examines them from the perspective of 24 cryptanalytic attack vectors available in the open literature. We have debunked the earlier claims by the backdoor engineers that their designs are stealthy against statistical distinguishers. A backdoored architecture fulfils the notions of randomness but lacks the strength to resist sophisticated cryptanalytic attacks. Our analysis has revealed that during the backdoor insertion phase, a malicious designer compromises vital cryptographic properties, prominently the algebraic degree, differential trails, avalanche characteristics and leaving the open ground for hybrid attacks. It is observed that these mappings attain the upper bound of BCT, FBCT and DLCT, thus paving the way for hybrid attacks with high probability.

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$. As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.

We construct a succinct non-interactive argument ($\mathsf{SNARG}$) for the class of monotone policy batch $\mathsf{NP}$ languages under the Learning with Errors ($\mathsf{LWE}$) assumption. This class is a subclass of $\mathsf{NP}$ that is associated with a monotone function~$f:\{0,1\}^k\rightarrow\{0,1\}$ and an $\mathsf{NP}$ language $\mathcal L$, and contains instances $(x_1,\ldots,x_k)$ such that $f(b_1,\ldots,b_k)=1$ where $b_j=1$ if and only if $x_j\in \mathcal L$. Our $\mathsf{SNARG}$s are arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries. This is the first $\mathsf{SNARG}$ under standard hardness assumptions for a sub-class of $\mathsf{NP}$ that is not known to have a (computational) non-signaling $\mathsf{PCP}$ with small locality. Indeed, our approach necessarily departs from the known framework of constructing $\mathsf{SNARG}$s dating back to [Kalai-Raz-Rothblum, STOC '13] Our construction combines existing quasi-arguments for $\mathsf{NP}$ (based on batch arguments for $\mathsf{NP}$) with a novel ingredient which we call a predicate-extractable hash ($\mathsf{PEH}$) family. This notion generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our $\mathsf{PEH}$ extracts a global property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.

Incompressibility is a popular security notion for white-box cryptography and captures that a large encryption program cannot be compressed without losing functionality. Fouque, Karpman, Kirchner and Minaud (FKKM) defined strong incompressibility, where a compressed program should not even help to distinguish encryptions of two messages of equal length. Equivalently, the notion can be phrased as indistinguishability under chosen-plaintext attacks and key-leakage (LK-IND-CPA), where the leakage rate is high. In this paper, we show that LK-IND-CPA security with superlogarithmic-length leakage, and thus strong incompressibility, cannot be proven under standard (i.e. single-stage) assumptions, if the encryption scheme is key-fixing, i.e. a polynomial number of message-ciphertext pairs uniquely determine the key with high probability. Our impossibility result refutes a claim by FKKM that their big-key generation mechanism achieves strong incompressibility when combined with any PRG or any conventional encryption scheme, since the claim is not true for encryption schemes which are key-fixing (or for PRGs which are injective). In particular, we prove that the cipher block chaining (CBC) block cipher mode is key-fixing when modelling the cipher as a truly random permutation for each key. Subsequent to and inspired by our work, FKKM prove that their original big-key generation mechanism can be combined with a random oracle into an LK-IND-CPA-secure encryption scheme, circumventing the impossibility result by the use of an idealised model. Along the way, our work also helps clarifying the relations between incompressible white-box cryptography, big-key symmetric encryption, and general leakage resilient cryptography, and their limitations.

Consider the standard setting of two-party computation where the sender has a secret function $f$ and the receiver has a secret input $x$ and the output $f(x)$ is delivered to the receiver at the end of the protocol. Let us consider the unidirectional message model where only one party speaks in each round. In this setting, Katz and Ostrovsky (Crypto 2004) showed that at least four rounds of interaction between the parties are needed in the plain model (i.e., no trusted setup) if the simulator uses the adversary in a black-box way (a.k.a. black-box simulation). Suppose the sender and the receiver would like to run multiple sequential iterations of the secure computation protocol on possibly different inputs. For each of these iterations, do the parties need to start the protocol from scratch and exchange four messages? In this work, we explore the possibility of \textit{amortizing} the round complexity or in other words, \textit{reusing} a certain number of rounds of the secure computation protocol in the plain model. We obtain the following results. 1. Under standard cryptographic assumptions, we construct a four-round two-party computation protocol where (i) the first three rounds of the protocol could be reused an unbounded number of times if the receiver input remains the same and only the sender input changes, and (ii) the first two rounds of the protocol could be reused an unbounded number of times if the receiver input needs to change as well. In other words, the sender sends a single additional message if only its input changes, and in the other case, we need one message each from the receiver and the sender. The number of additional messages needed in each of the above two modes is optimal and, additionally, our protocol allows arbitrary interleaving of these two modes. 2. We also extend these results to the multiparty setting (in the simultaneous message exchange model) and give round-optimal protocols such that (i) the first two rounds could be reused an unbounded number of times if the inputs of the parties need to change and (ii) the first three rounds could be reused an unbounded number of times if the inputs remain the same but the functionality to be computed changes. As in the two-party setting, we allow arbitrary interleaving of the above two modes of operation.

The security of several cryptosystems rests on the trust assumption that a certain fraction of the parties are honest. This trust assumption has enabled a diverse of cryptographic applications such as secure multiparty computation, threshold encryption, and threshold signatures. However, current and emerging practical use cases suggest that this paradigm of one-person-one-vote is outdated. In this work, we consider {\em weighted} cryptosystems where every party is assigned a certain weight and the trust assumption is that a certain fraction of the total weight is honest. This setting can be translated to the standard setting (where each party has a unit weight) via virtualization. However, this method is quite expensive, incurring a multiplicative overhead in the weight. We present new weighted cryptosystems with significantly better efficiency. Specifically, our proposed schemes incur only an {\em additive} overhead in weights. \begin{itemize} \item We first present a weighted ramp secret-sharing scheme where the size of the secret share is as short as $O(w)$ (where $w$ corresponds to the weight). In comparison, Shamir's secret sharing with virtualization requires secret shares of size $w\cdot\lambda$, where $\lambda=\log |\mathbb{F}|$ is the security parameter. \item Next, we use our weighted secret-sharing scheme to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our secret sharing scheme and incur only an additive overhead in the weights. \end{itemize} Our weighted secret-sharing scheme is based on the Chinese remainder theorem. Interestingly, this secret-sharing scheme is {\em non-linear} and only achieves statistical privacy. These distinct features introduce several technical hurdles in applications to MPC and threshold cryptosystems. We resolve these challenges by developing several new ideas.

In this work, we provide a systematisation of knowledge of delay-based cryptography, in which we discuss and compare the existing primitives within cryptography that utilise a time-delay. We start by considering the role of time within cryptography, explaining broadly what a delay aimed to achieve at its inception and now, in the modern age. We then move on to describing the underlying assumptions used to achieve these goals, and analyse topics including trust, decentralisation and concrete methods to implement a delay. We then survey the existing primitives, discussing their security properties, instantiations and applications. We make explicit the relationships between these primitives, identifying a hierarchy and the theoretical gaps that exist. We end this systematisation of knowledge by highlighting relevant future research directions within the field of delay-based cryptography, from which this area would greatly benefit.

This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of switching to the next sender. We then present a matching upper bound with a latency of $2\Delta$ ($\Delta$ is the pessimistic synchronous delay) with an optimistically responsive change to the next sender. The results imply that both our lower and upper bounds are tight. We implement and evaluate our protocol and show that our protocol obtains similar latency compared to state-of-the-art stable-leader protocol Sync~HotStuff while allowing optimistically responsive leader rotation.

Oblivious RAMs (ORAMs) are an important cryptographic primitive that enable outsourcing data to a potentially untrusted server while hiding patterns of access to the data. ORAMs provide strong guarantees even in the face of a {\em persistent adversary} that views the transcripts of all operations and resulting memory contents. Unfortunately, the strong guarantees against persistent adversaries comes at the cost of efficiency as ORAMs are known to require $\Omega(\log n)$ overhead. In an attempt to obtain faster constructions, prior works considered security against {\em snapshot adversaries} that only have limited access to operational transcripts and memory. We consider $(s,\ell)$-snapshot adversaries that perform $s$ data breaches and views the transcripts of $\ell$ total queries. Promisingly, Du, Genkin and Grubbs [Crypto'22] presented an ORAM construction with $O(\log \ell)$ overhead protecting against $(1,\ell)$-snapshot adversaries with the transcript of $\ell$ consecutive operations from a single breach. For small values of $\ell$, this outperforms standard ORAMs. In this work, we tackle whether it is possible to further push this construction beyond a single breach. Unfortunately, we show that protecting against even slightly stronger snapshot adversaries becomes difficult. As our main result, we present a $\Omega(\log n)$ lower bound for any ORAM protecting against a $(3,1)$-snapshot adversary that performs three breaches and sees the transcript of only one query. In other words, our lower bound holds even if an adversary observes only memory contents during two breaches while managing to view the transcript of only one query in the other breach. Therefore, we surprisingly show that protecting against a snapshot adversary with three data breaches is as difficult as protecting against a persistent adversary

We present a new framework for defining information leakage in the setting of US equities trading, and construct methods for deriving trading schedules that stay within specified information leakage bounds. Our approach treats the stock market as an interactive protocol performed in the presence of an adversary, and draws inspiration from the related disciplines of differential privacy as well as quantitative information flow. We apply a linear programming solver using examples from historical trade and quote (TAQ) data for US equities and describe how this framework can inform actual algorithmic trading strategies.

We build non-interactive zero-knowledge (NIZK) and ZAP arguments for all $\mathsf{NP}$ where soundness holds for infinitely-many security parameters, and against uniform adversaries, assuming the subexponential hardness of the Computational Diffie-Hellman (CDH) assumption. We additionally prove the existence of NIZK arguments with these same properties assuming the polynomial hardness of both CDH and the Learning Parity with Noise (LPN) assumption. In both cases, the CDH assumption does not require a group equipped with a pairing. Infinitely-often uniform security is a standard byproduct of commonly used non-black-box techniques that build on disjunction arguments on the (in)security of some primitive. In the course of proving our results, we develop a new variant of this non-black-box technique that yields improved guarantees: we obtain explicit constructions (previous works generally only obtained existential results) where security holds for a relatively dense set of security parameters (as opposed to an arbitrary infinite set of security parameters). We demonstrate that our technique can have applications beyond our main results.

Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient querying. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $\ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately embed and query data where it is integral to ensure small failure probability when constructing cuckoo hashing tables as it directly relates to the privacy guarantees. As our main result, we present a more query-efficient cuckoo hashing construction using more hash functions. For construction failure probability $\epsilon$, the query overhead of our scheme is $O(1 + \sqrt{\log(1/\epsilon)/\log n})$. Our scheme has quadratically smaller query overhead than prior works for any target failure probability $\epsilon$. We also prove lower bounds matching our construction. Our improvements come from a new understanding of the locality of cuckoo hashing failures for small sets of items. We also initiate the study of robust cuckoo hashing where the input set may be chosen with knowledge of the hash functions. We present a cuckoo hashing scheme using more hash functions with query overhead $\tilde{O}(\log \lambda)$ that is robust against poly$(\lambda)$ adversaries. Furthermore, we present lower bounds showing that this construction is tight and that extending previous approaches of large stashes or entries cannot obtain robustness except with $\Omega(n)$ query overhead. As applications of our results, we obtain improved constructions for batch codes and PIR. In particular, we present the most efficient explicit batch code and blackbox reduction from single-query PIR to batch PIR.

In this paper we consider multipartite access structures obtained from polymatroids with extreme rank function. They are proved to be ideal and partially hierarchical. It turns out that the family of structures induced by polymatroids with minimal rank function is a natural generalization of the class of disjunctive access structure considered by Simmons and the class of conjunctive access structures introduced by Tassa. The results are based on the connections between multipartite access structures and polymatroids discovered by Farràs, Martí-Farré and Padró.

Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of any total NP search problem (collision-resistant hash functions being just one such example). We make progress towards this conjecture by ruling out a large class of “single-query” reductions. In particular, we improve over the prior work of Hubáček et al. (2020) in two ways: our result is established via a novel simpler combinatorial technique and applies to a broader class of semi black-box reductions.

Cuckoo Hashing is a dictionary data structure in which a data item is stored in a small constant number of possible locations. It has the appealing property that a data structure of size $2m$ can hold up to $n = \frac{1}{d} m$ elements for any constant $d > 1$; i.e. the data structure size is a small constant times larger than the combined size of all inserted data elements. However, the probability that a cuckoo hash table build fails is $\Theta(\frac{1}{m})$. This is too high for many applications, especially cryptographic applications and Oblivious RAM. An alternative proposal introduced by Kirsch et al. is to store elements which cannot be placed in the main table in a ``stash'', reducing the failure probability to $\mathcal{O}(m^{-(s+1)})$ where $s$ is any constant stash size. However, this analysis did not apply to super-constant $s$, and the bounds are asymptotic rather than explicit. Further works improved upon this, but either were not explicit, not closed-form or had limitations on the stash size. In this paper we present the first explicit, closed-form bounds for the failure probability of cuckoo hashing with a stash for general stash sizes.

We introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking knowledge of a witness in one relation to checking knowledge of a witness in another (simpler) relation. Reductions of knowledge unify a growing class of modern techniques as well as provide a compositional framework to modularly reason about individual steps in complex arguments of knowledge. As a demonstration, we simplify and unify recursive arguments over linear algebraic statements by decomposing them as a sequence of reductions of knowledge. To do so, we develop the tensor reduction of knowledge, which generalizes the central reductive step common to many recursive arguments. Underlying the tensor reduction of knowledge is a new information-theoretic reduction, which, for any modules $U$, $U_1$, and $U_2$ such that $U \cong U_1 \otimes U_2$, reduces the task of evaluating a homomorphism in $U$ to evaluating a homomorphism in $U_1$ and evaluating a homomorphism in $U_2$.

A functional commitment (FC) scheme allows one to commit to a vector $\vec{x}$ and later produce a short opening proof of $(f, f(\vec{x}))$ for any admissible function $f$. Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed. In this work, we introduce a novel primitive that we call chainable functional commitment (CFC), which extends the functionality of FCs by allowing one to 1) open to functions of multiple inputs $f(\vec x_1, \ldots, \vec x_m)$ that are committed independently, 2) while preserving the output also in committed form. We show that CFCs for quadratic polynomial maps generically imply FCs for circuits. Then, we efficiently realize CFCs for quadratic polynomials over pairing groups and lattices, resulting in the first FC schemes for circuits of unbounded depth based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require fixing a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. Additionally, our FCs feature other nice properties such as being additively homomorphic and supporting sublinear-time verification after offline preprocessing. Using a recent transformation that constructs homomorphic signatures (HS) from FCs, we obtain the first pairing- and lattice-based realisations of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.

Time-lock puzzles wrap a solution $\mathrm{s}$ inside a puzzle $\mathrm{P}$ in such a way that ``solving'' $\mathrm{P}$ to find $\mathrm{s}$ requires significantly more time than generating the pair $(\mathrm{s},\mathrm{P})$, even if the adversary has access to parallel computing; hence it can be thought of as sending a message $\mathrm{s}$ to the future. It is known [Mahmoody, Moran, Vadhan, Crypto'11] that when the source of hardness is only a random oracle, then any puzzle generator with $n$ queries can be (efficiently) broken by an adversary in $O(n)$ rounds of queries to the oracle. In this work, we revisit time-lock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of time-lock puzzles solely from quantum (accessible) random oracles. In particular, for any $n$-query classical puzzle generator, our attack only asks $O(n)$ (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing. Assuming perfect completeness, we also show how to make the above attack run in exactly $n$ rounds while asking a total of $m\cdot n$ queries where $m$ is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask $n-1$ rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from $\Omega(mn \log n)$ to $mn$. Finally, assuming perfect completeness, we present an attack in the ``dual'' setting in which the puzzle generator is quantum while the solver is classical. We then ask whether one can extend our classical-query attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv'2009] is false, then there is indeed a time-lock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto'22] about key agreements (that can have interactions in both directions) to time-lock puzzles (that only include unidirectional communication).

The subset cover problem for $k \geq 1$ hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, $\dots$). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make $\Omega\left((k+1)^{-\frac{2^{k}}{2^{k+1}-1}}\cdot N^{\frac{2^{k}-1}{2^{k+1}-1}}\right)$ queries to the underlying hash functions with codomain size $N$ to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general $(r,k)$-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a $r$-chosen message attack (for $r \geq 1$). We prove that a generic quantum algorithm needs to make $\Omega\left(N^{k/5}\right)$ queries to the underlying hash functions to find a $(1,k)$-subset cover. We also propose a quantum algorithm that finds a $(r,k)$-subset cover making $O\left(N^{k/(2+2r)}\right)$ queries to the $k$ hash functions.

Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model. In this work, we study the question whether these strong idealized models are necessary for proving the security of ECDSA. Specifically, we focus on the programmability of ECDSA's "conversion function" which maps an elliptic curve point into its $x$-coordinate modulo the group order. Unfortunately, our main results are negative. We establish, by means of a meta reductions, that an algebraic security reduction for ECDSA can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for ECDSA is unlikely to exist without strong idealization.

In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices. To mitigate this issue, Bolboceanu et al (Asiacrypt 2019) defined q-Order-LWE over any order (modulo q) in a number field and based its hardness on worst-case hard problems of ideal lattices of the same order, but restricted to invertible ideals. Orders generalize the ring of integers to non-Dedekind domains. In a subsequent work in 2021, they proved a non-effective ``ideal-clearing" lemma for q-Order-LWE for any q that is co-prime to index of the order in the ring of integers. This work can be shown to give an efficient reduction from any ideal of the same order. However, this requires factorization of arbitrary integers, namely the norm of the given ideal. In this work we give a novel approach to proving the ``ideal-clearing" lemma for q-Order-LWE by showing that all ideals I of an order are principal modulo qI, for any q that is co-prime to index of the order in the ring of integers. Further, we give a rather simple (classical) randomized algorithm to find a generator for this principal ideal, which makes our hardness reduction (from all ideals of the order) not require any further quantum steps on top of the quantum Gaussian sampling of the original Regev reduction. This also removes the ``known factorization" requirement on q for the original RLWE hardness result of Peikert et al. Finally, we recommend a ``twisted'' cyclotomic field as an alternative for the cyclotomic field used in NIST PQC algorithm CRYSTALS-Kyber, as it leads to a more efficient implementation and is based on hardness of ideals in a non-Dedekind domain following Dedekind index theorem.

In this paper, we pose the problem of defining technical privacy guarantees for anonymizing stories. This is a challenge that arises in practice in contexts like journalism and memoir writing, and can be crucial in determining whether a story gets told and how effectively it is presented. While recent decades have seen leaps and bounds in the development of approaches like differential privacy for numerical and categorical data sets, none of these techniques are directly applicable to settings where narrative structure is crucial to preserve. Here we begin an exploration of what kind of definitions could be achievable in such settings, and discuss the building blocks and interdisciplinary collaborations that could shape new solutions. Having scientific guarantees for anonymity in narrative forms could have far-reaching effects - in the peace of mind of potential tellers and subjects of stories, as well as in the legal sphere. This could ultimately expand the kinds of stories that can be told.

Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions, new properties and applications of pseudorandom states, and present the following contributions: 1. New Definitions: We study variants of pseudorandom function-like state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show the feasibility of these variants assuming the existence of post-quantum one-way functions. 2. Classical Communication: We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication. Previous constructions of such schemes from PRS generators required quantum communication. 3. Simplified Proof: We give a simpler proof of the Brakerski-Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states. 4. Necessity of Computational Assumptions: We also show that a secure PRS with output length logarithmic, or larger, in the key length necessarily requires computational assumptions.

Randomness testing is one of the essential and easiest tools for evaluating cryptographic primitives. The faster we can test, the greater volume of data that can be tested. Thus a more detailed analysis is possible. This paper presents a range of observations made for a well-known frequency test for overlapping vectors in binary sequence testing. We have obtained precise chi-square statistic computed in $O \left(dt 2^{dt} \right)$ instead of $O\left( 2^{2dt}\right)$ time, without precomputed tables.

We initiate a formal study of individual cryptography. Informally speaking, an algorithm $\mathsf{Alg}$ is "individual" if, in every implementation of $\mathsf{Alg}$, there always exists an individual user with full knowledge of the cryptographic data $S$ used by $\mathsf{Alg}$. In particular, it should be infeasible to design implementations of this algorithm that would hide $S$ by distributing it between a group of parties using an MPC protocol or outsourcing it to a trusted execution environment. We define and construct two primitives in this model. The first one, called "proofs of individual knowledge", is a tool for proving that a given message is fully known to a single ("individual") machine on the Internet, i.e., it cannot be shared between a group of parties. The second one, dubbed "individual secret sharing", is a scheme for sharing a secret $S$ between a group of parties so that the parties have no knowledge of $S$ as long as they do not reconstruct it. The reconstruction ensures that if the shareholders attempt to collude, one of them will learn the secret entirely. Individual secret sharing has applications for preventing collusion in secret sharing. A central technique for constructing individual cryptographic primitives is the concept of MPC hardness. MPC hardness precludes an adversary from completing a cryptographic task in a distributed fashion within a specific time frame.

Permutation polynomials with low $c$-differential uniformity and boomerang uniformity have wide applications in cryptography. In this paper, by utilizing the Weil sums technique and solving some certain equations over $\mathbb{F}_{2^n}$, we determine the $c$-differential uniformity and boomerang uniformity of these permutation polynomials: (1) $f_1(x)=x+\mathrm{Tr}_1^n(x^{2^{k+1}+1}+x^3+x+ux)$, where $n=2k+1$, $u\in\mathbb{F}_{2^n}$ with $\mathrm{Tr}_1^n(u)=1$; (2) $f_2(x)=x+\mathrm{Tr}_1^n(x^{{2^k}+3}+(x+1)^{2^k+3})$, where $n=2k+1$; (3) $f_3(x)=x^{-1}+\mathrm{Tr}_1^n((x^{-1}+1)^d+x^{-d})$, where $n$ is even and $d$ is a positive integer. The results show that the involutions $f_1(x)$ and $f_2(x)$ are APcN functions for $c\in\mathbb{F}_{2^n}\backslash \{0,1\}$. Moreover, the boomerang uniformity of $f_1(x)$ and $f_2(x)$ can attain $2^n$. Furthermore, we generalize some previous works and derive the upper bounds on the $c$-differential uniformity and boomerang uniformity of $f_3(x)$.

In this article, we give evidence that free modules (i.e., modules which admit a basis) are no weaker than arbitrary modules, when it comes to solving cryptographic algorithmic problems (and when the rank of the module is at least 2). More precisely, we show that for three algorithmic problems used in cryptography, namely the shortest vector problem, the Hermite shortest vector problem and a variant of the closest vector problem, there is a reduction from solving the problem in any module of rank $n ≥ 2$ to solving the problem in any free module of the same rank $n$. As an application, we show that this can be used to dequantize the LLL algorithm for module lattices presented by Lee et al. (Asiacrypt 2019).

The security analysis of real-world protocols involves reduction steps that are conceptually simple but still have to account for many protocol complications found in standards and implementations. Taking inspiration from universal composability, abstract cryptography, process algebras, and type-based verification frameworks, we propose a method to simplify large reductions, avoid mistakes in carrying them out, and obtain concise security statements. Our method decomposes monolithic games into collections of stateful *packages* representing collections of oracles that call one another using well-defined interfaces. Every component scheme yields a pair of a real and an ideal package. In security proofs, we then successively replace each real package with its ideal counterpart, treating the other packages as the reduction. We build this reduction by applying a number of algebraic operations on packages justified by their state separation. Our method handles reductions that emulate the game perfectly, and leaves more complex arguments to existing game-based proof techniques such as the code-based analysis suggested by Bellare and Rogaway. It also facilitates computer-aided proofs, inasmuch as the perfect reductions steps can be automatically discharged by proof assistants. We illustrate our method on two generic composition proofs: (1) a proof of self-composition using a hybrid argument; and (2) the composition of keying and keyed components. For concreteness, we apply them to the KEM-DEM proof of hybrid-encryption by Cramer and Shoup and to the composition of forward-secure game-based key exchange protocols with symmetric-key protocols.

A large number of works prove lower bounds on space-time trade-offs in preprocessing attacks, i.e., trade-offs between the size of the advice and the time needed to break a scheme given such advice. We contend that the question of how much {\em time} is needed to produce this advice is equally important, and often highly non-trivial. However, this question has received significantly less attention. In this paper, we present lower bounds on the complexity of preprocessing attacks that depend on both offline and online time. As in the case of space-time trade-offs, we focus in particular on settings with ideal primitives, where both the offline and online time-complexities are approximated by the number of queries to the given primitive. We give generic results that highlight the benefits of salting to generically increase the offline costs of preprocessing attacks. The majority of our paper presents several results focusing on {\em salted} hash functions. In particular, we provide a fairly involved analysis of the pre-image-and collision-resistance security of the (two-block) Merkle-Damgård construction in our model.

Addition of $n$ inputs is often the easiest nontrivial function to compute securely. Motivated by several open questions, we ask what can be computed securely given only an oracle that computes the sum. Namely, what functions can be computed in a model where parties can only encode their input locally, then sum up the encodings over some Abelian group $\G$, and decode the result to get the function output. An *additive randomized encoding* (ARE) of a function $f(x_1,\ldots,x_n)$ maps every input $x_i$ independently into a randomized encoding $\hat x_i$, such that $\sum_{i=1}^n$ $\hat x_i$ reveals $f(x_1,\ldots,x_n)$ and nothing else about the inputs. In a *robust* ARE, the sum of any subset of the $\hat x_i$ only reveals the residual function obtained by restricting the corresponding inputs. We obtain positive and negative results on ARE. In particular: * Information-theoretic ARE. We fully characterize the 2-party functions $f:X_1\times X_2\to\{0,1\}$ admitting a perfectly secure ARE. For $n\ge 3$ parties, we show a useful ``capped sum'' function that separates statistical security from perfect security. * Computational ARE. We present a general feasibility result, showing that *all functions* can be computed in this model, under a standard hardness assumption in bilinear groups. We also describe a heuristic lattice-based construction. * Robust ARE. We present a similar feasibility result for {\em robust} computational ARE based on ideal obfuscation along with standard cryptographic assumptions. We then describe several applications of ARE and the above results. * Under a standard cryptographic assumption, our computational ARE schemes imply the feasibility of general non-interactive secure computation in the shuffle model, where messages from different parties are shuffled. This implies a general utility-preserving compiler from differential privacy in the central model to computational differential privacy in the (non-robust) shuffle model. * The existence of information-theoretic {\em robust} ARE implies "best-possible" information-theoretic MPC protocols (Halevi et al., TCC 2018) and degree-2 multiparty randomized encodings (Applebaum et al., TCC 2018). This yields new positive results for specific functions in the former model, as well as a simple unifying barrier for obtaining negative results in both models.

Lossy trapdoor functions (LTFs) constitute a useful and versatile cryptographic building block. LTFs have found applications in various types of encryption schemes, are closely connected to statistically secure oblivious transfer protocols, and have led to the first constructions of group-based trapdoor functions. However, with one recent exception, all known group-based LTFs are comparatively inefficient, and in particular suffer from large images. In this work, we attempt to explain this inefficiency, and derive lower bounds for the image size of group-based LTFs. In essence, we find that purely algebraic group-based LTFs (i.e., LTFs that use the underlying group in a generic way, without considering group representations) must suffer from a large image size (of an at least super-constant number of group elements). Our results also help to explain the mentioned exceptional group-based LTF with compact images.

Consider a state-level adversary who observes and stores large amounts of encrypted data from all users on the Internet, but does not have the capacity to store it all. Later, it may target certain "persons of interest" in order to obtain their decryption keys. We would like to guarantee that, if the adversary's storage capacity is only (say) $1\%$ of the total encrypted data size, then even if it can later obtain the decryption keys of arbitrary users, it can only learn something about the contents of (roughly) $1\%$ of the ciphertexts, while the rest will maintain full security. This can be seen as an extension of incompressible cryptography (Dziembowski CRYPTO '06, Guan, Wichs and Zhandry EUROCRYPT '22) to the multi-user setting. We provide solutions in both the symmetric key and public key setting with various trade-offs in terms of computational assumptions and efficiency. As the core technical tool, we study an information-theoretic problem which we refer to as "multi-instance randomness extraction". Suppose $X_1, \ldots, X_t$ are correlated random variables whose total joint min-entropy rate is $\alpha$, but we know nothing else about their individual entropies. We choose $t$ random and independent seeds $S_1, \ldots, S_t$ and attempt to individually extract some small amount of randomness $Y_i = \mathsf{Ext}(X_i;S_i)$ from each $X_i$. We'd like to say that roughly an $\alpha$-fraction of the extracted outputs $Y_i$ should be indistinguishable from uniform even given all the remaining extracted outputs and all the seeds. We show that this indeed holds for specific extractors based on Hadamard and Reed-Muller codes.

The goal of this research is to raise technical doubts regarding the usefulness of the repeated attempts by governments to curb Cryptography (aka the ``Crypto Wars''), and argue that they, in fact, cause more damage than adding effective control. The notion of Anamorphic Encryption was presented in Eurocrypt '22 for a similar aim. There, despite the presence of a Dictator who possesses all keys and knows all messages, parties can arrange a hidden ``anamorphic'' message in an otherwise indistinguishable from regular ciphertexts (wrt the Dictator). In this work, we postulate a stronger cryptographic control setting where encryption does not exist (or is neutralized) since all communication is passed through the Dictator in, essentially, cleartext mode (or otherwise, when secure channels to and from the Dictator are the only confidentiality mechanism). Messages are only authenticated to assure recipients of the identity of the sender. We ask whether security against the Dictator still exists, even under such a strict regime which allows only authentication (i.e., authenticated/ signed messages) to pass end-to-end, and where received messages are determined by/ known to the Dictator, and the Dictator also eventually gets all keys to verify compliance of past signing. To frustrate the Dictator, this authenticated message setting gives rise to the possible notion of anamorphic channels inside signature and authentication schemes, where parties attempt to send undetectable secure messages (or other values) using signature tags which are indistinguishable from regular tags. We define and present implementation of schemes for anamorphic signature and authentication; these are applicable to existing and standardized signature and authentication schemes which were designed independently of the notion of anamorphic messages. Further, some cornerstone constructions of the foundations of signatures, in fact, introduce anamorphism.

We study the local leakage resilience of Shamir's secret sharing scheme. In Shamir's scheme, a random polynomial $f$ of degree $t$ is sampled over a field of size $p>n$, conditioned on $f(0)=s$ for a secret $s$. Any $t$ shares $(i, f(i))$ can be used to fully recover $f$ and thereby $f(0)$. But, any $t-1$ evaluations of $f$ at non-zero coordinates are completely independent of $f(0)$. Recent works ask whether the secret remains hidden even if say only 1 bit of information is leaked from each share, independently. This question is well motivated due to the wide range of applications of Shamir's scheme. For instance, it is known that if Shamir's scheme is leakage resilient in some range of parameters, then known secure computation protocols are secure in a local leakage model. Over characteristic 2 fields, the answer is known to be negative (e.g., Guruswami and Wootters, STOC '16). Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO '18) were the first to give a positive answer assuming computation is done over prime-order fields. They showed that if $t \ge 0.907n$, then Shamir's scheme is leakage resilient. Since then, there has been extensive efforts to improve the above threshold and after a series of works, the current record shows leakage resilience for $t\ge 0.78n$ (Maji et al., ISIT '22). All existing analyses of Shamir's leakage resilience for general leakage functions follow a single framework for which there is a known barrier for any $t \le 0.5 n$. In this work, we a develop a new analytical framework that allows us to significantly improve upon the previous record and obtain additional new results. Specifically, we show: $\bullet$ Shamir's scheme is leakage resilient for any $t \ge 0.69n$. $\bullet$ If the leakage functions are guaranteed to be ``balanced'' (i.e., splitting the domain of possible shares into 2 roughly equal-size parts), then Shamir's scheme is leakage resilient for any $t \ge 0.58n$. $\bullet$ If the leakage functions are guaranteed to be ``unbalanced'' (i.e., splitting the domain of possible shares into 2 parts of very different sizes), then Shamir's scheme is leakage resilient as long as $t \ge 0.01 n$. Such a result is $provably$ impossible to obtain using the previously known technique. All of the above apply more generally to any MDS codes-based secret sharing scheme. Confirming leakage resilience is most important in the range $t \leq n/2$, as in many applications, Shamir’s scheme is used with thresholds $t\leq n/2$. As opposed to the previous approach, ours does not seem to have a barrier at $t=n/2$, as demonstrated by our third contribution.

For decades now, mathematical complexity is being regarded as the sole means to creating a sufficient distance between a ciphertext and its generating plaintext. Alas, mathematical complexity operates under the irremovable shadow of stealth cryptanalysis. By its nature mathematical complexity is vulnerable to smarter mathematicians and better equipped adversaries, which is a sufficient motivation to explore an alternative means to project security. Applying the Innovation Solution Protocol such an alternative has been found: randomness. Not as next to mathematical complexity, rather as its replacement. Unlike complexity, randomness is not vulnerable to smarter mathematicians and better equipped adversaries. It removes the shadow under which all modern ciphers operate by proposing a framework wherein the message transmitter may apply arbitrary quantities of ad-hoc randomness with which to secure a transmission over a secret key of arbitrary large size; and where only a part thereto may participate in any instance of encryption; and where security is increased in proportion to the amount of randomness involved. Handling the large quantities of randomness is 'messy' and inconvenient, albeit, the user, not the cipher designer, decides how much inconvenience to put up with in order to build sufficient security to meet the pressing threat. With sufficient randomness, transmission security may exceed One-Time-Pad (OTP) in as much as even the size of the plaintext is not determinable. Ciphers that shift the security responsibility to the user are called "Trans-Vernam", honoring Gilbert S. Vernam's OTP, or "Tesla Ciphers", reflective of the fact that Tesla offered a new power source for the automotive industry, much as the Tesla ciphers offer a new security source for cyberspace. The Tesla cryptographic modality has its security substantiated with a mathematical proof. It is Quantum ready and AI resistant. It is battery-friendly, and ultra fast. Albeit this proposal brings to question a long-established cryptographic premise, with all that is involved.

We will revisit recent techniques and results on the cryptoanalysis of local pseudorandom number generators (PRGs). By doing so, we will achieve a new attack on PRGs whose time complexity only depends on the algebraic degree of the PRG. Concretely, for PRGs $F : \{0,1\}^n\rightarrow \{0,1\}^{n^{1+e}}$, we will give an algebraic algorithm that distinguishes between random points and image points of $F$, whose time complexity is bounded by \[\exp(O(\log(n)^{\deg F /(\deg F - 1)} \cdot n^{1-e/(\deg F -1)} ))\] and whose advantage is at least $1 - o(1)$ in the worst case. To the best of the author's knowledge, this attack outperforms current attacks on the pseudorandomness of local random functions with guaranteed noticeable advantage and gives a new baseline algorithm for local PRGs. Furthermore, this is the first subexponential attack that is applicable to polynomial PRGs of constant degree over fields of any size with a guaranteed noticeable advantage. We will extend this distinguishing attack further to achieve a search algorithm that can invert a uniformly random constant-degree map $F : \{0,1\}^n\rightarrow \{0,1\}^{n^{1+e}}$ with high advantage in the average case. This algorithm has the same runtime complexity as the distinguishing algorithm.

Compressed oracles (Zhandry, Crypto 2019) are a powerful technique to reason about quantum random oracles, enabling a sort of lazy sampling in the presence of superposition queries. A long-standing open question is whether a similar technique can also be used to reason about random (efficiently invertible) permutations. In this work, we make a step towards answering this question. We first define the compressed permutation oracle and illustrate its use. While the soundness of this technique (i.e., the indistinguishability from a random permutation) remains a conjecture, we show a curious 2-for-1 theorem: If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then we get the fact that this methodology is actually sound for free.

Motivated and inspired by the emergence of blockchains, many new protocols have recently been proposed for generating publicly verifiable randomness in a distributed yet secure fashion. These protocols work under different setups and assumptions, use various cryptographic tools, and entail unique trade-offs and characteristics. In this paper, we systematize the design of distributed randomness beacons (DRBs) as well as the cryptographic building blocks they rely on. We evaluate protocols on two key security properties, unbiasability and unpredictability, and discuss common attack vectors for predicting or biasing the beacon output and the countermeasures employed by protocols. We also compare protocols by communication and computational efficiency. Finally, we provide insights on the applicability of different protocols in various deployment scenarios and highlight possible directions for further research.

A system-on-chip (SoC) security can be weakened by exploiting the potential vulnerabilities of the intellectual property (IP) cores used to implement the design and interaction among the IPs. These vulnerabilities not only increase the security verification effort but also can increase design complexity and time-to-market. The design and verification engineers should be knowledgeable about potential vulnerabilities and threat models at the early SoC design life cycle to protect their designs from potential attacks. However, currently, there is no publicly available repository that can be used as a base to develop such knowledge in practice. In this paper, we develop ‘SoC Security Property/Rule Database’ and make it available publicly to all researchers to facilitate and extend security verification effort to address this need. The database gathers a comprehensive security vulnerability and property list. It also provides all the corresponding design behavior that should be held in the design to ensure such vulnerabilities do not exist. The database contains 67 different vulnerability scenarios for which 105 corresponding security properties have been developed till now. This paper reviews the existing database and presents the methodologies we used to gather vulnerabilities and develop such comprehensive security properties. Additionally, this paper discusses the challenges for security verification and the utilization of this database to overcome the research challenges.

The main results in the paper are as follows: (1) We randomly select an extremely large integer and verify whether it can return to 1. The largest one has been verified has length of 6000000 bits, which is overwhelmingly much larger than currently known and verified, e.g., 128 bits, and its Collatz computation sequence consists of 28911397 `I' and `O', only by an ordinary laptop. (2) We propose an dedicated algorithm that can compute 3x+1 for extremely large integers in million bit scale, by replacing multiplication with bit addition, and further only by logical condition judgement. (3) We discovery that the ratio - the count of `O' over the count of `I' in computation sequence goes to 1 asymptotically with the growth of starting integers. (4) We further discover that once the length of starting integer is sufficient large, e.g., 500000 bits, the corresponding computation sequence (in which `I' is replaced with 1 and `O' is replaced with 0), presents sufficient randomness as a bit sequence. We firstly obtain the computation sequence of randomly selected integer with L bit length, where L is 500000, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, by our proposed algorithm for extremely large integers. We evaluate the randomness of all computation sequences by both NIST SP 800-22 and GM/T 0005-2021. All sequences can pass the tests, and especially, the larger the better. (5) We thus propose an algorithm for random bit sequence generator by only using logical judgement (e.g., logic gates) and less than 100 lines in ANSI C. The throughput of the generator is about 625.693 bits/s over an ordinary laptop with Intel Core i7 CPU (1.8GHz).

The relationship between complexity classes BQP and QMA is analogous to the relationship between P and NP. In this paper, we design a quantum bit commitment problem that is in QMA, but not in BQP. Therefore, it is proved that BQP $\neq$ QMA. That is, problems that are verifiable in quantum polynomial time are not necessarily solvable in quantum polynomial time, the quantum analog of P $\neq$ NP.

The goal of a covert learning algorithm is to learn a function $f$ by querying it, while ensuring that an adversary, who sees all queries and their responses, is unable to (efficiently) learn any more about $f$ than they could learn from random input-output pairs. We focus on a relaxation that we call local covertness, in which queries are distributed across $k$ servers and we only limit what is learnable by $k - 1$ colluding servers. For any constant $k$, we give a locally covert algorithm for efficiently learning any Fourier-sparse function (technically, our notion of learning is improper, agnostic, and with respect to the uniform distribution). Our result holds unconditionally and for computationally unbounded adversaries. Prior to our work, such an algorithm was known only for the special case of $O(\log n)$-juntas, and only with $k = 2$ servers, Ishai et al. (Crypto 2019). Our main technical observation is that the original Goldreich-Levin algorithm only utilizes i.i.d. pairs of correlated queries, where each half of every pair is uniformly random. We give a simple generalization of this algorithm in which pairs are replaced by $k$-tuples in which any $k - 1$ components are jointly uniform. The cost of this generalization is that the number of queries needed grows exponentially with $k$.

We show the following results: - The post-quantum equivalence of indistinguishability obfuscation and differing inputs obfuscation in the restricted setting where the outputs differ on at most a polynomial number of points. Our result handles the case where the auxiliary input may contain a quantum state; previous results could only handle classical auxiliary input. - Bounded collusion traitor tracing from general public key encryption, where the decoder is allowed to contain a quantum state. The parameters of the scheme grow polynomially in the collusion bound. - Collusion-resistant traitor tracing with constant-size ciphertexts from general public key encryption, again for quantum state decoders. The public key and secret keys grow polynomially in the number of users. - Traitor tracing with embedded identities in the keys, again for quantum state decoders, under a variety of different assumptions with different parameter size trade-offs. Traitor tracing and differing inputs obfuscation with quantum decoders / auxiliary input arises naturally when considering the post-quantum security of these primitives. We obtain our results by abstracting out a core algorithmic model, which we call the Back One Step (BOS) model. We prove a general theorem, reducing many quantum results including ours to designing classical algorithms in the BOS model. We then provide simple algorithms for the particular instances studied in this work.

Modular arithmetic used for cryptography includes modular adding, modular subtracting, modular multiplying, modular inverting, modular exponentiating etc. In this paper, the authors well analyze the bit complexity of a bitwise modular operation and the time complexity of a non-bitwise modular operation. Besides discuss the clock cycles for one bytewise modular operation utilizing directives from the ATmel 8-bit AVR instruction set. Last, reveal that the ratio of derivate numbers of clock cycles for two modular operations under different modulus lengths is almost a constant.

This paper introduces customizable constraint system (CCS), a generalization of R1CS that can simultaneously capture R1CS, Plonkish, and AIR without overheads. Unlike existing descriptions of Plonkish and AIR, CCS is not tied to any particular proof system. Furthermore, we observe that the linear-time polynomial IOP for R1CS in Spartan (CRYPTO 20) extends easily to CCS, and when combined with a polynomial commitment scheme, it yields a family of SNARKs for CCS, which we refer to as SuperSpartan. SuperSpartan supports high-degree constraints without its prover incurring cryptographic costs that scale with the degree of constraints (only field operations scale with the constraint degree). Moreover, as in Spartan, it does not employ superlinear-time and hard-to-distribute operations such as FFTs. Similar properties were achieved for Plonkish by HyperPlonk (EUROCRYPT 23) via a different route. However, it is unclear how to prove CCS instances (or even R1CS instances) with HyperPlonk (or Plonk itself), without overheads. Furthermore, unlike HyperPlonk, SuperSpartan can prove uniform instances of CCS (including AIR) without requiring a linear-time preprocessing for the verifier, and for those instances, SuperSpartan provides “free” addition gates. SuperSpartan for AIR is the first SNARK for AIR with a linear-time prover, transparent and sublinear-time pre-processing, polylogarithmic proof size, and plausible post-quantum security. In particular, SuperSpartan for AIR provides a faster prover than existing transparent SNARKs for AIR (which are sometimes referred to as STARKs).

Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are ``consistent'' with some legal codeword or ``conflicted''. What type of information about $c$ can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results: (1) (Almost-MDS conflict-checkable codes:) For every distance $d\leq n$, there exists a code that supports conflict-based error-detection whose dimension $k$ almost achieves the singleton bound, i.e., $k\geq n-d+0.99$. Interestingly, the code is non-linear, and we give some evidence that suggests that this is inherent. Combinatorially, this yields an $n$-partite graph over $[q]^n$ that contains $q^k$ cliques of size $n$ whose pair-wise intersection is at most $n-d\leq k-0.99$ vertices, generalizing a construction of Alon (Random Struct. Algorithms, '02) that achieves a similar result for the special case of triangles ($n=3$). (2) (Conflict Decodable Codes below half-distance:) For every distance $d\leq n$ there exists a linear code that supports conflict-based error-decoding up to half of the distance. The code's dimension $k$ ``half-meets'' the singleton bound, i.e., $k=(n-d+2)/2$, and we prove that this bound is tight for a natural class of such codes. The construction is based on symmetric bivariate polynomials and is rooted in the literature on verifiable secret sharing (Ben-Or, Goldwasser and Wigderson, STOC '88; Cramer, Damgård, and Maurer, EUROCRYPT '00). (3) (Robust Conflict Decodable Codes:) We show that the above construction also satisfies a non-trivial notion of robust decoding/detection even when the number of errors is unbounded and up to $d/2$ of the servers are Byzantine and may lie about their conflicts. The resulting conflict-decoder runs in exponential time in this case, and we present an alternative construction that achieves quasipolynomial complexity at the expense of degrading the dimension to $k=(n-d+3)/3$. Our construction is based on trilinear polynomials, and the algorithmic result follows by showing that the induced conflict graph is structured enough to allow efficient recovery of a maximal vertex cover. As an application of the last result, we present the first polynomial-time statistical two-round Verifiable Secret Sharing (resp., three-round general MPC protocol) that remains secure in the presence of an active adversary that corrupts up to $t<n/3.001$ of the parties. We can upgrade the resiliency threshold to $n/3$, which is known to be optimal in this setting, at the expense of increasing the computational complexity to be quasipolynomial. Previous solutions (Applebaum, Kachlon, and Patra, TCC'20) suffered from an exponential-time complexity even when the adversary corrupts only $n/4$ of the parties.

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of $n$-party access structures to $1.5^{n+o(n)}$, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in $\mathsf{P}$ and $\mathsf{NP}$.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. SNARKs with desirable properties such as transparent setup are constructed in the random oracle model. However, using such SNARKs to construct PCD requires heuristically instantiating the oracle and using it in a non-black-box way. Chen, Chiesa and Spooner (EC'22) constructed SNARKs in the low-degree random oracle model, circumventing this issue, but instantiating their model in the real world appears difficult. In this paper, we introduce a new model: the arithmetized random oracle model (AROM). We provide a plausible standard-model (software-only) instantiation of the AROM, and we construct PCD in the AROM, given only a standard-model collision-resistant hash function. Furthermore, our PCD construction is for arbitrary-depth compliance predicates. We obtain our PCD construction by showing how to construct SNARKs in the AROM for computations that query the oracle, given an accumulation scheme for oracle queries in the AROM. We then construct such an accumulation scheme for the AROM. We give an efficient "lazy sampling" algorithm (an emulator) for the ARO up to some error. Our emulator enables us to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM. The algorithm is non-trivial, and relies on results in algebraic query complexity and the combinatorial nullstellensatz.

The key transform of the REESSE1+ asymmetrical cryptosystem is Ci = (Ai * W ^ l(i)) ^ d (% M) with l(i) in Omega = {5, 7, ..., 2n + 3} for i = 1, ..., n, where l(i) is called a lever function. In this paper, we give a simplified key transform Ci = Ai * W ^ l(i) (% M) with a new lever function l(i) from {1, ..., n} to Omega = {+/-5, +/-6, ..., +/-(n + 4)}. Discuss the necessity of the new l(i), namely that a simplified private key is insecure if the new l(i) is a constant but not one-to-one function. Further, expound the sufficiency of the new l(i) from four aspects: (1) indeterminacy of the new l(i), (2) insufficient conditions for neutralizing the powers of W and W ^-1 even if Omega = {5, 6, ..., n + 4}, (3) verification by examples, and (4) the running time of continued fraction attack and running time of W-parameter intersection attack which are the two most efficient of the probabilistic polytime attack algorithms so far. Last, we detail the relation between a lever function and a random oracle.

Recently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography. 1. We construct the first public key encryption scheme from cryptographic non-abelian group actions. Interestingly, ciphertexts of our scheme are quantum even if messages are classical. This resolves an open question posed by Ji et al. (TCC ’19). We construct the scheme through a new abstraction called swap-trapdoor function pairs, which may be of independent interest. 2. We give a simple and efficient compiler that converts the flavor of quantum bit commitments. More precisely, for any prefix X, Y $\in$ {computationally,statistically,perfectly}, if the base scheme is X-hiding and Y-binding, then the resulting scheme is Y-hiding and X-binding. Our compiler calls the base scheme only once. Previously, all known compilers call the base schemes polynomially many times (Crépeau et al., Eurocrypt ’01 and Yan, Asiacrypt ’22). For the security proof of the conversion, we generalize the result of Aaronson et al. by considering quantum auxiliary inputs.

Commitments are fundamental in cryptography. In the classical world, commitments are equivalent to the existence of one-way functions. It is also known that the most desired form of commitments in terms of their round complexity, i.e., non-interactive commitments, cannot be built from one-way functions in a black-box way [Mahmoody-Pass, Crypto'12]. However, if one allows the parties to use quantum computation and communication, it is known that non-interactive commitments (to classical bits) are in fact possible [Koshiba-Odaira, Arxiv'11 and Bitansky-Brakerski, TCC'21]. We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation and classical communication based on a black-box use of one-way functions. We prove that doing so is impossible unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto'22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC'21], as they only required a classical decommitment message. Because non-interactive commitments can be based on injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science'21] in which they only allowed the security reduction to be quantum. At a technical level, we prove that sampling oracles at random from ``sufficiently large'' sets (of oracles) will make them one-way against polynomial quantum-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al.[Asiacrypt'19] and Chung et al. [FOCS'20].

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties. In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the "hash-and-MAC" paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving. Finally, we demonstrate that blind unforgeability is stronger than a previous definition of Boneh and Zhandry [EUROCRYPT '13, CRYPTO '13] in the sense that we can construct an explicit function family which is forgeable by an attack that is recognized by blind-unforgeability, yet satisfies the definition by Boneh and Zhandry.

We consider the following basic question: to what extent are standard secret sharing schemes and protocols for secure multiparty computation that build on them resilient to leakage? We focus on a simple local leakage model, where the adversary can apply an arbitrary function of a bounded output length to the secret state of each party, but cannot otherwise learn joint information about the states. We show that additive secret sharing schemes and high-threshold instances of Shamir’s secret sharing scheme are secure under local leakage attacks when the underlying field is of a large prime order and the number of parties is sufficiently large. This should be contrasted with the fact that any linear secret sharing scheme over a small characteristic field is clearly insecure under local leakage attacks, regardless of the number of parties. Our results are obtained via tools from Fourier analysis and additive combinatorics. We present two types of applications of the above results and techniques. As a positive application, we show that the “GMW protocol” for honest-but-curious parties, when implemented using shared products of random field elements (so-called “Beaver Triples”), is resilient in the local leakage model for sufficiently many parties and over certain fields. This holds even when the adversary has full access to a constant fraction of the views. As a negative application, we rule out multiparty variants of the share conversion scheme used in the 2-party homomorphic secret sharing scheme of Boyle et al. (Crypto 2016).

In this paper, we observe that it is possible to solve partially-synchronous BFT and simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness. Prior work falls short in achieving one or more of these properties, e.g., the most closely related work, HotStuff, requires a three-phase view while achieving all other properties. We demonstrate that these properties are achievable through a two-phase HotStuff variant named HotStuff-2. The quest for two-phase HotStuff variants that achieve all the above desirable properties has been long, producing a series of results that are yet sub-optimal and, at the same time, are based on somewhat heavy hammers. HotStuff-2 demonstrates that none of these are necessary: HotStuff-2 is remarkably simple, adding no substantive complexity to the original HotStuff protocol. The main takeaway is that two phases are enough for BFT after all.

Recent work in the design of rate $1 - o(1)$ lattice-based cryptosystems have used two distinct design paradigms, namely replacing the noise-tolerant encoding $m \mapsto (q/2)m$ present in many lattice-based cryptosystems with a more efficient encoding, and post-processing traditional lattice-based ciphertexts with a lossy compression algorithm, using a technique very similar to the technique of ``vector quantization'' within coding theory. We introduce a framework for the design of lattice-based encryption that captures both of these paradigms, and prove information-theoretic rate bounds within this framework. These bounds separate the settings of trivial and non-trivial quantization, and show the impossibility of rate $1 - o(1)$ encryption using both trivial quantization and polynomial modulus. They furthermore put strong limits on the rate of constructions that utilize lattices built by tensoring a lattice of small dimension with $\mathbb{Z}^k$, which is ubiquitous in the literature. We additionally introduce a new cryptosystem, that matches the rate of the highest-rate currently known scheme, while encoding messages with a ``gadget'', which may be useful for constructions of Fully Homomorphic Encryption.

$\newcommand{\Z}{\mathbb{Z}} \newcommand{\basis}{B}$We study the computational problem of finding a shortest non-zero vector in a rotation of $\Z^n$, which we call $\Z$SVP. It has been a long-standing open problem to determine if a polynomial-time algorithm for $\Z$SVP exists, and there is by now a beautiful line of work showing how to solve it efficiently in certain very special cases. However, despite all of this work, the fastest known algorithm that is proven to solve $\Z$SVP is still simply the fastest known algorithm for solving SVP (i.e., the problem of finding shortest non-zero vectors in arbitrary lattices), which runs in $2^{n + o(n)}$ time. We therefore set aside the (perhaps impossible) goal of finding an efficient algorithm for $\Z$SVP and instead ask what else we can say about the problem. E.g., can we find any non-trivial speedup over the best known SVP algorithm? And, if $\Z$SVP actually is hard, then what consequences would follow? Our results are as follows. 1. We show that $\Z$SVP is in a certain sense strictly easier than SVP on arbitrary lattices. In particular, we show how to reduce $\Z$SVP to an approximate version of SVP in the same dimension (in fact, even to approximate unique SVP, for any constant approximation factor). Such a reduction seems very unlikely to work for SVP itself, so we view this as a qualitative separation of $\Z$SVP from SVP. As a consequence of this reduction, we obtain a $2^{n/2 + o(n)}$-time algorithm for $\Z$SVP, i.e., the first non-trivial speedup over the best known algorithm for SVP on general lattices. (In fact, this reduction works for a more general class of lattices---semi-stable lattices with not-too-large $\lambda_1$.) 2. We show a simple public-key encryption scheme that is secure if (an appropriate variant of) $\Z$SVP is actually hard. Specifically, our scheme is secure if it is difficult to distinguish (in the worst case) a rotation of $\Z^n$ from either a lattice with all non-zero vectors longer than $\sqrt{n/\log n}$ or a lattice with smoothing parameter significantly smaller than the smoothing parameter of $\Z^n$. The latter result has an interesting qualitative connection with reverse Minkowski theorems, which in some sense say that ``$\Z^n$ has the largest smoothing parameter.'' 3. We show a distribution of bases $\basis$ for rotations of $\Z^n$ such that, if $\Z$SVP is hard for any input basis, then $\Z$SVP is hard on input $\basis$. This gives a satisfying theoretical resolution to the problem of sampling hard bases for $\Z^n$, which was studied by Blanks and Miller (PQCrypto, 2021). This worst-case to average-case reduction is also crucially used in the analysis of our encryption scheme. (In recent independent work that appeared as a preprint before this work, Ducas and van Woerden showed essentially the same thing for general lattices (Eurocrypt, 2022), and they also used this to analyze the security of a public-key encryption scheme. Similar ideas also appeared in different contexts in work of Cash, Hofheinz, Kiltz, and Peikert, as well as Aono, Espitau, and Nguyen in different contexts.) 4. We perform experiments to determine how practical basis reduction performs on bases of $\Z^n$ that are generated in different ways and how heuristic sieving algorithms perform on $\Z^n$. Our basis reduction experiments complement and add to those performed by Blanks and Miller, as we work with a larger class of algorithms (i.e., larger block sizes) and study the ``provably hard'' distribution of bases described above. Our sieving experiments confirm that heuristic sieving algorithms perform as expected on $\Z^n$.

The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting $C$ into a Boolean circuit and applying Yao's garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not "arithmetic". In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit $|\widehat C|$ and that of the computation tableau $|C|\ell$ in the clear, where $\ell$ is the bit length of wire values (e.g., Yao's garbled circuit has rate $O(\lambda)$). $\bullet$ We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz. $\bullet$ We construct an arithmetic garbling scheme for modular computation over $\mathcal{R} = \mathbb{Z}_p$ for any integer modulus $p$, based on either DCR or LWE. The DCR-based instantiation achieves rate $O(\lambda)$ for large $p$. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget. $\bullet$ We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.

A garbling scheme is a fundamental cryptographic building block with a long list of applications. The study of different techniques for garbling a function, towards optimizing computation and communication complexity, has been an area of active research. Most common garbling techniques work by representing each gate in the circuit as a set of ciphertexts that encrypt its truth table row-by-row. In this work we present a new garbling scheme in the random oracle (RO) model that garbles circuits in the gate-by-gate paradigm by capturing the gate functionality (AND, XOR) as a whole rather than as a set of ciphertexts. The final gate garbling requires $4\kappa$ bits of communication in expectation, 4 RO calls for garbling and 1 RO call for evaluation. We prove that the scheme satisfies privacy in the non-programmable random oracle model and against PPT adversaries. We also show how this scheme can be extended to support free-XOR and garble any gate functionality over binary inputs.

Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution of the linear transformation of the discrete spherical Gaussian and the discrete spherical Gaussian are close with respect to the Rényi divergence (RD), which we call the weak SGLHL (wSGLHL). As an application of wSGLHL, we construct a sharper self-reduction of the learning with errors problem (LWE) problem. Applebaum et al. (CRYPTO 2009) showed that linear sums of LWE samples are statistically close to (plain) LWE samples with some unknown error parameter. In contrast, we show that linear sums of LWE samples and (plain) LWE samples with a known error parameter are close with respect to RD. As another application, we weaken the independence heuristic required for the fully homomorphic encryption scheme TFHE.