In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field \(\mathbb{F}_2\) drawn from a specified distribution. In particular, for any \(d \ge 2\), we design a distribution of degree up to \(d\) polynomials \(\{p_i(x_1,\ldots,x_n)\}_{i\in[m]}\) for \(m \lt n\) over \(\mathbb{F}_2\) for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves \(\{p_i(x_1,\ldots,x_n) = y_i\}_{i\in[m]}\) for a random vector \((y_1,\ldots,y_m)\). On the other hand, while solutions exist with high probability, we conjecture that for constant \(d \gt 2\), it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.

We prove that SVPp is NP-hard to approximate within a factor of 2log1 − ε n, for all constants ε > 0 and p > 2, under standard deterministic Karp reductions. This result is also the first proof that exact SVPp is NP-hard in a finite ℓp norm. Hardness for SVPp with p finite was previously only known if NP ⊈ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVPp is NP-hard to approximate within a small polynomial factor, for all constants p > 2.

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Suppose there exists any set of constants \(\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)\) such that the sub-exponential security of the following assumptions hold: — the Learning With Errors ( \(\mathsf {LWE}\) ) assumption with subexponential modulus-to-noise ratio \(2^{k^\epsilon }\) and noises of magnitude polynomial in k , where k is the dimension of the \(\mathsf {LWE}\) secret, — the Learning Parity with Noise ( \(\mathsf {LPN}\) ) assumption over general prime fields \(\mathbb {Z}_p\) with polynomially many \(\mathsf {LPN}\) samples and error rate \(1/\ell ^\delta\) , where \(\ell\) is the dimension of the \(\mathsf {LPN}\) secret, — the existence of a Boolean Pseudo-Random Generator ( \(\mathsf {PRG}\) ) in \(\mathsf {NC}^0\) with stretch \(n^{1+\tau }\) , where n is the length of the \(\mathsf {PRG}\) seed, — the Decision Linear ( \(\mathsf {DLIN}\) ) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Furthermore, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.

Fabrice Y Harel-Canada, Boran Erol, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Fabrice Y Harel-Canada, Hanyu Zhou, Sreya Muppalla, Zeynep Senahan Yildiz, Miryung Kim, Amit Sahai, Nanyun Peng. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Abstract We investigate algebraic attacks on the Learning Parity with Noise ($\mathsf{LPN}$) problem over large fields in parameter settings relevant to building indistinguishability obfuscation in which the proportion of corrupted equations is inverse-polynomially sparse. Our aim was to obtain a subexponential algorithm using the Macaulay expansion and relinearization. Alas, we did not. Nevertheless, our findings suggest an interesting relation between runtime and the rank of the Macaulay expansion. The runtime of this attack is $O\big(2^{d \log m}\big)$, where $m$ is the number of initial equations and $d$ is the degree of the Macaulay expansion. If the resulting system of equations has sufficiently large rank, we show that solving the $\mathsf{LPN}$ polynomial system requires an $O(\sqrt{m})$ degree expansion, which would imply a subexponential attack. Under the (more widely believed) assumption that the expanded system is semi-regular, however, we show that an $O(m)$ degree expansion is required to recover the secret vector. Since $O(\sqrt{m})$-degree expansions may not have sufficient rank, we propose a randomized algorithm which introduces carefully chosen equations that hold with high probability to increase the rank and improve the likelihood of a successful attack. We highlight the empirical and theoretical challenges in analyzing this approach. Our code is available at www.tinyurl.com/attacklpn.

Abstract A wiretap coding scheme (Wyner in Bell Syst Tech J 54(8):1355–1387, 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel $$\textsf{ChB}$$ ChB , while at the same time hiding m from Eve who receives c over another noisy channel $$\textsf{ChE}$$ ChE . Wiretap coding is clearly impossible when $$\textsf{ChB}$$ ChB is a degraded version of $$\textsf{ChE}$$ ChE , in the sense that the output of $$\textsf{ChB}$$ ChB can be simulated using only the output of $$\textsf{ChE}$$ ChE . A classic work of Csiszár and Korner (IEEE Trans Inf Theory 24(3):339–348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $$(\textsf{ChB},\textsf{ChE})$$ ( ChB , ChE ) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if $$\textsf{ChB}$$ ChB is not a degraded version of $$\textsf{ChE}$$ ChE . Our construction assumes the existence of virtual black-box obfuscation of specific classes of “evasive” functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on $$\textsf{ChB}$$ ChB and not on $$\textsf{ChE}$$ ChE .

In this work, we initiate a new conceptual line of attack on the fundamental question of how to generate hard problems. Motivated by the need for one-way functions in cryptography, we propose an information-theoretic framework to study the question of generating new provably hard one-way functions by composing functions that are easy to invert and evaluate, where each such easy function is modeled as a random oracles paired with another oracle that implements an inverse function.

The existence of “unstructured” hard languages in NP ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NP ∩ coNP relative to a random oracle, a question that remained open ever since. While a hard language in NP ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.

This issue of SICOMP contains ten specially selected papers from STOC 2017, the Forty-ninth Annual ACM Symposium on the Theory of Computing, which was held June 19--23 in Montreal, Canada. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2017 consisted of Nina Balcan, Allan Borodin, Keren Censor-Hillel, Edith Cohen, Artur Czumaj, Yevgeniy Dodis, Andrew Drucker, Nick Harvey, Monika Henzinger, Russell Impagliazzo, Ken-ichi Kawarabayashi, Ravi Kumar, James R. Lee, Katrina Ligett, Aleksander Mądry, Cristopher Moore, Jelani Nelson, Eric Price, Amit Sahai, Jared Saia, Shubhangi Saraf, Alexander Sherstov, Mohit Singh, and Gábor Tardos. The program chair was Valerie King. Included in this issue are the following papers: ``Short Presburger Arithmetic Is Hard," by Danny Nguyen and Igor Pak, proves that the satisfiability of short sentences in Presburger arithmetic with $m+2$ alternating quantifiers is $\Sigma^{{P}}_m$-complete or $\Pi^{{P}}_m$-complete when the first quantifier is $\exists$ or $\forall$, respectively. ``An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy," by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma, gets an explicit bipartite Ramsey graph (or a twosource extractor) for sets of size 2$k$ for $k = O(\log n \log \log n)$, using the currently best explicit nonmalleable extractors. ``Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain," by Jin-Yi Cai and Zhiguo Fu, classifies all counting CSPs over Boolean variables into one of three categories: polynomial-time tractable, \#P-hard for general instances but solvable in polynomial time over planar graphs, and \#P-hard over planar graphs. ``Deciding Parity Games in Quasipolynomial Time," by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan, shows the parameterized parity game, with $n$ nodes and $m$ priorities, is in the class of fixed parameter tractable problems when parameterized over $m$. ``New Hardness Results for Routing on Disjoint Paths," by Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat, proves that node-disjoint paths is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. ``A Weighted Linear Matroid Parity Algorithm," by Satoru Iwata and Yusuke Kobayashi, presents a combinatorial, deterministic, strongly polynomial-time algorithm for the weighted linear matroid parity problem. ``Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace," by William M. Hoza and Chris Umans, shows that $\mathbf{BPL} \subseteq \bigcap_{\alpha > 0} {DSPACE}(\log^{1 + \alpha} n)$, assuming that for every derandomization result for log-space algorithms there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. ``Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs," by Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra, shows that for CSPs, subexponential size LP relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali--Adams LP hierarchy. ``Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model," by Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam, defines a new type of encryption and shows that Yao's garbling scheme, implemented with this encryption mechanism, is secure against adaptive adversaries. ``Geodesic Walks in Polytopes," by Yin Tat Lee and Santosh Vempala, introduces the geodesic walk for sampling Riemannian manifolds and applies it to the problem of generating uniform random points from the interior of polytopes in ${\mathbb{R}}^{n}$ specified by m inequalities; the resulting sampling algorithm for polytopes mixes in $O^{*}(mn^{\frac{3}{4}})$ steps. We thank the authors, the STOC 2017 program committee, the STOC 2017 external reviewers, and the SICOMP referees for all of their hard work. Andy Drucker, Ravi Kumar, Amit Sahai, Mohit Singh, Guest editors

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto 2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:

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.

An affine determinant program ADP: {0,1}^n → {0,1} is specified by a tuple (A,B_1,…,B_n) of square matrices over ?_q and a function Eval: ?_q → {0,1}, and evaluated on x ∈ {0,1}^n by computing Eval(det(A + ∑_{i∈[n]} x_i B_i)). In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation. As a proof-of-concept, we give a candidate ADP-based construction of indistinguishability obfuscation (i?) for all circuits along with a simple witness encryption candidate. We provide cryptanalysis demonstrating that our schemes resist several potential attacks, and leave further cryptanalysis to future work. Lastly, we explore practically feasible applications of our witness encryption candidate, such as public-key encryption with near-optimal key generation.

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifically, letting n denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space (T(n), S(n)) with communication complexity poly(S(n)), verifier runtime n.polylog(T(n))+poly(S(n)), and prover runtime poly(T(n)).

Non-malleable commitments, introduced by Dolev, Dwork and Naor (STOC 1991), are a fundamental cryptographic primitive, and their round complexity has been a subject of great interest. And yet, the goal of achieving non-malleable commitments with only one or two rounds has been elusive. Pass (TCC 2013) captured this difficulty by proving important impossibility results regarding two-round non-malleable commitments. This led to the widespread belief that achieving two-round nonmalleable commitments was impossible from standard assumptions. We show that this belief was false. Indeed, we obtain the following positive results: We construct two-message non-malleable commitments satisfying non-malleability with respect to commitment, based on standard sub-exponential assumptions, namely: sub-exponential one-way permutations, sub-exponential ZAPs, and sub-exponential DDH. Furthermore, our protocol is public-coin.; We obtain two-message private-coin non-malleable commitments with respect to commitment, assuming only sub-exponential DDH or QR or Nth-residuosity.; We bootstrap the above protocols (under the same assumptions) to obtain two round constant boundedconcurrent non-malleable commitments. In the simultaneous message model, we obtain unbounded concurrent non-malleability in two rounds.; In the simultaneous messages model, we obtain oneround non-malleable commitments, with unbounded concurrent security with respect to opening, under standard sub-exponential assumptions.; This implies non-interactive non-malleable commitments with respect to opening, in a restricted model with a broadcast channel, and a-priori bounded polynomially many parties such that every party is aware of every other party in the system. To the best of our knowledge, this is the first protocol to achieve completely non-interactive non-malleability in any plain model setting from standard assumptions.; As an application of this result, in the simultaneous exchange model, we obtain two-round multi-party pseudorandom coin-flipping.; We construct two-message zero-knowledge arguments with super-polynomial strong simulation (SPSS-ZK), which also serve as an important tool for our constructions of non-malleable commitments.; In order to obtain our results, we develop several techniques that may be of independent interest.; We give the first two-round black-box rewinding strategy based on standard sub-exponential assumptions, in the plain model.;- We also give a two-round tag amplification technique for non-malleable commitments, that amplifies a 4-tag scheme to a scheme for all tags, while relying on sub-exponential DDH. This includes a more efficient alternative to the DDN encoding.

Functional encryption provides fine-grained access control for encrypted data, allowing each user to learn only specific functions of the encrypted data. We study the notion of hierarchical functional encryption, which augments functional encryption with delegation capabilities, offering significantly more expressive access control. We present a generic transformation that converts any general-purpose public-key functional encryption scheme into a hierarchical one without relying on any additional assumptions. This significantly refines our understanding of the power of functional encryption, showing that the existence of functional encryption is equivalent to that of its hierarchical generalization. Instantiating our transformation with the existing functional encryption schemes yields a variety of hierarchical schemes offering various trade-offs between their delegation capabilities (i.e., the depth and width of their hierarchical structures) and underlying assumptions. When starting with a scheme secure against an unbounded number of collusions, we can support arbitrary hierarchical structures. In addition, even when starting with schemes that are secure against a bounded number of collusions (which are known to exist under rather minimal assumptions such as the existence of public-key encryption and shallow pseudorandom generators), we can support hierarchical structures of bounded depth and width.

We consider the problem of distributing a computation between two parties, such that any bounded-communication leakage function applied to the local views of the two parties reveals essentially nothing about the input. This problem can be motivated by the goal of outsourcing computations on sensitive data to two servers in the cloud, where both servers can be simultaneously corrupted by viruses that have a limited communication bandwidth. We present a simple and efficient reduction of the above problem to that of constructing parity-resilient circuits, namely circuits that map an encoded input to an encoded output so that the parity of any subset of the wires is essentially independent of the input. We then construct parity-resilient circuits from circuits that are resilient to local leakage, which can in turn be obtained from protocols for secure multiparty computation. Our main reduction builds on a novel generalization of the ε-biased masking lemma that applies to interactive protocols. Applying the above, we obtain two-party protocols with resilience to bounded-communication leakage either in the information-theoretic setting, relying on random oblivious transfer correlations, or in the computational setting, relying on non-committing encryption which can be based on a variety of standard cryptographic assumptions.

We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting. Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well. However, somewhat surprisingly, we show that this barrier breaks down in the setting of two unidirectional messages by the committer (with no message from the receiver), for non-malleability with respect to opening.°Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.°Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.°Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.°Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et al) w.r.t. natural black-box reductions.

We study the cryptographic complexity of two-party differentially-private protocols for a large natural class of boolean functionalities. Information theoretically, McGregor et al. [FOCS 2010] and Goyal et al. [Crypto 2013] demonstrated several functionalities for which the maximal possible accuracy in the distributed setting is significantly lower than that in the client-server setting. Goyal et al. [Crypto 2013] further showed that "highly accurate" protocols in the distributed setting for any non-trivial functionality in fact imply the existence of one-way functions. However, it has remained an open problem to characterize the exact cryptographic complexity of this class. In particular, we know that semi-honest oblivious transfer helps obtain optimally accurate distributed differential privacy. But we do not know whether the reverse is true. We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer (or equivalently secure multi-party computation)? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs. We give a reduction from oblivious transfer to: - Any distributed optimally accurate epsilon-differentially private protocol with epsilon > 0 computing a functionality with a boolean XOR embedded on adjacent inputs. - Any distributed non-optimally accurate epsilon-differentially private protocol with epsilon > 0, for a constant range of non-optimal accuracies and constant range of values of epsilon, computing a functionality with a boolean XOR embedded on adjacent inputs. Enroute to proving these results, we demonstrate a connection between optimally-accurate twoparty differentially-private protocols for functions with a boolean XOR embedded on adjacent inputs, and noisy channels, which were shown by Crépeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.

How much adversarial noise can protocols for interactive communication tolerate? This question was examined by Braverman and Rao (IEEE Trans. Inf. Theory, 2014) for the case of “robust” protocols, where each party sends messages only in fixed and predetermined rounds. We consider a new class of protocols for interactive communication, which we call adaptive protocols. Such protocols adapt structurally to the noise induced by the channel in the sense that both the order of speaking, and the length of the protocol may vary depending on observed noise. We define models that capture adaptive protocols and study upper and lower bounds on the permissible noise rate in these models. When the length of the protocol may adaptively change according to the noise, we demonstrate a protocol that tolerates noise rates up to 1/3. When the order of speaking may adaptively change as well, we demonstrate a protocol that tolerates noise rates up to 2/3. Hence, adaptivity circumvents an impossibility result of 1/4 on the fraction of tolerable noise (Braverman and Rao, 2014).

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits $C_0$ and $C_1$ of similar size, the obfuscations of $C_0$ and $C_1$ should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs $x$ and keys are issued for circuits $C$. Using the key $\mathrm{SK}_C$ to decrypt a ciphertext $\mathrm{CT}_x={\sf Enc}(x)$ yields the value $C(x)$ but does not reveal anything else about $x$. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: (1) We describe a candidate construction for indistinguishability obfuscation for $\mathbf{NC}^1$ circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call multilinear jigsaw puzzles. (2) We show how to use indistinguishability obfuscation for $\mathbf{NC}^1$ together with fully homomorphic encryption (with decryption in $\mathbf{NC}^1$) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and noninteractive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

We revisit the question of constructing secure general-purpose indistinguishability obfuscation, with a security reduction based on explicit computational assumptions over multilinear maps. Previous to our work, such reductions were only known to exist based on meta-assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself. In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

Consider two parties, Alice and Bob, who hold private inputs x and y, and wish to compute a function f (x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f (x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f (x, y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties' inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and errorresilience are contradictory goals. In particular, we show that for every constant c > 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.

In this work, we seek to optimize the efficiency of secure general-purpose obfuscation schemes. We focus on the problem of optimizing the obfuscation of Boolean formulas and branching programs -- this corresponds to optimizing the "core obfuscator" from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, where efficiency in proposed instantiations is closely tied to the maximum number of "levels" of multilinearity required.

Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors.

An oblivious transfer (OT) channel takes as input a pair of bits (s0, s1) from the sender and delivers (c, sc) to the receiver, where c ∈ {0, 1} is chosen uniformly at random. A secure implementation of such a channel hides c from the sender and s1-cfrom the receiver. These secrecy properties make OT channels very useful for cryptography; for example, they can be used to perform general secure multi-party computation.

We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit. This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation.

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, Dwork, Naor, and Ostrovsky 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 pre-planning by the party that must later issue a denial.

MOTIVATION: High-throughput sequencing technologies have impacted many areas of genetic research. One such area is the identification of relatives from genetic data. The standard approach for the identification of genetic relatives collects the genomic data of all individuals and stores it in a database. Then, each pair of individuals is compared to detect the set of genetic relatives, and the matched individuals are informed. The main drawback of this approach is the requirement of sharing your genetic data with a trusted third party to perform the relatedness test. RESULTS: In this work, we propose a secure protocol to detect the genetic relatives from sequencing data while not exposing any information about their genomes. We assume that individuals have access to their genome sequences but do not want to share their genomes with anyone else. Unlike previous approaches, our approach uses both common and rare variants which provide the ability to detect much more distant relationships securely. We use a simulated data generated from the 1000 genomes data and illustrate that we can easily detect up to fifth degree cousins which was not possible using the existing methods. We also show in the 1000 genomes data with cryptic relationships that our method can detect these individuals. AVAILABILITY: The software is freely available for download at http://genetics.cs.ucla.edu/crypto/.

We revisit the problem of reliable interactive communication over a noisy channel and obtain the first fully (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memoryless noisy channel with constant capacity and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman (1993), our simulation uses a tree-code, yet as opposed to the nonefficient construction of absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an efficient emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore, we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits C0and C1of similar size, the obfuscations of C0and C1should be computationally indistinguishable. In functional encryption, cipher texts encrypt inputs x and keys are issued for circuits C. Using the key SKCto decrypt a cipher text CTx= Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: - (1) We describe a candidate construction for indistinguishability obfuscation for NC1circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles. (2) We show how to use indistinguishability obfuscation for NC1together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct cipher texts, which enables several other applications.

We put forth the concept of witness encryption. A witness encryption scheme is defined for an NP language L (with corresponding witness relation R). In such a scheme, a user can encrypt a message M to a particular problem instance x to produce a ciphertext. A recipient of a ciphertext is able to decrypt the message if x is in the language and the recipient knows a witness w where R(x,w) holds. However, if x is not in the language, then no polynomial-time attacker can distinguish between encryptions of any two equal length messages. We emphasize that the encrypter himself may have no idea whether $x$ is actually in the language. Our contributions in this paper are threefold. First, we introduce and formally define witness encryption. Second, we show how to build several cryptographic primitives from witness encryption. Finally, we give a candidate construction based on the NP-complete Exact Cover problem and Garg, Gentry, and Halevi's recent construction of "approximate" multilinear maps.

One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against “honest-but-curious” participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design, based on zero-knowledge protocols based on computational hardness assumptions. In this work, we describe a new general paradigm/protocol compiler for secure protocol design known as the IPS compiler, that departs considerably from the GMW framework, and provides a method for obtaining efficient protocols with information-theoretic security guarantees in settings where appropriate channels exist. This new approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, the new approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting - where the majority of participants are completely honest (such multi-party protocols can exist with information-theoretic security guarantees without assuming any special channels). The IPS paradigm yields protocols that rely on Oblivious Transfer channels (OT) as a building block. This offers a number of advantages in generality and efficiency. In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, the IPS paradigm is able to treat all of its building blocks as “black boxes”. This allows improvement over previous results in the area of secure computation. In particular, the IPS compiler yields conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT and other noisy channels; more efficient protocols for generating a large number of OTs using a small number of OTs; and secure and efficient protocols which only make a blackbox use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before.

Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \\compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is \\unintel-ligible " in some sense. Obfuscators, if they exist, would have a wide vari-ety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice’s theorem. Most of these applications are based on an interpretation of the \\unintelligibility " condition in obfuscation as mean-ing that O(P) is a \\virtual black box, " in the sense that anything one can eciently compute given O(P), one could also eciently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above in-tuition, obfuscation is impossible. We prove this by constructing a family of functions F that are inherently unobfuscatable in the following sense:

Noninteractive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including public-key encryption secure against chosen ciphertext attack, digital signatures, and various other cryptographic protocols. We introduce new techniques for constructing NIZK proofs based on groups with a bilinear map. Compared to previous constructions of NIZK proofs, our techniques yield dramatic reduction in the length of the common reference string (proportional to security parameter) and the size of the proofs (proportional to security parameter times the circuit size). Our novel techniques allow us to answer several long-standing open questions in the theory of noninteractive proofs. We construct the first perfect NIZK argument system for all NP. We construct the first universally composable NIZK argument for all NP in the presence of an adaptive adversary. We construct a non-interactive zap for all NP, which is the first that is based on a standard cryptographic security assumption.

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memory less noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman [Schulman 1993] our simulation uses a tree-code, yet as opposed to the non-constructive absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an explicit emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.

In [8,9] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption.

In this work, we put forward the notion of Worry-Free Encryption. This allows Alice to encrypt confidential information under Bob's public key and send it to him, without having to worry about whether Bob has the authority to actually access this information. This is done by encrypting the message under a hidden access policy that only allows Bob to decrypt if his credentials satisfy the policy. Our notion can be seen as a functional encryption scheme but in a public-key setting. As such, we are able to insist that even if the credential authority is corrupted, it should not be able to compromise the security of any honest user.

Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.

In this work, we design a method for creating public key broadcast encryption systems. Our main technical innovation is based on a new "two equation" technique for revoking users. This technique results in two key contributions: First, our new scheme has ciphertext size overhead O(r), where r is the number of revoked users, and the size of public and private keys is only a constant number of group elements from an elliptic-curve group of prime order. In addition, the public key allows us to encrypt to an unbounded number of users. Our system is the first to achieve such parameters. We give two versions of our scheme: a simpler version which we prove to be selectively secure in the standard model under a new, but non-interactive assumption, and another version that employs the new dual system encryption technique of Waters to obtain adaptive security under the d-BDH and decisional Linear assumptions. Second, we show that our techniques can be used to realize Attribute-Based Encryption (ABE) systems with nonmonotonic access formulas, where our key storage is significantly more efficient than previous solutions. This result is also proven selectively secure in the standard model under our new non-interactive assumption.

Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

In keeping with an annual tradition, this issue of the SIAM Journal on Computing contains extended versions of selected papers from the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006), which was held May 21–23, 2006, in Seattle, Washington. The conference program included 78 papers selected by a program committee consisting of Scott Aaronson, Eli Ben-Sasson, Allan Borodin, David Eppstein, Sudipto Guha, Piotr Indyk, Jon Kleinberg, Tal Malkin, Frank McSherry, Dieter van Melkebeek, Michael Mitzenmacher, Assaf Naor, Rafail Ostrovsky, Toniann Pitassi, R. Ravi, Dana Ron, Amin Saberi, Amit Sahai, Rocco Servedio, and Madhu Sudan. Preliminary versions of these papers appeared in the conference proceedings published by ACM Press. This special issue contains 11 of these papers; the authors were invited by the program committee to prepare extended versions of their papers, which were then refereed according to the journal's high standards. In the process, these papers were considerably revised and expanded. Collectively, they represent some of the recent highlights from a broad cross-section of active areas within theoretical computer science, including randomness in computation, approximation algorithms and inapproximability, proof complexity, property testing, constraint satisfaction, quantum computing, algorithmic game theory, and high-dimensional geometric algorithms. In total, the six of us listed below handled the editing of these papers. We would like to thank all of the referees and the full program committee for their contributions to the preparation of this special issue.

A zero-knowledge proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows n mutually suspicious players to jointly compute a function of their local inputs without revealing to any t corrupted players additional information beyond the output of the function. We present a new general connection between these two fundamental notions. Specifically, we present a general construction of a zero-knowledge proof for an NP relation $R(x,w)$, which makes only a black-box use of any secure protocol for a related multiparty functionality f. The latter protocol is required only to be secure against a small number of “honest but curious” players. We also present a variant of the basic construction that can leverage security against a large number of malicious players to obtain better efficiency. As an application, one can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming that one-way functions exist, we get the following types of zero-knowledge proof protocols: (1) Approaching the witness length. If C has constant depth over $\wedge,\vee,\oplus,\neg$ gates of unbounded fan-in, we get a zero-knowledge proof protocol with communication complexity $m\cdot{poly}(k)\cdot{polylog}(s)$, where k is a security parameter. (2) “Constant-rate” zero-knowledge. For an arbitrary circuit C of size s and a bounded fan-in, we get a zero-knowledge protocol with communication complexity $O(s)+{poly}(k,\log s)$. Thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. This improves over the $O(ks)$ complexity of the best previous protocols.

A well-known concern in the setting of identity based encryption is that the PKG is all powerful and has to be completely trusted. To mitigate this problem, the notion of Accountable Authority Identity-Based Encryption (A-IBE) was recently introduced by Goyal. Goyal provided constructions to realize the notion of A-IBE only in the white box and weak black box models. However, the security guarantees provided by these models fall short of those required in practice.

Non-interactive zero-knowledge proofs and non-interactive 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 non-interactive 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 non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, 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 non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.

Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing basic cryptographic primitives, such as encryption, authentication, signatures, and secure two-party computation, while incurring only a constant computational overhead compared to insecure implementations of the same tasks. Here we make the usual security requirement that the advantage of any polynomial-time attacker must be negligible in the input length.

In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space. The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two finite metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2√2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the “forbidden pattern” based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4√3 (≃ 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.

We construct an Attribute-Based Encryption (ABE) scheme that allows a user's private key to be expressed in terms of any access formula over attributes. Previous ABE schemes were limited to expressing only monotonic access structures. We provide a proof of security for our scheme based on the Decisional Bilinear Diffie-Hellman (BDH) assumption. Furthermore, the performance of our new scheme compares favorably with existing, less-expressive schemes.

In STOC'05, Aim, Hopper and Longford introduced the notion of covert computation. A covert computation protocol is one in which parties am run a protocol without knowing if other parties ore also participating in the protocol or not. At the end of the protocol, if all parties participated in the protocol and if the function output is favorable to all parties, then the output is revealed. Ahn et al. constructed a protocol for covert two-partv computation in the random oracle model In this paper, we offer a construction for covert multiparty computation. Our construction is in the standard model and does not require random oracles. In order to achieve this goal, we introduce a number of new techniques. Central to our work is the development of "zero-knowledge proofs to garbled circuits," which we believe could be of independent interest. Along the way, we also develop a definition of covert computation as per the Ideal/Real model simulation paradigm.

In several distributed systems a user should only be able to access data if a user posses a certain set of credentials or attributes. Currently, the only method for enforcing such policies is to employ a trusted server to store the data and mediate access control. However, if any server storing the data is compromised, then the confidentiality of the data will be compromised. In this paper we present a system for realizing complex access control on encrypted data that we call ciphertext-policy attribute-based encryption. By using our techniques encrypted data can be kept confidential even if the storage server is untrusted; moreover, our methods are secure against collusion attacks. Previous attribute-based encryption systems used attributes to describe the encrypted data and built policies into user's keys; while in our system attributes are used to describe a user's credentials, and a party encrypting data determines a policy for who can decrypt. Thus, our methods are conceptually closer to traditional access control methods such as role-based access control (RBAC). In addition, we provide an implementation of our system and give performance measurements.

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.

As more sensitive data is shared and stored by third-party sites on the Internet, there will be a need to encrypt data stored at these sites. One drawback of encrypting data, is that it can be selectively shared only at a coarse-grained level (i.e., giving another party your private key). We develop a new cryptosystem for fine-grained sharing of encrypted data that we call Key-Policy Attribute-Based Encryption (KP-ABE). In our cryptosystem, ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. We demonstrate the applicability of our construction to sharing of audit-log information and broadcast encryption. Our construction supports delegation of private keys which subsumesHierarchical Identity-Based Encryption (HIBE).

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. middot Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and general multi-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted. middot Efficiency. We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to both communication and computation

We construct a secure protocol for any multiparty functionality that remains secure (under a relaxed definition of security introduced by Prabhakaran and Sahai (STOC '04)) when executed concurrently with multiple copies of itself and other protocols, without any assumptions on existence of trusted parties, common reference string, honest majority or synchronicity of the network. The relaxation of security is obtained by allowing the ideal-model simulator to run in quasipolynomial (as opposed to polynomial) time. Quasipolynomial simulation suffices to ensure security for most applications of multiparty computation. Furthermore, Lindell (FOCS '03, TCC' 04) recently showed that such a protocol is impossible to obtain under the more standard definition of polynomial-time simulation by an ideal adversary. Our construction is the first such protocol under reasonably standard cryptographic assumptions (i.e., existence of a hash function collection that is collision resistent with respect to circuits of subexponential size, and existence of trapdoor permutations which are secure with respect to circuits of quasi-polynomial size). We introduce a new technique: "protocol condensing". That is, taking a protocol that has strong security properties but requires super-polynomial communication and computation, and then transforming it into a protocol with polynomial communication and computation, that still inherits the strong security properties of the original protocol. Our result is obtained by combining this technique with previous techniques of Canetti, Lindell, Ostrovsky, and Sahai (STOC '02) and Pass (STOC '04).

This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string /spl sigma/? This is a natural question about a fundamental object connected to many fields such as data compression, Kolmogorov complexity, pattern identification, and addition chains. Due to the problem's inherent complexity, our objective is to find an approximation algorithm which finds a small grammar for the input string. We focus attention on the approximation ratio of the algorithm (and implicitly, the worst case behavior) to establish provable performance guarantees and to address shortcomings in the classical measure of redundancy in the literature. Our first results are concern the hardness of approximating the smallest grammar problem. Most notably, we show that every efficient algorithm for the smallest grammar problem has approximation ratio at least 8569/8568 unless P=NP. We then bound approximation ratios for several of the best known grammar-based compression algorithms, including LZ78, B ISECTION, SEQUENTIAL, LONGEST MATCH, GREEDY, and RE-PAIR. Among these, the best upper bound we show is O(n/sup 1/2/). We finish by presenting two novel algorithms with exponentially better ratios of O(log/sup 3/n) and O(log(n/m/sup */)), where m/sup */ is the size of the smallest grammar for that input. The latter algorithm highlights a connection between grammar-based compression and LZ77.

We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following: (1) certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, non-interactive zero-knowledge, and secure two-party computation for any non-trivial junction are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any un-proven assumption. (2) On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. Batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes. We initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. We also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (PIR) and related cryptographic protocols.

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto . In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (α, β) timing constraint : for any two processors P 1 and P 2 , if P 1 measures α elapsed time on its local clock and P 2 measures β elapsed time on its local clock, and P 2 starts after P 1 does, then P 2 will finish after P 1 does. We show that if the adversary is constrained by an (α, β) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP . We also address the more specific problem of Deniable Authentication , for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing , that is, in the standard model.

An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by means of a clock routing tree rooted at a global clock source. The difference in length between the longest and shortest root-leaf path is called the skew of the tree. The problem is to construct a clock tree with zero skew (to achieve synchronicity) and minimal sum of edge lengths (so that circuit area and clock tree capacitance are minimized). We give the first constant-factor approximation algorithms for this problem and its variants that arise in the VLSI context. For the zero skew problem in general metric spaces, we give an approximation algorithm with a performance guarantee of 2e. For the L 1 version on the plane, we give an (8/ln 2)-approximation algorithm.

We describe a new method for protecting the anonymity of message receivers in an untrusted network. Surprisingly, existing methods fail to provide the required level of anonymity for receivers (although those methods do protect sender anonymity). Our method relies on the use of multicast, along with a novel cryptographic primitive that we call an Incomparable Public Key cryptosystem, which allows a receiver to efficiently create many anonymous "identities" for itself without divulging that these separate "identities" actually refer to the same receiver, and without increasing the receiver's workload as the number of identities increases. We describe the details of our method, along with a prototype implementation.

We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge .We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as:---A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2).---Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Hεstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement.---Strong closure properties of SZK that amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK.---New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.---Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations that "polarize" and "reverse" the statistical relationship between a pair of distributions.

The Johnson-Lindenstrauss lemma shows that any set of n points in Euclidean space can be mapped linearly down to O((log n)//spl epsi//sup 2/) dimensions such that all pairwise distances are distorted by at most 1+/spl epsi/. We study the basic question of whether there exists an analogue of the Johnson-Lindenstrauss lemma for the /spl lscr//sub 1/ norm? Note that Johnson-Lindenstrauss lemma gives a linear embedding which is independent of the point set. For the /spl lscr//sub 1/ norm, we show that one cannot hope to use linear embeddings as a dimensionality reduction tool for general point sets, even if the linear embedding is chosen as a function of the given point set. In particular, we construct a set of O(n) points in /spl lscr//sub 1//sup n/ such that any linear embedding into /spl lscr//sub 1//sup d/ must incur a distortion of /spl Omega//spl radic/(n/d). This bound is tight up to a log n factor. We then initiate a systematic study of general classes of /spl lscr//sub 1/ embeddable metrics that admit low dimensional, small distortion embeddings. In particular, we show dimensionality reduction theorems for tree metrics, circular-decomposable metrics, and metrics supported on K/sub 2,3/-free graphs, giving embeddings into /spl lscr//sub 1//sup O(log(2) n)/ with constant distortion. Finally, we also present lower bounds on dimension reduction techniques for other /spl lscr//sub p/ norms. Our work suggests that the notion of a stretch-limited embedding, where no distance is stretched by more than a factor d in any dimension, is important to the study of dimension reduction for /spl lscr//sub 1/. We use such stretch limited embeddings as a tool for proving lower bounds for dimension reduction and also as an algorithmic tool for proving positive results.

We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.

We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction.The smallest grammar is known to be hard to approximate to within a constant factor, and an o(logn/log logn) approximation would require progress on a long-standing algebraic problem [10]. Previously, the best proved approximation ratio was O(n1/2) for the Bisection algorithm [8]. Our main result is an exponential improvement of this ratio; we give an O(log (n/g*)) approximation algorithm, where g* is the size of the smallest grammar.We then consider other computable variants of Kolomogorov complexity. In particular we give an O(log2 n) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. We also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.

Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of multidimensional objects, the goal is to select a subset K of relevant dimensions (or features) such that some desired property /spl Pi/ holds for the set S restricted to K. Depending on /spl Pi/, the goal could be to either maximize or minimize the size of the subset K. Several well-studied feature selection problems can be cast in this form. We study the problems in this class derived from several natural and interesting properties /spl Pi/, including variants of the classical p-center problem as well as problems akin to determining the VC-dimension of a set system. Our main contribution is a theoretical framework for studying combinatorial feature selection, providing (in most cases essentially tight) approximation algorithms and hardness results for several instances of these problems.

Given n relatively prime integers p/sub 1/, where m/sub i/=m(mod p/sub i/). The soft-decision decoding problem for the Chinese remainder code is given as input a vector of residues r/spl I.oarr/=(r/sub 1/,...,r/sub n/), a vector of weights, and an agreement parameter t. The goal is to find all messages m /spl isin/ M such that the weighted agreement between the encoding of m and r/spl I.oarr/(i.e., /spl Sigma//sub i/ w/sub i/ summed over all i such that r/sub i/=m(mod pi)) is at least t. Here we give a new algorithm for solving the soft-decision problem for the CRT code that works provided the agreement parameter t is sufficiently large. We derive our algorithm by digging deeper into the algebra underlying the error-correcting algorithms and unveiling an "ideal"-theoretic view of decoding. When all weights are equal to 1, we obtain the more commonly studied "list decoding" problem. List decoding algorithms for the Chinese Remainder Code were given recently by O. Goldreich et al. (1999), and improved by D. Boneh. Their algorithms work for t/spl ges//spl radic/(2knlogp/sub n//logp1) and t/spl ges//spl radic/(knlogp/sub n//logp/sub 1/), respectively. We improve upon the algorithms above by using our soft-decision decoding algorithm with a non-trivial choice of weights, solve the list decoding problem provided t/spl ges//spl radic/(k(n+/spl epsi/)), for arbitrarily small /spl epsi//spl ges/0.

We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest "proof" for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework, constructing a set of prices for any AND/OR tree that satisfies a very strong type of equilibrium property.

We focus on methods to solve multiclass learning problems by using only simple and efficient binary learners.We investigate the approach of Dietterich and Bakiri [2] based on error-correcting codes (which we call ECC).We distill ermr COTrelation as one of the key parameters influencing the performance of the ECC approach, and prove upper and lower bounds on the training error of the final hypothesis in terms of the error-correlation between the various binary hypotheses.Boosting is a powerful and well-studied learning technique that appears to annul error correlation disadvantages by cleverly weighting training examples and hypotheses.An interesting algorithm called ADABOOST.OC [12] combines boosting with the ECC approach and gives an algorithm that has the performance advantages of boosting and at the same time relies only on simple binary weak leamers.We propose a variant of this algorithm, which we call ADABoosT.ECC, that, by using a different weighting of the votes of the weak hypotheses, is able to improve on the performance of ADA-BoosT.OC, both theoretically and experimentally, and in addition is arguably a more direct reduction of multiclass learning to binary learning problems than previous multiclass boosting algorithms.

We introduce the notion of non-malleable non-interactive zero-knowledge (NIZK) proof systems. We show how to transform any ordinary NIZK proof system into one that has strong non-malleability properties. We then show that the elegant encryption scheme of Naor and Yung (1990) can be made secure against the strongest form of chosen-ciphertext attack by using a non-malleable NIZK proof instead of a standard NIZK proof. Our encryption scheme is simple to describe and works in the standard cryptographic model under, general assumptions. The encryption scheme can be realized assuming the existence of trapdoor permutations.

Article The power of a pebble: exploring and mapping directed graphs Share on Authors: Michael A. Bender Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA Division of Engineering and Applied Sciences, Harvard University, Cambridge, MAView Profile , Antonio Fernández Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MIT Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MITView Profile , Dana Ron Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Amit Sahai Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Salil Vadhan Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 269–278https://doi.org/10.1145/276698.276759Online:23 May 1998Publication History 103citation603DownloadsMetricsTotal Citations103Total Downloads603Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Concurrent executions of a zero-knowledge protocol by a ainSle prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto; for example, in the case of zero-knowledge interactive proofs or arguments, the interactions remain proofs but may fail to remain zero-ltnowlcd~e, This paper addresses the problem of achieving concurrent zero-knowledge,We introduce timing in order to obtain zero-knowledge in concurrent executions.We assume that the adversary is conntrained in its control over processors' clocks by what we call an (cr,j+constroint for some o < p: for any two processors Pr and Pa, if A measures (Y elapsed time on its local clock nnd Pz measures /3 elapsed time on its local clock, and Pz atarts ajtcr PI does, then P2 will finish after PI does.We obtain four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP.We also address the more apccific problem of Deniable Authentication, for which we propose efilcicnt solutions.

We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof systemwhich is statistical zero-knowledgewith respect to any verifier. This is done by limiting the behavior of potentially cheating verifiers, without using computational assumptions or even referring to the complexity of such verifier strategies. (Previous transformations have either relied on computational assumptions or were applicable only to constant-round public-coin proof systems.) Our transformation also applies to public-coin (aka Arthur-Merlin) computational zero-knowledge proofs: We transform any ArthurMerlin proof system which is computational zero-knowledge with respect to the honest-verifier, into an Arthur-Merlin proof system which is computational zero-knowledge with respect to any probabilistic polynomial-time verifier. A crucial ingredient in our analysis is a new lemma regarding 2-universal hashing functions. 1 Introduction Zer...

We present a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge. From this theorem and its proof we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions.

If disks are moved so that each center-center distance does not increase, must the area of their union also be nonincreasing?We show that the answer is yes, assuming that there is a continuous motion such that each center-center distance is a nonincreaaing function of time.This generalizes a previous result on unit disks.Our proof relies on a recent construction of Edelsbrunner and on new isoperimetric inequalities of independent int crest.We go on to show analogous results for the intersection and for holes between disks.