<p>Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution.  The $i$th value in the sequence is given by</p>

<p>$$x_i = 2^{128} i + y_i$$</p>

<p>where $y_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y_i$) and where each $y_i$ is 128 bits wide (i.e., $0 \le y_i &lt; 2^{128}$).  For instance, you could use</p>

<p>$$y_i = F(K,i)$$</p>

<p>where $F$ is any pseudorandom function (e.g., AES) with a 128-bit output, and $K$ is a key (the seed from which the entire sequence is generated).</p>

CC BY-SA 3.0
2013-04-21T05:59:10.810Z
2013-04-21T10:55:48.120Z
2013-04-21T10:55:48.120Z
D.W.
<p>I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It should be possible to efficiently find the $k$-th element in the sequence for a given $k$.</p>

<p>Nonexamples:</p>

<ol>
<li><p>A linear congruential generator is not increasing, but it is possible to generate the $k$-th element, $x_k = A^kX_0+(1+\dotsc+A^{k-1})B \pmod{p}$, using $O(log(k))$ arithmetic operations.</p></li>
<li><p>Accumulating the sum of a linear congruential generator gives a sequence with the desired pseudorandomness property, but I don't know how to get the $k$-th element efficiently.</p></li>
</ol>

CC BY-SA 3.0
2012-03-18T20:50:09.923Z
How do you define _efficiently_? Presumably you mean less than $O(k)$.
Dave Clarke
CC BY-SA 3.0
2012-03-18T22:11:53.420Z
@DaveClarke: Yes. Less than O(k). And hopefully much closer to O(log(k)).
user302099
CC BY-SA 3.0
2012-03-18T22:26:33.820Z
Are you sure that the sequence $\{x_k\}$ defined by recurrence $x_{k+1}=Ax_k+B \bmod p$ is pseudorandom enough for you?  It is not pseudorandom in almost any definition because given p (which is usually fixed), the whole sequence can be predicted from the first three terms.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-19T09:19:50.117Z
Please define "pseudorandom".  Do you mean "approximately uniform"?  Or do you just mean "unpredictable"?
Jeffε
CC BY-SA 3.0
2012-03-19T18:41:42.063Z
@JɛﬀE: Unpredictable would be enough.
user302099
CC BY-SA 3.0
2012-03-20T00:40:34.993Z
Did you read my previous comment?
Tsuyoshi Ito
<cr.crypto-security><pseudorandom-generators>
Pseudorandom increasing sequence
user302099
# Pseudorandom increasing sequence

(Asked by: username_0 on 2012-03-18)

I am looking for a way to generate an increasing sequence of integers $(x\_i)$ such that the sequence of differences $(x\_{i+1}-x\_i)$ is pseudorandom (in any common way of defining pseudorandomness). It should be possible to efficiently find the $k$-th element in the sequence for a given $k$.

Nonexamples:

1. A linear congruential generator is not increasing, but it is possible to generate the $k$-th element, $x\_k = A^kX\_0+(1+\dotsc+A^{k-1})B \pmod{p}$, using $O(log(k))$ arithmetic operations.
2. Accumulating the sum of a linear congruential generator gives a sequence with the desired pseudorandomness property, but I don't know how to get the $k$-th element efficiently.

**Tags:** cr.crypto-security, pseudorandom-generators

> **Comments:**
> **username_1**: How do you define _efficiently_? Presumably you mean less than $O(k)$.  
> **username_0**: @DaveClarke: Yes. Less than O(k). And hopefully much closer to O(log(k)).  
> **username_2**: Are you sure that the sequence $\{x_k\}$ defined by recurrence $x_{k+1}=Ax_k+B \bmod p$ is pseudorandom enough for you?  It is not pseudorandom in almost any definition because given p (which is usually fixed), the whole sequence can be predicted from the first three terms.  
> **username_3**: Please define "pseudorandom".  Do you mean "approximately uniform"?  Or do you just mean "unpredictable"?  
> **username_0**: @JɛﬀE: Unpredictable would be enough.  
> **username_2**: Did you read my previous comment?  

---

## 1 answers

### Answer by username_4 on 2013-04-21. Score: 3

Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution. The $i$th value in the sequence is given by

$$x\_i = 2^{128} i + y\_i$$

where $y\_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y\_i$) and where each $y\_i$ is 128 bits wide (i.e., $0 \le y\_i < 2^{128}$). For instance, you could use

$$y\_i = F(K,i)$$

where $F$ is any pseudorandom function (e.g., AES) with a 128-bit output, and $K$ is a key (the seed from which the entire sequence is generated).


---

