Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / pseudorandom functions, pseudorandom permutations, unconditional security, information-theoretic primitive, design of keyed hash functions

Date: received 12 May 2005

Contact author: jacques patarin at club-internet fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050512:211505 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]