Plaintext equivalence proof techniques in communication systems
Methods aiding in proving shuffles of re-encryptions of ciphertexts and a mixnet employing such methods. A method for compacting ciphertexts includes encrypting a plaintext using an asymmetric key encryption scheme for a ciphertext, dividing the ciphertext into partial ciphertexts, encrypting each of the partial ciphertexts using the asymmetric key encryption scheme to obtain re-encrypted partial ciphertexts, creating hash exponents from a digest of a cryptographic hash function taking the partial ciphertexts, the re-encrypted partial ciphertexts and arbitrary salt values as argument of the cryptographic hash function, calculating a compacted ciphertext by multiplying all of the partial ciphertexts exponentiated by a respective one of the plurality of hash exponents, and calculating a compacted re-encrypted ciphertext by multiplying all of the re-encrypted partial ciphertexts exponentiated by a respective one of the hash exponents.
1. A method for compacting ciphertexts, the method comprising:
encrypting a plaintext using an asymmetric key encryption scheme to obtain a ciphertext;
dividing the ciphertext into a plurality of partial ciphertexts;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme to obtain a plurality of re-encrypted partial ciphertexts;
creating a plurality of hash exponents from a digest of a cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a plurality of arbitrary salt values as argument of the cryptographic hash function, wherein the plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the plurality of hash exponents; and
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the plurality of hash exponents.
2. The method of claim 1 , wherein the cryptographic hash function is a one-way function.
3. The method of claim 1 , wherein output values of the cryptographic hash function are chosen uniformly at random.
4. The method of claim 1 , wherein the asymmetric key encryption scheme is an ElGamal encryption system.
5. The method of claim 4 , wherein each of the plurality of partial ciphertexts include unambiguously paired ElGamal ciphertext tuples.
6. A method for performing a zero-knowledge proof of plaintext equivalence, the method comprising:
by a prover:
dividing a ciphertext into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a plurality of hash exponents from a digest of a cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a plurality of salt values as argument of the cryptographic hash function, the plurality of salt values being based on a commitment chosen by the prover and wherein the plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings;
transmitting the plurality of re-encrypted partial ciphertexts to a verifier; and
transmitting a sum of the commitment and a product of the plurality of salt values, the plurality of hash exponents and the plurality of re-encryption keys to the verifier; and
by the verifier:
re-calculating the plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the plurality of re-calculated hash exponents; and
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that each of the plurality of re-encrypted partial ciphertexts is an encryption of the plurality of partial ciphertexts.
7. The method of claim 6 , wherein the cryptographic hash function is a one-way function.
8. The method of claim 6 , wherein output values of the cryptographic hash function are chosen uniformly at random.
9. The method of claim 6 , wherein the asymmetric key encryption scheme is an ElGamal encryption system.
10. The method of claim 9 , wherein each of the plurality of partial ciphertexts include unambiguously paired ElGamal ciphertext tuples.
11. A method for performing a disjunctive proof of plaintext equivalence, the method comprising in a first stage of a proof of plaintext equivalence:
by a prover:
dividing a ciphertext into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a first plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a first plurality of hash exponents from a digest of a cryptographic hash function taking a selected first one of the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a first plurality of salt values as argument of the cryptographic hash function, the first plurality of salt values being based on a first commitment chosen by the prover;
transmitting the plurality of re-encrypted partial ciphertexts to a verifier; and
transmitting a sum of the first commitment and a product of the first plurality of salt values, the first plurality of hash exponents and the first plurality of re-encryption keys to the verifier; and
by the verifier:
re-calculating the first plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the first plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that at least one of the plurality of re-encrypted partial ciphertexts is an encryption of an arbitrary one of the plurality of partial ciphertexts; and
iterating steps of the prover and the verifier for a selected second one of the plurality of partial ciphertexts using a second plurality of re-encryption keys, a second plurality of salt values being based on a second commitment chosen by the prover and a second plurality of hash exponents as input parameters for the second stage of the proof of plaintext equivalence;
wherein the first plurality of arbitrary salt values and the second plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings.
12. The method of claim 11 , wherein the cryptographic hash function is a one-way function.
13. The method of claim 11 , wherein output values of the cryptographic hash function are chosen uniformly at random.
14. The method of claim 11 , wherein the asymmetric key encryption scheme is an ElGamal encryption system.
15. The method of claim 14 , wherein each of the plurality of partial ciphertexts include unambiguously paired ElGamal ciphertext tuples.
16. A method for verifying a shuffle of re-encryptions of a plurality of ciphertexts in zero-knowledge, the method comprising in a first stage of a proof of plaintext equivalence:
by a prover:
dividing a first one of the plurality of ciphertexts into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a first plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a first plurality of hash exponents from a digest of a cryptographic hash function taking a selected first one of the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a first plurality of salt values as argument of the cryptographic hash function, the first plurality of salt values being based on a first commitment chosen by the prover;
transmitting the plurality of re-encrypted partial ciphertexts to a verifier; and
transmitting a sum of the first commitment and a product of the first plurality of salt values, the first plurality of hash exponents and the first plurality of re-encryption keys to the verifier;
the method further comprising in a second stage of a proof of plaintext equivalence by the verifier:
re-calculating the first plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the first plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that at least one of the plurality of re-encrypted partial ciphertexts is an encryption of an arbitrary one of the plurality of partial ciphertexts; and
iterating steps of the prover and the verifier for a selected second one of the plurality of partial ciphertexts using a second plurality of re-encryption keys, a second plurality of salt values being based on a second commitment chosen by the prover and a second plurality of hash exponents as input parameters for the second stage of the proof of plaintext equivalence, and
the method comprising in a third stage of a proof of plaintext equivalence:
by the prover:
dividing a second one of the plurality of ciphertexts into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a first plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a first plurality of hash exponents from a digest of a cryptographic hash function taking a selected first one of the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a first plurality of salt values as argument of the cryptographic hash function, the first plurality of salt values being based on a first commitment chosen by the prover;
transmitting the plurality of re-encrypted partial ciphertexts to the verifier; and
transmitting a sum of the first commitment and a product of the first plurality of salt values, the first plurality of hash exponents and the first plurality of re-encryption keys to the verifier;
the method further comprising a fourth stage of a proof of plaintext equivalence by the verifier:
re-calculating the first plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the first plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that at least one of the plurality of re-encrypted partial ciphertexts is an encryption of an arbitrary one of the plurality of partial ciphertexts; and
iterating steps of the prover and the verifier for a selected second one of the plurality of partial ciphertexts using a second plurality of re-encryption keys, a second plurality of salt values being based on a second commitment chosen by the prover and a second plurality of hash exponents as input parameters for the fourth stage of the proof of plaintext equivalence,
the method further comprising performing a proof of plaintext equivalence on a product of the compacted ciphertexts of the first to fourth stages and a product of the compacted re-encrypted ciphertexts of the first to fourth stages;
wherein the first plurality of arbitrary salt values and the second plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings.
17. A mixnet, comprising:
a plurality of mixes, each mix configured to re-encrypt a plurality of ciphertexts input to the mix and to shuffle the re-encryptions of the input plurality of ciphertexts; and
a verification device coupled to each of the mixes,
wherein each of the mixes as prover and the verification device as verifier are together configured to perform a method for performing a zero-knowledge proof of plaintext equivalence, the method comprising:
by the mix:
dividing a ciphertext into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a plurality of hash exponents from a digest of a cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a plurality of salt values as argument of the cryptographic hash function, the plurality of salt values being based on a commitment chosen by the prover;
transmitting the plurality of re-encrypted partial ciphertexts to a verifier; and
transmitting the sum of the commitment and the product of the plurality of salt values, the plurality of hash exponents and the plurality of re-encryption keys to the verifier;
by the verification device:
re-calculating the plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the plurality of re-calculated hash exponents; and
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that each of the plurality of re-encrypted partial ciphertexts is an encryption of the plurality of partial ciphertexts;
wherein the plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings.
18. A mixnet, comprising:
a plurality of mixes, each mix configured to re-encrypt a plurality of ciphertexts input to the mix and to shuffle the re-encryptions of the input plurality of ciphertexts; and
a verification device coupled to each of the mixes,
wherein each of the mixes as prover and the verification device as verifier are together configured to perform a method for performing a disjunctive proof of plaintext equivalence, the method comprising in a first stage of a proof of plaintext equivalence:
by the mix:
dividing a ciphertext into a plurality of partial ciphertexts, the ciphertext being an encrypted plaintext using an asymmetric key encryption scheme;
encrypting each of the plurality of partial ciphertexts using the asymmetric key encryption scheme with a first plurality of re-encryption keys to obtain a plurality of re-encrypted partial ciphertexts;
creating a first plurality of hash exponents from a digest of a cryptographic hash function taking a selected first one of the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and a first plurality of salt values as argument of the cryptographic hash function, the first plurality of salt values being based on a first commitment chosen by the prover;
transmitting the plurality of re-encrypted partial ciphertexts to a verifier; and
transmitting a sum of the first commitment and a product of the first plurality of salt values, the first plurality of hash exponents and the first plurality of re-encryption keys to the verifier;
by the verification device:
re-calculating the first plurality of hash exponents from the digest of the cryptographic hash function taking the plurality of partial ciphertexts, the plurality of re-encrypted partial ciphertexts and the first plurality of salt values as argument of the cryptographic hash function;
calculating a compacted ciphertext by multiplying all of the plurality of partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
calculating a compacted re-encrypted ciphertext by multiplying all of the plurality of re-encrypted partial ciphertexts exponentiated by a respective one of the first plurality of re-calculated hash exponents;
verifying that the compacted re-encrypted ciphertext is a re-encryption of the compacted ciphertext, thereby verifying that at least one of the plurality of re-encrypted partial ciphertexts is an encryption of an arbitrary one of the plurality of partial ciphertexts; and
iterating steps of the prover and the verifier for a selected second one of the plurality of partial ciphertexts using a second plurality of re-encryption keys, a second plurality of salt values being based on a second commitment chosen by the prover and a second plurality of hash exponents as input parameters for the second stage of the proof of plaintext equivalence;
wherein the plurality of arbitrary salt values comprise auxiliary chosen one-time use bit strings.