You are looking at a specific version 20050512:211505 of this paper. See the latest version.

Paper 2005/135

Design of near-optimal pseudorandom functions and pseudorandom permutations in the information-theoretic model

Jacques Patarin and Paul Camion

Abstract

In this paper we will extend the Benes and Luby-Rackoff constructions to design various pseudo-random functions and pseudo-random permutations with near optimal information-theoretic properties. An example of application is when Alice wants to transmit to Bob some messages against Charlie, an adversary with unlimited computing power, when Charlie can receive only a percentage $\tau$ of the transmitted bits. By using Benes, Luby-Rackoff iterations, concatenations and fixing at 0 some values, we will show in this paper how to design near optimal pseudo-random functions for all values of $\tau$. Moreover we will show how to design near optimal pseudo-random permutations when $\tau$ can have any value such that the number of bits obtained by Charlie is smaller than the square root of all the transmitted bits.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
pseudorandom functionspseudorandom permutationsunconditional securityinformation-theoretic primitivedesign of keyed hash functions
Contact author(s)
jacques patarin @ club-internet fr
History
2005-05-12: received
Short URL
https://ia.cr/2005/135
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.