Paper 2005/352

Candidate One-Way Functions and One-Way Permutations Based on Quasigroup String Transformations

Danilo Gligoroski

Abstract

In this paper we propose a definition and construction of a new family of one-way candidate functions ${\cal R}_N:Q^N \rightarrow Q^N$, where $Q=\{0,1,\ldots,s-1\}$ is an alphabet with $s$ elements. Special instances of these functions can have the additional property to be permutations (i.e. one-way permutations). These one-way functions have the property that for achieving the security level of $2^n$ computations in order to invert them, only $n$ bits of input are needed. The construction is based on quasigroup string transformations. Since quasigroups in general do not have algebraic properties such as associativity, commutativity, neutral elements, inverting these functions seems to require exponentially many readings from the lookup table that defines them (a Latin Square) in order to check the satisfiability for the initial conditions, thus making them natural candidates for one-way functions.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Submitted to Conference
Keywords
one-way functionsone-way permutationsquasigroup string transformations
Contact author(s)
gligoroski @ yahoo com
History
2005-10-09: received
Short URL
https://ia.cr/2005/352
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/352,
      author = {Danilo Gligoroski},
      title = {Candidate One-Way Functions and One-Way Permutations Based on Quasigroup String Transformations},
      howpublished = {Cryptology ePrint Archive, Paper 2005/352},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/352}},
      url = {https://eprint.iacr.org/2005/352}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.