A Greater Tel-Aviv Area Seminar

Ran Gelles: Efficient and Explicit Coding for Interactive Communication

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memoryless noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol.

21/09/2011 - 11:00

Eran Omri @ TAU: Coin Flipping with Constant Bias Implies One-Way Functions

It is well known (c.f., Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, i,e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much.

23/11/2011 - 10:10

Gil Segev (MSR- SVC) @ TAU: From Cryptography to Algorithms and Back Again

Title: From Cryptography to Algorithms and Back Again
Abstract: For more than 30 years cryptography has been enjoying rich and fertile interactions with a wide variety of other research areas. These include number theory, complexity theory, learning theory, and more, each of which has had a major effect on the development of modern cryptography. This talk will review my recent work on a somewhat less obvious and insufficiently explored interaction between cryptography and fundamental problems in the design and analysis of algorithms.

07/12/2011 - 10:15

Claudio Orlandi @ BIU: Lower and Upper Bounds for Deniable Public-Key Encryption

A deniable cryptosystem allows a sender and a receiver to communicate over an insecure channel in such a way that the communication is still secure even if the adversary can threaten the parties into revealing their internal states after the execution of the protocol. This is done by allowing the parties to change their internal state to make it look like a given ciphertext decrypts to a message different from what it really decrypts to. Deniable encryption was in this way introduced to allow to deny a message exchange and hence combat coercion.

30/11/2011 - 10:00

Ran Canetti @TAU on: From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08].

04/01/2012 - 11:00