|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 402, Pages 91–107
(Mi znsl5240)
|
|
|
|
A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module
S. I. Nikolenkoab, D. S. Tugaryova a Academic University, St. Petersburg, Russia
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia
Abstract:
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.
Key words and phrases:
one-way functions, average-case complexity, tiling problems.
Received: 16.05.2012
Citation:
S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, Combinatorics and graph theory. Part IV, RuFiDiM'11, Zap. Nauchn. Sem. POMI, 402, POMI, St. Petersburg, 2012, 91–107; J. Math. Sci. (N. Y.), 192:3 (2013), 307–315
Linking options:
https://www.mathnet.ru/eng/znsl5240 https://www.mathnet.ru/eng/znsl/v402/p91
|
Statistics & downloads: |
Abstract page: | 161 | Full-text PDF : | 58 | References: | 38 |
|