Geodesic
A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 91-107 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

It is known that the subsemimodule membership problem for finite rank free $\mathbb Z\times\mathbb Z$-modules is undecidable. Modifying the undecidability construction, we present a complete one-way function based on finite rank free $\mathbb Z\times\mathbb Z$-modules. 
@article{ZNSL_2012_402_a6,
     author = {S. I. Nikolenko and D. S. Tugaryov},
     title = {A complete one-way function based on a~free finite rank $\mathbb Z\times\mathbb Z$-module},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {91--107},
     year = {2012},
     volume = {402},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a6/}
}
TY  - JOUR
AU  - S. I. Nikolenko
AU  - D. S. Tugaryov
TI  - A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 91
EP  - 107
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a6/
LA  - ru
ID  - ZNSL_2012_402_a6
ER  - 
%0 Journal Article
%A S. I. Nikolenko
%A D. S. Tugaryov
%T A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 91-107
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a6/
%G ru
%F ZNSL_2012_402_a6
S. I. Nikolenko; D. S. Tugaryov. A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 91-107. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a6/

[1] Sanjeev Arora, Boaz Barak, Complexity Theory: A Modern Approach, Cambridge University Press, 2009 | MR | Zbl

[2] Andrej Bogdanov, Luca Trevisan, “Average-case complexity”, Foundations and Trends in Theoretical Computer Science, 2 (2006), 1–106 | DOI | MR

[3] Egon Börger, Erich Grädel, Yuri Gurevich, The classical decision problem, Springer-Verlag, Berlin, 2001 | MR

[4] Stephen A. Cook, “The complexity of theorem-proving procedures”, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, 151–158 | Zbl

[5] Michael R. Garey, David S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, CA, 1979 | MR | Zbl

[6] Oded Goldreich, Foundations of Cryptography. Basic Tools, Cambridge University Press, 2001 | MR | Zbl

[7] Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev, “A complete public-key cryptosystem”, Groups, Complexity, and Cryptology, 1 (2009), 1–12 | DOI | MR

[8] Yuri Gurevich, “Average case completeness”, J. Comput. System Sciences, 42:3 (1991), 346–398 | DOI | MR | Zbl

[9] D. Harnik, J. Kilian, M. Naor, O. Reingold, A. Rosen, “On robust combiners for oblivious transfers and other primitives”, Proceedings of EuroCrypt 2005, Lecture Notes in Computer Science, 3494, 2005, 96–113 | DOI | MR | Zbl

[10] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 2000 | MR

[11] John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979 | MR | Zbl

[12] Richard M. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Computations, Plenum, New York, 1972, 85–103 | MR

[13] Leonid A. Levin, “Average case complete problems”, SIAM J. of Computing, 15:1 (1986), 285–286 | DOI | MR | Zbl

[14] Leonid A. Levin, “One-way functions and pseudorandom generators”, Combinatorica, 7:4 (1987), 357–363 | DOI | MR

[15] Leonid A. Levin, “The tale of one-way functions”, Probl. Information Transmission, 39:1 (2003), 92–103 | DOI | MR

[16] Markus Lohrey, Benjamin Steinberg, “Tilings and submonoids of metabelian groups”, Theory of Computing Systems, 48:2 (2011), 411–427 | DOI | MR | Zbl

[17] Sergey I. Nikolenko, Provably Secure Constructions in Cryptography, Lamberts Academic Publishing, 2011 | Zbl

[18] Christos Harilaos Papadimitriou, Complexity Theory, Addison Wesley, 1994 | Zbl

[19] Jan van Leeuwen (editor), Handbook of Theoretical Computer Science, v. A, Algorithms and Complexity, The MIT Press/Elsevier, 1990 | MR

[20] Jie Wang, “Average-case intractible NP problems”, Advances in Languages, Algorithms, and Complexity, 1998, 313–378 | MR

[21] A. A. Kozhevnikov, S. I. Nikolenko, “O polnykh odnostoronnikh funktsiyakh”, Problemy peredachi informatsii, 45:2 (2009), 101–118 | MR | Zbl

[22] L. A. Levin, “Universalnye perebornye zadachi”, Problemy peredachi informatsii, 9:3 (1973), 115–116 | MR | Zbl

[23] L. A. Levin, “Odnostoronnie funktsii”, Problemy peredachi informatsii, 39:1 (2003), 103–117 | MR | Zbl