# US 2019/0319791 A1 · Encryption schemes with additional properties

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0319791 A1
- Document ID: US20190319791A1
- Status: Published application
- Kind: A1
- Application number: 15/951,590
- Filed: 2018-04-12
- Published: 2019-10-17
- Earliest claimed: 2018-04-12
- Assignees: NXP B.V.
- Applicants: NXP B.V.
- Inventors: Joppe Willem BOS; Marc JOYE
- Web page: https://patentgrep.com/patent/US20190319791A1

## CPC

- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- H04L 9/3033: {details relating to pseudo-prime or prime number generation, e.g. primality test}
- H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein c=(1+mN)rN mod N2.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 3)

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

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 6)

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

### Claim 9 (depends on 1)

The method of claim 1, wherein V=G(uN mod N) where V is the first verification value and G is a hash function different from hash function H.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

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

### Claim 12 (depends on 1)

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

### Claim 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.

### Claim 14 (depends on 13)

The method of claim 13, wherein validating the ciphertext further includes:
computing e=H(c, V) and U=sNc−e mod N, where V is first verification value; and
checking that the first verification value V equals H(U).

### Claim 15 (depends on 13)

The method of claim 13, wherein validating the ciphertext further includes:
computing e=H(c, V) and U=sNc−e 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.

### Claim 16 (depends on 13)

The method of claim 13, wherein
m
=
(
c
λ
-
1


mod


N
2
N
)
/
λ


mod
N where λ=lcm(p−1, q−1) is the secret key.

### Claim 17 (depends on 13)

The method of claim 13, wherein deciphering the ciphertext to produce a message m further includes:
computing r=cd mod N, where d is the secret key and d=N−1 mod λ where λ=lcm(p−1, q−1); and
computing
m
=
cr
-
N
-
1


mod


N
2
N
.

### Claim 18 (depends on 13)

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 sNc−e mod N.

### Claim 19 (depends on 13)

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