Publications |
-
Yuriy Arbitman,
Moni Naor and Gil Segev
Backyard
Cuckoo Hashing: Constant Worst-Case Operations with a Succinct
Representation
In submission.
[Abstract]
[PDF]
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. In
this paper we settle two fundamental open problems:
-- We construct the first dynamic dictionary that enjoys the best of
both worlds: we present a two-level variant of cuckoo hashing that
stores $n$ elements using $(1 + \epsilon) n$ memory words, and
guarantees constant-time operations in the worst case with high
probability. Specifically, for any $\epsilon = \Omega( (\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 $\epsilon$.
The construction is based on augmenting cuckoo hashing with a
"backyard" that handles a large fraction of the elements, together
with a de-amortized perfect hashing scheme for eliminating the
dependency on $\epsilon$.
-- We present a variant of our construction that uses only $(1 +
o(1))B$ bits of memory, 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. Our approach is based on $k$-wise almost
independent permutations with a succinct representation and a
constant evaluation time.
-
We construct the first public-key
encryption scheme in the Bounded-Retrieval Model (BRM), providing
security against various forms of adversarial "key leakage" attacks.
In this model, the adversary is allowed to learn arbitrary
information about the decryption key, subject only to the constraint
that the overall amount of "leakage" is bounded by at most L bits.
The goal of the BRM is to design cryptographic schemes that can
flexibly tolerate arbitrarily leakage bounds L (few bits or many
Gigabytes), by only increasing the size of secret key
proportionally, but keeping all the other parameters -- including
the size of the public key, ciphertext, encryption/decryption time,
and the number of secret-key bits accessed during decryption --small
and independent of L.
As our main technical tool, we introduce the concept of an
Identity-Based Hash Proof System (IB-HPS), which generalizes the
notion of hash proof systems of Cramer and Shoup [CS02] to the
identity-based setting. We give three different constructions of
this primitive based on: (1) bilinear groups, (2) lattices, and (3)
quadratic residuosity. As a result of independent interest, we show
that an IB-HPS almost immediately yields an Identity-Based
Encryption (IBE) scheme which is secure against (small) partial
leakage of the target identity’s decryption key. As our main result,
we use IB-HPS to construct public-key encryption (and IBE) schemes
in the Bounded-Retrieval Model.
-
David Freeman,
Oded Goldreich,
Eike Kiltz,
Alon Rosen and Gil Segev
More Constructions of Lossy and Correlation-Secure Trapdoor
Functions
International Conference
on Practice and Theory in Public Key Cryptography (PKC), 2010.
[Abstract]
[PDF]
We propose new and improved
instantiations of lossy trapdoor functions (Peikert and Waters, STOC
'08), and correlation-secure trapdoor functions (Rosen and Segev,
TCC '09). Our constructions widen the set of number-theoretic
assumptions upon which these primitives can be based, and are
summarized as follows:
-- Lossy trapdoor functions based on the quadratic residuosity
assumption. Our construction relies on modular squaring, and whereas
previous such constructions were based on seemingly stronger
assumptions, we present the first construction that is based solely
on quadratic residuosity.
-- Lossy trapdoor functions based on the composite residuosity
assumption. Our construction guarantees essentially any required
amount of lossiness, where at the same time the functions are more
efficient than the matrix-based approach of Peikert and Waters.
-- Lossy trapdoor functions based on the $d$-Linear assumption. Our
construction both simplifies the DDH-based construction of Peikert
and Waters, and admits a generalization to the whole family of
$d$-Linear assumptions without any loss of efficiency.
-- Correlation-secure trapdoor functions related to the hardness of
syndrome decoding.
-
Vadim Lyubashevsky,
Adriana Palacio,
and Gil Segev
Public-Key Cryptographic Primitives Provably as Secure as Subset
Sum
Theory of
Cryptography Conference (TCC), 2010.
[Abstract]
[PDF]
We propose a semantically-secure
public-key encryption scheme whose security is polynomial-time
equivalent to the hardness of solving random instances of the subset
sum problem. The subset sum assumption required for the security of
our scheme is weaker than that of existing subset-sum based
encryption schemes, namely the lattice-based schemes of Ajtai and
Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC
'09). Additionally, our proof of security is simple and direct. We
also present a natural variant of our scheme that is secure against
key-leakage attacks, as well as an oblivious transfer protocol that
is secure against semi-honest adversaries.
-
Moni Naor and Gil Segev
Public-Key Cryptosystems Resilient to Key Leakage
Advances in Cryptology - CRYPTO 2009.
[Abstract]
[PDF] [Slides]
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. (USENIX Security '08), Akavia,
Goldwasser and Vaikuntanathan (TCC '09) 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, Akavia et al. showed that Regev's lattice-based scheme (STOC
'05) is resilient to any leakage of $L / 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:
-- We present a generic
construction of a public-key encryption scheme that is resilient to
key leakage from any universal hash proof system. The
construction does not rely on additional computational assumptions,
and the resulting scheme is as efficient as the underlying proof
system. Existing constructions of such 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.
-- 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. (CRYPTO '08), 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.
-- 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.
-
Mihir Bellare, Zvika
Brakerski, Moni Naor,
Thomas Ristenpart, Gil
Segev, Hovav Shacham and
Scott Yilek
Hedged Public-Key Encryption: How to Protect Against Bad
Randomness
Advances in Cryptology - ASIACRYPT 2009.
[Abstract]
[PDF]
Public-key encryption schemes
rely for their IND-CPA security on per-message fresh randomness. In
practice, randomness may be of poor quality for a variety of
reasons, leading to failure of the schemes. Expecting the systems to
improve is unrealistic. What we show in this paper is that we can,
instead, improve the cryptography to offset the lack of possible
randomness. We provide public-key encryption schemes that achieve IND-CPA security when the randomness they use is of high quality,
but, when the latter is not the case, rather than breaking
completely, they achieve a weaker but still useful notion of
security that we call IND-CDA. This hedged public-key encryption
provides the best possible security guarantees in the face of bad
randomness. We provide simple RO-based ways to make in-practice IND-CPA
schemes hedge secure with minimal software changes. We also provide
non-RO model schemes relying on lossy trapdoor functions (LTDFs) and
techniques from deterministic encryption. They achieve adaptive
security by establishing and exploiting the anonymity of LTDFs which
we believe is of independent interest.
-
Yuriy Arbitman,
Moni Naor and Gil Segev
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and
Experimental Results
International Colloquium on Automata, Languages and Programming (ICALP),
2009.
[Abstract]
[PDF] [Slides]
Cuckoo hashing is a highly
practical dynamic dictionary: it provides amortized constant
insertion time, worst case constant deletion time and lookup time,
and good memory utilization. However, with a noticeable probability
during the insertion of $n$ elements some insertion requires
$\Omega(\log n)$ time. Whereas such an amortized guarantee may be
suitable for some applications, in other applications (such as
high-performance routing) this is highly undesirable.
Kirsch and Mitzenmacher (Allerton '07) proposed a de-amortization of
cuckoo hashing using queueing techniques that preserve its
attractive properties. They demonstrated a significant improvement
to the worst case performance of cuckoo hashing via experimental
results, but left open the problem of constructing a scheme with
provable properties.
In this work we present a de-amortization of cuckoo hashing that
provably guarantees constant worst case operations.
Specifically, for any sequence of polynomially many operations, with
overwhelming probability over the randomness of the initialization
phase, each operation is performed in constant time. In addition, we
present a general approach for proving that the performance
guarantees are preserved when using hash functions with limited
independence instead of truly random hash functions. Our approach
relies on a recent result of Braverman (CCC '09) showing that
poly-logarithmic independence fools $AC^0$ circuits, and may find
additional applications in various similar settings. Our theoretical
analysis and experimental results indicate that the scheme is highly
efficient, and provides a practical alternative to the only other
known approach for constructing dynamic dictionaries with such worst
case guarantees, due to Dietzfelbinger and Meyer auf der Heide (ICALP
'90).
-
Tal Moran,
Moni Naor and Gil Segev
An Optimally Fair Coin Toss
Theory of
Cryptography Conference (TCC), 2009.
Invited to the Journal of Cryptology.
[Abstract]
[PDF] [Slides]
We address one of the
foundational problems in cryptography: the bias of coin-flipping
protocols. Coin-flipping protocols allow mutually distrustful
parties to generate a common unbiased random bit, guaranteeing that
even if one of the parties is malicious, it cannot significantly
bias the output of the honest party. A classical result by Cleve [STOC
'86] showed that for any two-party coin-flipping protocol with $r$
rounds, there exists an efficient adversary that can bias the output
of the honest party by $\Omega(1/r)$. However, the best previously
known protocol only guarantees $O(1/\sqrt{r})$ bias, and the
question of whether Cleve's bound is tight has remained open for
more than twenty years.
In this paper we establish the optimal tradeoff between the round
complexity and the bias of two-party coin-flipping protocols. Under
standard assumptions, we show that Cleve's lower bound is tight: we
construct an $r$-round protocol with bias $O(1/r)$.
-
Alon Rosen and Gil Segev
Chosen-Ciphertext Security via Correlated Products
Theory of
Cryptography Conference (TCC), 2009.
[Abstract]
[PDF] [Slides]
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, ..., x_k)$, so that the function
$(f(x_1), ..., 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 (CCA). 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.
We provide evidence that security under correlated products is
achievable by demonstrating that lossy trapdoor functions (Peikert
and Waters, STOC '08) 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.
-
Ilya Mironov,
Moni Naor and Gil Segev
Sketching in Adversarial Environments
ACM Symposium on Theory of Computing (STOC),
2008.
Journal version to appear in SIAM Journal on Computing (STOC '08 special issue).
[Abstract]
[PDF] [Slides]
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 many 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 the compressed 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 and efficient protocols that are optimal up to
poly-logarithmic 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.
-
Tal Moran and
Gil Segev
David and Goliath Commitments: UC Computation for Asymmetric Parties
Using Tamper-Proof Hardware
Advances in Cryptology - EUROCRYPT 2008.
[Abstract]
[PDF]
[Slides]
Designing secure protocols in the
Universal Composability (UC) framework confers many advantages. In
particular, it allows the protocols to be securely used as building
blocks in more complex protocols, and assists in understanding their
security properties. Unfortunately, most existing models in which
universally composable computation is possible (for useful
functionalities) require a trusted setup stage. Recently, Katz (EUROCRYPT
'07) proposed an alternative to the trusted setup assumption:
tamper-proof hardware. Instead of trusting a third party to
correctly generate the setup information, each party can create its
own hardware tokens, which it sends to the other parties. Each party
is only required to trust that its own tokens are tamper-proof.
Katz designed a UC commitment protocol that requires both parties to
generate hardware tokens. In addition, his protocol relies on a
specific number-theoretic assumption. In this paper, we construct UC
commitment protocols for ''David'' and ''Goliath'': we only require
a single party (Goliath) to be capable of generating tokens. We
construct a version of the protocol that is secure for
computationally unbounded parties, and a more efficient version that
makes computational assumptions only about David (we require only
the existence of a one-way function). Our protocols are simple
enough to be performed by hand on David's side.
These properties may allow such protocols to be used in situations
which are inherently asymmetric in real-life, especially those
involving individuals versus large organizations. Classic examples
include voting protocols (voters versus ''the government'') and
protocols involving private medical data (patients versus
insurance-agencies or hospitals).
-
Moni Naor, Gil Segev
and Udi Wieder
History-Independent Cuckoo Hashing
International Colloquium on Automata, Languages and Programming (ICALP),
2008.
[Abstract]
[PDF] [Slides]
Cuckoo hashing is an efficient
and practical dynamic dictionary. It provides expected amortized
constant update time, worst case constant lookup time, and good
memory utilization. Various experiments demonstrated that cuckoo
hashing is highly suitable for modern computer architectures and
distributed settings, and offers significant improvements compared
to other schemes.
In this work we construct a practical history-independent
dynamic dictionary based on cuckoo hashing. In a history-independent
data structure, the memory representation at any point in time
yields no information on the specific sequence of insertions and
deletions that led to its current content, other than the content
itself. Such a property is significant when preventing unintended
leakage of information, and was also found useful in several
algorithmic settings.
Our construction enjoys most of the attractive properties of cuckoo
hashing. In particular, no dynamic memory allocation is required,
updates are performed in expected amortized constant time, and
membership queries are performed in worst case constant time.
Moreover, with high probability, the lookup procedure queries only
two memory entries which are independent and can be queried in
parallel. The approach underlying our construction is to enforce a
canonical memory representation on cuckoo hashing. That is, up to
the initial randomness, each set of elements has a unique memory
representation.
-
Iftach Haitner,
Jonathan J. Hoch and Gil
Segev
A Linear Lower
Bound on the Communication Complexity of Single-Server Private
Information Retrieval
Theory of
Cryptography Conference (TCC), 2008.
[Abstract]
[PDF] [Slides]
We study the communication complexity
of single-server Private Information Retrieval (PIR) protocols that
are based on fundamental cryptographic primitives in a black-box
manner. In this setting, we establish a tight lower bound on the
number of bits communicated by the server in any polynomially-preserving
construction that relies on trapdoor permutations. More
specifically, our main result states that in such constructions $\Omega(n)$
bits must be communicated by the server,
where $n$ is the size of the server's database, and this improves
the $\Omega(n / \log n)$ lower bound due to Haitner, Hoch, Reingold
and Segev (FOCS
'07). Therefore, in the setting under consideration, the naive
solution in which the user downloads the entire database turns out
to be optimal up to constant multiplicative factors. We note that
the lower bound we establish holds for the most generic form of
trapdoor permutations, including in particular enhanced trapdoor
permutations.
Technically speaking, this paper consists of two main contributions
from which our lower bound is obtained. First, we derive a tight
lower bound on the number of bits communicated by the sender during
the commit stage of any black-box construction of a
statistically-hiding bit-commitment scheme from a family of trapdoor
permutations. This lower bound asymptotically matches the upper
bound provided by the scheme of Naor, Ostrovsky, Venkatesan and Yung
(CRYPTO '92). Second, we improve the efficiency of the reduction of
statistically-hiding commitment schemes to low-communication
single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC
'99). In particular, we present a reduction that essentially
preserves the communication complexity of the underlying
single-server PIR protocol.
-
Iftach Haitner,
Jonathan J. Hoch,
Omer Reingold and Gil
Segev
Finding Collisions
in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of
Statistically-Hiding Commitments
IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
[Abstract]
[PDF]
[Slides]
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 one-way permutations, and even from 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 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 (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.
-
Tal Moran,
Moni Naor and Gil Segev
Deterministic History-Independent Strategies for Storing
Information on Write-Once Memories
International Colloquium on Automata, Languages and Programming (ICALP), 2007
(best paper award in the security & cryptography track).
Journal version in Theory of Computing, 2009.
[Abstract]
[PDF] [Slides]
Motivated by
the challenging task of designing "secure" vote storage mechanisms,
we study information storage mechanisms that operate in extremely
hostile environments. In such environments, the majority of existing
techniques for information storage and for security are susceptible
to powerful adversarial attacks. We propose a mechanism for storing
a set of at most $K$ elements from a large universe of size $N$ on
write-once memories in a manner that does not reveal the insertion
order of the elements. We consider a standard model for write-once
memories, in which the memory is initialized to the all $0$'s state,
and the only operation allowed is flipping bits from $0$ to $1$.
Whereas previously known constructions were either inefficient
(required $\Theta(K^2)$ memory), randomized, or employed
cryptographic techniques which are unlikely to be available in
hostile environments, we eliminate each of these undesirable
properties. The total amount of memory used by the mechanism is
linear in the number of stored elements and poly-logarithmic in the
size of the universe of elements.
We also demonstrate a connection between secure vote storage
mechanisms and one of the classical distributed computing problems:
conflict resolution in multiple-access channels. By establishing a
tight connection with the basic building block of our mechanism, we
construct the first deterministic and non-adaptive conflict
resolution algorithm whose running time is optimal up to
poly-logarithmic factors.
-
Moni Naor, Gil Segev and
Adam
Smith
Tight Bounds for Unconditional Authentication
Protocols in the Manual Channel and Shared Key Models
Advances in Cryptology - CRYPTO 2006.
Journal version in IEEE Transactions on Information Theory (special issue on
Information Theoretic Security), 2008.
[Abstract]
[PDF] [Slides]
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 "manually"
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 $0 < \epsilon < 1$ there exists a $\log^*
n$-round protocol for authenticating $n$-bit messages, in which only
$2 \log (1 /\epsilon) + O(1)$ bits are manually authenticated, and
any adversary (even computationally unbounded) has probability of at
most $\epsilon$ 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 $2
\log (1/ \epsilon) - O(1)$ 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 $2 \log (1/ \epsilon) - 2$ on the required Shannon
entropy of the shared key. This settles an open question posed by
Gemmell and Naor (CRYPTO '93).
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.
-
Danny Segev and Gil
Segev
Approximate k-Steiner Forests via the Lagrangian
Relaxation Technique with Internal Preprocessing
European Symposium on Algorithms (ESA),
2006.
Journal version in Algorithmica, 2010.
[Abstract]
[PDF] [Slides]
An instance of the
$k$-Steiner forest problem consists of an undirected graph $G = (V,E)$,
the edges of which are associated with non-negative costs, and a
collection ${\cal D} = \{ (s_1, t_1), \ldots, (s_d, t_d) \}$ of
distinct pairs of vertices, interchangeably referred to as demands.
We say that a forest ${\cal F} \subseteq G$ connects a demand $(s_i,
t_i)$ when it contains an $s_i$-$t_i$ path. Given a requirement
parameter $k \leq |{\cal D}|$, the goal is to find a minimum cost
forest that connects at least $k$ demands in ${\cal D}$. This
problem has recently been studied by Hajiaghayi and Jain [SODA '06],
whose main contribution in this context was to relate the
inapproximability of $k$-Steiner forest to that of the dense $k$-subgraph
problem. However, Hajiaghayi and Jain did not provide any
algorithmic result for the respective settings, and posed this
objective as an important direction for future research.
In this paper, we
present the first non-trivial approximation algorithm for the
$k$-Steiner forest problem, which is based on a novel extension of
the Lagrangian relaxation technique. Specifically, our algorithm
constructs a feasible forest whose cost is within a factor of $O(
\min \{ n^{ 2/3 }, \sqrt{d} \} \cdot \log d )$ of optimal, where $n$
is the number of vertices in the input graph and $d$ is the number
of demands. We believe that the approach illustrated in the current
writing is of independent interest, and may be applicable in other
settings as well. |
