We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $γ> 1$ such that $\mathsf{CVP}_{p,γ}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,γ}$. Our main contribution is a randomized ETH hardness result for $\mathsf{SVP}_{p,γ}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p \in (2, \infty)$. This result relies on a novel geometric property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm, which says that for any $p \in (2, \infty)$, the number of lattice vectors close to $\frac{1}{2}\vec{1}_n$ (in the $\ell_p$ norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from $\mathsf{CVP}_{p,γ}$ to $\mathsf{SVP}_{p,γ'}$. Finally, we also use our ideas to give some minor improvements over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p,α}$ (the Bounded Distance Decoding Problem), yielding better ETH hardness results for $\mathsf{BDD}_{p,α}$ for any $p \in [1, \infty)$ and $α> α_p^{\ddagger}$, where $α_p^{\ddagger}$ is an explicit threshold depending on $p$.

Abstract. The most important computational problem on lattices is the shortest vector problem ([Formula: see text]). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for [Formula: see text]. We present the following results: (1) A new algorithm for [Formula: see text] that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer [Formula: see text], our algorithm takes [Formula: see text] time and requires [Formula: see text] memory. This tradeoff, which ranges from enumeration ([Formula: see text]) to sieving ([Formula: see text] constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for [Formula: see text] that runs in time [Formula: see text] and requires [Formula: see text] classical memory and [Formula: see text] qubits. In a quantum random access memory (QRAM) model, this algorithm takes only [Formula: see text] time and requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733–742] that has a time and space complexity [Formula: see text]. (3) A classical algorithm for [Formula: see text] that runs in time [Formula: see text] time and [Formula: see text] space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285–306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is [Formula: see text]. We conjecture that for most lattices this quantity is a [Formula: see text]. Assuming that this is the case, our classical algorithm runs in time [Formula: see text], our quantum algorithm runs in time [Formula: see text], and our quantum algorithm in a QRAM model runs in time [Formula: see text]. As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909–916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice [Formula: see text] ([Formula: see text] LIP ) that runs in time [Formula: see text]. Our algorithm requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space.

Non-malleable codes introduced by Dziembowski, Pietrzak and Wichs [1] encode a classical messageSin a manner such that the tampered codeword either decodes to the original messageSor a message that is unrelated/independent ofS. Constructing non-malleable codes for various tampering function families has received significant attention in the recent years. We consider the well studied (2-part)split-statemodel, in which the messageSis encoded into two partsXandY, and the adversary is allowed to arbitrarily tamper with eachXandYindividually. Non-malleable codes in the split-state model have found applications in other important security notions likenon-malleable commitmentsandnon-malleable secret sharing. Thus, it is vital to understand if such non-malleable codes are secure against quantum adversaries. We consider the security of non-malleable codes in the split-state model when the adversary is allowed to make use of arbitrary entanglement to tamper the partsXandY. We construct explicit quantum secure non-malleable codes in the split-state model. Our construction of quantum secure non-malleable codes is based on the recent construction of quantum secure 2-source non-malleable extractorsby Boddu, Jain and Kapshikar [2]. • We extend the connection of Cheraghchi and Guruswami [3] between 2-source non-malleable extractors and non-malleable codes in the split-state model in the classical setting to the quantum setting, i.e. we show that explicit quantum secure 2-source non-malleable extractors in (k1,k2)-qpa-state framework of [2] give rise to explicit quantum secure non-malleable codes in the split-state model. • We construct the first quantum secure non-malleable code with efficient encoding and decoding procedures for message lengthm=nΩ(1), error ε = 2-nΩ(1)and codeword of size 2n. Prior to this work, it remained open to provide such quantum secure non-malleable code even for a single bit message in the split-state model. • We also study its natural extension when the tampering of the codeword is performedt-times. We construct quantum secure one-many non-malleable code with efficient encoding and decoding procedures fort=nΩ(1), message lengthm=nΩ(1), error ε = 2-nΩ(1)and codeword of size 2n. • As an application, we also construct the first quantum secure 2-out-of-2 non-malleable secret sharing scheme for message/secret lengthm=nΩ(1), error ε = 2-nΩ(1)and share of sizen.

Multi-source extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. Quantum multi-source extractors were considered by Kasher and Kempe (2010) (for the quantum independent adversary and the quantum bounded storage adversary), Chung et al. (2014) (for the general entangled adversary) and Arnon-Friedman et al. (2016) (for the quantum Markov adversary). One of the main objectives of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary ($\mathsf {qma}$), which generates side information using entanglement and on post-measurement; and 2) the quantum communication adversary ($\mathsf {qca}$), which generates side information using entanglement and communication between multiple sources. We show that: 1)$\mathsf {qma}$is the strongest adversary among all the known adversaries, in the sense that the side information of all other adversaries can be generated by$\mathsf {qma}$; 2) The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor with matching parameters as that of Chor and Goldreich (1985) against classical adversaries; 3) A non-malleable extractor proposed by Li (2012) (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal et al. (2019) with uniform seed. We strengthen their result via a completely different proof to make the non-malleable extractor of Li secure against quantum side information even when the seed is not uniform; 4) A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs (2009) protocol for privacy-amplification is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to Aggarwal et al. (2019) which uses uniform local randomness; 5) A tight efficiency lower bound for the (generalized) inner-product function (in fact a general class of two-wise independent functions).

Stochastic Gradient Descent (SGD) is a popular training algorithm, a cornerstone of modern machine learning systems. Several security applications benefit from determining if SGD executions are forgeable, i.e., whether the model parameters seen at a given step are obtainable by more than one distinct set of data samples. In this paper, we present the first attempt at proving impossibility of such forgery. We furnish a set of conditions, which are efficiently checkable on concrete checkpoints seen during training runs, under which checkpoints are provably unforgeable at that step. Our experiments show that the conditions are somewhat mild and hence always satisfied at checkpoints sampled in our experiments. Our results sharply contrast prior findings at a high level: We show that checkpoints we find to be provably unforgeable have been deemed to be forgeable using the same methodology and experimental setup suggested in prior work. This discrepancy arises because of unspecified subtleties in definitions. We experimentally confirm that the distinction matters, i.e., small errors amplify during training to produce significantly observable difference in final models trained. We hope our results serve as a cautionary note on the role of algebraic precision in forgery definitions and related security arguments.

Recent work has shown SETH hardness of CVP in the $\ell_{p}$ norm for any p that is not an even integer. This result was shown by giving a Karp reduction from k-SAT on n variables to CVP on a lattice of rank n. In this work, we show a barrier towards proving a similar result for CVP in the $\ell_{p}$ norm where p is an even integer. We show that for any $c\gt0$, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a CVP instance for a lattice of rank at most $n^{c}$ in the Euclidean norm, then coNP $\subset NP/Poly$. We prove a similar result for CVP for all even norms under a mild additional promise that the ratio of the distance of the target from the lattice and the shortest non-zero vector in the lattice is bounded by $\exp \left(n^{O(1)}\right)$. Furthermore, we show that for any $c\gt0$, and any even integer p, if for every $k\gt0$, there exists an efficient reduction that maps a k-SAT instance on n variables to a $SVP_{p}$ instance for a lattice of rank at most $n^{c}$, then coNP $\subset NP /$ Poly.1While prior results have indicated that lattice problems in the $\ell_{2}$ norm (Euclidean norm) are easier than lattice problems in other norms, this is the first result that shows a separation between these problems. We achieve this by using a result by Dell and van Melkebeek on the impossibility of the existence of a reduction that compresses an arbitrary k-SAT instance into a string of length $\mathcal{O}\left(n^{k-\varepsilon}\right)$ for any $\varepsilon\gt0$. In addition to CVP, we also show that the same result holds for the Subset-Sum problem using similar techniques.1The result for SVP does not require any additional promise.

Model counting is a fundamental problem with many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In this work, we focus on a variant of this problem where the underlying formula is expressed in Disjunctive Normal Form (DNF), also known as #DNF. This problem has been shown to be #P-complete, making it intractable to solve exactly. Much research has therefore been focused on obtaining approximate solutions, particularly in the form of (epsilon, delta) approximations. The primary contribution of this paper is a new approach, called pepin, to approximate #DNF counting that achieves (nearly) optimal time complexity and outperforms existing FPRAS. Our approach is based on the recent breakthrough in the context of union of sets in streaming. We demonstrate the effectiveness of our approach through extensive experiments and show that it provides an affirmative answer to the challenge of efficiently computing #DNF.

We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2є n time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.

Abstract Consider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it possible to encode the inputs in such a way that only linear functions can be evaluated over the encodings? I.e., learning an arbitrary function of the encodings will not reveal more information about the inputs than a linear combination. In this work, we introduce the notion of algebraic restriction codes (AR codes), which constrain adversaries who might compute any function to computing a linear function. Our main result is an information-theoretic construction AR codes that restrict any class of function with a bounded number of output bits to linear functions. Our construction relies on a seed which is not provided to the adversary. While interesting and natural on its own, we show an application of this notion in cryptography. In particular, we show that AR codes lead to the first construction of rate-1 oblivious transfer with statistical sender security from the Decisional Diffie–Hellman assumption, and the first-ever construction that makes black-box use of cryptography. Previously, such protocols were known only from the LWE assumption, using non-black-box cryptographic techniques. We expect our new notion of AR codes to find further applications, e.g., in the context of non-malleability, in the future.

At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs) which protect against tampering of a codeword of a given message into the codeword of a related message. A well-studied model of tampering is the 2-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates.

We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed tofully corruptthe internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: 1) we give a privacy amplification protocol via low-error non-malleable two-source extractors with one source having low min-entropy. In particular, this implies the existence of such (non-efficient) protocols; 2) we show that even slight improvements to the state-of-the-art explicit non-malleable two-source extractors would lead to explicit low-error, low min-entropy two-source extractors, thereby resolving a long-standing open question. This suggests that obtaining (information-theoretically secure)explicitnon-malleable two-source extractors for (1) might be hard; 3) we present explicit constructions of low-error, low min-entropy non-malleable two-source extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasi-polynomial hardness of DDH or the existence of nearly-optimal collision-resistant hash functions; 4) we instantiate our privacy amplification protocol with the above mentioned non-malleable two-source extractors in the CRS model, leading to explicit, computationally-secure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasi-polynomial hardness of DDH to sub-exponential hardness of DDH.We emphasize that each of the first three results can be read independently.

We show a number of fine-grained hardness results for the Closest Vector Problem in the ℓp norm (CVPp), and its approximate and non-uniform variants. First, we show that CVPp cannot be solved in 2(1–∊)n time for all p ∉ 2ℤ and ∊ > 0, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extend this by showing that there is no 2(1–∊)n-time algorithm for approximating CVPp to within a constant factor γ for such p assuming a “gap” version of SETH, with an explicit relationship between γ, p, and the arity k = k(∊) of the underlying hard CSP. Third, we show the same hardness result for (exact) CVPp with preprocessing (assuming non-uniform SETH). For exact “plain” CVPp, the same hardness result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitely many p ∉ 2ℤ, where the set of exceptions depended on ∊ and was not explicit. For the approximate and preprocessing problems, only very weak bounds were known prior to this work. We also show that the restriction to p ∉ 2ℤ is in some sense inherent. In particular, we show that no “natural” reduction can rule out even a 23n/4-time algorithm for CVP2 under SETH. For this, we prove that the possible sets of closest lattice vectors to a target in the ℓ2 norm have quite rigid structure, which essentially prevents them from being as expressive as 3-CNFs. We prove these results using techniques from many different fields, including complex analysis, functional analysis, additive combinatorics, and discrete Fourier analysis. E.g., along the way, we give a new (and tighter) proof of Szemerédi's cube lemma for the boolean cube. Please see the full version of this paper for the proofs of these results [1].

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓp norms (SVPp and CVPp respectively). Specifically, we present the following 2∊m-time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: a reduction from Õ(1/∊1/p)γ-approximate SVPq to γ-approximate SVPp; a reduction from Õ(1/∊1/p)γ-approximate CVPp to γ-approximate CVPq; and a reduction from Õ(1/∊1+1/p)-CVPq to (1 + ∊)-unique SVPp (which in turn trivially reduces to (1 + ∊)-approximate SVPp). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2O(m)-time SVPp algorithms to solve O(1)-approximate CVPp. In fact, we show a stronger result in the special case when 1 ≤ p = q ≤ 2 and the SVPp oracle is exact: a reduction from O(1/∊1/p)-CVPp to (exact) SVPp in 2∊m time. For example, taking ∊ = log m/m and p = 2 gives a slight improvement over Kannan's celebrated polynomial-time reduction from to SVP2. We also note that the last two reductions can be combined to give a reduction from approximate-CVPp to SVPq for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [21] (which showed how to adapt the current fastest known algorithm for these problems in the ℓ2 norm to all ℓp norms) together with sparsification-based techniques.

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. 1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a "change in quantifiers" over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input sources with sufficient min-entropy, a somewhere extractor only requires that there exists a seed whose output bias is small. More generally, we study what we call probable extractors, which on input a source with sufficient min-entropy guarantee that a large enough fraction of seeds have small enough associated output bias. Such extractors have played a key role in many constructions of pseudorandom objects, though they are often defined implicitly and have not been studied extensively. Prior known techniques fail to yield good seed length lower bounds when applied to the variants above. Our novel approach yields significantly improved lower bounds for somewhere and probable extractors. To complement this, we construct a somewhere extractor that implies our lower bound for such functions is tight in the high min-entropy regime. Surprisingly, this means that a random function is far from an optimal somewhere extractor in this regime. The techniques that we develop also yield an alternative, simpler proof of the celebrated optimal lower bound for strong extractors originally due to Radhakrishnan and Ta-Shma (SIAM J. Discrete Math., 2000).

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely “unrelated value”. The family which received the most attention is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. In this work, we give a constant rate non-malleable code from the tampering family containing so called 2-lookahead functions and forgetful functions, and combined with the work of Dodis, Kazana and the authors from STOC 2015, this gives the first constant rate non-malleable code in the split-state model with negligible error. The full version of this paper can be found here: https://eprint.iacr.org/2019/1299.

Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest non-zero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer and Naewe, 2009] generalized the algorithm to other norms. We study this problem for the special but important case of the l_infty norm. We give a new sieving procedure that runs in time linear in N, thereby improving the running time of the algorithm for SVP in the l_infty norm. As in [Ajtai et al., 2002; Blömer and Naewe, 2009], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the l_infty norm. We also show that the heuristic sieving algorithms of Nguyen and Vidick [Nguyen and Vidick, 2008] and Wang et al. [Wang et al., 2011] can also be analyzed in the l_infty norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest.

Algebraic Manipulation Detection (AMD) codes [CDFPW08] are keyless message authentication codes that protect messages against additive tampering by the adversary assuming that the adversary cannot “see” the codeword. For certain applications, it is unreasonable to assume that the adversary computes the added offset without any knowledge of the codeword c. Recently, Ahmadi and Safavi-Naini [AS13], and then Lin, Safavi-Naini, and Wang [LSW16] gave a construction of leakage-resilient AMD codes where the adversary has some partial information about the codeword before choosing added offset, and the scheme is secure even conditioned on this partial information. In this paper we show the bounds on the leakage rate ρ and the code rate K for leakage-resilient AMD codes. In particular we prove that and for the weak case (security is averaged over a uniformly random message) . These bounds hold even if adversary is polynomial-time bounded, as long as we allow leakage function to be arbitrary. We present the constructions of AMD codes that (asymptotically) fulfill above bounds for almost full range of parameters ρ and κ. This shows that above bounds and constructions are in-fact optimal. In the full version of the paper we also show that if a leakage function is computationally bounded (we use Ideal Cipher Model) then it is possible to break these bounds.

We prove the following quantitative hardness results for the Shortest Vector Problem in the ℓp norm (SVP_p), where n is the rank of the input lattice.

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible, for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. Although such codes do not exist if the family of “tampering functions” ${\mathcal F}$ is completely unrestricted, they are known to exist for many broad tampering families ${\mathcal F}$. One such natural family is the family of tampering functions in the so-called split-state model. Here the message $m$ is encoded into two shares $L$ and $R$, and the attacker is allowed to arbitrarily tamper with $L$ and $R$ individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature but either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function $\langle{L,R\rangle}$ over the vector space ${{F}_p}^n$ (for a prime $p$ and large enough dimension $n$): if $L$ and $R$ are uniformly random over ${\mathbb{F}_p}^n$, and $f,g:{\mathbb{F}_p}^n\rightarrow {\mathbb{F}_p}^n$ are two arbitrary functions on $L$ and $R$, then the joint distribution $(\langle{L,R\rangle},\langle{f(L),g(R)\rangle})$ is “close” to the convex combination of “affine distributions” $\{(U,aU+b)\mid a,b\in \mathbb{F}_p\}$, where $U$ is uniformly random in ${\mathbb{F}_p}$. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so-called quasi-polynomial Freiman--Ruzsa theorem, which was recently established by Sanders [Anal. PDE, 5 (2012), pp. 627--655] as a step toward resolving the polynomial Freiman--Ruzsa conjecture [B. Green, in Surveys in Combinatorics, London Mathematical Society, London, 2005, pp. 1--29].

Non-malleable codes (NMCs) protect sensitive data against degrees of corruption that prohibit error detection, ensuring instead that a corrupted codeword decodes correctly or to something that bears little relation to the original message. The split-state model, in which codewords consist of two blocks, considers adversaries who tamper with either block arbitrarily but independently of the other. The simplest construction in this model, due to Aggarwal, Dodis, and Lovett (STOC'14), was shown to give NMCs sending k-bit messages to O(k7)-bit codewords. It is conjectured, however, that the construction allows linear-length codewords. Towards resolving this conjecture, we show that the construction allows for code-length O(k5). This is achieved by analysing a special case of Sanders's Bogolyubov-Ruzsa theorem for general Abelian groups. Closely following the excellent exposition of this result for the group F2nby Lovett, we expose its dependence on p for the group Fpn, where p is a prime.linear-length codewords.Bogolyubov-Ruzsa theorem

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a “weak” random source X with min-entropy k and a uniformly random seed Y of length d, and outputs a string of length close to k that is close to uniform and independent of Y. Dodis and Wichs [DW09] introduced a generalization of randomness extractors called non-malleable extractors (nmExt) where nmExt(X, Y) is close to uniform and independent of Y and nmExt(X, f(Y)) for any function f with no fixed points. We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor (AmExt : Fnx Fd→ F) where AmExt(X, Y ) is close to uniform and independent of Y and has some limited dependence of AmExt(X, f(Y )) - that conditioned on Y , (AmExt(X, Y ), AmExt(X, f(Y ))) is ε-close to (U, A · U + B) where U is uniformly distributed in F and A, B E F are random variables independent of U. We show that the inner-product function (·, ·) : Fn×Fn→ F is an affine-malleable extractor for min-entropy k = n/2 + Ω(log(1/ε)). Moreover, under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture), we show that this holds for k = Ω(log n log(1/ε)). As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture. We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and their many variants has been in constructing secure privacy amplification protocols. We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. This gives a much simpler protocol for min-entropy k = n/2 + Ω(log(1/ε)), and additionally, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.

Let$N$be a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring$N$is believed to be hard. The RSA assumption states that, given an$a$chosen uniformly at random from$ {\mathbb {Z}}_{N}$and an$e \in {\mathbb {N}} \setminus \{1\}$such that$\gcd (e, \phi (N)) = 1$, it is computationally hard to find an$x\in {\mathbb {Z}} _{N}$such that$x^{e} - a \equiv 0 \pmod N$. When complexity-theoretic (relative) lower bounds for certain cryptographic problems in a general model of computation seem to elude discovery, a common practice in cryptography is to give proofs of computational security in meaningful restricted models of computation. An example of such a restricted model that is interesting in cryptography is the generic group model that has been used for proving lower bounds for the discrete logarithm problem and other related problems. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. In this paper, we prove that the problem of factoring$N$can be efficiently reduced to solving the RSA problem on$ {\mathbb {Z}}_{N}$in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality. This provides evidence toward the soundness of the RSA encryption and digital signature scheme, in particular showing that under the factoring assumption, they are not vulnerable to certain kinds of cryptanalytic attacks.

We give a 2n+o(n)-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic Õ(4n)-time and Õ(2n)-space algorithm of Micciancio and Voulgaris [1]. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [2] to solve the problem of discrete Gaussian sampling over lattice shifts, L - t, with very low parameters. While the actual algorithm is a natural generalization of [2], the analysis uses substantial new ideas. This yields a 2n+o(n)-time algorithm for approximate CVP with the very good approximation factor γ = 1 + 2-o(n/ log n). Second, we show that the approximate closest vectors to a target vector t can be grouped into “lower-dimensional clusters,” and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that “behaves well with these clusters.” Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value". Although such codes do not exist if the family of "tampering functions" cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families cF. The family which received the most attention [DPW10,LL12,DKO13,ADL14,CG14a,CG14b] is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L|=|R|=O(|x|).

We give a randomized 2n+o(n)-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic ~O(4n)-time and ~O(2n)-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2n/2 vectors from the discrete Gaussian distribution at any parameter in 2n+o(n) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS.

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model.