Characterizing the existence of one-way permutations

被引：9
作者：
Hemaspaandra, LA
Rothe, J
机构：
[1] Univ Rochester, Dept Comp Sci, Rochester, NY 14627 USA
[2] Univ Jena, Inst Informat, D-07740 Jena, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2000年 / 244卷 / 1-2期
关键词：
one-way permutations; one-way functions; ranking; worst-case cryptography; computational complexity;
D O I：
10.1016/S0304-3975(00)00014-1
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We establish a condition necessary and sufficient for the existence of one-way permutations: One-way permutations exist if and only if there exist total one-one one-way functions whose range is P-rankable. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：257 / 261
页数：5
相关论文
共 13 条
  • [1] [Anonymous], 1982, 23 ANN S FDN COMPUTE, DOI DOI 10.1109/SFCS.1982.45
  • [2] Inverting onto functions
    Fenner, SA
    Fortnow, L
    Naik, AV
    Rogers, JD
    [J]. ELEVENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1996, : 213 - 222
  • [3] COMPRESSION AND RANKING
    GOLDBERG, AV
    SIPSER, M
    [J]. SIAM JOURNAL ON COMPUTING, 1991, 20 (03) : 524 - 536
  • [4] Goldsmith J., 1992, Computational Complexity, V2, P18, DOI 10.1007/BF01276437
  • [5] COMPLEXITY-MEASURES FOR PUBLIC-KEY CRYPTOSYSTEMS
    GROLLMANN, J
    SELMAN, AL
    [J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (02) : 309 - 335
  • [6] A pseudorandom generator from any one-way function
    Hästad, J
    Impagliazzo, R
    Levin, LA
    Luby, M
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 28 (04) : 1364 - 1396
  • [7] ON THE COMPLEXITY OF RANKING
    HEMACHANDRA, LA
    RUDICH, S
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (02) : 251 - 271
  • [8] Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
    Hemaspaandra, LA
    Rothe, J
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (03) : 648 - 659
  • [9] Easy sets and hard certificate schemes
    Hemaspaandra, LA
    Rothe, J
    Wechsung, G
    [J]. ACTA INFORMATICA, 1997, 34 (11) : 859 - 879
  • [10] Impagliazzo R., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P44, DOI 10.1145/73007.73012
12