Flexible verifiable encryption from lattices
View Patent ↗Embodiments of the present invention may provide the capability for performing public-key encryption with proofs of plaintext knowledge using a lattice-based scheme that provides improved efficiency over conventional techniques. For example, in an embodiment, a computer-implemented method of verifying encryption may comprise generating a ciphertext, derived from a plaintext, via an encryption scheme, proving validity of the ciphertext, wherein the proof includes at least one challenge value, and using a decryption procedure that recovers a plaintext by choosing at least one additional challenge value at random from a challenge space.
1. A computer-implemented method of verifiable encryption comprising:
generating a ciphertext, derived from a plaintext, via an encryption scheme using a computer to execute program instructions stored on a non-transitory computer readable storage medium;
proving validity of the ciphertext using the computer, wherein the proof includes at least one challenge value; and
using a decryption procedure that recovers the plaintext by using the computer to choose at least one additional challenge value at random from a challenge space C;
wherein the encryption scheme is a Ring-LWE encryption scheme that generates an output (v, w), where v←p(ar+e) and w←p(tr+e′)+m, where e and e′ are error terms, m is a message term, r is a randomness term, p is a public parameter that is a positive integer greater than 2, and a and t are public keys, R q is a ring of polynomials equal to Z q [x]/(x n +1) with n a power of 2 and q a prime, s 1 and s 2 are secret keys defined such that s 1 ,
where S 1 is a set of polynomials in R q with coefficients that are zero or one, and the public keys a and t are defined such that
wherein the decryption scheme comprises:
selecting a challenge c′ at random from the challenge space C⊆S 1 , the challenge space C is stored on the non-transitory computer readable storage medium, the challenge space C including at least one challenge c′ which proves the ciphertext is valid;
generating, using the computer, a new challenge c =c−c′, wherein c is a challenge value in the ciphertext proof, determining whether
c
_
[
v
w
]
mod
q
is a valid ciphertext;
if
c
_
[
v
w
]
mod
q
is a valid ciphertext, then decrypting the ciphertext, otherwise, repeatedly selecting a new challenge c′ stored on the non-transitory computer readable storage medium until one of the challenge values satisfies the ciphertext proof;
computing m′=(w−vs 1 )(c−c′) mod q using the computer;
checking that c and c′ prove the validity of the ciphertext by checking a bound on the norm of m′ using the computer; and
if c and c′ prove the validity of the ciphertext, outputting m=m′ mod p from the computer as part of the decrypted plaintext.
2. A computer program product for verifying encryption, the computer program product comprising a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising:
generating a ciphertext, derived from a plaintext, via an encryption scheme;
proving validity of the ciphertext, wherein the proof includes at least one challenge value; and
using a decryption procedure that recovers a plaintext by choosing at least one additional challenge value at random from a challenge space C;
wherein the encryption scheme is a Ring-LWE encryption scheme that generates an output (v, w), where v←p(ar+e) and w←p(tr+e′)+m, where e and e′ are error terms, m is a message term, r is a randomness term, p is a public parameter that is a positive integer greater than 2, and a and t are public keys, R q is a ring of polynomials equal to Z q [x]/(x n +1) with n a power of 2 and q a prime, s 1 and s 2 are secret keys defined such that s 1 ,
where S 1 is a set of polynomials in R q with coefficients that are zero or one, and the public keys a and t are defined such that
wherein the decryption scheme comprises:
selecting a challenge c′ at random from the challenge space C⊆S 1 , the challenge space C is stored on the non-transitory computer readable storage medium, the challenge space C including at least one challenge c′ which proves the ciphertext is valid;
generating, using the computer, a new challenge c =c−c′, wherein c is a challenge value in the ciphertext proof, determining whether
c
_
[
v
w
]
mod
q
is a valid ciphertext;
if
c
_
[
v
w
]
mod
q
is a valid ciphertext, then decrypting the ciphertext, otherwise, repeatedly selecting a new challenge c′ stored on the non-transitory computer readable storage medium until one of the challenge values satisfies the ciphertext proof;
computing m′=(w−vs 1 )(c−c′)mod q using the computer;
checking that c and c′ prove the validity of the ciphertext by checking a bound on the norm of m′ using the computer; and
if c and c′ prove the validity of the ciphertext, outputting m=m′ mod p from the computer as part of the decrypted plaintext.
3. A system for verifying encryption, the system comprising a processor, memory accessible by the processor, and computer program instructions stored in the memory and executable by the processor to cause the processor to perform:
generating a ciphertext, derived from a plaintext, via an encryption scheme;
proving validity of the ciphertext, wherein the proof includes at least one challenge value; and
using a decryption procedure that recovers a plaintext by choosing at least one additional challenge value at random from a challenge space C;
wherein the encryption scheme is a Ring-LWE encryption scheme that generates an output (v, w), where v←p(ar+e) and w←p(tr+e′)+m, where e and e′ are error terms, m is a message term, r is a randomness term, p is a public parameter that is a positive integer greater than 2, and a and t are public keys, R q is a ring of polynomials equal to Z q [x]/(x n +1) with n a power of 2 and q a prime, s 1 and s 2 are secret keys defined such that s 1 ,
where S 1 is a set of polynomials in R q with coefficients that are zero or one, and the public keys a and t are defined such that
wherein the decryption procedure comprises:
selecting a challenge c′ at random from the challenge space C⊆S 1 , the challenge space C is stored on the non-transitory computer readable storage medium, the challenge space C including at least one challenge c′ which proves the ciphertext is valid;
generating, using the computer, a new challenge c =c−c′, wherein c is a challenge value in the ciphertext proof, determining whether
c
_
[
v
w
]
mod
q
is a valid ciphertext;
if
c
_
[
v
w
]
mod
q
is a valid ciphertext, then decrypting the ciphertext, otherwise, repeatedly selecting a new challenge c′ stored on the non-transitory computer readable storage medium until one of the challenge values satisfies the ciphertext proof;
computing m′=(w−vs 1 )(c−c′) mod q using the computer;
checking that c and c′ prove the validity of the ciphertext by checking a bound on the norm of m′ using the computer; and
if c and c′ prove the validity of the ciphertext, outputting m=m′ mod p from the computer as part of the decrypted plaintext.