ENCRYPTION SCHEMES WITH ADDITIONAL PROPERTIES

• US 20190319791A1
• Filed: 04/12/2018
• Published: 10/17/2019
• 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
• Granted Patent: US 10,680,818 B2
• Time in Patent Office: Days
• 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);

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

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

3. The method of claim 1, wherein U=u^N mod N where U is the first verification value.

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

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

6. The method of claim 1, wherein V=H(u^N mod N) where V is the first verification value.

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

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

9. The method of claim 1, 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.

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

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

12. 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={λ

}.

13. 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.

14. The method of claim 13, wherein validating the ciphertext further includes:

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).

15. The method of claim 13, wherein validating the ciphertext further includes:

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.

16. The method of claim 13, wherein

17. The method of claim 13, 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

18. The method of claim 13, wherein validating the ciphertext further includes:

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.

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