## All papers in 1996 (16 results)

Public-Key Cryptosystems from Lattice Reduction Problems

Uncategorized

Uncategorized

We present a new proposal for a trapdoor one-way function, from which
we derive public-key encryption and digital signatures.
The security of the new construction is based on the
conjectured computational difficulty of lattice-reduction problems,
providing a possible alternative to existing
public-key encryption algorithms
and digital signatures such as RSA and DSS.

Verifiable Partial Key Escrow

Uncategorized

Uncategorized

One of the main objections to existing proposals for key escrow is that the
individual's privacy relies on too high a level of trust in the law enforcement
agencies. In particular, even if the government is trustworthy today, it may be
replaced by an un-trustworthy government tomorrow which could immediately and
suddenly recover the secret keys of all users.

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Uncategorized

Uncategorized

The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show that this problem has a (perfect) zero-knowledge
interactive proof system.

On the Contrast in Visual Cryptography Schemes

Uncategorized

Uncategorized

A visual cryptography scheme is a method to encode a secret image SI into
shadow images called shares such that certain qualified subsets of shares
enable the ``visual'' recovery of the secret image.
The ``visual'' recovery consists of xeroxing the shares onto transparencies,
and then stacking them. The shares of a qualified set will reveal the secret
image without any cryptographic computation.
In this paper we analyze the contrast of the reconstructed image
in k out of n visual cryptography schemes. (In such a scheme
any k shares will reveal the image, but no set of k-1 shares
gives any information about the image.)
In the case of 2 out of n threshold schemes we give a complete
characterization of schemes having optimal contrast and minimum
pixel expansion in terms of certain balanced incomplete block designs.
In the case of k out of n threshold schemes with k>2 we obtain
upper and lower bounds on the optimal contrast.

Proactive RSA

Uncategorized

Uncategorized

We consider a "mobile adversary" which may corrupt all
participants throughout the lifetime of the system in a non-monotonic
fashion (i.e. recoveries are possible) but the adversary is unable to
corrupt too many participants during any short time period.
Schemes resiliant to such adverasry are called proactive.
We present a proactive RSA system in which a threshold of servers
applies the RSA signature (or decryption) function in a distributed manner.
Employing new combinatorial and elementary number theoretic
techniques, our protocol enables the dynamic updating
of the servers (which hold the RSA key distributively);
it is secure even when a linear number of
the servers are corrupted during any time period;
it efficiently "self-maintains" the
security of the function and its
messages (ciphertexts or signatures); and it enables continuous
availability, namely, correct function application using the shared
key is possible at any time.

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Uncategorized

Uncategorized

Luby and Rackoff showed a method for constructing a pseudo-random permutation
from a pseudo-random function. The method is based on composing four
(or three for weakened security) so called Feistel permutations
each of which requires the evaluation of a pseudo-random function.
We reduce somewhat the complexity of the construction
and simplify its proof of security by showing
that two Feistel permutations are sufficient together with initial
and final pair-wise independent permutations.
The revised construction and proof provide a framework in which
similar constructions may be brought up and their security can
be easily proved.
We demonstrate this by presenting some additional adjustments
of the construction that achieve the following:
1. Reduce the success probability of the adversary.
2. Provide a construction of pseudo-random permutations with large input
size using pseudo-random functions with small input size.
3. Provide a construction of a pseudo-random permutation
using a single pseudo-random function.

Oblivious Transfers and Intersecting Codes

Uncategorized

Uncategorized

Assume A owns t secret k-bit strings.
She is willing to disclose one of them to B, at his choosing,
provided he does not learn anything about the other strings.
Conversely, B does not want A to learn which secret he chose to learn.
A protocol for the above task is said to implement
One-out-of-t String Oblivious Transfer. An apparently simpler task
corresponds to the case k=1 and t=2 of two one-bit secrets:
this is known as One-out-of-two Bit OT.
We address the question of implementing the former assuming the
existence of the later.
In particular, we prove that the general protocol can be implemented from
O(tk) calls to One-out-of-two Bit OT. This is
optimal up to a small multiplicative constant.
Our solution is based on the notion of self-intersecting codes.
Of independent interest, we give several efficient new constructions for
such codes.
Another contribution of this paper is a set
of information-theoretic definitions for correctness and
privacy of unconditionally-secure oblivious transfer.

Collision-Free Hashing from Lattice Problems

Uncategorized

Uncategorized

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

Access Control and Signatures via Quorum Secret Sharing

Uncategorized

Uncategorized

We suggest a method of controlling the access to a secure
database via quorum systems. A quorum system is a collection of sets
(quorums) every two of which have a nonempty intersection.
Quorum systems have been used for a number of applications in the area of
distributed systems.
We propose a separation between access servers which are protected and
trustworthy, but may be outdated, and the data servers which may all
be compromised. The main paradigm is that only the servers in a
complete quorum can collectively grant (or revoke) access permission.
The method we suggest ensures that after authorization is revoked, a
cheating user Alice will not be able to access the data even if many
access servers still consider her authorized, and even if the complete
raw database is available to her. The method has a low overhead in
terms of communication and computation. It can also be converted into
a distributed system for issuing secure signatures.

Visual Cryptography II: Improving the Contrast Via the Cover Base

Uncategorized

Uncategorized

In Eurocrypt'94 we proposed a a new type of cryptographic scheme,
which can decode concealed images without any cryptographic computations,
by placing two transparencies on top of each other and using the decoder's
(human) visual systems.
One of the drawback of that proposal was a loss in contrast: a black pixel
is translated in the reconstruction into a black region, but a white
pixel is translated into a grey region (half black and half white).
In this paper we propose am alternative model for reconstruction with a
different set of operation (which we call the ``Cover" semi-group) is proposed.
In this model we are able to obtain a better contrast than
is possible in the previous one.
We prove tight bounds on the contrast
as a function of the complexity of the scheme. We also show
that for constructing k-out-n secret sharing schemes when
n and k are greater than 2 the new method is not applicable.

Upper bound on the communication complexity of private information retrieval

Uncategorized

Uncategorized

Private information retrieval was introduced
by Chor, Goldreich, Kushilevitz and Sudan.
It is the problem of reading a bit from the database so
that it remains secret which bit we need.
If the database exists in several identical copies,
it is possible to ask queries so that each of copies
alone does not get any information about the adress
of the needed bit.
We construct a scheme for private information retrieval
with k databases and O(n sup (1/(2k-1)) ) bits of communication.

Private Information Storage

Uncategorized

Uncategorized

We consider the setting of hiding information through the use of
multiple databases that do not interact with one another. Previously,
in this setting solutions for retrieval of data in the efficient
manner were given, where a user achieves this by interacting with all
the databases. We consider the case of both writing and
reading. While the case of reading was well studied before, the case
of writing was previously completely open. In this paper, we show how
to implement both read and write operations. As in the previous
papers, we measure, as a function of k and n the amount of
communication required between a user and all the databases for a
single read/write operation, and achieve efficient read/write schemes.
Moreover, we show a general reduction from reading database scheme to
reading and writing database scheme, with the following guarantees:
for any k, given a retrieval only k-database scheme with communication
complexity R(k,n) we show a (k+1) reading and writing database scheme
with total communication complexity O(R(k,n) * (log n)^{O(1)}). It
should be stressed that prior to the current paper no trivial
(i.e. sub-linear) bounds for private information storage were known.

Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments

Uncategorized

Uncategorized

We present a zero-knowledge proof system for any NP language L, which
allows showing that x is in L using communication corresponding
to $O(|x| sup c)+k$ bit commitments, with error probability $2 sup -k$,
and where c is a constant depending only on L.
The proof can be based on any bit
commitment scheme with a particular set of properties. We suggest an
efficient implementation based on factoring. The protocol allows showing
that a Boolean formula of size n is satisfiable,
with error probability $2 sup -n$, using O(n) commitments.
This is the first protocol for SAT that is linear in this sense.<br>
[The rest of the abstract was truncated and appears below -- the library.]

On Monotone Function Closure of Statistical Zero-Knowledge

Uncategorized

Uncategorized

Assume we are given a language L with an honest verifier
perfect zero-knowledge proof system. Assume also that the proof system is an
Arthur-Merlin game with at most 3 moves. The class of such languages
includes all random self-reducible language, and also any language with a
perfect zero-knowledge non-interactive proof.
We show that such a language satisfies a certain closure property, namely
that languages constructed from L by applying certain monotone functions to
statements on membership in L have perfect zero-knowledge proof systems.
The new set of languages we can build includes L itself, but also for
example languages consisting of n words of which at least t are in L.
A similar closure property is shown to hold for the complement of L and for
statistical zero-knowledge. The property we need for the monotone functions used
to build the new languages is that there are efficient secret sharing schemes
for their associated access structures. This includes (but is not necessarily
limited to) all monotone functions with polynomial size monotone formulas.

Deniable Encryption

Uncategorized

Uncategorized

Consider a situation in which the transmission of encrypted
messages is intercepted by an adversary who can later
ask the sender to reveal
the random choices (and also the secret key, if one exists)
used in generating
the ciphertext, thereby exposing the cleartext.
An encryption scheme is <B>deniable</B> if the sender can generate
`fake random choices' that will make the ciphertext `look like'
an encryption of a different cleartext, thus keeping the
real cleartext private.
Analogous requirements can be formulated with respect to
attacking the receiver and with respect to attacking both parties.
In this paper we introduce deniable encryption and propose
constructions of schemes with polynomial deniability. In addition to
being interesting by itself, and having several applications, deniable
encryption provides a simplified and elegant construction of
<B>adaptively secure</B> multiparty computation.

Incoercible Multiparty Computation

Uncategorized

Uncategorized

Current secure multiparty protocols have the following deficiency.
The public transcript of the communication can be used as an involuntary
<B>commitment</B> of the parties to their inputs and outputs. Thus parties
can be later coerced by some authority to reveal their private data.
Previous work that has pointed this interesting problem out contained only
partial treatment.
In this work we present the first general and rigorous treatment of the
coercion problem in secure computation.
First we present a general definition of protocols that
provide resilience to coercion. Our definition
constitutes a natural extension of the general paradigm used
for defining secure multiparty protocols.
Next we show that if trapdoor permutations exist then
any function can be incoercibly computed
(i.e., computed by a protocol that provides resilience to coercion)
in the presence of computationally
bounded adversaries and only public communication channels.
This holds as long as less than half the parties are coerced (or corrupted).
In particular, ours are the first incoercible protocols without
physical assumptions. Also, our protocols constitute an alternative
solution to the recently solved adaptive security problem.