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

**Category / Keywords: **foundations / one-way functions, one-way permutations, quasigroup string transformations

**Publication Info: **Submitted to Conference

**Date: **received 27 Sep 2005, last revised 7 Oct 2005

**Contact author: **gligoroski at yahoo com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20051009:091927 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]