Search

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections. [ABSTRACT FROM AUTHOR]

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a "small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in a running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a "random looking" graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t). nc, where f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in n (i.e., n (1)). In particular, given constants d > c 1, we output a bipartite graph that has n left nodes and nc right nodes with right-degree of d so that any right set of size at most n (1) expands by factor of (d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and lowdensity parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [SIAM J. Comput., 36 (2006), pp. 845-888] and Ishai et al. [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433-442]). [ABSTRACT FROM AUTHOR]

The article discusses various papers published within the issue, including one by Benny Applebaum, Yuval Ishai and Eyal Kushilevitz on cryptographic primitives and another by Salil P. Vadhan on computational zero-knowledge.

In their seminal work on nonmalleable cryptography, Dolev, Dwork, and Naor showed how to construct a nonmalleable commitment with logarithmically-many "rounds"/"slots," the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of nonmalleable commitments leaves something to be desired. In this paper we propose a new technique that allows us to construct a nonmalleable protocol with only a single slot and to im- prove in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four-round nonmalleable commitment and a four-round nonmalleable zero-knowledge argument, the latter matching the round-complexity of the best known zero-knowledge argument (without the nonmalleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols. Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic subprotocols in a way that simulta- neously amplifies soundness and nonmalleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the editor discusses various papers published within the issue which features topics such as dynamical systems, cryptography and approximation algorithms.

This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich-Micali-Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: QSZK = QSZKHV. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation. [ABSTRACT FROM AUTHOR]

Permutation polynomials have been a subject of study for a long time and have applications in many areas of science and engineering. However, only a small number of specific classes of permutation polynomials are described in the literature so far. In this paper we present a number of permutation trinomials over finite fields, which are of different forms. [ABSTRACT FROM AUTHOR]

An introduction to topics discussed at the 54th annual IEEE Symposium on Foundations of Computer Science held in Berkeley, California on October 27 to 29, 2013 and published within the issue is presented, including cryptography, approximation algorithms and learning theory.

A permutation rational function f ∈ Fq(x) is a rational function that induces a bijection on Fq, that is, for all y ∈ Fq there exists exactly one x ∈ Fq such that f(x) = y. Permutation rational functions are intimately related to exceptional rational functions, and, more generally, exceptional covers of the projective line, of which they form the first important example. In this paper, we show how to efficiently generate many permutation rational functions over large finite fields using isogenies of elliptic curves, and discuss some cryptographic applications. Our algorithm is based on Fried's modular interpretation of certain dihedral exceptional covers of the projective line [Finite Fields: Theory, Applications, and Algorithms, Contemp. Math. 168, 1994, pp. 69-100]. [ABSTRACT FROM AUTHOR]

Suppose that you have n truly random bits x = (x1, . . .,xn) and you wish to use them to generate m ≫ n pseudorandom bits y = (y1, . . ., ym) using a local mapping, i.e., each yi should depend on at most d = O(1) bits of x. In the polynomial regime of m = ns, s > 1, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct input indices (xi1, . . ., xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has small bias) is achieved if the predicate is (a) k = Ω(s)-resilient, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local small-biased generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka, and Trevisan [Proceedings of FOCS, 2003]. Our negative result shows that a candidate for a pseudorandom generator proposed by Applebaum [Comput. Complexity, 25 (2016), pp. 667-722] and by O'Donnell and Witmer [Proceedings of CCC 2014] is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins, and Vempala [Proceedings of STOC 2015] regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the polynomial calculus proof system. We show that algebraic attacks succeed if and only if the predicate P has rational degree e = Θ(s), where the rational degree of a predicate P is the smallest integer e for which there exist degree e polynomials Q,R, not both zero, such that PQ = R. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by Applebaum [Comput. Complexity, 25 (2016), pp. 667-722]. [ABSTRACT FROM AUTHOR]

Noninteractive zero-knowledge proofs and noninteractive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that noninteractive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient noninteractive zero-knowledge proofs and noninteractive witness-indistinguishable proofs that work directly for a wide class of languages that are relevant in practice (namely, ones involving the satisfiability of equations over bilinear groups), without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides noninteractive witness-indistinguishable proofs and noninteractive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of noninteractive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups. [ABSTRACT FROM AUTHOR]

In this paper we compute the Fourier spectra of some recently discovered binomial almost perfect nonlinear (APN) functions. One consequence of this is the determination of the nonlinearity of the functions, which measures their resistance to linear cryptanalysis. Another consequence is that certain error-correcting codes related to these functions have the same weight distribution as the 2-error-correcting Bose-Chaudury-Hocquenghem (BCH) code. Furthermore, for field extensions of F2 of odd degree, our results provide an alternative proof of the APN property of the functions. [ABSTRACT FROM AUTHOR]

Lattices have received considerable attention as a Potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai [in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, PA, 1996, pp. 99-108] connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous self-contained proof of results along the lines of Ajtai's seminal work. At the same time, we explore to what extent Ajtai's original results can be quantitatively improved. As a by-product, we define a random class of lattices such that computing short nonzero vectors in the class with nonnegligible probability is at least as hard as approximating the length of the shortest nonzero vector in any n-dimensional lattice within worst- case approximation factors γ(n) = n³ ω(√log n log log n). This improves previously known best connection factor γ(n) = n4+ϵ [J.-Y. Cai and A. P. Nerurkar, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 468-4771. We also show how our reduction implies the existence of collision resistant cryptographic hash functions based on the worst-case inapproximability of the shortest vector problem within the same factors γ(n) = n³ ω(√log n log log n). in the process we distill various new lattice problems that might be of independent interest, related to the covering radius, the bounded distance decoding problem, approximate counting of lattice points inside convex bodies, and the efficient construction of lattices with good geometric and algorithmic decoding properties. We also show how further investigation of these new lattice problems might lead to even stronger connections between the average-case and worst-case complexity of the shortest vector problem, possibly leading to connection factors as low as γ(n) = n1.5ω(log n). [ABSTRACT FROM AUTHOR]

Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczyński [Some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733–748] introduced e*(G) = ¦ V (G) ¦ (k − 1) − k2 as the minimum number of edges for a k-UCG and S. J. Xu [J. Combin. Theory Ser. B, 50 (1990), pp. 319–320] conjectured that any minimal k-UCG contains a Kk as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a k-UCG with clique number k − t, for each t ≥ 1 and each k, when k is large enough. This also improves some known results for the case t = 1. Second, we analyze the parameter Λ(G) = ¦ E(G) ¦ − e*(G) for our constructions, and we obtain some bounds for the functions λt(k) = min{Λ(G) : G is a k-UCG and cl(G) = k - t}, vt(k) = min{¦ V (G) ¦ : G is a k-UCG and cl(G) = k − t}. Also, we introduce some possible applications of the technique in cryptography and data compression. [ABSTRACT FROM AUTHOR]

An introduction to the special section of the journal is presented which features computer science-related topics such as cryptography, approximation algorithms and combinatorics.

Randomized encodings of functions can be used to replace a "complex" function f(x) by a "simpler" randomized mapping ...(x; r) whose output distribution on an input x encodes the value of f(x) and hides any other information about x. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding ... of f in which most of the output can be precomputed and published before seeing the input x. When the input x is available, it remains to publish only a short string ..., where the online complexity of computing ... is independent of (and is typically much smaller than) the complexity of computing f. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part ... consists of n encryption keys of length κ each, where n = |x| and κ is a security parameter. Thus, the online rate |...|/|x| of this encoding is proportional to the security parameter μ. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function f : {0,1}n → {0, 1}m(n) with online rate of 1 + o(1) and with nearly linear online computation. More concretely, the online part x consists of an n-bit string and a single encryption key. These constructions can be based on the decisional Diffie-Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation. [ABSTRACT FROM AUTHOR]

One of the main problems we want to address is the fact that in the construction theory of authentication codes, the expression "new code" is used all the time, while it is almost never shown that the obtained codes indeed are new, or even what the notion "new" means to begin with. In this paper, we formally define authentication codes and introduce a comparison method for them, using the notion of isomorphism and the invariant isomorphism group. We then define operations in this framework which enable us to "multiply" and "add" arbitrary authentication codes, regardless of how they are initially constructed. We obtain (nonisomorphic) codes with easily calculated parameters, a large number of which are new. [ABSTRACT FROM AUTHOR]

Most of the work in the analysis of cryptographic schemes is concentrated in abstract adversarial models that do not capture side-channel attacks. Such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. Inspired by recent side-channel attacks, especially the "cold boot attacks" of Halderman et al. [Proceedings of the 17th USENIX Security Symposium, San Jose, CA, 2008, pp. 45-60], Akavia, Goldwasser, and Vaikuntanathan [Proceedings of the 6th IACR Theory of Cryptography Conference, San Francisco, CA, 2009, pp. 474-495] formalized a realistic framework for modeling the security of encryption schemes against a wide class of side-channel attacks in which adversarially chosen functions of the secret key are leaked. In the setting of public-key encryption, they showed that Regev's lattice-based scheme [Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, 2005, pp. 84-93] is resilient to any leakage of L/polylog(L)bits, where L is the length of the secret key. In this paper we revisit the above-mentioned framework and our main results are as follows. (A) We present a generic construction of a public-key encryption scheme that is resilient to key leakage from any hash proof system. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying hash proof system. Existing constructions of hash proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional Diffie-Hellman assumption (and its progressively weaker d-linear variants), the quadratic residuosity assumption, and Paillier's composite residuosity assumption. (B) We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-linear variants) and show that the resulting scheme is resilient to any leakage of L(1-o(1)) bits. In addition, we prove that the recent scheme of Boneh et al. [Advances in Cryptology--CRYPTO'08, Santa Barbara, CA, 2008, pp. 108-125], constructed to be a "circular-secure" encryption scheme, fits our generic approach and is also resilient to any leakage of L(1-o(1)) bits. (C) We extend the framework of key leakage to the setting of chosen-ciphertext attacks. On the theoretical side, we prove that the Naor-Yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are CCA2-secure with any leakage of L(1-o(1)) bits. On the practical side, we prove that variants of the Cramer-Shoup cryptosystem (along the lines of our generic construction) are CCA1-secure with any leakage of L/4 bits, and CCA2-secure with any leakage of L/6bits. [ABSTRACT FROM AUTHOR]

We formalize a realistic model for computations over massive data sets. The model, referred to as the adversarial sketch model, unifies the well-studied sketch and data stream models together with a cryptographic flavor that considers the execution of protocols in "hostile environments," and provides a framework for studying the complexity of tasks involving massive data sets. In the adversarial sketch model several parties are interested in computing a joint function in the presence of an adversary that dynamically chooses their inputs. These inputs are provided to the parties in an on-line manner, and each party incrementally updates a compressed sketch of its input. The parties are not allowed to communicate, they do not share any secret information, and any public information they share is known to the adversary in advance. Then, the parties engage in a protocol in order to evaluate the function on their current inputs using only their sketches. In this paper we settle the complexity of two fundamental problems in this model: testing whether two massive data sets are equal, and approximating the size of their symmetric difference. For these problems we construct explicit protocols that are optimal up to polylogarithmic factors. Our main technical contribution is an explicit and deterministic encoding scheme that enjoys two seemingly conflicting properties: incrementality and high distance, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way. [ABSTRACT FROM AUTHOR]

We design innovative algorithms for visual multiple-secret sharing using circle or cylinder random grids in this paper. Formal validations, security analyses, and computer implementations are discussed to demonstrate the correctness and feasibility of our algorithms. As compared to the schemes developed in conventional visual cryptography, our design delivers three significant advantages: (1) it is capable of sharing multiple (instead of only one or two) secret images in two shares; (2) it does not result in any extra pixel expansion so that the sizes of the secret image and the encrypted shares are exactly the same; and (3) it is simple and easy to implement. These advantages broaden the potential applicability and flexibility of visual secret sharing schemes. [ABSTRACT FROM AUTHOR]

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of NP with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in NP and cryptanalysis of key agreement protocols in the "bounded storage model" when mixed with (time) complexity-based cryptography. [ABSTRACT FROM AUTHOR]

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of NP with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in NP and cryptanalysis of key agreement protocols in the "bounded storage model" when mixed with (time) complexity-based cryptography. [ABSTRACT FROM AUTHOR]

A system of algebraic equations over a finite field is called sparse if each equation depends on a low number of variables. Efficiently finding solutions to the system is an underlying hard problem in cryptanalysis of modern ciphers. In this paper the deterministic Agreeing-Gluing algorithm introduced earlier by Raddum and Semaev for solving such equations is studied. Its expected running time on uniformly random instances of the problem is rigorously estimated. The estimate is at present the best theoretical bound on the complexity of solving average instances of the problem. In sparse Boolean equations we observe an exciting difference with the worst-case complexity provided by SAT solving methods. [ABSTRACT FROM AUTHOR]

Many approximation algorithms have been presented in the last decades for NP-hard search problems. The focus of this paper is on cryptographic applications, where it is desirable to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms--efficient approximation algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information. For functions, Feigenbaum et al. [ACM Trans. Algorithms, 2 (2006), pp. 435-472] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to relations is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms; applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. We argue that our privacy requirement is natural and quite minimal. We show that, even under this minimal definition of privacy, for well-studied problems such as vertex cover and max exact 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similarly to Halevi et al. [in Proceedings of the 33rd ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 550-559], we define a relaxed notion of approximation algorithms that leak (a little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for max exact 3SAT that leak a little information. [ABSTRACT FROM AUTHOR]

Presents an overview of articles about cryptography featured in the December 2003 issue of "SIAM Review."

An (n, k)-bit-fixing source is a distribution X over {0, 1}n such that there is a subset of k variables in X1,…, Xn which are uniformly distributed and independent of each other, and the remaining n - k variables are fixed. A deterministic bit-fixing source extractor is a function E : {0, 1}n → {0, 1}m which on an arbitrary (n, k)-bit-fixing source outputs m bits that are statistically close to uniform. Recently, Kamp and Zuckerman [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 92–101] gave a construction of a deterministic bit- fixing source extractor that extracts Ω(k²/n) bits and requires k > √n. In this paper we give constructions of deterministic bit-fixing source extractors that extract (1 - o(1))k bits whenever k > (log n)c for some universal constant c > 0. Thus, our constructions extract almost all the randomness from bit-fixing sources and work even when k is small. For k ⪢ √n the extracted bits have statistical distance 2-nΩ(1) from uniform, and for k ≤ √n the extracted bits have statistical distance k-ω(1) from uniform. Our technique gives a general method to transform deterministic bit-fixing source extractors that extract few bits into extractors which extract almost all the bits. [ABSTRACT FROM AUTHOR]

We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class \sansT \sansI, namely problems that reduce to the tensor isomorphism problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives a multipartite-to-tripartite entanglement transformation procedure that preserves equivalence under stochastic local operations and classical communication. [ABSTRACT FROM AUTHOR]

A program obfuscator takes a program and outputs a "scrambled" version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. [Advances in Cryptology - CRYPTO, 2001, Lect. Notes Comput. Sci. 2139, Springer, Berlin, Heidelberg, pp. 1-18], the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. In 2013, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. [Proceedings of the Symposium on Theory of Computing Conference, STOC, ACM, 2013, pp. 467-476]. This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters [Proceedings of the Symposium on Theory of Computing, 2014, STOC, pp. 475-484]). Most of them explicitly rely on additional hardness assumptions, such as one-way functions. Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if P=NP, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if P≠NP and program obfuscation is possible, then one-way functions exist. Our main result is that if NP⊈io-BPP and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for NP. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the-average NP problems. To get some of our results we need obfuscators for simple programs such as 3CNF circuits. [ABSTRACT FROM AUTHOR]

In his seminal work, Cleve [Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364-369] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(1/r). This lower bound was met for the two-party case by Moran, Naor, and Segev [J. Cryptology, 29 (2016), pp. 491-513] and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SIAM J. Comput., 46 (2017), pp. 479-542] and was approached for nparty protocols when n < loglog r by Buchbinder et al. [Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms, 2017, pp. 2580-2600]. For n > loglog r, however, the best bias for n-party coin-flipping protocols remains O(n/√r) achieved by the majority protocol of Awerbuch et al. [How to implement Bracha's O(log n) Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε > 0, an rε-party r-round coin-flipping protocol can be efficiently biased by eΩ(1/√r). As far as we know, this is the first improvement of Cleve's bound and is only n = rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence. [ABSTRACT FROM AUTHOR]

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines. [ABSTRACT FROM AUTHOR]

We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean hidden matching problem of Bar-Yossef et al.). Previously, such an exponential separation was known only for a relational problem. The communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones. [ABSTRACT FROM AUTHOR]

Monotone span programs represent a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question regarding them is how the choice of the field in which the algebraic operations are performed affects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a superpolynomial separation between any two fields with different characteristics, solving an open problem of Pudlák and Sgall [Algebraic models of computation and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 39, P. W. Beame and S. Buss, eds., AMS, Providence, RI, 1998, pp. 279--296]. Using this result we prove a superpolynomial lower bound for monotone span programs for a function in uniform-${\cal N}C^2$ (and therefore in ${\cal P}$), solving an open problem of Babai, Gál, and Wigderson [Combinatorica, 19 (1999), pp. 301--319]. (All previous superpolynomial lower bounds for monotone span programs were for functions not known to be in ${\cal P}$.) Finally, we show that quasi-linear secret sharing schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai [On the power of nonlinear secret-sharing, in Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 188--202], are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that nonlinear secret sharing schemes are more efficient than linear secret sharing schemes. [ABSTRACT FROM AUTHOR]

The article focuses on lattices as a potential source of computational hardness. It is stated that lattices are used in cryptography, after a breakthrough result of Ajtai, connecting the average-case and worst-case complexity of several lattice problems. It presents a self-contained proof of results along the line of Miklos Ajtai's seminal work and explores the possibility of quantitative improvement in Ajtai's original results. It also presents several lattice problems related to the covering radius, the bounded distance decoding problem and approximate counting of lattice points inside convex bodies.

Profiles the Russian mathematician Boris Alexandrovich Sevastyanov. Educational attainment; Fields of specialization; Transformation of probability theory from applied science to mathematical discipline; Establishment of basic results for Markov and non-Markov branching processes; Focus on probabilistic problems of discrete mathematics and theoretical cryptography.

A (k, n)-threshold visual cryptography scheme (VCS) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the "visual" recovery of the secret image. However, by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of copying the shares onto transparencies and then stacking them. Any k shares will reveal the secret image without any cryptographic computation. In this paper we analyze the contrast of the reconstructed image for a (k, n)-threshold VCS. We define a canonical form for a (k, n)-threshold VCS and provide a characterization of a (k, n)-threshold VCS. We completely characterize a contrast optimal (n- 1, n)-threshold VCS in canonical form. Moreover, for n ≥ 4, we provide a contrast optimal (3, n)-threshold VCS in canonical form. We first describe a family of (3, n)-threshold VCS achieving various values of contrast and pixel expansion. Then we prove an upper bound on the contrast of any (3, n)-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for k = 4, 5 we present two schemes with contrast asymptotically equal to 1/64 and 1/256, respectively. [ABSTRACT FROM AUTHOR]

Abstract. Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of noncontiguous memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer). We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly optimal read efficiency. Specifically, for a database of size N, under the modest assumption that no keyword appears in more than N1-1/ log logN documents, we construct a scheme with read efficiency O(log logN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT '14) showing that any SSE scheme must be suboptimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency O(logN). Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations ("balls and bins") problem that we put forward. We construct nearly optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques. [ABSTRACT FROM AUTHOR]

We present the first exponentiation algorithm that uses the entropy of the source of the exponent to improve on existing exponentiation algorithms when the entropy is smaller than (1 + w(S)/l(S))[SUP-1], where w(S) is the Hamming weight of the exponent, and l(S) is its length. For entropy 1 it is comparable to the best-known general purpose exponentiation algorithms. [ABSTRACT FROM AUTHOR]

We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems. We use this technique to carry out a systematic study of the applicability of indistinguishability obfuscation to a variety of cryptographic goals. Along the way, we resolve the 16-year-old open question of deniable encryption, posed by Canetti et al. in 1997: In deniable encryption, a sender who is forced to reveal to an adversary both her message and the randomness she used for encrypting it should be able to convincingly provide "fake" randomness that can explain any alternative message that she would like to pretend that she sent. We resolve this question by giving the first construction of deniable encryption that does not require any preplanning by the party that must later issue a denial. In addition, we show the generality of our punctured programs technique by also constructing a variety of core cryptographic objects from indistinguishability obfuscation and one-way functions (or close variants). In particular we obtain public-key encryption, short "hash-and-sign" selectively secure signatures, chosen-ciphertext secure public-key encryption, noninteractive zero knowledge arguments and injective trapdoor functions. These results suggest the possibility of indistinguishability obfuscation becoming a "central hub" for cryptography. [ABSTRACT FROM AUTHOR]

Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so-called structured) complexity classes such as NPΠ∞NP or statistical zero-knowledge (SZK). Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes--they imply hard problems NPΠ∞NP in and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer. We show that the above primitives, and many others, do not imply hard problems in NPΠ∞NP or SZK via black-box reductions. In fact, we first show that even the very powerful notion of indistinguishability obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO. [ABSTRACT FROM AUTHOR]

We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the ma jority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The protocol is efficient for NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f. We further introduce a new notion of effective degree, and show that the round complexity of a functionality f is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity. [ABSTRACT FROM AUTHOR]

A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt--Picard group of such an order is a certain group of ideal classes that is closely related to the "minus part" of the class group. We present a deterministic polynomial-time algorithm for the following problem, which may be viewed as a special case of the principal ideal testing problem: given a CM-order, decide whether two given elements of its Witt--Picard group are equal. In order to prevent coefficient blow-up, the algorithm operates with lattices rather than with ideals. An important ingredient is a technique introduced by Gentry and Szydlo in a cryptographic context. Our application of it to lattices over CM-orders hinges upon a novel existence theorem for auxiliary ideals, which we deduce from a result of Konyagin and Pomerance in elementary number theory. [ABSTRACT FROM AUTHOR]

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF F, we create a marked program e C that evaluates F(·). An adversary that gets C cannot come up with any program C* in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs. The work of Barak et al. [CRYPTO 2001, Springer, Berlin, 2001, pp. 1-18; J. ACM, 59 (2012), 6] shows that, assuming indistinguishability obfuscation (iO), such watermarking is impossible if the marked program e C evaluates the original program with perfect correctness. In this work we show that, assuming iO, such watermarking is possible if the marked program e C is allowed to err with even a negligible probability, which would be undetectable to the user. We also significantly extend the impossibility results to our relaxed setting. Our watermarking schemes are public key, meaning that we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against chosen program attacks where the adversary is given oracle access to the marking functionality. We emphasize that our security notion of watermark nonremovability considers arbitrary adversarial strategies to modify the marked program, in contrast to the prior works [R. Nishimaki in EUROCRYPT 2013, Springer, Berlin, pp. 111-125]. [ABSTRACT FROM AUTHOR]

We show how to construct indistinguishability obfuscation (iO) for RAM programs with bounded space, assuming iO for circuits and one-way functions, both with subexponential security. That is, given a RAM program whose computation requires space s(n) in the worst case for inputs of length at most n, we generate an obfuscated RAM program that, for inputs of size at most n, runs in roughly the same time as the original program, using space roughly s(n). The obfuscation process is quasi-linear in the description length of the input program and s(n). At the heart of our construction are succinct randomized encodings for RAM programs. We present two very different constructions of such encodings, each with its own unique properties. Beyond their use as a tool in obfuscation for RAM programs, we show that succinct randomized encodings are interesting objects in their own right. We demonstrate the power of succinct randomized encodings in applications such as publicly verifiable delegation, functional encryption for RAMs, and key-dependent security amplification. [ABSTRACT FROM AUTHOR]

In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364-369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol the corrupted parties can bias the honest partie's common output bit by Ω(1/m). For more than two decades the best known coin-flipping protocols against dishonest majority had bias ⊖ (l/√m), where l is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1-18], who constructed an m-round, two-party coin- flipping protocol with optimal bias ⊖(1/m). In a subsequent work, Beimel, Omri and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503-513] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still, for the case of 2/3 (or more) corrupted parties, the best known protocol had bias ⊖(l/√m). In particular, this was the state of a airs for the natural three-party case. We take a step toward eliminating the above gap, presenting an m-round, three-party coin- flipping protocol, with bias O(log3 m)/m . Our approach (which we also apply to the two-party case) does not follow the "threshold round" paradigm used in the work of Moran, Naor and Segev and Beimel, Omri and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned ⊖(l/√m)-bias protocol. [ABSTRACT FROM AUTHOR]

We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition--assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angel-based" framework of Prabhakaran and Sahai [STOC'04, ACM, New York, 2004, pp. 242-251] and implies superpolynomial-time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment attacks (CCA security), means that security holds even if the attacker has access to an extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent nonmalleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted setup. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive having adaptive hardness from standard hardness assumptions, using no trusted setup or public keys. [ABSTRACT FROM AUTHOR]

Mochon's proof [Quantum Weak Coin Flipping with Arbitrarily Small Bias, preprint, arXiv:0711.4114, 2007] of the existence of quantum weak coin flipping with arbitrarily small bias is a fundamental result in quantum cryptography, but at the same time one of the least understood. Though used several times as a black box in important follow-up results [M. Ganz, Quantum Leader Election, preprint, arXiv:0910.4952, 2009; A. Chailloux and I. Kerenidis, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 527-533; N. Aharon and J. Silman, New J. Phys., 12 (2010), 033027; A. Chailloux and I. Kerenidis, in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2011; I. Kerenidis and S. Zhang, in Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science 7582, Springer, Berlin, 2013, pp. 13-28], the result has not been peer reviewed, its novel techniques (and, in particular, Kitaev's point game formalism) have not been applied anywhere else, and an explicit protocol is missing. We believe that truly understanding the existence proof and the novel techniques it relies on would constitute a major step in quantum information theory, leading to deeper understanding of entanglement and of quantum protocols in general. In this work, we make a first step in this direction. We simplify parts of Mochon's construction considerably, making about 20 pages of analysis in the original proof superfluous, clarifying some other parts of the proof on the way, and presenting the proof in a way which is conceptually easier to grasp. We believe the resulting proof of existence is easier to understand, more readable, and certainly verifiable. Moreover, we analyze the resources needed to achieve a bias ε and show that the number of qubits is O(log 1/ε), while the number of rounds is (1/ε)O(1/ε). A true understanding of the proof, including Kitaev's point-game techniques and their applicability, as well as completing the task of constructing an explicit (and also simpler and more efficient) protocol, are left to future work. [ABSTRACT FROM AUTHOR]

We study connections between the Natural Proofs of Razborov and Rudich, derandomization, and the problem of proving "weak" circuit lower bounds such as NEXP ⊄ TC0, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm A is embedded in them), have largeness (A accepts a large fraction of strings), and are useful (A rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are "naturalizing" would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable: largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove the following: (i) Constructivity is unavoidable, even for NEXP lower bounds. Informally, we prove for all "typical" nonuniform circuit classes C, NEXP ⊄ C if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by C-circuits. Hence NEXP ⊄ C is equivalent to exhibiting a constructive property useful against C. (ii) There are no P-natural properties useful against C if and only if randomized exponential time can be "derandomized" using truth tables of circuits from C as random seeds. Therefore the task of proving there are no P-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results, including improved ACC0 lower bounds and new unconditional derandomizations. In general, we develop and apply several new connections between the existence of certain algorithms for analyzing truth tables, and the nonexistence of small circuits for problems in large classes such as NEXP. [ABSTRACT FROM AUTHOR]

The simulation paradigm, introduced by Goldwasser, Micali, and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak [FOCS 2001, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 106{115] introduced a novel non-blackbox simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably sound zero-knowledge arguments, that cannot be proven secure using just blackbox simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth [FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 223{232] instead requires the existence of an oblivious transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge arguments. [ABSTRACT FROM AUTHOR]

A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries are of the form "What fraction of individual records in the database satisfy the property q?" We prove that if one-way functions exist, then there is no algorithm that takes as input a database D ∈ ({0, 1}d)n, and k = Θ(n²) arbitrary efficiently computable counting queries, runs in time poly(d, n), and returns an approximate answer to each query, while satisfying differential privacy. We also consider the complexity of answering "simple" counting queries, and make some progress in this direction by showing that the above result holds even when we require that the queries are computable by constant-depth (AC0) circuits. Our result is almost tight because it is known that Ω(n²) counting queries can be answered efficiently while satisfying differential privacy. Moreover, many more than n² queries (even exponential in n) can be answered in exponential time. We prove our results by extending the connection between differentially private query release and cryptographic traitor-tracing schemes to the setting where the queries are given to the algorithm as input, and by constructing a traitor-tracing scheme that is secure in this setting. [ABSTRACT FROM AUTHOR]