International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Danilo Gligoroski
Download:
URL: http://eprint.iacr.org/2005/352
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12686,
  title={Candidate One-Way Functions and One-Way Permutations Based on Quasigroup String Transformations},
  booktitle={IACR Eprint archive},
  keywords={foundations / one-way functions, one-way permutations, quasigroup string transformations},
  url={http://eprint.iacr.org/2005/352},
  note={Submitted to Conference gligoroski@yahoo.com 13064 received 27 Sep 2005, last revised 7 Oct 2005},
  author={Danilo Gligoroski},
  year=2005
}