# Polynomial for secure communication

Can we use a polynomial $P(x)$ to securely communicate ?

For example Alice & Bob agree on a degree of a polynomial. The value $x$ & the coeficients are generated from a seed using a hash function or any other PRG and change in each communication, the plaintext $m$ is hidden into $P(x)$. For example $P(x) = ax^2+b(m)x+c$

alice sends the result of $P(x)$ to Bob, once received bob retreive $m$ from $P(x)$

can we provide a certain security level with the above method ?

• How do you send the coefficients of the polynomial? And the example presented doesn't make much sense to me, the whole polynomial except the $b(m)x$ term is a constant wrt $m$ so this becomes a simple affine cipher... – Thomas Aug 5 '12 at 12:18
• the coefficients are generated by both participants using the same seed. Suppose Alice and Bob share two keys and Alice uses these keys to encrypt m and the result of p(x). Alice --> Bob : C1 = enc(m), C2 = enc(p(x)) Can bob verify the integrity of m using P(x) ? – zof751 Aug 5 '12 at 12:53

If you're operating in some finite field, and the PRG used to generate the coefficients and $x$ is cryptographically secure (that is, it is infeasible to distinguish the output of the PRG from a truly random source of field elements), and you go back to the PRG for every single message, then it is secure as far as privacy is concerned (of course, you need to make sure that $bx$ is nonzero; otherwise, it might be a bit tricky for the decryptor to recover $m$).
As for integrity, well, if the attacker replaces a ciphertext $C$ with another $C'$, then that will decrypt to some message $m'$, where $m - m' = I(C - C')$ for some invertible element $I$ which is unknown to the attacker. This is why you want to do the operation in a finite field (rather than a finite ring); in a field, $I$ can be any nonzero value, and so while the attacker can make the altered ciphertext decrypt to something else other than m, but he literally has no control beyond that.
On the other hand, the simpler polynomial $P(x) = mx + a$ has the same property; if $a$ and $m$ is generated via cryptographically secure source and you're operating in a finite field, then transmitting $mx+a$ also provides privacy, and prevents the attacker from making nonrandom changes to the decrypted ciphertext.
• @zof751: As I pointed out, if someone replaces $C1$ with $C1'$, the receiver (Bob) decrypts it to form a random message $m'$. How does Bob know that is not the correct message? After all, if Bob knew what the correct message was beforehand, there's no point in sending the message. And, having Bob plug his decrypted message in the polynomial won't tell him anything; that'll just verify that the decrypted message really does correspond to the encrypted message he received. – poncho Aug 5 '12 at 18:03