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.

Abstract. Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [C. Gentry, STOC ’09, ACM, New York, 2009, pp. 169–178; Z. Brakerski and V. Vaikuntanathan, FOCS ’11, IEEE Computer Society, Los Alamitos, CA, 2011, pp. 97–106], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [S. Gorbunov, V. Vaikuntanathan, and H. Wee, STOC ’13, ACM, New York, 2013, pp. 545–554; D. Boneh et al., Eurocrypt ’14, Springer, Berlin, 2014, pp. 533–556], only accommodate circuits up to a predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size; based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [H. Wee, Eurocrypt ’22, Springer, Cham, Switzerland, 2022, pp. 217–241; R. Tsabary, Crypto ’22, Springer, Cham, Switzerland, 2022, pp. 535–559], we construct full-fledged ABE and predicate encryption (PE) schemes for circuits of unbounded depth and size. Our LFE, 1-key FE, and reusable garbling schemes achieve almost optimal succinctness (up to polynomial factors in the security parameter). Their ciphertexts and input encodings have sizes linear in the input length, while function digest, secret keys, and garbled circuits have constant sizes independent of circuit parameters (for Boolean outputs). In fact, this gives the first constant-size garbled circuits without relying on indistinguishability obfuscation. Our ABE and PE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant size.

Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $\left(m_{1}, \ldots, m_{n}\right)$ and their tags $\left(\sigma_{1}, \ldots, \sigma_{n}\right)$, anyone can evaluate a circuit C on the data and tags to produce a succinct tag authenticating the output $C\left(m_{1}, \ldots, m_{n}\right)$. Importantly, tags remain succinct-of size polynomial in the security parameter $\lambda$-regardless of the size of C. This work introduces an enhanced variant of HMACs called algebraic HMAC (aHMAC), in which all tags (input and output) take the form $\vec{\Delta} \cdot m+\vec{K}$, as in standard information-theoretic MACs. We construct an aHMAC from group-based assumptions, including variants of the DDH and DCR assumptions, and use it to obtain group-based constructions of several cryptographic primitives:•Succinct CDS for circuits. For any $P:[N]^{k} \rightarrow[N]$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with $\operatorname{poly}(\lambda, k, \log N)$ communication.•Succinct PSM for simple programs. For any $P:[N]^{k} \rightarrow[N]$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with $\operatorname{poly}(\lambda, k, \log N)$ communication.•Constrained PRFs for circuits. We obtain the first groupbased constrained pseudorandom functions for general circuits, improving over a previous construction for $\mathrm{NC}^{1}$ circuits.Prior to our work, these applications could only be obtained from lattice assumptions or indistinguishability obfuscation.

The random oracle model (ROM) allows us to opti-mistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO '07] proposed the auxiliary-input random oracle model (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle. Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting, where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh. In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve$2^{\lambda}$security while having sublinear$\mathrm{o}(\lambda)$evaluation time.

We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability. Adopting this perspective leads us naturally not only to our graph theoretic results, but also to new, more efficient algorithms for multicalibration in certain parameter regimes and a novel proof of a hardcore lemma for real-valued functions.

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, FOCS ’10; Brakerski-Vaikuntanathan, STOC ’11], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov-Vaikuntanathan-Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to all predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. Intriguingly, for over a decade, it has remained unclear whether the circular security assumptions empowering FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: •Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.•Based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct a full-fledged ABE scheme for circuits of unbounded depth and size. Our constructions eliminate the multiplicative overheads polynomial in depth from previous constructions. Our LFE, 1key FE, and reusable garbling schemes achieve almost optimal succinctness. Their ciphertexts and input encodings are proportional in length to the input, while function digest, secret keys, and garbled circuits maintain a constant size independent of circuit parameters. Our ABE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.

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 the subexponential hardness of three well-founded assumptions. We prove the following. Theorem (Informal) Assume sub-exponential hardness for the following: - the Learning Parity with Noise (LPN) assumption over general prime fields 𝔽_p with polynomially many LPN samples and error rate 1/k^δ, where k is the dimension of the LPN secret, and δ > 0 is any constant; - the existence of a Boolean Pseudo-Random Generator (PRG) in NC⁰ with stretch n^(1+τ), where n is the length of the PRG seed, and τ > 0 is any constant; - the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exist. As a corollary, all cryptographic goals that can be achieved using indistinguishability obfuscation can now be achieved assuming the above three assumptions. This includes fully homomorphic encryption, functional encryption, multiparty non-interactive key-exchange, succinct garbled random access machine, and many others. This is joint work with Aayush Jain (UCLA and NTT Research) and Amit Sahai (UCLA).

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:

Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, their round-complexity has been extensively studied, leading up to constant-round protocols based on one-way functions (OWFs), and three-round protocols based on sub-exponential OWFs, and standard polynomial-time hardness assumptions such as decisional Diffie--Hellman (DDH) and ZAPs (i.e., two-round witness-indistinguishable proofs). But constructions of two-round, or non-interactive, non-malleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of two-round concurrent non-malleable commitments based on the following four primitives (all with sub-exponential security): (1) non-interactive commitments, (2) ZAPs (i.e., 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a “weak” time-lock puzzle. Primitives (1), (2), and (3) can be based on, e.g., the discrete log and the RSA assumption. Time-lock puzzles---puzzles that can be solved by “brute-force” in time $2^t$, but cannot be solved significantly faster even using parallel computers---were proposed by Rivest, Shamir, and Wagner in 1996 and have been extensively studied since. We additionally obtain a non-interactive (i.e., one-message) version of our protocol satisfying concurrent non-malleability w.r.t. uniform attackers and show that our non-malleable commitments satisfy an even stronger notion of chosen commitment attack security.

Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open. We initiate a systematic study of HSS, making the following contributions. - A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework. - Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer. - Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.

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

Non-malleable commitments are a fundamental cryptographic tool for preventing against (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, the round-complexity of non-malleable commitments has been extensively studied, leading up to constant-round concurrent non-malleable commitments based only on one-way functions, and even 3-round concurrent non-malleable commitments based on subexponential one-way functions. But constructions of two-round, or non-interactive, nonmalleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility, using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of a two-round concurrent non-malleable commitment based on subexponential “standard-type” assumptions-notably, assuming the existence of the following primitives (all with subexponential security): (1) non-interactive commitments, (2) ZAPs (i.e., 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a “weak” time-lock puzzle. Primitives (1),(2),(3) can be based on e.g., the discrete log assumption and the RSA assumption. Time-lock puzzles-puzzles that can be solved by “brute-force” in time 2t, but cannot be solved significantly faster even using parallel computers-were proposed by Rivest, Shamir, and Wagner in 1996, and have been quite extensively studied since; the most popular instantiation relies on the assumption that 2t repeated squarings mod N = pq require “roughly” 2t parallel time. Our notion of a “weak” time-lock puzzle, requires only that the puzzle cannot be solved in parallel time 2tϵ(and thus we only need to rely on the relatively mild assumption that there are no huge improvements in the parallel complexity of repeated squaring algorithms). We additionally show that if replacing assumption (2) for a non-interactive witness indistinguishable proof (NIWI), and (3) for a uniform collision-resistant hash function, then a non-interactive (i.e., one-message) version of our protocol satisfies concurrent non-malleability w.r.t. uniform attackers.

This demonstration introduces the database community to state-of-the-art cryptographic methods that ensure efficient oblivious access to cloud data. In particular, we explore oblivious storage systems which hide both the content of data and data access patterns from an untrusted cloud provider. The demo considers the popular and realistic setting where multiple users from a trusted group asynchronously access and edit potentially overlapping data sets through a trusted proxy. We present a detailed implementation of TaoStore (Sahin et al., S&P 2016), a new tree-based ORAM scheme that processes client requests concurrently and asynchronously in a non-blocking fashion, resulting in substantial gains in throughput, simplicity, and flexibility over previous systems. The demo is presented in the context of a pedagogical game, Guess the Access, which allows participants to play as an adversary trying to guess queries against TaoStore or ObliviStore (Stefanov and Shi, S&P 2013), a recent oblivious storage system which has been shown to leak access patterns. The proposed game will highlight the subtleties and intricacies that underlie the cryptographic methods used to design oblivious storage systems.

All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014 and Lin, EUROCRYPT 2016), or polynomial families of assumptions on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014). We present a new construction of IO, with a security reduction based on two assumptions: (a) a DDH-like assumption - called the sSXDH assumption - on constant degree graded encodings, and (b) the existence of polynomial-stretch pseudorandom generators (PRG) in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose indistinguishability obfuscation.

We consider oblivious storage systems hiding both the contents of the data as well as access patterns from an untrusted cloud provider. We target a scenario where multiple users from a trusted group (e.g., corporate employees) asynchronously access and edit potentially overlapping data sets through a trusted proxy mediating client-cloud communication. The main contribution of our paper is twofold. Foremost, we initiate the first formal study of asynchronicity in oblivious storage systems. We provide security definitions for scenarios where both client requests and network communication are asynchronous (and in fact, even adversarially scheduled). While security issues in ObliviStore (Stefanov and Shi, S&P 2013) have recently been surfaced, our treatment shows that also CURIOUS (Bindschaedler at al., CCS 2015), proposed with the exact goal of preventing these attacks, is insecure under asynchronous scheduling of network communication. Second, we develop and evaluate a new oblivious storage system, called Tree-based Asynchronous Oblivious Store, or TaoStore for short, which we prove secure in asynchronous environments. TaoStore is built on top of a new tree-based ORAM scheme that processes client requests concurrently and asynchronously in a non-blocking fashion. This results in a substantial gain in throughput, simplicity, and flexibility over previous systems.

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

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested in settings where significant computational gain can be made in solving a single primary instance by having access to additional auxiliary instances which are correlated to the primary instance via the solution space.

A randomized encoding allows to express a "complex" computation, given by a function f and input x, by a "simple to compute" randomized representation f(x) whose distribution encodes f(x), while revealing nothing else regarding f and x. Existing randomized encodings, geared mostly to allow encoding with low parallel-complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: the time required to encode. We construct succinct randomized encodings where the time to encode a computation, given by a program Π and input x, is essentially independent of Π's time complexity, and only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of (Π,x), and is based on indistinguishability obfuscation for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps.

We show unconditionally that the existence of commitment schemes implies the existence of constant-round nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent nonmalleability and robustness. As a corollary, we establish that constant-round nonmalleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multiparty computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

An important security concern for crypto-graphic protocols is the extent to which they adversely affect the security of the systems in which they run. In particular, can we rule out the possibility that introducing a new protocol to a system might, as a "side effect", break the security of unsuspecting protocols in that system? Universally Composable (UC) security rules out such adverse side effects. However, many functionalities of interest provably cannot be realized with UC security unless the protocol participants are willing to put some trust in external computational entities. We propose a notion of security that: (a) allows realizing practically any functionality by protocols in the plain model without putting trust in any external entity; (b) guarantees that secure protocols according to this notion have no adverse side-effects on existing protocols in the system -- as long as the security of these existing protocols is proven via the traditional methodology of black box reduction to a game-based cryptographic hardness assumption with bounded number of rounds. Our security notion builds on the angel-based security notion of Prabhakaran and Sahai. A key part in our analysis is to come up with a CCA-secure commitment scheme that (a) cannot be proven secure via a black box reduction to a game-based assumption, but (b) can be proven secure using a non-black-box reduction. To the best of our knowledge, this is the first time that the interplay between black-box provability and unprovability is used to demonstrate security properties of protocols.

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.

Nonuniform proofs of security are common in cryptography, but traditional black-box separations consider only uniform security reductions. In this paper, we initiate a formal study of the power and limits of nonuniform black-box proofs of security. We first show that a known protocol (based on the existence of one-way permutations) that uses a nonuniform proof of security, and it cannot be proven secure through a uniform security reduction. Therefore, nonuniform proofs of security are indeed provably more powerful than uniform ones. We complement this result by showing that many known black-box separations in the uniform regime actually do extend to the nonuniform regime. We prove our results by providing general techniques for extending certain types of black-box separations to handle nonuniformity.

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

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

We show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length Ω(2t), while only incurring a constant overhead in round-complexity. As a result we obtain a construction of O(1)log* n-round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)--are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions.

In sensor networks we aim to achieve global objectives through local decisions at each node, based only on data available in the node's neighborhood. In this paper, we diffuse information away from source nodes holding desired data, so as to establish information potentials that allow network queries to navigate towards and reach these sources through local greedy decisions, following information gradients. We compute these information potentials by solving for a discrete approximation to a partial differential equation over appropriate network neighborhoods, through a simple local iteration that can be executed in a distributed manner and can be re-invoked to repair the information field locally when links fail, sources move, etc. The solutions to this equation are classical harmonic functions, which have a rich algebraic structure and many useful properties, including the absence of local extrema, providing a guarantee that our local greedy navigation will not get stuck.Unlike shortest path trees, which can also be used to guide queries to sources, information potentials are robust to low-level link volatility as they reflect more global properties of the underlying connectivity. By exploiting the algebraic structure of harmonic functions such potentials can be combined in interesting ways to enable far greater path diversity and thus provide better load balancing than is possible with fixed tree structures, or they can be used to answer range queries about the number of sources in a certain regions by simply traversing the boundary of the region. Potentials for multiple information types can be aggregated and compressed using a variant of the q-digest data structure. The paper provides both analytic results and detailed simulations supporting these claims.