I a problem that essentially boils down to the following:

There is raw data, D, encrypted with key K (call its encrypted form E). The same raw data, D, is also encrypted with key K' (call its encrypted form E'). Given E and E', and also secure hashes of K and K', it should be verified that D was properly encrypted both times.

The use case of this would be performing client-side encryption and uploading the encrypted data. If the encryption key is changed, the server should validate that the data has not been corrupted. Is there some sort of schema that fits what I am describing? I intentionally did not specify the encryption or hashing algorithms as I assume that those would be dependent on the schema, if one exists. Thanks for the help, and sorry if this is a stupid question - I am no cryptography expert.


Well, I've come up with one potential answer. I'm not sure how practical it is, however it does indicate that their exists a solution (and maybe a better solution can be found).

After writing it up, I decided that it's not a very good answer (likely going way over your head, and certainly not something you should try to implement yourself), however I'll keep the answer just in case someone else could improve o it.

It is based on "ECElGamal on a pairing friendly curve".

In ECElGamal, we work on a curve with order $n$ and well-known generator $G$; for a secret key, we select a random value $k$ between 1 and $n-1$; we compute the public key $K = kG$ (which we can publish).

To encrypt a message to us, someone first encodes their message into an curve point $D$ somehow (it doesn't really matter how, except it needs to be invertible), and selects a random value $r$ between 1 and $n-1$, and then generates a ciphertext that consists of the two points $rG$ and $rK + D$ (remember, $K$ is our public key).

Then, to decrypt a message that consists of two points $A, B$, we compute $B - kA$ (using our private key $k$), if $A = rG$ and $B = rK + D$, the result of this is $B - kA = rK + D - k(rG) = rkG + D - krG = D$; hence, we get the encoded curve point (and so we then convert the curve point $D$ back into the original message).

Now, suppose we publish a ciphertext $(A, B)$ encrypted with public key $K$, and then publishes a ciphertext $(A', B')$ encrypted with public key $K'$; how can we check if they encrypted the same message? Here's where the pairing-friendly part comes in: we check if:

$$e(A, K) / e(A', K') = e( G, B - B')$$

Here's how it works: if $A = rG$, $A' - r'G$, $B = rK + M$, $B' = r'K' + M$ (that is, encrypts the same message with a different $r$ and key values), then,

$e(A, K) / e(A', K') = e(rG, K) / e(r', K') = e( G, rK ) / e( G, r'K')$

$e( G, B - B') = e( G, rK - r'K') = e( G, rK) / e(G, r'K')$

That is, if the two ciphertexts encode the same message, the test passes.

So, if it solves the problem, but it does have these drawbacks:

  • It uses nonhybrid public key cryptography; hence it is inefficient (and each ciphertext encodes a relatively small amount of data, say, a few hundred bits). To encode more than that, you'd have to encode each block separately, which is not going to be fun...

  • Worse, the "key hash" is actually the public key; what this means is that if someone has a guess to the data $D$, all they need to do is encrypt it with a random public key (doesn't matter which), and then use the above procedure to check if the two ciphertexts (the one under test, and the one they just generated) have the same plaintext. If this is an issue, then you'd need an alternative method where the hash isn't a public key.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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