Arrow Research search

Author name cluster

Charles Rackoff

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

FOCS Conference 2008 Conference Paper

On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations

  • Dan Boneh
  • Periklis A. Papakonstantinou
  • Charles Rackoff
  • Yevgeniy Vahlis
  • Brent Waters

We ask whether an Identity Based Encryption (IBE) system can be built from simpler public-key primitives. We show that there is no black-box construction of IBE from Trapdoor Permutations (TDP) or even from Chosen Ciphertext Secure Public Key Encryption (CCA-PKE). These black-box separation results are based on an essential property of IBE, namely that an IBE system is able to compress exponentially many public-keys into a short public parameters string.

Details

TCS Journal 2005 Journal Article

Simple permutations mix well

  • Shlomo Hoory
  • Avner Magen
  • Steven Myers
  • Charles Rackoff

We study the random composition of a small family of O ( n 3 ) simple permutations on { 0, 1 } n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k -wise independent. We improve on a result of Gowers [An almost m -wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119–130] and show that up to a polylogarithmic factor, n 3 k 3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k -wise independence against adaptive adversaries. This question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. We also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k -wise independence with fewer compositions and fewer random bits.

Details DOI

FOCS Conference 1998 Conference Paper

Lower Bounds for Zero Knowledge on the Internet

  • Joe Kilian
  • Erez Petrank
  • Charles Rackoff

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.

Details

FOCS Conference 1983 Conference Paper

How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin

  • Michael Luby
  • Silvio Micali
  • Charles Rackoff

We present a cryptographic protocol allowing two mutually distrusting parties, A and B, each having a secret bit, to "simultaneously" exchange the values of those bits. It is assumed that initially each party presents a correct encryption of his secret bit to the other party. We develop a new tool to implement our protocol: a slightly biased symmetric coin. The key property of this coin is that from each flip A receives a piece of probabilistic information about B's secret bit which is symmetric to the piece of information B receives about A's secret bit.

Details

TCS Journal 1978 Journal Article

The covering and boundedness problems for vector addition systems

  • Charles Rackoff

New decision procedures for the covering and boundedness problems for vector addition systems are obtained. These procedures require at most space 2 cn log n for some constant c. The procedures nearly achieve recently established lower bounds on the amount of space inherently required to solve these problems, and so are much more efficient than previously known non-primitive-recursive decision procedures.

Details DOI