Encryption schemes with additional properties

• US 10,680,818 B2
• Filed: 04/12/2018
• Issued: 06/09/2020
• Est. Priority Date: 04/12/2018
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Bos, Joppe Willem, Joye, Marc
• Primary Examiner(s): Lanier, Benjamin E
• Application Number:
  US15/951,590
• Publication Number:
  US 20190319791A1
• Time in Patent Office: 789 Days
• Field of Search: None
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

Various embodiments relate to a method of encrypting a message m using a Paillier cryptosystem, including: computing a ciphertext c based upon the message m, N, and r, where N is the product of two distinct primes p and q, and r is randomly chosen such that r∈[1, N); computing a first verification value based upon u and N, where u is randomly chosen such that u∈[1, N); computing a second verification value s based upon u, r, the ciphertext c, the verification value, and a hash function H.

Claims

1. A method of encrypting a message m using a Paillier cryptosystem, comprising:

computing a ciphertext c based upon the message m, N, and r, where N is the product of two distinct primes p and q, and r is randomly chosen such that r∈

[1, N);

computing a first verification value based upon u and N, where u is randomly chosen such that u∈

[1, N); and

computing a second verification value s based upon u, r, the ciphertext c, the verification value, and a hash function H,

wherein U=u^N mod N where U is the first verification value, and

wherein s=u r^e mod N and where e=H (c, U).

2. The method of claim 1, wherein c=(1+mN)r^N mod N².

3. The method of claim 1, wherein s=u r^e mod N and where e=H(c, U, pk) where pk is a public key.

10. The method of claim 1, further comprising generating a secret key sk and public key pk further including:

generating the two distinct primes p and q and computing N;

computing λ

=lcm(p−

1, q−

1);

selecting the hash function H modeled as a random oracle with an identifier H_identifier; and

wherein the public key pk={N, H_identifier} and the private key sk={λ

}.

4. A method of encrypting a message m using a Paillier cryptosystem, comprising:

computing a ciphertext c based upon the message m, N, and r, where N is the product of two distinct primes p and q, and r is randomly chosen such that r∈

[1,N);

computing a first verification value based upon u and N, where u is randomly chosen such that u∈

[1,N); and

computing a second verification value s based upon u, r, the ciphertext c, the verification value, and a hash function H,

wherein V=H(u^N mod N) where V is the first verification value.

5. The method of claim 4, wherein s=ur^e mod N and where e=H(c, V).

6. The method of claim 4, wherein s=ur^e mod N and where e=H(c, U, pk) where pk is a public key.

7. A method of encrypting a message m using a Paillier cryptosystem, comprising:

computing a ciphertext c based upon the message m, N, and r, where N is the product of two distinct primes p and q, and r is randomly chosen such that r∈

[1,N);

computing a first verification value based upon u and N, where u is randomly chosen such that u∈

[1,N); and

computing a second verification value s based upon u, r, the ciphertext c, the verification value, and a hash function H,

wherein V=G(u^N mod N) where V is the first verification value and G is a hash function different from hash function H.

8. The method of claim 7, wherein s=ur^e mod N and where e=H(c, V).

9. The method of claim 7, wherein s=ur^e mod N and where e=H(c, V, pk) where pk is a public key.

11. A method of decrypting a ciphertext using a Paillier cryptosystem including a value c, a first verification value, and a second verification value s, comprising:

validating the ciphertext by checking the first verification value based upon the second verification value s, N, the value c, and a hash function H, where N is the product of two distinct primes p and q;

deciphering the ciphertext to produce a message m from the value c using a secret key and N;

computing e=H(c, V) and U=s^Nc<sup>−

e</sup> mod N, where V is first verification value; and

checking that the first verification value V equals H(U).

13. The method of claim 11, wherein

14. The method of claim 11, wherein deciphering the ciphertext to produce a message m further includes:

computing r=c^d mod N, where d is the secret key and d=N<sup>−

1</sup> mod λ

where λ

=lcm(p−

1, q−

1); and

computing

16. The method of claim 11, wherein validating the ciphertext further includes a public key pk.

12. A method of decrypting a ciphertext using a Paillier cryptosystemincluding a value c, a first verification value, and a second verification value s, comprising:

validating the ciphertext by checking the first verification value based upon the second verification value s, N, the value c, and a hash function H, where N is the product of two distinct primes p and q;

deciphering the ciphertext to produce a message m from the value c using a secret key and N;

computing e=H (c, V) and U=s^Nc<sup>−

e</sup> mod N, where V is first verification value; and

checking that the first verification value V equals G (U), where G is a hash function different from hash function H.

15. A method of decrypting a ciphertext using a Paillier cryptosystemincluding a value c, a first verification value, and a second verification value s, comprising:

validating the ciphertext by checking the first verification value based upon the second verification value s, N, the value c, and a hash function H, where Nis the product of two distinct primes p and q;

deciphering the ciphertext to produce a message m from the value c using a secret key and N;

computing e=H (c, U), where U is verification value; and

checking that the verification value U equals s^Nc<sup>−

e</sup> mod N.