TECHNICAL FIELD

Various exemplary embodiments disclosed herein relate generally to a method and apparatus for implementing new encryption schemes with additional properties.

BACKGROUND

Various schemes have been developed for encrypting and decrypting data. Chosen ciphertext attacks are one method used by attacker to compromise encryption and decryption schemes, so implementing encryption schemes resistant to chosen ciphertext attacks provides increased security.

SUMMARY

A summary of various exemplary embodiments is presented below. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the various exemplary embodiments, but not to limit the scope of the invention. Detailed descriptions of an exemplary embodiment adequate to allow those of ordinary skill in the art to make and use the inventive concepts will follow in later sections.

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.

Various embodiments are described, wherein c=(1+mN)r^Nmod N².

Various embodiments are described, wherein U=u^Nmod N where U is the first verification value.

Various embodiments are described, wherein s=ur^emod N and where e=H(c, U).

Various embodiments are described, wherein s=ur^emod N and where e=H(c, U, pk) where pk is a public key.

Various embodiments are described, wherein V=H(u^Nmod N) where V is the first verification value.

Various embodiments are described, wherein s=ur^emod N and where e=H(c, V).

Various embodiments are described, wherein s=ur^emod N and where e=H(c, U, pk) where pk is a public key.

Various embodiments are described, wherein V=G(u^Nmod N) where V is the first verification value and G is a hash function different from hash function H.

Various embodiments are described, wherein s=ur^emod N and where e=H(c, V).

Various embodiments are described, wherein s=ur^emod N and where e=H(c, V, pk) where pk is a public key.

Various embodiments are described, further including 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={λ}.

Further various embodiments relate to a method of decrypting a ciphertext using a Paillier cryptosystem including a value c, a first verification value, and a second verification value s, including: 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.

Various embodiments are described, wherein validating the ciphertext further includes: computing e=H(c, V) and U=s^Nc^−emod N, where V is first verification value; and checking that the first verification value V equals H(U).

Various embodiments are described, wherein validating the ciphertext further includes: computing e=H(c, V) and U=s^Nc^−emod 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.

Various embodiments are described, wherein

m
=

(

c
λ

-

1



mod




N
2

N

)

/
λ




mod

N where λ=lcm(p−1, q−1) is the secret key.

Various embodiments are described, wherein deciphering the ciphertext to produce a message m further includes: computing r=c^dmod N, where d is the secret key and d=N⁻¹mod λ where λ=lcm(p−1, q−1); and computing

m
=

cr

-
N

-

1



mod




N
2

N

.

Various embodiments are described, 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^−emod N.

Various embodiments are described, wherein validating the ciphertext further includes a public key pk.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein:

FIG. 1 illustrates an exemplary hardware diagram for implementing a cryptosystem according to the embodiments described herein.

To facilitate understanding, identical reference numerals have been used to designate elements having substantially the same or similar structure and/or substantially the same or similar function.

DETAILED DESCRIPTION

The description and drawings illustrate the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its scope. Furthermore, all examples recited herein are principally intended expressly to be for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Additionally, the term, “or,” as used herein, refers to a non-exclusive or (i.e., and/or), unless otherwise indicated (e.g., “or else” or “or in the alternative”). Also, the various embodiments described herein are not necessarily mutually exclusive, as some embodiments can be combined with one or more other embodiments to form new embodiments.

First, a formal definition for public-key encryption will be described. Then the notion of a zero-knowledge proof will be described.

A public-key encryption scheme includes a tuple of three algorithms (KeyGen, Enc, Dec).

The key generation algorithm KeyGen is a randomized algorithm that takes as input a security parameter κ and returns a matching pair (pk, sk) of a public key and a secret key. This may be expressed as

[Image Omitted]

Encryption is carried out as follows. Let [Image Omitted] denote the message space. The encryption algorithm Enc is a randomized algorithm that takes as input a public key pk and a plaintext m∈, and returns a ciphertext c. This may be expressed as

[Image Omitted]

The decryption algorithm Dec takes as input a secret key sk (associated with pk) and a ciphertext c. It returns the corresponding plaintext m or a special symbol ⊥ indicating that the ciphertext is invalid. This may be expressed as m←Dec_sk(c) if c is a valid ciphertext and ⊥←Dec_sk(c) if it is not.

For any

[Image Omitted]

it is required that Dec_sk(Enc_pk(m))=m for any message m∈ [Image Omitted] .

Zero-knowledge proofs will now be described. Informally, in a zero-knowledge proof, Peggy (prover) proves to Victor (verifier) the validity of a statement that includes secret information in a way that Victor does not learn anything more as a result of this process.

For example, consider a cyclic group [Image Omitted] =g of prime order q, generated by an element g. In order to prove that Peggy knows the discrete logarithm of y=g^x, Peggy executes l times the following protocol with Victor:

- 1. Peggy chooses a random integer r∈_q, computes the commitment C=g^r(in ), and sends C to Victor;
- 2. Victor flips a fair coin c∈{0,1} and sends the challenge c to Peggy;
- 3. Peggy computes the response

R=r+cx mod q

- and sends R to Victor; and
- 4. Victor checks that g^RC·y^C(in ).
  
  It can be verified that the cheating probability for Peggy is 2^−l.

Zero-knowledge proofs can be made non-interactive in the random oracle model by replacing the challenge by a hash of the transcript to that point. This is known as the Fiat-Shamir heuristic. In the above example, the challenge c is then set to c=h(C) for some cryptographic hash function h mapping to {0,1}. This can be further improved to a single pass using the Schnorr protocol (again in the random oracle model) by viewing the pair (x, y=g^x) as a signing/verification key pair:

- 1a. Peggy chooses a random integer r∈_qand computes the commitment C=g^r;
- 1b. Peggy forms the challenge c=H(C) (for some cryptographic hash function mapping to _q), generates the signature

s=r+cx mod q

- and sends the pair (C, s) to Victor; and
- 2. Victor checks that g^sC·y^c(in ) where c=H(C).
  
  Assuming that H behaves as a random oracle, the cheating probability for Peggy is 1/q.

If the representation of c is shorter than that of C (which is usually the case), Peggy can instead send the pair (c, s) to Victor. The verification equation is then replaced with c [Image Omitted] H(g^s·y^−c).

The Paillier cryptosystem and the Guillou-Quisquater (GQ) identification scheme will now be briefly described.

The Paillier cryptosystem is a public-key encryption scheme supporting a large message space. For a more detailed description see Pascal Paillier, Public-key cryptosystems based on composite degree residuosity classes, Advances in Cryptology—EUROCRYPT '99 (Jacques Stern, ed.), Lecture Notes in Computer Science, vol. 1592, Springer, Heidelberg, May 1999, pp. 223-238, which incorporated herein for all purposes by reference. Furthermore, as will be apparent, the scheme is equipped with an additive homomorphism. This property is useful when one performs addition operations on the ciphertexts.

A description of the Paillier cryptosystem is as follows.

- Key generation: Let κ be a security parameter. On input κ, the key generation algorithm generates two distinct primes p and q and computes N=pq and λ=lcm(p−1, q−1). The public key is pk={N} and private key is sk={λ}.
- The message space is =_N, namely the ring of integers modulo N.
- Encryption: The encryption of a message m∈,

[Image Omitted]

is given by

c=(1+mN)r^Nmod N²

- for a random integer r∈[1, N).
- Decryption: Given a ciphertext c, the corresponding plaintext is recovered using the private key λ in two steps as:
- 1. Compute

L
=

c
λ

-

1



mod




N
2

N

;

and

- 2. Return m=L/λ mod N.

It is worth noting that for any ρ∈ [Image Omitted] _N₂, one has ρ^N≡(ρ mod N)^N(mod N²). This is why random integer r is defined in the range [1, N) in Paillier's encryption.

The Paillier cryptosystem is additively homomorphic. Given two Paillier ciphertexts,

[Image Omitted]

the addition of c₁and c₂is defined as

AddH(c₁,c₂)=(c₁·c₂)ρ^Nmod N²

for some integer ρ∈[1, N). The scheme is said to be additively homomorphic because the decryption of the so-obtained ciphertext yields the message m₁+m₂(as an element in [Image Omitted] ). Indeed, letting c₁=(1+m₁N)r₁^Nmod N²and c₂=(1+m₂N)r₂^Nmod N², the following results

(

c
1

·

c
2

)



ρ
N

≡



(

1
+

m
1


N

)



r
1
N



(

1
+

m
2


N

)



r
2
N



ρ
N

≡



(

1
+

(

m
1

+

m
2

)


N

)



R
N



(

mod




N
2

)

with R=r₁r₂ρ mod N², the decryption of which leads to m₁+m₂(mod N).

The Guillou-Quisquater (GQ) identification protocol will now be described. The so-called GQ protocol, named after its inventors Guillou and Quisquater, is a practical zero-knowledge protocol. For more detailed information about the GQ protocol see Louis C. Guillou and Jean-Jacques Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, Advances in Cryptology—EUROCRYPT '88 (C. G. Günther, ed.), Lecture Notes in Computer Science, vol. 330, Springer, Heidelberg, May 1988, pp. 123-128, which is incorporated herein for all purposes by reference.

Let N=pq where p and q are distinct primes. To prove in a zero-knowledge way that Peggy knows a secret value s satisfying s^ev≡1(mod N) where v, e, N are public, Peggy (prover) executes the following protocol with Victor (verifier):

- 1. Peggy chooses a random integer r in _N, computes the commitment C=r^emod N, and sends C to Victor;
- 2. Victor chooses a random challenge c∈_eand sends c to Peggy;
- 3. Peggy computes the response R=rs^cmod N and sends R to Victor;
- 4. Victor checks that CR^ev^c(mod N).
- Proof. It is easily verified that R^ev^c≡(rs^c)^ev^c≡r^e(s^ev)^c≡C(mod N).

Assuming the random oracle model, the proof can be made non-interactive by replacing c with H(C) for some cryptographic hash function H mapping to [Image Omitted] _e.

In the presence of a passive adversary, the “right” notion of security for public-key encryption is known as semantic security. Informally, it means that an adversary should not learn any information whatsoever about a plaintext given its encryption (beyond the length of the plaintext).

Against active adversaries, this is not enough. The “right” notion of security is then chosen-ciphertext security or equivalently non-malleability. Intuitively, it implies that semantic security must hold even if the attacker is given adaptive access to a decryption oracle.

More formally, an adversary [Image Omitted] is viewed as a pair (₁, ₂) of probabilistic algorithms. This corresponds to adversary running the algorithms in two stages.

In the “find” stage, algorithm [Image Omitted] ₁takes as input the public key pk. ₁can submit any ciphertext of its choice and receives the corresponding plaintext (or ⊥). ₁outputs two equal-size messages m₀and m₁∈.

In the “guess” stage, algorithm [Image Omitted] ₂receives a challenge ciphertext c* which is the encryption of m₀or of m₁under pk; i.e., c*←Enc_pk(m_b) where b is chosen uniformly at random in {0,1}. Again, ₂can submit any ciphertext and see the corresponding decryption; the sole exception is that ₂cannot ask for the decryption of the challenge ciphertext c*.

The goal of [Image Omitted] ₂is to guess correctly—with probability significantly greater than ½—if c* corresponds to the encryption of m₀or of m₁.

An encryption scheme is said chosen-ciphertext secure if no such adversary [Image Omitted] =(₁, ₂) exists.

The Paillier cryptosystem is semantically secure. Unfortunately, the Paillier cryptosystem does not meet the stronger notion of chosen-ciphertext security. This is due to the underlying additive homomorphism.

Upon receiving the challenge ciphertext c*=(1+m_bN)r^Nmod N², the adversary [Image Omitted] ₂does the following:

- 1. It chooses at random μ, ρ∈_Nand forms the ciphertext c^†=c*(1+μN)ρ^Nmod N²;
- 2. It submits c^† to the decryption oracle and obtains the corresponding plaintext m^†;
- 3. It recovers m_b=m^†−μ mod N; and
- 4. If m_b=m₀it outputs 0; otherwise it outputs 1.

To remedy this situation, Paillier subsequently proposed with Pointcheval a chosen-ciphertext secure version of his cryptosystem. For more details see Pascal Paillier and David Pointcheval, Efficient pubic-key cryptosystems provably secure against active adversaries, Advances in Cryptology—ASIACRYPT '99 (Kwok-Yan Lam, Eiji Okamoto, and Chaoping Xing, eds.), Lecture Notes in Computer Science, vol. 1716, Springer, Heidelberg, November 1999, pp. 165-179, which is hereby incorporated herein by reference for all purposes. The improved cryptosystem requires two hash functions G, H mapping to [Image Omitted] _N. Slightly simplifying the scheme described by Paillier and Pointcheval, the encryption of a message m∈ is given by

c=(1+MN)z mod N²where

z=H(m,r)^Nmod N²and M=m∥r+G(z mod N)mod N.

The decryption of c proceeds in two stages as follows.

- Recovering M: Recover M using the private key λ as:
- 1. Compute

L
=

c
λ

-

1



mod




N
2

N

;

and

- 2. Obtain M=L/λ mod N.
- Validating the ciphertext and returning the message or ⊥:
- Define m∥r=M−G(c mod N).
  - If H(m, r)^N≡c(mod N) return m;
  - Otherwise, return ⊥ (invalid ciphertext).

The Paillier-Pointcheval cryptosystem is chosen-ciphertext secure. Unfortunately, checking the validity of a ciphertext requires the knowledge of the private decryption key. In a threshold environment none of the decryption servers possess the private key needed to perform this validity test. Consequently, there is a need for chosen-ciphertext versions of Paillier cryptosystem with public validity test. This disclosure presents several embodiments of such a Paillier cryptosystem.

In addition to chosen-ciphertext security, the proposed cryptosystems have two useful features: public validity and compatibility. Anyone can check the validity of a ciphertext. No private key is involved in the process. This is useful for threshold decryption. The resulting ciphertexts can readily be converted into regular Paillier ciphertexts. This is useful when addition operations need to be applied to ciphertexts.

An important observation is that a Paillier ciphertext, c=(1+mN)r^Nmod N², satisfies the relation

r^Nc⁻¹≡1(mod N).

Viewing the pair (r, c⁻¹mod N) as a signing/verification key pair in the GQ protocol, the encryptor can prove the knowledge of the randomness r used for forming the ciphertext by issuing a GQ ‘signature’ (U, s) with

U=u^Nmod N and s=ur^emod N where e=H(c,U)

for some cryptographic hash function H.

A first embodiment of a modified Paillier cryptosystem will now be described. Based on the above observation, the Paillier cryptosystem can therefore be modified into a new cryptosystem. The key generation, encryption, and decryption operations of the first embodiment will now be described.

Key generation proceeds as follows. Let κ be a security parameter. On input κ, the key generation algorithm generates two distinct primes p and q and selects a hash function H modeled as a random oracle. The key generation operation computes N=pq and λ=lcm(p−1, q−1). The public key is pk={N, H_identifier} and private key is sk={λ}. The message space is [Image Omitted] =_N, namely the ring of integers modulo N.

Encryption proceeds as follows. The encryption of a message m∈ [Image Omitted] ,

[Image Omitted]

is given by the tuple (c, U, s) where

c=(1+mN)r^Nmod N², U=u^Nmod N, s=ur^emod N

for random integers r, u∈[1, N) and where e=H(c, U).

Decryption proceeds as follows. Given a ciphertext [Image Omitted] =(c, U, s), the decryption process proceeds in two stages.

- Validating the ciphertext: Compute e=H(c, U) and check whether Us^Nc^−e(mod N). If not, return ⊥ and abort.
- Deciphering the ciphertext: From the component c, the corresponding plaintext may be recovered using the private key λ in two steps as:
- 1. Compute

L
=

c
λ

-

1



mod




N
2

N

;

and

- 2. Return m=L/λ mod N.

Given a ciphertext [Image Omitted] =(c, U, s) with c=(1+mN)r^Nmod N², the knowledge of the randomness r(mod N) used in the construction of c is equivalent to the knowledge of the underlying plaintext m since

m
=

cr

-
N

-

1



mod




N
2

N

.

Hence, the above cryptosystem yields a zero-knowledge proof of knowledge of the plaintext.

The previous cryptosystem is subject to many variants. For example, the hash function can include the public key as an additional input by defining e=H(c, U, pk).

Another variant is to define the private sk={d} where d=N⁻¹mod λ, and to recover the plaintext corresponding to a valid ciphertext [Image Omitted] =(c, U, s) using d to

- 1. Compute r=c^dmod N, and
- 2. Return

m
=

cr

-
N

-

1



mod




N
2

N

.

A second embodiment of a modified Paillier cryptosystem will now be described. In practical settings, the size of modulus N is much larger than the image size of hash function H. For example, for a security level of κ=128 bits, N is of size 3072 bits, and a hash value is of size 256 bits.

It is therefore advantageous to trade a mod-N value against a hash value. The second embodiment provides such a modification. It results in shorter ciphertexts while keeping the properties of the first embodiment. The key generation, encryption, and decryption operations of the second embodiment will now be described.

Key generation proceeds as follows: Let κ be a security parameter. On input κ, the key generation algorithm generates two distinct primes p and q and selects a hash function H modeled as a random oracle. It computes N=pq and λ=lcm(p−1, q−1). The public key is pk={N, H_identifier} and the private key is sk={λ}. The message space is [Image Omitted] =_N, namely the ring of integers modulo N.

Encryption proceeds as follows. The encryption of a message m∈ [Image Omitted] ,

[Image Omitted]

is given by the tuple (c, V, s) where

c=(1+mN)r^Nmod N², V=H(u^Nmod N), s=ur^emod N

for random integers r, u∈[1, N) and where e=H(c, V).

Decryption proceeds as follows: Given a ciphertext [Image Omitted] =(c, V, s), the decryption process proceeds in two stages.

- Validating the ciphertext: Compute e=H(c, V) and U=s^Nc^−emod N, and check whether VH(U). If not, return ⊥ and abort.
- Deciphering the ciphertext: From the component c, the corresponding plaintext can be recovered using the private key λ in two steps as:
- 1. Compute

L
=

c
λ

-

1



mod




N
2

N

;

and

- 2. Return m=L/λ mod N.

Several variants may be derived from the above description. In particular, the modifications mentioned with respect to the first embodiment described above apply similarly to this second embodiment. Yet another variant is to select a different hash function, for example V=G(u^Nmod N), for defining the component V of a ciphertext.

Note that the embodiments described above produce ciphertexts that are triplets where the first component is a regular Paillier ciphertext. It is therefore straightforward to convert any ciphertext into a regular Paillier ciphertext.

Embodiments described herein may be applied to all services or products requiring chosen-ciphertext secure encryption. Remarkably, the validity of the resulting ciphertexts can be publicly verified. Furthermore, the resulting ciphertexts can be converted into regular Paillier ciphertexts and so combined using the underlying additive homomorphism. Accordingly, the embodiments described herein provide a technological advancement to encryption protocols that are both homomorphic and secure against chosen ciphertext attacks.

FIG. 1 illustrates an exemplary hardware diagram 100 for implementing a cryptosystem according to the embodiments described above. As shown, the device 100 includes a processor 120, memory 130, user interface 140, network interface 150, and storage 160 interconnected via one or more system buses 110. It will be understood that FIG. 1 constitutes, in some respects, an abstraction and that the actual organization of the components of the device 100 may be more complex than illustrated.

The processor 120 may be any hardware device capable of executing instructions stored in memory 130 or storage 160 or otherwise processing data. As such, the processor may include a microprocessor, field programmable gate array (FPGA), application-specific integrated circuit (ASIC), or other similar devices.

The memory 130 may include various memories such as, for example L1, L2, or L3 cache or system memory. As such, the memory 130 may include static random access memory (SRAM), dynamic RAM (DRAM), flash memory, read only memory (ROM), or other similar memory devices.

The user interface 140 may include one or more devices for enabling communication with a user such as an administrator. For example, the user interface 140 may include a display, a mouse, and a keyboard for receiving user commands. In some embodiments, the user interface 140 may include a command line interface or graphical user interface that may be presented to a remote terminal via the network interface 150. In some embodiments, no user interface may be present.

The network interface 150 may include one or more devices for enabling communication with other hardware devices. For example, the network interface 150 may include a network interface card (NIC) configured to communicate according to the Ethernet protocol. Additionally, the network interface 150 may implement a TCP/IP stack for communication according to the TCP/IP protocols. Various alternative or additional hardware or configurations for the network interface 150 will be apparent.

The storage 160 may include one or more machine-readable storage media such as read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, or similar storage media. In various embodiments, the storage 160 may store instructions for execution by the processor 120 or data upon with the processor 120 may operate. For example, the storage 160 may store a base operating system 161 for controlling various basic operations of the hardware 100. Further, software for key generation, 162, encryption 163, and decryption 163 may be stored in the memory. This software may implement the various embodiments described above.

It will be apparent that various information described as stored in the storage 160 may be additionally or alternatively stored in the memory 130. In this respect, the memory 130 may also be considered to constitute a “storage device” and the storage 160 may be considered a “memory.” Various other arrangements will be apparent. Further, the memory 130 and storage 160 may both be considered to be “non-transitory machine-readable media.” As used herein, the term “non-transitory” will be understood to exclude transitory signals but to include all forms of storage, including both volatile and non-volatile memories.

While the host device 100 is shown as including one of each described component, the various components may be duplicated in various embodiments. For example, the processor 120 may include multiple microprocessors that are configured to independently execute the methods described herein or are configured to perform steps or subroutines of the methods described herein such that the multiple processors cooperate to achieve the functionality described herein. Further, where the device 100 is implemented in a cloud computing system, the various hardware components may belong to separate physical systems. For example, the processor 120 may include a first processor in a first server and a second processor in a second server.

Any combination of specific software running on a processor to implement the embodiments of the invention, constitute a specific dedicated machine.

As used herein, the term “non-transitory machine-readable storage medium” will be understood to exclude a transitory propagation signal but to include all forms of volatile and non-volatile memory.

It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention.

Although the various exemplary embodiments have been described in detail with particular reference to certain exemplary aspects thereof, it should be understood that the invention is capable of other embodiments and its details are capable of modifications in various obvious respects. As is readily apparent to those skilled in the art, variations and modifications can be effected while remaining within the spirit and scope of the invention. Accordingly, the foregoing disclosure, description, and figures are for illustrative purposes only and do not in any way limit the invention, which is defined only by the claims.