NDLI: The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives

Please wait, while we are loading the content...

The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives

Content Provider	Springer Nature Link
Author	Chang, Yan Cheng Hsiao, Chun Yuan Lu, Chi Jen
Copyright Year	2005
Abstract	We know that trapdoor permutations can be used to construct all kinds of basic cryptographic primitives, including trapdoor functions, public-key encryption, private information retrieval, oblivious transfer, key agreement, and those known to be equivalent to one-way functions such as digital signature, private-key encryption, bit commitment, pseudo-random generator and pseudo-random functions. On the other hand, trapdoor functions are not as powerful as trapdoor permutations, so the structural property of permutations seems to be something special that deserves a more careful study. In this paper we investigate the relationships between one-way permutations and all these basic cryptographic primitives. Following previous works, we focus on an important type of reductions called black-box reductions. We prove that no such reductions exist from one-way permutations to either trapdoor functions or private information retrieval. Together with previous results, all the relationships with one-way permutations have now been established, and we know that no such reductions exist from one-way permutations to any of these primitives except trapdoor permutations. This may have the following meaning, with respect to black-box reductions. We know that one-way permutations imply none of the primitives in "public cryptography," where additional properties are required on top of "one-wayness" \cite{IR89}, so permutations cannot be traded for any of these additional properties. On the other hand, we now know that none of these additional properties can be traded for permutations either. Thus, being a permutation seems to be something orthogonal to those additional properties on top of one-wayness. Like previous non-reducibility results, our proofs follow the oracle separation paradigm of Impagliazzo and Rudich.
Starting Page	97
Ending Page	114
Page Count	18
File Format	PDF
ISSN	09332790
Journal	Journal of Cryptology
Volume Number	19
Issue Number	1
e-ISSN	14321378
Language	English
Publisher	Springer-Verlag
Publisher Date	2005-08-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computational Mathematics and Numerical Analysis Combinatorics Probability Theory and Stochastic Processes Communications Engineering, Networks Coding and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Black-Box Model for Cryptographic Primitives

Selecting Cryptographic Key Sizes

Short Non-Interactive Cryptographic Proofs

Security and Composition of Multiparty Cryptographic Protocols

Practical Aspects of Quantum Cryptographic Key Distribution

Obfuscation for Cryptographic Purposes

Enhancements of Trapdoor Permutations

Constructing Pseudo-Random Permutations with a Prescribed Structure

On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited

The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives

Similar Documents

The Black-Box Model for Cryptographic Primitives

Selecting Cryptographic Key Sizes

Short Non-Interactive Cryptographic Proofs

Security and Composition of Multiparty Cryptographic Protocols

Practical Aspects of Quantum Cryptographic Key Distribution

Obfuscation for Cryptographic Purposes

Enhancements of Trapdoor Permutations

Constructing Pseudo-Random Permutations with a Prescribed Structure

On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited

The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives