RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Probl. Peredachi Inf., 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.

Full text: PDF file (339 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2009, 45:2, 168–183

Bibliographic databases:

UDC: 621.391.1+519.4
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

Citation in format AMSBIB
\Bibitem{KojNik09}
\by A.~A.~Kozhevnikov, S.~I.~Nikolenko
\paper On complete one-way functions
\jour Probl. Peredachi Inf.
\yr 2009
\vol 45
\issue 2
\pages 101--118
\mathnet{http://mi.mathnet.ru/ppi1982}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2554711}
\zmath{https://zbmath.org/?q=an:1181.68144}
\transl
\jour Problems Inform. Transmission
\yr 2009
\vol 45
\issue 2
\pages 168--183
\crossref{https://doi.org/10.1134/S0032946009020082}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000268246600008}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-67749127886}


Linking options:
  • http://mi.mathnet.ru/eng/ppi1982
  • http://mi.mathnet.ru/eng/ppi/v45/i2/p101

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46  mathnet  crossref  mathscinet
    2. S. Yu. Erofeev, V. A. Romankov, “O postroenii vozmozhno odnostoronnikh funktsii na osnove algoritmicheskoi nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, PDM, 2012, no. 3(17), 13–24  mathnet
    3. S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, J. Math. Sci. (N. Y.), 192:3 (2013), 307–315  mathnet  crossref  mathscinet
    4. Erofeev S.Yu., Romankov V.A., “O vozmozhnosti postroeniya odnostoronnikh funktsii na osnove nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, Vestnik omskogo universiteta, 2012, no. 2, 53–56  mathscinet  elib
    5. Sotiraki K., Zampetakis M., Zirdelis G., “Ppp-Completeness With Connections to Cryptography”, 2018 IEEE 59Th Annual Symposium on Foundations of Computer Science (Focs), Annual IEEE Symposium on Foundations of Computer Science, ed. Thorup M., IEEE Computer Soc, 2018, 148–158  crossref  mathscinet  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:288
    Full text:69
    References:29
    First page:12

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020