Randomized stream cipher using multivariant quadratic equations

Question

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?

Answer 1

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 of the HFE Public Key Cryptosystem. Aviad Kipnis and Adi Shamir. CRYPTO 1999.

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.