Article

Free access

Improved security bounds for pseudorandom permutations

Author:

Jacques PatarinAuthors Info & Claims

CCS '97: Proceedings of the 4th ACM conference on Computer and communications security

Pages 142 - 150

https://doi.org/10.1145/266420.266452

Published: 01 April 1997 Publication History

PDF eReader

References

[1]

W. Aiello and R. Venkatesan, "Foiling birthday attacks in length-doubling transformations". Eurocrypt'96, Springer-Verlag, pp. 307-320.

Digital Library

Google Scholar

[2]

M. Luby and C. Rackoff, "How to construct pseudorandom permutations from pseudorandom functions". SIAM Journal on Computing, Vol. 17, n02, pp. 373-386, April 1988.

Digital Library

Google Scholar

[3]

U. Maurer and J. Massey, "Local randomness in pseudorandom sequences". Journal of Cryptology, Vol. 4, n02, pp. 135-149, 1991 (a preliminary version of this paper was presented at Crypto'89, pp. 100-112).

Digital Library

Google Scholar

[4]

U. Maurer, "A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators". Eurocrypt'92, Springer-Verlag, pp. 239-255.

Digital Library

Google Scholar

[5]

J. Patarin, "New results on pseudorandom permutation generators based on the DES scheme". Crypto'91, Springer-Verlag, pp. 301-312.

Digital Library

Google Scholar

[6]

J. Patarin, "How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function". Eurocrypt'92, Springer-Verlag, pp. 256-266.

Digital Library

Google Scholar

[7]

J. Patarin, "Etude des generateurs de permutations bases sur le schema du DES" . Ph. D. Thesis, Inria, Domaine de Voluceau, Le Chesnay, France, 1991.

Google Scholar

[8]

J. Pieprzyk, "How to construct pseudorandom permutations from single pseudorandom functions". Eurocrypt'90, Springer-Verlag, pp. 140-150.

Digital Library

Google Scholar

[9]

C.Schnorr, "On the construction of random number generators and random function generators". Eurocrypt'88, Springer-Verlag, pp. 225-232.

Digital Library

Google Scholar

[10]

C.E. Shannon, "A mathematical theory of communication". Bell System Technical Journal, Vol. 27, n03, July 1948, pp. 379-423 and 623-656.

Crossref

Google Scholar

[11]

Y. Zheng, T. Matsumoto and H. Imai, "On the construction of block ciphers probably secure and not relying on any unproved hypotheses". Crypto'89, Springer-Verlag, pp. 461-480.

Digital Library

Google Scholar

[12]

Y. Zheng, T. Matsumoto and H. Imai, "Impossibility and optimality results on constructing pseudorandom permutations". Eurocrypt'89, Springer-Verlag, pp. 412-421.

Digital Library

Google Scholar

Cited By

View all

Jha ANandi M(2022)A Survey on Applications of H-Technique: Revisiting Security Analysis of PRP and PRFEntropy10.3390/e2404046224:4(462)Online publication date: 26-Mar-2022
https://doi.org/10.3390/e24040462
Guo CWang L(2018)Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user SecurityAdvances in Cryptology – ASIACRYPT 201810.1007/978-3-030-03326-2_8(213-243)Online publication date: 2-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-03326-2_8
Nachef VPatarin JVolte ENachef VPatarin JVolte E(2017)Luby-Rackoff TheoremsFeistel Ciphers10.1007/978-3-319-49530-9_4(45-53)Online publication date: 22-Feb-2017
https://doi.org/10.1007/978-3-319-49530-9_4
Show More Cited By

Index Terms

Improved security bounds for pseudorandom permutations

Recommendations

Improved upper bound for sorting permutations by prefix transpositions
Abstract
Modelling of chromosomes with permutations has triggered the research of sorting permutations using global rearrangement operations in computational molecular biology. One such rearrangement is transposition which swaps two adjacent ...
How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function
EUROCRYPT'92: Proceedings of the 11th annual international conference on Theory and application of cryptographic techniques

In this paper we will solve two open problems concerning pseudorandom permutations generators.

1. We will see that it is possible to obtain a pseudorandom permutation generator with only three rounds of DES - like permutation and a single pseudorandom ...
A construction for super pseudorandom permutations from a single pseudorandom function
EUROCRYPT'92: Proceedings of the 11th annual international conference on Theory and application of cryptographic techniques

In this paper, we show how to construct a super pseudorandom permutation generator from a single pseudorandom function generator, based on DES-like permutations. First, we show ψ(g, 1, f, g, 1, f), which consists of six rounds of DES-like permutations ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCS '97: Proceedings of the 4th ACM conference on Computer and communications security

April 1997

161 pages

ISBN:0897919122

DOI:10.1145/266420

Chairmen:
Richard Graveman
Bellcore
,
Phil Janson
IBM Zurich Research Lab., Zurich, Switzerland
,
Clifford Neumann
USC Information Sciences Institute
,
Li Gong
JavaSoft

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

4CCS97

Sponsor:

SIGSAC

4CCS97: 4th ACM Conference on Computer & Communications Security

April 1 - 4, 1997

Zurich, Switzerland

Acceptance Rates

CCS '97 Paper Acceptance Rate 17 of 64 submissions, 27%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
583
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)7

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jha ANandi M(2022)A Survey on Applications of H-Technique: Revisiting Security Analysis of PRP and PRFEntropy10.3390/e2404046224:4(462)Online publication date: 26-Mar-2022
https://doi.org/10.3390/e24040462
Guo CWang L(2018)Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user SecurityAdvances in Cryptology – ASIACRYPT 201810.1007/978-3-030-03326-2_8(213-243)Online publication date: 2-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-03326-2_8
Nachef VPatarin JVolte ENachef VPatarin JVolte E(2017)Luby-Rackoff TheoremsFeistel Ciphers10.1007/978-3-319-49530-9_4(45-53)Online publication date: 22-Feb-2017
https://doi.org/10.1007/978-3-319-49530-9_4
Dinur IDunkelman OKeller NShamir A(2014)Cryptanalysis of Iterated Even-Mansour Schemes with Two KeysAdvances in Cryptology – ASIACRYPT 201410.1007/978-3-662-45611-8_23(439-457)Online publication date: 2014
https://doi.org/10.1007/978-3-662-45611-8_23
Dara SFluhrer S(2014)FNR: Arbitrary Length Small Domain Block Cipher ProposalSecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-319-12060-7_10(146-154)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1007/978-3-319-12060-7_10
Bowers KJuels AOprea ASion RSong D(2009)Proofs of retrievabilityProceedings of the 2009 ACM workshop on Cloud computing security10.1145/1655008.1655015(43-54)Online publication date: 13-Nov-2009
https://dl.acm.org/doi/10.1145/1655008.1655015
Kaplan ENaor MReingold O(2009)Derandomized Constructions of k-Wise (Almost) Independent PermutationsAlgorithmica10.1007/s00453-008-9267-y55:1(113-133)Online publication date: 22-May-2009
https://dl.acm.org/doi/10.1007/s00453-008-9267-y
Patarin J(2008)A proof of security in O(2n) for the Benes schemeProceedings of the Cryptology in Africa 1st international conference on Progress in cryptology10.5555/1788634.1788655(209-220)Online publication date: 11-Jun-2008
https://dl.acm.org/doi/10.5555/1788634.1788655
Yasuda K(2008)A One-Pass Mode of Operation for Deterministic Message Authentication-- Security beyond the Birthday BarrierFast Software Encryption10.1007/978-3-540-71039-4_20(316-333)Online publication date: 10-Feb-2008
https://dl.acm.org/doi/10.1007/978-3-540-71039-4_20
Patarin J(2008)A Proof of Security in O(2 n ) for the Benes SchemeProgress in Cryptology – AFRICACRYPT 200810.1007/978-3-540-68164-9_14(209-220)Online publication date: 2008
https://doi.org/10.1007/978-3-540-68164-9_14
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improved upper bound for sorting permutations by prefix transpositions

How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function

A construction for super pseudorandom permutations from a single pseudorandom function