Current 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 ...

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 ...

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.

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 ...

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 ...

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...

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 ...

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 ...

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 ...

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 ...