Publications - Abstracts
# Publications - Abstracts

Research Group of Prof.C.P.Schnorr, University of Frankfurt am Main

###
Pseudorandom Function Tribe Ensembles
Based on One-Way Permutations:
Improvements and Applications

Marc Fischlin

Fachbereich Mathematik (AG 7.2)

Johann Wolfgang Goethe-Universität Frankfurt am Main

PSF 111932

60054 Frankfurt/Main, Germany
e-mail: `marc@mi.informatik.uni-frankfurt.de`

URL: `http://www.mi.informatik.uni-frankfurt.de`

Pseudorandom function tribe ensembles are pseudorandom function
ensembles that have an
additional collision resistance property: almost all functions have
disjoint ranges.
We present an alternative to the construction of pseudorandom function
tribe ensembles
based on one-way permutations given by Canetti, Micciancio and Reingold
[CMR98].
Our approach yields two different but related solutions: One
construction is somewhat theoretic,
but conceptually simple and therefore gives an easier proof that
one-way permutations suffice to construct pseudorandom function tribe
ensembles. The other,
slightly more complicated solution provides a practical construction;
it starts with an arbitrary pseudorandom function ensemble and assimilates
the one-way permutation to this ensemble. Therefore, the second solution
inherits important characteristics of the underlying pseudorandom
function ensemble:
it is almost as efficient and if the starting pseudorandom function
ensemble is
efficiently invertible (given the secret key) then so is the derived
tribe ensemble.
We also show that the latter solution yields so-called committing private-key
encryption schemes. i.e., where each ciphertext corresponds to exactly
one plaintext - independently
of the choice of the secret key or the random bits used in the
encryption process.

Download the .ps (US letter),
.dvi
or gnuzipped .ps.gz (US letter)
version.