|
Problemy Peredachi Informatsii, 2009, Volume 45, Issue 2, Pages 101–118
(Mi ppi1982)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Large Systems
On complete one-way functions
A. A. Kozhevnikov, S. I. Nikolenko St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
Complete constructions play an important role in theoretical computer science. However, in cryptography complete constructions have so far been either absent or purely theoretical. In 2003, L. A. Levin presented the idea of a combinatorial complete one-way function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post correspondence problem. We also present the properties of a combinatorial problem that allow a complete one-way function to be based on this problem. The paper also gives an alternative proof of Levin's result.
Received: 19.05.2008 Revised: 20.01.2009
Citation:
A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Probl. Peredachi Inf., 45:2 (2009), 101–118; Problems Inform. Transmission, 45:2 (2009), 168–183
Linking options:
https://www.mathnet.ru/eng/ppi1982 https://www.mathnet.ru/eng/ppi/v45/i2/p101
|
|