Many blockchain systems today, including Bitcoin, rely on Proof of Work (PoW). Proof of work is crucial to the liveness and security of cryptocurrencies. The assumption when using PoW is that a lot of trial and error is required on average before a valid block is generated. One of the main concerns raised with regard to this kind of system is the inherent need to "waste" energy on "meaningless" problems. In fact, the Bitcoin system is believed to consume more electricity than several small countries. In this work we formally define three properties that are necessary for wasteless PoW systems: (1) solve "meaningful" problems (2) solve them efficiently and (3) be secure against double-spend attacks. These properties aim to create an open market for problem-solving, in which miners produce solutions to problems in the most efficient way (wasteless). The security of the system stems from the economical incentive created by the demand for solutions to these problems. We analyze these properties, and deduce constraints that must apply to such PoW systems. In our main result, we conclude that under realistic assumptions, the set of allowed problems must be preimage resistant functions in order to keep the system secure and efficient.

Non-malleable codes allow a sender to transmit a message to a receiver, while providing a "best-possible" integrity guarantee to ensure that no attacker - who cannot already decode the message - can meaningfully tamper the message in transit. If tampered, the received message should either be invalid or unrelated to the original message. Non-malleable time-lock puzzles (TLPs) are a special case of non-malleable codes for bounded polynomial-depth tampering with very efficient encoding. In this work, we give generic techniques for constructing non-malleable codes and non-malleable TLPs with improved rate, which captures the ratio of a message’s length to its encoding length. A key contribution of our work is identifying a security notion for non-malleability, which we term "CCA-hiding", sufficient for our compilers. CCA-hiding is a relaxation of CCA-security for encryption or commitments to the fine-grained setting of codes, and requires that the encoded message remains hidden, even given a decoding oracle for any other codeword. Intriguingly, CCA-hiding does not imply non-malleability in the fine-grained setting, as is the case for encryption and commitments. Using our new techniques, we give the following constructions: - Rate-1 CCA-hiding TLPs in the plain model. - Rate-1 non-malleable codes for bounded polynomial-depth tampering in the auxiliary-input random oracle model (AI-ROM). - Rate-(1/2) non-malleable TLPs in the AI-ROM.

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most f edges in an n-node m-edge D-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in n) for any f. This is in contrast to the exponential or polynomial dependence on f in prior works. Our main results are:

Abstract Sponge hashing is a novel alternative to the popular Merkle-Damgård hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers, r and c (bitrate and capacity, respectively), and by a fixed-size permutation on $$r+c$$ r + c bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with arbitrary S -bit auxiliary advice input about the random permutation that make T online queries. Recent work by Coretti et al. (CRYPTO ’18) showed that such adversaries can find collisions (with respect to a random c -bit initialization vector) with advantage $$\Theta (ST^2/2^c + T^2/ 2^{r})$$ Θ ( S T 2 / 2 c + T 2 / 2 r ) . Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of T blocks). Focusing on the task of finding short collisions, we study the complexity of finding a B -block collision for a given parameter $$B\ge 1$$ B ≥ 1 . We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage $$\begin{aligned} \Omega \left( \left( \frac{S^{2}T}{2^{2c}}\right) ^{2/3} + \frac{T^2}{2^r}\right) . \end{aligned}$$ Ω S 2 T 2 2 c 2 / 3 + T 2 2 r . In certain range of parameters (e.g., $$ST^2>2^c$$ S T 2 > 2 c ), our attack outperforms the previously-known best attack. To the best of our knowledge, this is the first natural application for which sponge hashing is provably less secure than the corresponding instance of Merkle-Damgård hashing. Our attack relies on a novel connection between single-block collision finding in sponge hashing and the well-studied function inversion problem. We also give a general attack that works for any $$B\ge 2$$ B ≥ 2 and has advantage $$\Omega ({STB}/{2^{c}} + {T^2}/{2^{\min \{r,c\}}})$$

Oblivious RAM (ORAM) is a central cryptographic primitive that enables secure memory access while hiding access patterns. Among existing ORAM paradigms, hierarchical ORAMs were long considered impractical despite their asymptotic optimality. However, recent advancements (FutORAMa, CCS'23) demonstrate that hierarchical ORAM-based schemes can be made efficient given sufficient client-side memory. In this work, we present a new hierarchical ORAM construction that achieves practical performance without requiring large local memory.

We study the complexity of memory checkers with computational security and prove the first general tight lower bound. Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS ’91, Algorithmica ’94), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity \(O(\log n/\log \log n)\) and local space proportional to a computational security parameter, assuming one-way functions, where n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC ’09) showed that for a restricted class of “deterministic and non-adaptive” memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem. In this work, we fully resolve the complexity of memory checkers by showing that any construction with local space p and query complexity q must satisfy \(\begin{equation*} p \ge \frac{n}{(\log n)^{O(q)}} \;. \end{equation*}\) This implies, as a special case, that \(q\ge \Omega (\log n/\log \log n)\) in any scheme, assuming that \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) . The bound applies to any scheme with computational security, completeness \(2/3\) , and inverse polynomial in n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity \(q_r\) and write complexity \(q_w\) differ. For instance, we show the tight bound that if \(q_r=O(1)\) and \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) , then \(q_w\ge n^{\Omega (1)}\) . This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off. Our proof is via a delicate compression argument showing that a “too good to be true” memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.

Abstract. An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky [ J. ACM, 43 (1996), pp. 431–473] is a (probabilistic) RAM that hides its access pattern; i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds and in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters. We observe that there is a very natural setting of parameters in which no nontrivial lower bound is known—not even those in restricted models of computation (like the so-called balls and bins model). Let [Formula: see text] and [Formula: see text] be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by [Formula: see text] the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative [Formula: see text] factor which makes them trivial in many settings of parameters of interest. In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) [Formula: see text] memory probes for every logical operation. Here, [Formula: see text] denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if [Formula: see text]. Our lower bound is tight for all settings of parameters, up to the [Formula: see text] factor. Our bound also extends to the noncolluding multiserver setting. As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online versus offline models. Specifically, we show that when [Formula: see text] and [Formula: see text], there exists an offline ORAM that makes (on average) [Formula: see text] memory probes per logical operation, while every online one must make [Formula: see text] memory probes per logical operation. No such previous separation was known for any setting of parameters—not even in the balls and bins model.

Consider the following problem: Given an$n$×$n$multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of${O}(n^{2}\log n)$. Allowing randomization. the best known algorithm has running time of$O(n^{2}\log(1/\delta))$, where$\delta > 0$is the error probability of the algorithm (Rajagopalan and Schulman, FOCS 1996, SICOMP 2000). In this work, we improve upon both of the above known algorithms. Specifically, we present a deterministic algorithm for the above problem whose running time is$O(n^{2})$. This performance is optimal up to constants. A central tool we develop is an efficient algorithm for finding a subset$A$of a group$G$satisfying$A^{2}=G$while$\vert A\vert=O(\sqrt{\vert G\vert })$.

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

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

Oblivious RAM (ORAM) is a general-purpose technique for hiding memory access patterns. This is a fundamental task underlying many secure computation applications. While known ORAM schemes provide optimal asymptotic complexity, despite extensive efforts, their concrete costs remain prohibitively expensive for many interesting applications. The current state-of-the-art practical ORAM schemes are suitable only for somewhat small memories (Square-Root ORAM or Path ORAM).

Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω (log N ) amortized blowup in memory accesses is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so-called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security. A long-standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this article, we resolve this problem and present the first secure ORAM with O (log N ) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O (log N ⋅ log log N ) amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O ( n ) algorithm improves the previously best-known deterministic or randomized algorithms whose running time is O ( n ⋅ log n ) or O ( n ⋅ log log n ), respectively.

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC '87 and J. ACM '96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT '20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead (in the balls and bins model). Despite the significant recent advances for constructing ORAM, there is still a significant gap for OPRAM: all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth. Our main result closes the aforementioned gap and provides an optimal OPRAM. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity N can be obliviously simulated in space O(N), incurring only O(log N) blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW (concurrent read, concurrent write) mode and the resulting simulation is in the CRCW mode as well.

We introduce the notion of aSuccinct Parallelizable Argument of Knowledge(SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel timeTwith at mostpprocessors: — The prover’s (parallel) running time is \( T + \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . (In other words, the prover’s running time is essentiallyTfor large computation times!) — The prover uses at most \( p \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) processors. — The communication and verifier complexity are both \( \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is \( T \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) when usingpprocessors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK foranyparallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinctnon-interactiveargument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to \( \mathrm{poly}\hspace{-2.0pt}\log (T\cdot p) \) factors. We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.

Abstract. 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 [Formula: see text], then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if [Formula: see text] and program obfuscation is possible, then one-way functions exist. Our main result is that if [Formula: see text] 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 [Formula: see text]. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the-average [Formula: see text] problems. To get some of our results we need obfuscators for simple programs such as [Formula: see text] circuits.

Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact, even the seemingly weaker notion of differential obliviousness, which intuitively "protects" a single access by guaranteeing that the observed access pattern for every two "neighboring" logical access sequences satisfy (ε,δ)-differential privacy, is subject to a logarithmic lower bound. In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes N transitions, the compiled Turing machine makes O(N ⋅ log log N) transitions in total and the physical head movements sequence satisfies (ε,δ)-differential privacy (for a constant ε and a negligible δ). We additionally show that Ω(log log N) overhead is necessary in a natural range of parameters (and in the balls and bins model). As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on N elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized O(log log N) overhead per operation, while it is known that any oblivious implementation must consume Ω(log N) operations unconditionally even on a RAM. Therefore, we obtain the first unconditional separation between obliviousness and differential obliviousness in the most natural setting of parameters where ε is a constant and δ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.

In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision-resistant hash function exists (which follows from the hardness of problems such as factoring, discrete-log, and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. This is also true for the colorful Ramsey problem where one is looking, say, for a monochromatic triangle. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is that of succinct black-box, where the complexity of an algorithm is measured as a function of the description size of the object in the box (and no limitation on the computation time). In this case, we show that for all TFNP problems there is an efficient algorithm with complexity proportional to the description size of the object in the box times the solution size. However, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property that is hard to test even when one is given the program for computing the graph (under the appropriate assumptions such as hardness of Decisional Diffie-Hellman). The hard property is whether the graph is a two-source extractor.

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where n parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates O(sqrt n) adaptive corruptions. They conjectured that this is optimal for such adversaries. We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message. Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica '89), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP '15).

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k = 2 and there are n parties, there are schemes for sharing an ℓ-bit secret in which the share size of each party is roughly max{ℓ, logn} bits, and this is tight even for secrets of 1 b. In these schemes, the number of parties n must be given in advance to the dealer. In this paper, we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the tthparty arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure and 1-bit secrets where the share size of party t is (k-1)·logt+poly(k)·o(logt). Fork = 2 we observe an equivalence to prefix codes and present matching upper and lower bounds of the form log t + log log t + log log log t + O(1). Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2t-1.

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision resistant hash function exist (which follows from the hardness of problems such as factoring, discrete-log and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is the succinct black-box, where there is a known upper bound on the size of the black-box (but no limit on the computation time). In this case we show that for all TFNP problems there is an upper bound on the number of queries proportional to the description size of the box times the solution size. On the other hand, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property which is hard to test even when one is given the program for computing the graph. The hard property is whether the graph is a two-source extractor.

We give an explicit function $h:\{0,1\}^n \to \{0,1\}$ such that every de Morgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. Our technical contributions include a theorem that shows that the “expected shrinkage” result of H\aastad [SIAM J. Comput., 27 (1998), pp. 48--64] actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), using ideas of Impagliazzo, Meka, and Zuckerman [Proceedings of FOCS, 2012, pp. 111--119].

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information x and Bob gets y, where (x, y) is drawn from a known distribution, and Bob wishes to compute some function g(x, y) (with high probability over (x, y)). In our variant, Alice does not know g, but only knows some function f which is an approximation of g. Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function h that is close to both f and g and then use a protocol for h to compute h(x, y). We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if g has a one-way communication protocol with complexity k in the standard setting, then it has a communication protocol with complexity O(k · (1 + I)) in the uncertain setting, where I denotes the mutual information between x and y. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information I is required. Namely, we construct a class of functions along with a non-product distribution over (x, y) for which the communication complexity is a single bit in the standard setting but at least bits in the uncertain setting.

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, giving near-matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A. A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).

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. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013). 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, STOC 2014). 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 formulas

We give an explicit function h: {0, 1}n→ {0, 1} such that every deMorgan formula of size n3-o(1)/r2agrees with h on at most a fraction of 1/2+2-Ω(r)of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013). Our technical contributions include a theorem that shows that the "expected shrinkage" result of Haastad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of h allows us to simplify a major part of the analysis of Komargodski and Raz1.

We give an explicit function h:{0,1}n->{0,1} such that any deMorgan formula of size O(n2.499) agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). We also show, using the same technique, that any boolean formula of size O(n1.999) over the complete basis, agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). Our construction is based on Andreev's Ω(n2.5-o(1)) formula size lower bound that was proved for the case of exact computation.