• New Combinatorial Complete One...

Treffer: New Combinatorial Complete One-Way Functions

Title:
New Combinatorial Complete One-Way Functions
Authors:
Kojevnikov, Arist, Nikolenko, Sergey, I.
Contributors:
St. Petersburg Department of V.A. Steklov Mathematical Institute (PDMI RAS), Steklov Mathematical Institute [Moscow] (SMI | RAS), Russian Academy of Sciences [Moscow] (RAS)-Russian Academy of Sciences [Moscow] (RAS), Susanne Albers, Pascal Weil
Source:
STACS 2008. :457-466
Publisher Information:
HAL CCSD; IBFI Schloss Dagstuhl, 2008.
Publication Year:
2008
Collection:
collection:STACS2008
Subject Terms:
cryptography, complete problem, one-way function, ACM E.3; F.1.1; F.1.3, [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC], [INFO.INFO-CR]Computer Science [cs], Cryptography and Security [cs.CR]
Subject Geographic:
Bordeaux, France
Original Identifier:
ARXIV: 0802.2863
HAL: hal-00232966
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0802.2863
Access URL:
https://hal.science/hal-00232966
https://hal.science/hal-00232966/document
https://hal.science/hal-00232966/file/Kojevnikov.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00232966v1
Database:
HAL

Weitere Informationen

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.