On a Family of Minimal Candidate One-way Functions and One-way Permutations
Danilo Gligoroski · 2009
In order to achieve computational workload equivalent to the exhaustive key search of an n-bit key for inversion of RSA or Diffie-Hellman one-way candidate functions the length of their arguments have to have from 10n to 60n bits. One-way functions based on Elliptic Curves in this moment are holding the record, demanding only 2n bits for their arguments. In this paper we propose a definition and construction of a new family of one-way candidate functions RN: Q N → Q N, where Q = {0, 1,..., s − 1} is an alphabet with s elements. Special instances of these functions can be permutations (i.e. one-way permutations). These one-way functions have the property that for achieving the security level equivalent of exhaustive key search of n-bit key, only n bits of input are needed. Keywords: One-way functions, one-way permutations, quasigroup string transformations 1