Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

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 ?

share|improve this question
1  
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

1 Answer

up vote 1 down vote

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.

This garbling property (where any change in the ciphertext will make a random change in the plaintext) is the best we can do if the ciphertext must be the same size as the plaintext. Generally, that is not considered good enough, and usually we include an authenticate operation which makes the ciphertext strictly larger than the plaintext, but also makes sure that any change in the ciphertext will cause the decryptor to reject the modified message (rather than emitting a random decryption).

share|improve this answer
Thank you for your reply. When Bob receives C1 & C2, he decrypts and retrieves m and P(x) and since Bob knows all coeficients of the polynomial and x, he can verify by replacing m in P(x) ... I think that the integrity is provided since the attacker who want to inject C1' corresponding to m' instead of C1, haven't enough information of P(x) to replace the corresponding C2' .... Bob rejects the modified message My question is : with this method, can we provide both confidentiality & integrity of the plaintext m ? – zof751 Aug 5 '12 at 17:47
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.