Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments
No full textWe present a zero-knowledge proof system for any NP language L, which
allows showing that x is in L using communication corresponding
to bit commitments, with error probability ,
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 , using O(n) commitments.
This is the first protocol for SAT that is linear in this sense.
[The rest of the abstract was truncated and appears below -- the library.
Proactive RSA
No full textWe 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
Visual Cryptography II: Improving the Contrast Via the Cover Base
No full textIn Eurocrypt\u2794 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\u27s
(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
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
No full textThe Graph Clustering Problem is parameterized by a sequence
of positive integers, .
The input is a sequence of 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 Monotone Function Closure of Statistical Zero-Knowledge
No full textAssume 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
Incoercible Multiparty Computation
No full textCurrent secure multiparty protocols have the following deficiency.
The public transcript of the communication can be used as an involuntary
commitment 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
Upper bound on the communication complexity of private information retrieval
No full textPrivate 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