ENCRYPTION SCHEMES WITH ADDITIONAL PROPERTIES

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First 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.
1 Assignment
0 Petitions
Accused Products
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.
0 Citations
No References
No References
19 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.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
 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.  View Dependent Claims (14, 15, 16, 17, 18, 19)
1 Specification
Various exemplary embodiments disclosed herein relate generally to a method and apparatus for implementing new encryption schemes with additional properties.
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.
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^{N }mod N^{2}.
Various embodiments are described, wherein U=u^{N }mod N where U is the first verification value.
Various embodiments are described, wherein s=ur^{e }mod N and where e=H(c, U).
Various embodiments are described, wherein s=ur^{e }mod N and where e=H(c, U, pk) where pk is a public key.
Various embodiments are described, wherein V=H(u^{N }mod N) where V is the first verification value.
Various embodiments are described, wherein s=ur^{e }mod N and where e=H(c, V).
Various embodiments are described, wherein s=ur^{e }mod N and where e=H(c, U, pk) where pk is a public key.
Various embodiments are described, 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.
Various embodiments are described, wherein s=ur^{e }mod N and where e=H(c, V).
Various embodiments are described, wherein s=ur^{e }mod 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^{N}c^{−e }mod 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^{N}c^{−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.
Various embodiments are described, wherein
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^{d }mod N, where d is the secret key and d=N^{−1 }mod λ where λ=lcm(p−1, q−1); and computing
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^{N}c^{−e }mod N.
Various embodiments are described, wherein validating the ciphertext further includes a public key pk.
In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein:
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.
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 nonexclusive 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 publickey encryption will be described. Then the notion of a zeroknowledge proof will be described.
A publickey 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
Encryption is carried out as follows. Let 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
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
it is required that Dec_{sk}(Enc_{pk}(m))=m for any message m∈.
Zeroknowledge proofs will now be described. Informally, in a zeroknowledge 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 =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^{R}C·y^{C }(in ).
It can be verified that the cheating probability for Peggy is 2^{−l}.
Zeroknowledge proofs can be made noninteractive in the random oracle model by replacing the challenge by a hash of the transcript to that point. This is known as the FiatShamir 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∈_{q }and 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^{s}C·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 cH(g^{s}·y^{−c}).
The Paillier cryptosystem and the GuillouQuisquater (GQ) identification scheme will now be briefly described.
The Paillier cryptosystem is a publickey encryption scheme supporting a large message space. For a more detailed description see Pascal Paillier, Publickey 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. 223238, 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∈,
is given by
c=(1+mN)r^{N }mod N^{2 }
 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
and
 2. Return m=L/λ mod N.
It is worth noting that for any ρ∈_{N}_{2}, one has ρ^{N}≡(ρ mod N)^{N}(mod N^{2}). 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,
the addition of c_{1 }and c_{2 }is defined as
AddH(c_{1},c_{2})=(c_{1}·c_{2})ρ^{N }mod N^{2 }
for some integer ρ∈[1, N). The scheme is said to be additively homomorphic because the decryption of the soobtained ciphertext yields the message m_{1}+m_{2 }(as an element in ). Indeed, letting c_{1}=(1+m_{1}N)r_{1}^{N }mod N^{2 }and c_{2}=(1+m_{2}N)r_{2}^{N }mod N^{2}, the following results
with R=r_{1}r_{2}ρ mod N^{2}, the decryption of which leads to m_{1}+m_{2}(mod N).
The GuillouQuisquater (GQ) identification protocol will now be described. The socalled GQ protocol, named after its inventors Guillou and Quisquater, is a practical zeroknowledge protocol. For more detailed information about the GQ protocol see Louis C. Guillou and JeanJacques Quisquater, A practical zeroknowledge 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. 123128, which is incorporated herein for all purposes by reference.
Let N=pq where p and q are distinct primes. To prove in a zeroknowledge way that Peggy knows a secret value s satisfying s^{e}v≡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^{e }mod N, and sends C to Victor;
 2. Victor chooses a random challenge c∈_{e }and sends c to Peggy;
 3. Peggy computes the response R=rs^{c }mod N and sends R to Victor;
 4. Victor checks that CR^{e}v^{c}(mod N).
 Proof. It is easily verified that R^{e}v^{c}≡(rs^{c})^{e}v^{c}≡r^{e}(s^{e}v)^{c}≡C(mod N).
Assuming the random oracle model, the proof can be made noninteractive by replacing c with H(C) for some cryptographic hash function H mapping to _{e}.
In the presence of a passive adversary, the “right” notion of security for publickey 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 chosenciphertext security or equivalently nonmalleability. Intuitively, it implies that semantic security must hold even if the attacker is given adaptive access to a decryption oracle.
More formally, an adversary is viewed as a pair (_{1}, _{2}) of probabilistic algorithms. This corresponds to adversary running the algorithms in two stages.
In the “find” stage, algorithm _{1 }takes as input the public key pk. _{1 }can submit any ciphertext of its choice and receives the corresponding plaintext (or ⊥). _{1 }outputs two equalsize messages m_{0 }and m_{1}∈.
In the “guess” stage, algorithm _{2 }receives a challenge ciphertext c* which is the encryption of m_{0 }or of m_{1 }under pk; i.e., c*←Enc_{pk}(m_{b}) where b is chosen uniformly at random in {0,1}. Again, _{2 }can submit any ciphertext and see the corresponding decryption; the sole exception is that _{2 }cannot ask for the decryption of the challenge ciphertext c*.
The goal of _{2 }is to guess correctly—with probability significantly greater than ½—if c* corresponds to the encryption of m_{0 }or of m_{1}.
An encryption scheme is said chosenciphertext secure if no such adversary =(_{1}, _{2}) exists.
The Paillier cryptosystem is semantically secure. Unfortunately, the Paillier cryptosystem does not meet the stronger notion of chosenciphertext security. This is due to the underlying additive homomorphism.
Upon receiving the challenge ciphertext c*=(1+m_{b}N)r^{N }mod N^{2}, the adversary _{2 }does the following:
 1. It chooses at random μ, ρ∈_{N }and forms the ciphertext c^{†}=c*(1+μN)ρ^{N }mod N^{2};
 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_{0 }it outputs 0; otherwise it outputs 1.
To remedy this situation, Paillier subsequently proposed with Pointcheval a chosenciphertext secure version of his cryptosystem. For more details see Pascal Paillier and David Pointcheval, Efficient pubickey cryptosystems provably secure against active adversaries, Advances in Cryptology—ASIACRYPT '"'"'99 (KwokYan Lam, Eiji Okamoto, and Chaoping Xing, eds.), Lecture Notes in Computer Science, vol. 1716, Springer, Heidelberg, November 1999, pp. 165179, which is hereby incorporated herein by reference for all purposes. The improved cryptosystem requires two hash functions G, H mapping to _{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^{2 }where
z=H(m,r)^{N }mod N^{2 }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
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 PaillierPointcheval cryptosystem is chosenciphertext 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 chosenciphertext versions of Paillier cryptosystem with public validity test. This disclosure presents several embodiments of such a Paillier cryptosystem.
In addition to chosenciphertext 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^{N }mod N^{2}, satisfies the relation
r^{N}c^{−1}≡1(mod N).
Viewing the pair (r, c^{−1 }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^{N }mod N and s=ur^{e }mod 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 =_{N}, namely the ring of integers modulo N.
Encryption proceeds as follows. The encryption of a message m∈,
is given by the tuple (c, U, s) where
c=(1+mN)r^{N }mod N^{2}, U=u^{N }mod N, s=ur^{e }mod N
for random integers r, u∈[1, N) and where e=H(c, U).
Decryption proceeds as follows. Given a ciphertext =(c, U, s), the decryption process proceeds in two stages.
 Validating the ciphertext: Compute e=H(c, U) and check whether Us^{N}c^{−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
and
 2. Return m=L/λ mod N.
Given a ciphertext =(c, U, s) with c=(1+mN)r^{N }mod N^{2}, 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
Hence, the above cryptosystem yields a zeroknowledge 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^{−1 }mod λ, and to recover the plaintext corresponding to a valid ciphertext =(c, U, s) using d to
 1. Compute r=c^{d }mod N, and
 2. Return
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 modN 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 =_{N}, namely the ring of integers modulo N.
Encryption proceeds as follows. The encryption of a message m∈,
is given by the tuple (c, V, s) where
c=(1+mN)r^{N }mod N^{2}, V=H(u^{N }mod N), s=ur^{e }mod N
for random integers r, u∈[1, N) and where e=H(c, V).
Decryption proceeds as follows: Given a ciphertext =(c, V, s), the decryption process proceeds in two stages.
 Validating the ciphertext: Compute e=H(c, V) and U=s^{N}c^{−e }mod 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
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^{N }mod 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 chosenciphertext 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.
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), applicationspecific 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 machinereadable storage media such as readonly memory (ROM), randomaccess memory (RAM), magnetic disk storage media, optical storage media, flashmemory 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 “nontransitory machinereadable media.” As used herein, the term “nontransitory” will be understood to exclude transitory signals but to include all forms of storage, including both volatile and nonvolatile 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 “nontransitory machinereadable storage medium” will be understood to exclude a transitory propagation signal but to include all forms of volatile and nonvolatile 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.