Prange’s information set algorithm is a well-known decoding algorithm for linear codes. It decodes corrupted codewords of most 𝔽₂-linear codes C of message length n up to relative error rate O(log n / n) in poly(n) time. We show that the error rate can be improved to O((log n)² / n), provided: (1) the decoder has access to a polynomial-length advice string that depends on C only, and (2) C is n^{-Ω(1)}-balanced. As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate. Our main technical result is that the Hamming weight of Hw, where the rows of H are a random sample of short dual codewords, measures the proximity of a received word w to the code in the regime of interest. Given such H as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding Hw for an arbitrary polynomial-size advice matrix H.

Abstract In an Instance-Hiding Interactive Proof (IHIP) (Beaver et al., in: Menezes and Vanstone (eds) Advances in cryptology—CRYPTO 1990, proceedings, lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), Springer, pp 326–338, 1990), an efficient verifier with a private input x interacts with an unbounded prover to determine whether x is contained in a language $$\mathcal {L}$$ L . In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties and may be seen as a generalization of the influential concept of randomized encodings (Ishai and Kushilevitz, in: Proceedings 41st annual symposium on foundations of computer science, pp 294–304, 2000; Applebaum et al., in: 45th annual IEEE symposium on foundations of computer science, pp 166–175, 2004; Agrawal et al., in: Halldórsson, Iwama, Kobayashi, Speckmann (eds) Automata, languages, and programming, Springer, Berlin, Heidelberg, pp 1–13, 2015) and as a counterpart to zero-knowledge proofs (Goldwasser et al., in: Symposium on the theory of computing, 1985). We investigate the properties and power of such instance-hiding proofs and show the following: Any language with an IHIP is contained in $${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$$ NP / poly ∩ coNP / poly . If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. IHIP’s are closed under composition with any efficiently computable function. We further study a stronger version of IHIP (that we call Simulatable IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above: Any language with a Simulatable IHIP is contained in $${\textsf{AM}}\cap {\textsf{coAM}}$$ AM ∩ coAM . If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.

Batch proofs are proof systems that convince a verifier that x1,…,xt ∈ L, for some NP language L, with communication that is much shorter than sending the t witnesses. In the case of statistical soundness (where the cheating prover is unbounded but the honest prover is efficient given the witnesses), interactive batch proofs are known for UP, the class of unique-witness NP languages. In the case of computational soundness (where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of NP, assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for L imply that L has a statistically witness indistinguishable (SWI) proof, with inverse polynomial SWI error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond UP (where witness indistinguishability is trivial). In particular, assuming that NP does not have SWI proofs, batch proofs for all of NP do not exist. - Computationally sound batch proofs (a.k.a batch arguments or BARGs) for NP, together with one-way functions, imply statistical zero-knowledge (SZK) arguments for NP with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive BARGs from one-way functions would yield constant-round SZK arguments from one-way functions. This would be surprising as SZK arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive BARGs for NP, together with one-way functions, imply non-interactive computational zero-knowledge arguments for NP. Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language L into an SWI protocol for L.

Abstract Collision-resistant hash functions ( $$\textsf{CRH}$$ CRH ) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of $$\textsf{CRH}$$ CRH called t-way multi-collision-resistant hash functions ( $$t\text {-}\textsf{MCRH}$$ t - MCRH ). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even $$(t-1)$$ ( t - 1 ) -way collisions may be easy to find). The case of $$t=2$$ t = 2 corresponds to standard $$\textsf{CRH}$$ CRH , but it is natural to study t- $$\textsf{MCRH}$$ MCRH for larger values of t. Multi-collision resistance seems to be a qualitatively weaker property than standard collision resistance. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t- $$\textsf{MCRH}$$ MCRH , for $$t \in \{3,4\}$$ t ∈ { 3 , 4 } , into an (infinitely often secure) $$\textsf{CRH}$$ CRH . This transformation is non-constructive—we can prove the existence of a $$\textsf{CRH}$$ CRH but cannot explicitly point out a construction. Our result partially extends to larger values of t. In particular, we show that for suitable values of $$t>t'$$ t > t ′ , we can transform a t- $$\textsf{MCRH}$$ MCRH into a $$t'$$ t ′ - $$\textsf{MCRH}$$ MCRH , at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed–Solomon codes.

Recent digital rights frameworks give users the right to delete their data from systems that store and process their personal information (e.g., the "right to be forgotten" in the GDPR).

Privacy attacks on machine learning models aim to identify the data that is used to train such models. Such attacks, traditionally, are studied on static models that are trained once and are accessible by the adversary. Motivated to meet new legal requirements, many machine learning methods are recently extended to support machine unlearning, i.e., updating models as if certain examples are removed from their training sets, and meet new legal requirements. However, privacy attacks could potentially become more devastating in this new setting, since an attacker could now access both the original model before deletion and the new model after the deletion. In fact, the very act of deletion might make the deleted record more vulnerable to privacy attacks. Inspired by cryptographic definitions and the differential privacy framework, we formally study privacy implications of machine unlearning. We formalize (various forms of) deletion inference and deletion reconstruction attacks, in which the adversary aims to either identify which record is deleted or to reconstruct (perhaps part of) the deleted records. We then present successful deletion inference and reconstruction attacks for a variety of machine learning models and tasks such as classification, regression, and language models. Finally, we show that our attacks would provably be precluded if the schemes satisfy (variants of) deletion compliance (Garg, Goldwasser, and Vasudevan, Eurocrypt’20).

In the conditional disclosure of secrets (CDS) problem (Gertner et al. in J Comput Syst Sci, 2000) Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol, who knows both x and y, if and only if the input (x, y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security. Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate f to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of $$\Omega (n)$$ or $$\Omega (n^{1-\epsilon })$$ , providing an exponential improvement over previous logarithmic lower-bounds. We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication—a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the communication complexity class $$\text {AM}^{\text {cc}}$$ , or even $$\text {AM}^{\text {cc}}\cap \text {co-AM}^{\text {cc}}$$ —a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the “civilized” part of the communication complexity world for which explicit lower-bounds are known.

In the conditional disclosure of secrets (CDS) problem [Gertner et al., J. Comput. System Sci., 60 (2000), pp. 592--629] Alice and Bob, who hold inputs $x$ and $y$, respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies some predefined predicate $f$. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some joint randomness and the goal is to minimize the communication complexity while providing information-theoretic security. In this work, we initiate the study of CDS manipulation techniques and derive the following positive and negative results: (Closure) A CDS for $f$ can be turned into a CDS for its complement $\bar{f}$ with only a minor blow-up in complexity. More generally, for a (possibly nonmonotone) predicate $h$, we obtain a CDS for $h(f_1,\ldots,f_m)$ whose cost is essentially linear in the formula size of $h$ and polynomial in the CDS complexity of $f_i$. (Amplification) It is possible to reduce the privacy and correctness error of a CDS from constant to $2^{-k}$ with a multiplicative overhead of $O(k)$. Moreover, this overhead can be amortized over $k$-bit secrets. (Amortization) Every predicate $f$ over $n$-bit inputs admits a CDS for multibit secrets whose amortized communication complexity per secret bit grows linearly with the input length $n$ for sufficiently long secrets. In contrast, the best known upper-bound for single-bit secrets is exponential in $n$. (Lower-bounds) There exists a (nonexplicit) predicate $f$ over $n$-bit inputs for which any perfect (single-bit) CDS requires communication of at least $\Omega(n)$. This is an exponential improvement over the previously known $\Omega(\log n)$ lower-bound. (Separations) There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lower-bound of Gay, Kerenidis, and Wee [ Advances in Cryptology, Lecture Notes in Comput. Sci. 9216, Springer, New York, 2015, pp. 485--502] and, combined with another result of theirs, yields an exponential separation between the communication complexity of linear CDS and non-linear CDS. This is the first provable gap between the communication complexity of linear CDS (which captures most known protocols) and nonlinear CDS.

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is "lossy" reductions, where the reduction loses some information about the input instance. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into "useful" hardness, namely cryptography. Our first, conceptual, contribution is a definition of lossy reductions in the language of mutual information. Roughly speaking, our definition says that a reduction C is t-lossy if, for any distribution X over its inputs, the mutual information I(X;C(X)) ≤ t. Our treatment generalizes a variety of seemingly related but distinct notions such as worst-case to average-case reductions, randomized encodings (Ishai and Kushilevitz, FOCS 2000), homomorphic computations (Gentry, STOC 2009), and instance compression (Harnik and Naor, FOCS 2006). We then proceed to show several consequences of lossy reductions: 1. We say that a language L has an f-reduction to a language L' for a Boolean function f if there is a (randomized) polynomial-time algorithm C that takes an m-tuple of strings X = (x_1,…,x_m), with each x_i ∈ {0,1}^n, and outputs a string z such that with high probability, L'(z) = f(L(x_1),L(x_2),…,L(x_m)). Suppose a language L has an f-reduction C to L' that is t-lossy. Our first result is that one-way functions exist if L is worst-case hard and one of the following conditions holds: - f is the OR function, t ≤ m/100, and L' is the same as L - f is the Majority function, and t ≤ m/100 - f is the OR function, t ≤ O(m log n), and the reduction has no error This improves on the implications that follow from combining (Drucker, FOCS 2012) with (Ostrovsky and Wigderson, ISTCS 1993) that result in auxiliary-input one-way functions. 2. Our second result is about the stronger notion of t-compressing f-reductions - reductions that only output t bits. We show that if there is an average-case hard language L that has a t-compressing Majority reduction to some language for t=m/100, then there exist collision-resistant hash functions. This improves on the result of (Harnik and Naor, STOC 2006), whose starting point is a cryptographic primitive (namely, one-way functions) rather than average-case hardness, and whose assumption is a compressing OR-reduction of SAT (which is now known to be false unless the polynomial hierarchy collapses). Along the way, we define a non-standard one-sided notion of average-case hardness, which is the notion of hardness used in the second result above, that may be of independent interest.

A k-LIN instance is a system of m equations over n variables of the form si1 + · · · + sik = 0 or 1 modulo 2 (each involving k variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are different. In a noisy planted instance, the right-hand side is obtained by evaluating the system on a random planted solution and adding independent noise with some constant bias to each equation; whereas in a random instance, the right-hand side is uniformly random. Alekhnovich (FOCS 2003) conjectured that the two are hard to distinguish when k = 3 and m = O(n). We give a sample-efficient reduction from solving noisy planted k-LIN instances (a sparse-equation version of the Learning Parity with Noise problem) to distinguishing them from random instances. Suppose that m-equation, n-variable instances of the two types are efficiently distinguishable with advantage ε. Then, we show that O(m · (m/ε)2/k)-equation, n-variable noisy planted k-LIN instances are efficiently solvable with probability exp –Õ((m/ε)6/k). Our solver has worse success probability but better sample complexity than Applebaum's (SICOMP 2013). We extend our techniques to show that this can generalize to (possibly non-linear) k-CSPs. The solver is based on a new approximate local list-decoding algorithm for the k-XOR code at large distances. The k-XOR encoding of a function F: ∑ → {–1, 1} is its k-th tensor power Fk(x1, …, xk) = F(x1) · · · F(xk). Given oracle access to a function G that µ-correlates with Fk, our algorithm, say for constant k, outputs the description of a message that Ω(µ1/k)-correlates with F with probability exp(–Õ(µ−4/k)). Previous decoders, for such k, have a worse dependence on µ (Levin, Combinatorica 1987) or do not apply to subconstant µ1/k. We also prove a new XOR lemma for this parameter regime. The decoder and its analysis rely on a new structure-versus-randomness dichotomy for general Boolean-valued functions over product sets, which may be of independent interest.

We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002. Second, we “lift” this oracle separation to the setting of communication complexity, thereby answering a question of Goos et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles which separate SZK from PZK, NISZK from NIPZK and PZK from coPZK. The first of these results answers a question raised in 1991 by Aiello and Hastad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.

Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty to every other party that did not receive the output. These works show how to design protocols for secure computation with penalties that tolerate an arbitrary number of corruptions.