Paper 2017/324

Family of PRGs based on Collections of Arithmetic Progressions

Srikanth ch, Veni Madhavan C.E. and Kumar Swamy H.V.

Abstract

We propose a theory on the object: collection of arithmetic progressions with elements satisfying the property: $j^{th}$ terms of $i^{th}$ and $(i+1)^{th}$ progressions of the collection are multiplicative inverses of each other modulo the $(j+1)^{th}$ term of $i^{th}$ progression. Under certain conditions, such a collection is uniquely generated from a pair of co-prime seed integers. In this work, we present one application of this object to construction of a new family of pseudo random number generators (PRG). The amortized cost per bit is shown to be $O(1)$ for keystream generation. This result is supported by empirical data. One interesting aspect of the defined object is its connection to the standard Euclidean algorithm for finding the gcd of two numbers. The connection is useful in our proof of the amortized cost, which is based on results concerning the average behavior of the quotient sequence of the Euclidean algorithm. In security analysis, we study the difficulty of the inverse problem of recovering the seed pair from the keystream of the proposed method(s). Based on this study, we deduce a lower bound on the sizes for secret parameters that provide adequate security. The study of the inverse problem establishes a computational equivalence between a special case of it (defined as Problem A) and the problem of factoring integers. We present an authenticated encryption scheme which is another application of the defined object. The present work leaves some open issues which we presently are addressing in our ongoing work.