On complete one-way functions | Zendy

A. A. Kozhevnikov | Zendy; Sergey Nikolenko | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On complete one-way functions

Author(s) -

A. A. Kozhevnikov,

Sergey Nikolenko

Publication year - 2009

Publication title -

problems of information transmission

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.525

H-Index - 19

eISSN - 1608-3253

pISSN - 0032-9460

DOI - 10.1134/s0032946009020082

Subject(s) - rewriting , mathematics , string (physics) , function (biology) , np complete , cryptography , discrete mathematics , algebra over a field , combinatorics , algorithm , pure mathematics , computer science , time complexity , evolutionary biology , mathematical physics , biology , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research