S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank <nobr>$\mathbb Z\times\mathbb Z$</nobr>-module”, Zap. Nauchn. Sem. POMI, 2012, Volume 402,Pages <nobr>91

A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module

S. I. Nikolenko^ab, D. S. Tugaryov^a

^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.

UDC: 510.53

Received: 16.05.2012