<p>I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$.  (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one.  Of course, the running time of this method is exponential in $n$, so I assume it is not what you are looking for.)</p>

<p><strong>In the case where $p=m$</strong>, this generator is known as a linear congruential generator.  It is known to be weak.  See my answer to <a href="https://security.stackexchange.com/q/4268/971">Cracking a linear congruential generator</a> (on IT Security.Stack Exchange) for an efficient algorithm that breaks this pseudorandom generator.</p>

<p>To summarize the  security of the generator (when $p=m$): A constant number of samples is enough to break the generator.  The algorithm requires only simple arithmetic and requires only a constant number of additions and multiplications, followed by a gcd operation.  I don't know whether this generator going to be pseudorandom for any particular complexity class, like TC0 or AC0; perhaps others will have insights on that.</p>

<p>Note that if you are picky about requiring a cryptanalysis algorithm to succeed with probability 1, and run in polynomial time without any randomness, then you won't like my algorithm.  My algorithm runs in polynomial time, and succeeds in recovering $f$ on an overwhelming majority of inputs; as a consequence, it succeeds in distinguishing the output of this pseudorandom generator from a true-random stream with advantage close to 1.  In the cryptographic world, this constitutes a "break" of the security of the generator.  However, if you wanted a learning algorithm that succeeds (in recovering $f$) on <em>all</em> problem instances, and has a fixed running time, my algorithm isn't it.  (Then again, from an engineering perspective, if you want something that is guaranteed to succeed on all problem instances, you won't find it, since any real-life implementation always has some small chance of producing an incorrect answer, e.g., due to a cosmic-ray bit flip.  My algorithm infers $f$ correctly for all but an exponentially small fraction of inputs. You can choose parameters so the probability of error due to unlucky choice of inputs is smaller than the probability of error due to a cosmic ray causing a bit flip error. So from an engineering perspective, it's essentially as good as deterministic, for all practical purposes.  But it's possible it might not be what you are looking for, if you care more about complexity classes than about whether the generator is usefully secure in an engineering sense.)</p>

<p><strong>In the general case</strong>, I don't know what the most efficient cryptanalysis algorithm will be, but I would be pretty surprised if this is secure.  Linear congruential generators are notorious in the cryptographic community for being insecure.  However, you might enjoy the following paper, which while it does not address the specific question you asked, is somehow related:</p>

<ul>
<li><a href="http://asterix.cs.gsu.edu/crypto/p129-boyar.pdf" rel="nofollow noreferrer">Inferring sequences produced by a linear congruential generator missing low-order bits</a>.  J. Boyar.  J. ACM 36(1), pp.129--141, Jan 1989.</li>
</ul>

<p>Also, since $m$ is not a divisor of $p$, note that there will be a statistical bias of the outputs of this generator.  In particular, values in the range $0 .. b-1$ will be slightly more likely than values in the range $b .. p-1$, where $b= p \bmod m$.  The magnitude of this bias depends (roughly) upon the size of $p/m$; the larger $p/m$ is, the greater the bias.  More precisely, the statistical variation distance between pseudorandom and random, due to this effect, is $\delta = 2b(m-b)/mp$, for a single sample.  Therefore, I would expect that $O(1/\delta^2)$ samples should suffice to distinguish the pseudorandom stream from a truly random stream, simply by exploiting this bias.  This attack does not take into account all of the available structure in the output of the generator, so I would expect that better attacks are probably possible.</p>

CC BY-SA 3.0
2013-02-28T01:11:21.273Z
[edited comments]: It seems to me that you are not answering the question OP has asked completely: 1. you are using a model of computation which allows constant time addition and multiplication (similar to RAM models), that is not the default model for complexity theory (Turing machines or circuits). Multiplication is complete for complexity class $\mathsf{TC^0}$ and provably not computable in $\mathsf{AC^0}$. GCD is not known to be in $\mathsf{NC}$, so it is not clear if your algorithm is in $\mathsf{NC}$, let alone in $\mathsf{TC^0}$ or $\mathsf{AC^0}$, i.e. it can still be secrue
Kaveh
CC BY-SA 3.0
2013-02-28T01:12:47.703Z
[cont.] against $\mathsf{AC^0}$, $\mathsf{TC^0}$, or even $\mathsf{NC}$ . In practical crypto we may only care about the running time, however in complexity theory, particularly in small complexity classes like these the issue is more delicate. 2. It also seems to me that the algorithm on [security.se] is randomized/probabilistic.
Kaveh
CC BY-SA 3.0
2013-02-28T01:13:06.657Z
@Kaveh, OK, good points about TC0/AC0!  The OP asked 4 questions.  I answered the first 3, but I don't claim to have an answer to the 4th question about AC0/TC0.  As far as randomization, see my other comment.
D.W.
CC BY-SA 3.0
2013-02-28T01:37:04.567Z
You are correct, my mistake.
Kaveh
CC BY-SA 3.0
2013-02-28T00:46:33.690Z
2013-02-28T01:35:22.200Z
2017-03-17T10:46:00.600Z
D.W.
<p>Let $k$ be a fixed number.
Consider the following task $Q$: </p>

<blockquote>
  <p>We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $a,b,m,p \in [2^n]$ are some unknown values.
  The task is to find $f$.</p>
</blockquote>

<p>I have a couple of questions about this problem:</p>

<ol>
<li><p>How hard is this problem? </p></li>
<li><p>If we choose $a,b,p,m$ randomly but "wisely" will $f$ be a pseudorandom number generator secure against TC0 or AC0 circuits?</p></li>
<li><p>What is the smallest value of $k$ where $Q$ can be solved?</p></li>
<li><p>What is the fastest known algorithm for $Q$?</p></li>
</ol>

CC BY-SA 3.0
2013-01-31T09:24:51.663Z
This isn't really a learning question -- more like a number theory question: How many iterated evalutions of $f$ suffice to recover the values of a,b,m,p exactly?
Aryeh
CC BY-SA 3.0
2013-01-31T22:53:35.240Z
@Aryeh: I think that that is a different question.  In this question, I assume that k is given.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-01T04:45:05.297Z
Perhaps the notation is unclear to me, but isn't $(X\pmod p)\pmod m \equiv X\pmod {\min\{m, p\}}$? What is intended here?
Daniel Apon
CC BY-SA 3.0
2013-02-01T04:50:14.967Z
Also, $ax+b\pmod p$ looks quite close to the LWE problem, where you're given either terms $(a, ax+b\pmod p)$ or $(a, r)\leftarrow U(\mathbb{Z}_p\times\mathbb{Z}_p)$ and asked to distinguish which is the case: http://en.wikipedia.org/wiki/Learning_with_errors

In the canonical LWE case, $x$ is fixed across all samples, and in each sample, $a\leftarrow U(\mathbb{Z}_p)$ and $b$ is drawn from a small Gaussian-like distribution.

The closest related pseudorandom function I'm aware of can be found in http://www.cc.gatech.edu/~cpeikert/pubs/prf-lattice.pdf and can be implemented in $TC0$.
Daniel Apon
CC BY-SA 3.0
2013-02-01T04:54:49.190Z
Short version: In answer to the TITLE, noisy linear modular functions are believed to be pseudorandom in the hardest case.
Daniel Apon
CC BY-SA 3.0
2013-02-01T05:09:52.523Z
@Daniel, $(5 \mod 3) \mod 2 = 2 \mod 2 = 0$, $5 \mod 2 = 1$.
Kaveh
<cc.complexity-theory><cr.crypto-security><lg.learning><pseudorandom-generators>
How hard is it to learn a linear modular function?
Anonymous
# How hard is it to learn a linear modular function?

(Asked by: username_0 on 2013-01-31)

Let $k$ be a fixed number.
Consider the following task $Q$:

> We are given a sequence of numbers $(x\_0,x\_1,\cdots,x\_k)$. We know they satisfy $x\_{k+1}=f(x\_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $a,b,m,p \in [2^n]$ are some unknown values.
> The task is to find $f$.

I have a couple of questions about this problem:

1. How hard is this problem?
2. If we choose $a,b,p,m$ randomly but "wisely" will $f$ be a pseudorandom number generator secure against TC0 or AC0 circuits?
3. What is the smallest value of $k$ where $Q$ can be solved?
4. What is the fastest known algorithm for $Q$?

**Tags:** cc.complexity-theory, cr.crypto-security, lg.learning, pseudorandom-generators
> **Comments:**
> **username_1**: This isn't really a learning question -- more like a number theory question: How many iterated evalutions of $f$ suffice to recover the values of a,b,m,p exactly?  
> **username_2**: @Aryeh: I think that that is a different question.  In this question, I assume that k is given.  
> **username_3**: Perhaps the notation is unclear to me, but isn't $(X\pmod p)\pmod m \equiv X\pmod {\min\{m, p\}}$? What is intended here?  
> **username_3**: Also, $ax+b\pmod p$ looks quite close to the LWE problem, where you're given either terms $(a, ax+b\pmod p)$ or $(a, r)\leftarrow U(\mathbb{Z}_p\times\mathbb{Z}_p)$ and asked to distinguish which is the case: http://en.wikipedia.org/wiki/Learning_with_errors  In the canonical LWE case, $x$ is fixed across all samples, and in each sample, $a\leftarrow U(\mathbb{Z}_p)$ and $b$ is drawn from a small Gaussian-like distribution.  The closest related pseudorandom function I'm aware of can be found in http://www.cc.gatech.edu/~cpeikert/pubs/prf-lattice.pdf and can be implemented in $TC0$.  
> **username_3**: Short version: In answer to the TITLE, noisy linear modular functions are believed to be pseudorandom in the hardest case.  
> **username_4**: @Daniel, $(5 \mod 3) \mod 2 = 2 \mod 2 = 0$, $5 \mod 2 = 1$.  

---

## 1 answers

### Answer by username_5 on 2013-02-28. Score: 9

I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$. (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one. Of course, the running time of this method is exponential in $n$, so I assume it is not what you are looking for.)

**In the case where $p=m$**, this generator is known as a linear congruential generator. It is known to be weak. See my answer to [Cracking a linear congruential generator](https://security.stackexchange.com/q/4268/971) (on IT Security.Stack Exchange) for an efficient algorithm that breaks this pseudorandom generator.

To summarize the security of the generator (when $p=m$): A constant number of samples is enough to break the generator. The algorithm requires only simple arithmetic and requires only a constant number of additions and multiplications, followed by a gcd operation. I don't know whether this generator going to be pseudorandom for any particular complexity class, like TC0 or AC0; perhaps others will have insights on that.

Note that if you are picky about requiring a cryptanalysis algorithm to succeed with probability 1, and run in polynomial time without any randomness, then you won't like my algorithm. My algorithm runs in polynomial time, and succeeds in recovering $f$ on an overwhelming majority of inputs; as a consequence, it succeeds in distinguishing the output of this pseudorandom generator from a true-random stream with advantage close to 1. In the cryptographic world, this constitutes a "break" of the security of the generator. However, if you wanted a learning algorithm that succeeds (in recovering $f$) on *all* problem instances, and has a fixed running time, my algorithm isn't it. (Then again, from an engineering perspective, if you want something that is guaranteed to succeed on all problem instances, you won't find it, since any real-life implementation always has some small chance of producing an incorrect answer, e.g., due to a cosmic-ray bit flip. My algorithm infers $f$ correctly for all but an exponentially small fraction of inputs. You can choose parameters so the probability of error due to unlucky choice of inputs is smaller than the probability of error due to a cosmic ray causing a bit flip error. So from an engineering perspective, it's essentially as good as deterministic, for all practical purposes. But it's possible it might not be what you are looking for, if you care more about complexity classes than about whether the generator is usefully secure in an engineering sense.)

**In the general case**, I don't know what the most efficient cryptanalysis algorithm will be, but I would be pretty surprised if this is secure. Linear congruential generators are notorious in the cryptographic community for being insecure. However, you might enjoy the following paper, which while it does not address the specific question you asked, is somehow related:

* [Inferring sequences produced by a linear congruential generator missing low-order bits](http://asterix.cs.gsu.edu/crypto/p129-boyar.pdf). J. Boyar. J. ACM 36(1), pp.129--141, Jan 1989.

Also, since $m$ is not a divisor of $p$, note that there will be a statistical bias of the outputs of this generator. In particular, values in the range $0 .. b-1$ will be slightly more likely than values in the range $b .. p-1$, where $b= p \bmod m$. The magnitude of this bias depends (roughly) upon the size of $p/m$; the larger $p/m$ is, the greater the bias. More precisely, the statistical variation distance between pseudorandom and random, due to this effect, is $\delta = 2b(m-b)/mp$, for a single sample. Therefore, I would expect that $O(1/\delta^2)$ samples should suffice to distinguish the pseudorandom stream from a truly random stream, simply by exploiting this bias. This attack does not take into account all of the available structure in the output of the generator, so I would expect that better attacks are probably possible.

> **Comments:**
> **username_4**: [edited comments]: It seems to me that you are not answering the question OP has asked completely: 1. you are using a model of computation which allows constant time addition and multiplication (similar to RAM models), that is not the default model for complexity theory (Turing machines or circuits). Multiplication is complete for complexity class $\mathsf{TC^0}$ and provably not computable in $\mathsf{AC^0}$. GCD is not known to be in $\mathsf{NC}$, so it is not clear if your algorithm is in $\mathsf{NC}$, let alone in $\mathsf{TC^0}$ or $\mathsf{AC^0}$, i.e. it can still be secrue  
> **username_4**: [cont.] against $\mathsf{AC^0}$, $\mathsf{TC^0}$, or even $\mathsf{NC}$ . In practical crypto we may only care about the running time, however in complexity theory, particularly in small complexity classes like these the issue is more delicate. 2. It also seems to me that the algorithm on [security.se] is randomized/probabilistic.  
> **username_5**: @Kaveh, OK, good points about TC0/AC0!  The OP asked 4 questions.  I answered the first 3, but I don't claim to have an answer to the 4th question about AC0/TC0.  As far as randomization, see my other comment.  
> **username_4**: You are correct, my mistake.  

---

