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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra i Analiz:
Year:
Volume:
Issue:
Page:
Find






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


Algebra i Analiz, 2009, Volume 21, Issue 3, Pages 130–144 (Mi aa1142)  

This article is cited in 1 scientific paper (total in 1 paper)

Research Papers

Infinitely frequently one-sided function based on an assumption on complexity in the mean

E. A. Hirsch, D. M. Itsykson

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: We assume the existence of a function $f$ that is computable in polynomial time but cannot be inverted by a randomized average-case polynomial algorithm. The cryptographic setting is, however, different: even for a weak one-way function, a successful adversary should fail on a polynomial fraction of inputs. Nevertheless, we show how to construct an infinitely-often one-way function based on $f$.

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

English version:
St. Petersburg Mathematical Journal, 2010, 21:3, 459–468

Bibliographic databases:

MSC: 68Q15
Received: 29.05.2008

Citation: E. A. Hirsch, D. M. Itsykson, “Infinitely frequently one-sided function based on an assumption on complexity in the mean”, Algebra i Analiz, 21:3 (2009), 130–144; St. Petersburg Math. J., 21:3 (2010), 459–468

Citation in format AMSBIB
\Bibitem{HirIts09}
\by E.~A.~Hirsch, D.~M.~Itsykson
\paper Infinitely frequently one-sided function based on an assumption on complexity in the mean
\jour Algebra i Analiz
\yr 2009
\vol 21
\issue 3
\pages 130--144
\mathnet{http://mi.mathnet.ru/aa1142}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2588765}
\zmath{https://zbmath.org/?q=an:1205.68164}
\transl
\jour St. Petersburg Math. J.
\yr 2010
\vol 21
\issue 3
\pages 459--468
\crossref{https://doi.org/10.1090/S1061-0022-10-01103-9}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000277451000005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84861235113}


Linking options:
  • http://mi.mathnet.ru/eng/aa1142
  • http://mi.mathnet.ru/eng/aa/v21/i3/p130

    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. Hirsch E.A., Itsykson D., Monakhov I., Smal A., “On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography”, Theory Comput. Syst., 51:2 (2012), 179–195  crossref  mathscinet  zmath  isi  elib  scopus
  • Алгебра и анализ St. Petersburg Mathematical Journal
    Number of views:
    This page:265
    Full text:78
    References:25
    First page:24

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