RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2012 Number 3(17), Pages 13–24 (Mi pdm374)

Theoretical Foundations of Applied Discrete Mathematics

On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups

S. Y. Erofeev, V. A. Romankov

Omsk State University, Omsk, Russia

Abstract: The paper considers a schema for constructing a possibly one-way function on a group with the decidable word problem and undecidable endomorphism problem. Possible prerequisites for reliability of the proposed schema are analyzed. A corresponding authentication protocol with zero knowledge is proposed as an application. It is noted that for its security a more strong assumption on the undecidability of the two-level endomorphism problem is needed.

Keywords: one-way function, endomorphism problem, authentication protocol.

UDC: 512.62



© Steklov Math. Inst. of RAS, 2024