Mixing
Re-encrypting a message and proving that the message has not changed
up vote
9
down vote
favorite
Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?
More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$
is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?
encryption homomorphic-encryption zero-knowledge-proofs
edited 13 hours ago
kelalaka
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
9
down vote
favorite
Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?
More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$
is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?
encryption homomorphic-encryption zero-knowledge-proofs
edited 13 hours ago
kelalaka
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
1
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago
add a comment |
up vote
9
down vote
favorite
up vote
9
down vote
favorite
Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?
More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$
is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?
encryption homomorphic-encryption zero-knowledge-proofs
edited 13 hours ago
kelalaka
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?
More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$
is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?
encryption homomorphic-encryption zero-knowledge-proofs
encryption homomorphic-encryption zero-knowledge-proofs
edited 13 hours ago
kelalaka
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
kelalaka
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
kelalaka
3,071828
edited 13 hours ago
kelalaka
3,071828
edited 13 hours ago
kelalaka
3,071828
3,071828
asked 22 hours ago
zakum1
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 22 hours ago
zakum1
485
asked 22 hours ago
zakum1
485
485
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
zakum1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
1
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago
add a comment |
1
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
1
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago
1
1
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
1
1
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago
add a comment |
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
$e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
$e(G,G) ne 1$ (which implies that $e(G, aG) = 1$ iff $a equiv 0 pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \
e(G,A-B)^{r} cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.
answered 14 hours ago
poncho
88.4k2133226
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
add a comment |
up vote
8
down vote
I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
One weak solution can be based on Bongenaar' Multi-key FHE where;
In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.
Now we can use this scheme as follows;
- Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
- The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.
- Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,
- decrypt the result.
The results;
- If the result is not zero, then they are not the same.
- Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.
answered 22 hours ago
kelalaka
3,071828
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
$e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
$e(G,G) ne 1$ (which implies that $e(G, aG) = 1$ iff $a equiv 0 pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \
e(G,A-B)^{r} cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.
answered 14 hours ago
poncho
88.4k2133226
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
add a comment |
up vote
3
down vote
accepted
If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
$e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
$e(G,G) ne 1$ (which implies that $e(G, aG) = 1$ iff $a equiv 0 pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \
e(G,A-B)^{r} cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.
answered 14 hours ago
poncho
88.4k2133226
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
$e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
$e(G,G) ne 1$ (which implies that $e(G, aG) = 1$ iff $a equiv 0 pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \
e(G,A-B)^{r} cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.
answered 14 hours ago
poncho
88.4k2133226
If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
$e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
$e(G,G) ne 1$ (which implies that $e(G, aG) = 1$ iff $a equiv 0 pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \
e(G,A-B)^{r} cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.
answered 14 hours ago
poncho
88.4k2133226
edited 14 hours ago
answered 14 hours ago
poncho
88.4k2133226
answered 14 hours ago
poncho
88.4k2133226
answered 14 hours ago
poncho
88.4k2133226
88.4k2133226
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
add a comment |
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
El-Gamal has many tricks and one more.
– kelalaka
13 hours ago
add a comment |
up vote
8
down vote
I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
8
down vote
I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
8
down vote
up vote
8
down vote
I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 22 hours ago
answered 22 hours ago
Viou
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 22 hours ago
Viou
812
answered 22 hours ago
Viou
812
812
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Viou is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
up vote
1
down vote
One weak solution can be based on Bongenaar' Multi-key FHE where;
In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.
Now we can use this scheme as follows;
- Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
- The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.
- Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,
- decrypt the result.
The results;
- If the result is not zero, then they are not the same.
- Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.
answered 22 hours ago
kelalaka
3,071828
add a comment |
up vote
1
down vote
One weak solution can be based on Bongenaar' Multi-key FHE where;
In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.
Now we can use this scheme as follows;
- Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
- The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.
- Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,
- decrypt the result.
The results;
- If the result is not zero, then they are not the same.
- Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.
answered 22 hours ago
kelalaka
3,071828
add a comment |
up vote
1
down vote
up vote
1
down vote
One weak solution can be based on Bongenaar' Multi-key FHE where;
In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.
Now we can use this scheme as follows;
- Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
- The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.
- Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,
- decrypt the result.
The results;
- If the result is not zero, then they are not the same.
- Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.
answered 22 hours ago
kelalaka
3,071828
One weak solution can be based on Bongenaar' Multi-key FHE where;
In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.
Now we can use this scheme as follows;
- Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
- The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.
- Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,
- decrypt the result.
The results;
- If the result is not zero, then they are not the same.
- Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.
answered 22 hours ago
kelalaka
3,071828
edited 13 hours ago
answered 22 hours ago
kelalaka
3,071828
answered 22 hours ago
kelalaka
3,071828
answered 22 hours ago
kelalaka
3,071828
3,071828
add a comment |
add a comment |
zakum1 is a new contributor. Be nice, and check out our Code of Conduct.
zakum1 is a new contributor. Be nice, and check out our Code of Conduct.
zakum1 is a new contributor. Be nice, and check out our Code of Conduct.
zakum1 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64162%2fre-encrypting-a-message-and-proving-that-the-message-has-not-changed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....?
– ymbirtt
19 hours ago
1
Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to)
– poncho
18 hours ago
Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be.
– supercat
15 hours ago