Sending private data to Neural Network applications raises many privacy concerns. The cryptography community developed a variety of secure computation methods to address such privacy issues. As generic techniques for secure computation are typically prohibitively expensive, efforts focus on optimizing these cryptographic tools. Differently, we propose to optimize the design of crypto-oriented neural architectures, introducing a novel Partial Activation layer. The proposed layer is much faster for secure computation as it contains fewer non linear computations. Evaluating our method on three state-of-the-art architectures (SqueezeNet, ShuffleNetV2, and MobileNetV2) demonstrates significant improvement to the efficiency of secure inference on common evaluation metrics.

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

Motivated by a fundamental paradigm in cryptography, we consider a recent variant of the classic problem of bounding the distinguishing advantage between a random function and a random permutation. Specifically, we consider the problem of deciding whether a sequence of q values was sampled uniformly with or without replacement from [N], where the decision is made by a streaming algorithm restricted to using at most s bits of internal memory. In this work, the distinguishing advantage of such an algorithm is measured by the KL divergence between the distributions of its output as induced under the two cases. We show that for any s = Ω(logN) the distinguishing advantage is upper bounded by O(q · s/N), and even by O(q·s/N logN) when q ≤ N1-εfor any constant ε > 0 where it is nearly tight with respect to the KL divergence.

Faced with the threats posed by man-in-the-middle attacks, messaging platforms rely on “out-of-band” authentication, assuming that users have access to an external channel for authenticating one short value. For example, assuming that users recognizing each other’s voice can authenticate a short value, Telegram and WhatApp ask their users to compare 288-bit and 200-bit values, respectively. The existing protocols, however, do not take into account the plausible behavior of users who may be “lazy” and only compare parts of these values (rather than their entirety). Motivated by such a security-critical user behavior, we study the security of lazy users in out-of-band authentication. We start by showing that both the protocol implemented by WhatsApp and the statistically optimal protocol of Naor, Segev, and Smith (CRYPTO’06) are completely vulnerable to man-in-the-middle attacks when the users consider only a half of the out-of-band authenticated value. In this light, we put forward a framework that captures the behavior and security of lazy users. Our notions of security consider both statistical security and computational security, and for each flavor we derive a lower bound on the tradeoff between the number of positions that are considered by the lazy users and the adversary’s forgery probability. Within our framework, we then provide two authentication protocols. First, in the statistical setting, we present a transformation that converts any out-of-band authentication protocol into one that is secure even when executed by lazy users. Instantiating our transformation with a new refinement of the protocol of Naor et al. results in a protocol whose tradeoff essentially matches our lower bound in the statistical setting. Then, in the computational setting, we show that the computationally optimal protocol of Vaudenay (CRYPTO’05) is secure even when executed by lazy users—and its tradeoff matches our lower bound in the computational setting.

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.

Abstract The Border Gateway Protocol (BGP) computes routes between the organizational networks that make up today’s Internet. Unfortunately, BGP suffers from deficiencies, including slow convergence, security problems, a lack of innovation, and the leakage of sensitive information about domains’ routing preferences. To overcome some of these problems, we revisit the idea of centralizing and using secure multi-party computation (MPC) for interdomain routing which was proposed by Gupta et al. (ACM HotNets’12). We implement two algorithms for interdomain routing with state-of-the-art MPC protocols. On an empirically derived dataset that approximates the topology of today’s Internet (55 809 nodes), our protocols take as little as 6 s of topology-independent precomputation and only 3 s of online time. We show, moreover, that when our MPC approach is applied at country/region-level scale, runtimes can be as low as 0.17 s online time and 0.20 s pre-computation time. Our results motivate the MPC approach for interdomain routing and furthermore demonstrate that current MPC techniques are capable of efficiently tackling real-world problems at a large scale.

Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-contiguous memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer).

Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a “central hub” for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters [A. Sahai and B. Waters, How to use indistinguishability obfuscation: Deniable encryption, and more, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 475--484] and its variants, as well as subexponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: (1) There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. (2) There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using subexponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme itself is used in a black-box manner.

Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a "central hub" for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block in cryptographic constructions has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC '14) and its variants, as well as sub-exponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: - There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. - There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using sub-exponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., Obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.

We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon [Advances in Cryptology---EUROCRYPT'98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin, 1998, pp. 334--345] to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan [Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 305--313].

Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function $\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$ that takes two inputs---a weak source $W$ and a uniform (independent) seed $S$---and outputs a string $\mathsf{nmExt}(W,S)$ that is nearly uniform given the seed $S$ as well as the value $\mathsf{nmExt}(W,S')$ for any seed $S'\neq S$ that may be determined as an arbitrary function of $S$. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01\cdot\log n\leq d\leq n$, we present an explicit construction of a nonmalleable extractor $\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$, with $m=\Omega(d)$ and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output $\mathsf{nmExt}(W,S)$ is nearly uniform given the seed $S$ as well as the values $\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)$ for several seeds $S_1,\dots,S_t$ that may be determined as an arbitrary function of $S$, as long as $S\notin\{S_1,\dots,S_t\}$. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2+\delta$ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.

The dynamic approximate membership problem asks to represent a set S of size n, whose elements are provided in an on-line fashion, supporting membership queries without false negatives and with a false positive rate at most ε. That is, the membership algorithm must be correct on each x ∈ S, and may err with probability at most ε on each x ∉ S. We study a well-motivated, yet insufficiently explored, variant of this problem where the size n of the set is not known in advance. Existing optimal approximate membership data structures require that the size is known in advance, but in many practical scenarios this is not a realistic assumption. Moreover, even if the eventual size n of the set is known in advance, it is desirable to have the smallest possible space usage also when the current number of inserted elements is smaller than n. Our contribution consists of the following results: (1) We show a super-linear gap between the space complexity when the size is known in advance and the space complexity when the size is not known in advance. When the size is known in advance, it is well-known that Θ(n log(1/ε)) bits of space are necessary and sufficient (Bloom '70, Carter et al. '78). However, when the size is not known in advance, we prove that at least (1 -o(1))n log(1/ε)+Ω(n log log n) bits of space must be used. In particular, the average number of bits per element must depend on the size of the set. . We show that our space lower bound is tight, and can even be matched by a highly efficient data structure. We present a data structure that uses (1+o(1))n log(1/ε)+O(n log log n) bits of space for approximating any set of any size n, without having to know n in advance. Our data structure supports membership queries in constant time in the worst case with high probability, and supports insertions in expected amortized constant time. Moreover, it can be “de-amortized” to support also insertions in constant time in the worst case with high probability by only increasing its space usage to O(n log(1/ε) + n loglogn) bits.

Motivated by the classical problem of privacy amplification, Dodis and Wichs [9] introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function nmExt : {0, 1}n× {0, 1}d→ {0, 1}mthat takes two inputs: a weak source W and a uniform (independent) seed S, and outputs a string nmExt(W, S) that is nearly uniform given S as well as nmExt(W, S) for any seed S' ≠ S that is determined as an arbitrary function of S. The first explicit construction of a non-malleable extractor was recently provided by Dodis, Li, Wooley and Zuckerman [7]. Their extractor works for any weak source with min-entropy rate 1/2+δ, where δ >; 0 is an arbitrary constant, and outputs up to a linear number of bits, but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols) its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a non-malleable extractor with short seeds. For any integers n and d such that 2.01 · log n ≤ d ≤ n, we present an explicit construction of a non-malleable extractor nmExt: {0, 1}n× {0, 1}d→ {0, 1}m, with m = Ω(d), and error exponentially small in m. The extractor works for any weak source with min-entropy rate 1/2 + δ, where δ >; 0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of non-malleability: its output nmExt(W, S) is nearly uniform given the seed S as well as the values nmExt(W, S1),..., nmExt(W, St) for several seeds S1,..., St that may be determined as an arbitrary function of S, as long as S ∉ {S1,..., St}. By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2 + δ with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear.

Interdomain routing involves coordination among mutually distrustful parties, leading to the requirements that BGP provide policy autonomy, flexibility, and privacy. BGP provides these properties via the distributed execution of policy-based decisions during the iterative route computation process. This approach has poor convergence properties, makes planning and failover difficult, and is extremely difficult to change. To rectify these and other problems, we propose a radically different approach to interdomain-route computation, based on secure multi-party computation (SMPC). Our approach provides stronger privacy guarantees than BGP and enables the deployment of new policy paradigms. We report on an initial exploration of this idea and outline future directions for research.

We put forward the notion of targeted malleability: given a homomorphic encryption scheme, in various scenarios we would like to restrict the homomorphic computations one can perform on encrypted data. We introduce a precise framework, generalizing the foundational notion of non-malleability introduced by Dolev, Dwork, and Naor (SICOMP '00), ensuring that the malleability of a scheme is targeted only at a specific set of "allowable" functions.

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

A fundamental fact in the analysis of randomized algorithms is that when n balls are hashed into n bins independently and uniformly at random, with high probability each bin contains at most O(log n/ log log n) balls. In various applications, however, the assumption that a truly random hash function is available is not always valid, and explicit functions are required. In this paper we study the size of families (or, equivalently, the description length of their functions) that guarantee a maximal load of O(log n/ log log n) with high probability, as well as the evaluation time of their functions. Whereas such functions must be described using Omega(log n) bits, the best upper bound was formerly O(log2n/ log log n) bits, which is attained by O(log n/ log log n)-wise independent functions. Traditional constructions of the latter offer an evaluation time of O(log n/ log log n), which according to Siegel's lower bound [FOCS '89] can be reduced only at the cost of significantly increasing the description length. We construct two families that guarantee a maximal load of O(log n/ log log n) with high probability. Our constructions are based on two different approaches, and exhibit different trade-offs between the description length and the evaluation time. The first construction shows that O(log n/ log log n)-wise independence can in fact be replaced by "gradually increasing independence", resulting in functions that are described using O(log n log log n) bits and evaluated in time O(log n log log n). The second construction is based on derandomization techniques for space-bounded computations combined with a tailored construction of a pseudorandom generator, resulting in functions that are described using O(log3/2n) bits and evaluated in time O(√(log n)). The latter can be compared to Siegel's lower bound stating that O(log n / log log n)-wise independent functions that are evaluated in time O(√(log n)) must be described using Ω(2√(log n)) bits.

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

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: · We construct the first dynamic dictionary that enjoys the best of both worlds: it stores n elements using (1 + ϵ)n memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any ϵ = Ω((log log n/log n)1/2) and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of e. The construction is a two-level variant of cuckoo hashing, augmented with a "backyard" that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on e. · We present a variant of the above construction that uses only (1 + o(1))B bits, where B is the information-theoretic lower bound for representing a set of size n taken from a universe of size u, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the amortized setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe.

We initiate the study of one-wayness under correlated products. We are interested in identifying necessary and sufficient conditions for a function f and a distribution on inputs $(x_1,\dots,x_k)$ so that the function $(f(x_1),\dots,f(x_k))$ is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCAs). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork, and Naor [SIAM J. Comput., 30 (2000), pp. 391–437], while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions [Peikert and Waters, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 187–196] yield injective trapdoor functions that are secure under the above-mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.

We formalize a realistic model for computations over massive data sets. The model, referred to as the {\em adversarial sketch model}, unifies the well-studied sketch and data stream models together with a cryptographic flavor that considers the execution of protocols in "hostile environments", and provides a framework for studying the complexity of many tasks involving massive data sets.

We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ldquomanuallyrdquo authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any there exists a -round protocol for authenticating -bit messages, in which only bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of on the required length of the manually authenticated string. The second model we consider is the traditional message authentication model. In this model, the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (Advances in Cryptology-CRYPTO '93, pp. 355-367, 1993). Finally, we prove that one-way functions are necessary (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from oneway permutations, and even front trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other ctyptographicprotocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.