# How hard is it to learn a linear modular function?

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

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$?

• 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 Jan 31 '13 at 9:24
• @Aryeh: I think that that is a different question. In this question, I assume that k is given. – Tsuyoshi Ito Jan 31 '13 at 22:53
• 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: 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 cc.gatech.edu/~cpeikert/pubs/prf-lattice.pdf and can be implemented in $TC0$. – Daniel Apon Feb 1 '13 at 4:50
• Short version: In answer to the TITLE, noisy linear modular functions are believed to be pseudorandom in the hardest case. – Daniel Apon Feb 1 '13 at 4:54
• @Daniel, $(5 \mod 3) \mod 2 = 2 \mod 2 = 0$, $5 \mod 2 = 1$. – Kaveh Feb 1 '13 at 5:09

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 (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:

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.

• [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 Feb 28 '13 at 1:11
• [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 Information Security is randomized/probabilistic. – Kaveh Feb 28 '13 at 1:12
• @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. Feb 28 '13 at 1:13
• You are correct, my mistake. – Kaveh Feb 28 '13 at 1:37