# Randomized stream cipher using multivariant quadratic equations

This is an idea I had for cipher that I thought might reduce to a known hard problem. It is efficient (compared to something like BBS) in terms of time but not in terms of space.

Here's the algorithm:

1. Produce 128 real random streams equal in length to the plain-text. (These do not need to be secret, they can be published with the cipher text.)
2. Let each bit of the 128-bit streams define the terms of a multi-variant quadratic polynomial in 128 variables over GF(2). One way to do this would be to label each stream as defining a specific term to multiply.
3. Split the secret key in to 128-bit 1 bit variables and substitute in to the equation take from step 2.
4. The resultant bit is then XORed with the plain-text to produce cipher-text.
5. Repeat for all bits in the plain-text and transmit the cipher-text plus the 128-bit key-streams.

My security argument is that solving systems of multivariant quadratic equations in a lot of variables is a known hard problem. In the average case, it is meant to be NP Hard.

All I've done is randomized the selection of the specific instance of the problem. Of course, very quickly the system would become over-determined which might aid solution of the problem.

My question is whether I've made a mistake somewhere or misunderstood something?

-
1) Most proofs are asymptotic and don't tell you anything about concrete sizes of the problem. BBS has concrete proofs too, and those require much bigger modulus sizes than most people expect. 2) You need a proof that a problem choses in the manner you do is hard too. I believe some knapsack based cryptosystems fell to this. –  CodesInChaos Sep 5 '12 at 10:50
Yeah, step two is a bit handwavey and is probably where the security is made or lost. You'd need to prove that step 2 really defines a difficult set of equations in the average case. My question is whether I've generally misunderstood the underlying problem or whether I've broadly got it right and that this would actually work if all the details were ironed out? –  Simon Johnson Sep 5 '12 at 11:00
@Thomas - no, sorry, the streams can be published publicly with the cipher-text. I try to depend on MQ to make sure that even with the streams being public knowledge, the key can not be computed. –  Simon Johnson Sep 5 '12 at 11:59
@SimonJohnson Oh, right, I see, my bad - I will delete my previous comment as it serves no purpose. –  Thomas Sep 5 '12 at 12:01

Summary. This scheme is insecure. It can be cryptanalyzed using standard methods from the cryptanalytic literature. It also has poor performance.

Your algorithm. To summarize your scheme, in your algorithm a one-bit message $m \in GF(2)$ is encrypted by picking a random quadratic polynomial $p(x_1,\dots,x_{128})$ in $GF(2)[x_1,\dots,x_{128}]$, setting $c = m \oplus p(k)$, and transmitting $p(x_1,\dots,x_{128})$ and $c$. Here $k \in GF(2)^{128}$ is the key, and $k$ remains fixed for all messages (while in contrast $p$ is chosen afresh for each message).

Performance. This scheme expands the length of the message by a huge amount: by a factor of 16384 or so. That's an enormous overhead. Existing schemes don't have that problem. Also, I expect that it would be very slow (compared to state-of-the-art stream ciphers), since for each bit encrypted, you have to pick 16384 pseudorandom bits and then evaluate the polynomial.

Algorithmic background: solving multivariate equations. There has been a lot of work in the cryptographic literature on the hardness of solving a system of multivariate equations. One of the fundamental techniques is relinearization.

If you have $n^2$ systems of equations, where each equation is of degree $\le 2$ (i.e., a multivariate quadratic equation) and where you have $n$ unknowns, then relinearization can solve the system of equations in polynomial time (approx. $O(n^6)$ time or less).

Actually, you don't even need relinearization to solve this problem: simple linearization is sufficient. In particular, if $x_1,\dots,x_n$ denote the unknowns, then for each pair $x_i,x_j$ of unknowns, you introduce a new variable $y_{i,j} = x_i x_j$. Now we treat the $y_{i,j}$'s as additional unknowns. With these additional unknowns, each equation is now a linear equation (in the $x_i$'s and $y_{i,j}$'s). How many unknowns are there now? Well, there are about $n^2/2$ of the $y_{i,j}$'s, and another $n$ of the $x_i$'s. Consequently, we have $n^2$ linear equations in $\approx 0.5 n^2$ unknowns. Since there are more equations than unknowns, we can use standard linear algebra to solve these linear equations. The answer provides a solution to our original system of quadratic equations.

Relinearization is a generalization of this idea that works with a smaller number of equations, at some cost in running time.

For more on this subject, see the following research paper:

Cryptanalysis. With this background, it then becomes easy to see how to cryptanalyze your system. Each bit of ciphertext reveals one quadratic equation on 128 unknowns, where the unknowns are the bits of the key $k$. If we're given 16384 bits of known plaintext, then we have $16384 = 128^2$ quadratic equations in 128 unknowns. Now we can apply linearization to recover the key. (With relinearization, we could reduce the amount of known-plaintext required, but 16384 bits of known plaintext is already a very modest requirement, so the simple linearization attack is already devastating.)

Therefore, this algorithm falls to a simple known-plaintext attack. For that reason, it does not meet the standard security requirements and is not suitable for use.

-
Why are $n^2$ plaintext bits required instead of $n^2/2$? –  Antimony Dec 14 '13 at 21:53
@Antimony, yeah, $n^2/2$ should suffice. I wasn't trying to optimize the constant factors (just laziness). Thank you. –  D.W. Dec 15 '13 at 3:24