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

**Category / Keywords: **Arithmetic progression, sequence, pseudorandom number, factoring, Euclidean algorithm, authenticated encryption

**Date: **received 10 Apr 2017, last revised 14 Apr 2017

**Contact author: **sricheru1214 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20170417:143303 (All versions of this report)

**Short URL: **ia.cr/2017/324

[ Cryptology ePrint archive ]