The Tale of One-Way Functions

被引：35
|
作者：
L. A. Levin
机构：
[1] Boston University,
来源：
Problems of Information Transmission | 2003年 / 39卷 / 1期
关键词：
System Theory; Unify Approach; Basic Definition; Computer Theory;
D O I：
10.1023/A:1023634616182
中图分类号：
学科分类号：
摘要：
The existence of one-way functions (owf) is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.
引用
收藏
页码：92 / 103
页数：11
相关论文
共 50 条
  • [1] ON ONE-WAY FUNCTIONS
    WATANABE, O
    COMBINATORICS, COMPUTING AND COMPLEXITY, 1989, : 98 - 131
  • [2] One-way functions
    Levin, L.A.
    Problemy Peredachi Informatsii, 2003, 39 (01): : 103 - 117
  • [3] On continuous one-way functions
    Ko, Ker-, I
    Wu, Lidong
    THEORETICAL COMPUTER SCIENCE, 2021, 852 : 1 - 17
  • [4] Semigroups and one-way functions
    Birget, J. C.
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2015, 25 (1-2) : 3 - 36
  • [5] On complete one-way functions
    A. A. Kozhevnikov
    S. I. Nikolenko
    Problems of Information Transmission, 2009, 45 : 168 - 183
  • [6] Separability and one-way functions
    Lance Fortnow
    John D. Rogers
    computational complexity, 2002, 11 : 137 - 157
  • [7] Physical one-way functions
    Pappu, R
    Recht, R
    Taylor, J
    Gershenfeld, N
    SCIENCE, 2002, 297 (5589) : 2026 - 2030
  • [8] ON HARDNESS OF ONE-WAY FUNCTIONS
    WATANABE, O
    INFORMATION PROCESSING LETTERS, 1988, 27 (03) : 151 - 157
  • [9] ONE-WAY HASH FUNCTIONS
    SCHNEIER, B
    DR DOBBS JOURNAL, 1991, 16 (09): : 148 - 150
  • [10] Separability and one-way functions
    Fortnow, L
    Rogers, JD
    COMPUTATIONAL COMPLEXITY, 2002, 11 (3-4) : 137 - 157
12345