New Combinatorial Complete One-Way Functions

Authors Arist Kojevnikov, Sergey I. Nikolenko



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1365.pdf
  • Filesize: 151 kB
  • 10 pages

Document Identifiers

Author Details

Arist Kojevnikov
Sergey I. Nikolenko

Cite AsGet BibTex

Arist Kojevnikov and Sergey I. Nikolenko. New Combinatorial Complete One-Way Functions. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 457-466, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1365

Abstract

In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a 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 and prove their completeness. Besides, we present an alternative proof of Levin's result. We also discuss the properties a combinatorial problem should have in order to hold a complete one-way function.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail