Author name cluster

Gilad Asharov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

SODA Conference 2022 Conference Paper

Optimal Oblivious Parallel RAM

Gilad Asharov
Ilan Komargodski
Wei-Kai Lin
Enoch Peserico
Elaine Shi

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

Details

SODA Conference 2021 Conference Paper

Sorting Short Keys in Circuits of Size o ( n log n )

Gilad Asharov
Wei-Kai Lin
Elaine Shi

We consider the classical problem of sorting n elements, where each element is described with a k -bit comparison-key and a w -bit payload. A long-standing open problem is whether there exist ( k + w ) · o ( n log n )-sized boolean circuits for sorting. Ajtai, Komlós, and Szemerédi (STOC'83) constructed the famous AKS sorting network with ( k + w ) · O ( n log n ) boolean gates. Recently, Farhadi et al. (STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size w · o ( n log n ) do not exist for general k (while unconditional circuit lower bound is out of the reach of existing techniques). In this paper, we show that one can overcome the n log n barrier when the comparison-keys are short. Specifically, we construct a sorting circuit with ( k + w ) · O ( nk ) · poly(log∗ n – log∗( w + k )) boolean gates, asymptotically better than AKS sorting network if the keys are short, say, k = o (log n ) (ignoring poly log∗ terms). Such a result might be surprising since comparator-based techniques must incur Ω( n log n ) comparators even when the keys are only 1-bit long (e. g. , see Knuth's “Art of Programming” textbook). To the best of our knowledge, this is also the first non-trivial result on non-comparison-based sorting circuits. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring poly log∗ terms, for every k = O (log n ).

Details

STOC Conference 2016 Conference Paper

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations

Gilad Asharov
Moni Naor
Gil Segev 0001
Ido Shahaf

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). 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/loglog N documents, we construct a scheme with read efficiency Õ(loglog N ). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal 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 Õ(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.

Details

FOCS Conference 2015 Conference Paper

Limits on the Power of Indistinguishability Obfuscation and Functional Encryption

Gilad Asharov
Gil Segev 0001

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.

Details