1 /* 2 * Copyright 2019 Google LLC. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * https://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 // Implementation of the Damgaard-Jurik cryptosystem. 17 // Damgaard, Ivan, Mads Jurik, and Jesper Buus Nielsen. "A generalization of 18 // Paillier's public-key system with applications to electronic voting." 19 // International Journal of Information Security 9.6 (2010): 371-385. 20 // This header defines two classes: 21 // (1) PublicPaillier defining homomorphic operations (i.e., Add, Multiply and 22 // LeftShift) and also the Encrypt function using the public key. 23 // (2) PrivatePaillier defining Decrypt and a more efficient Encrypt function 24 // than the one in PublicPaillier by utilizing the private key. 25 // One example usage (the possible usages of these two classes are by no means 26 // limited to this one): 27 // Alice Bob 28 // +-------------------------------+ +------------------------------+ 29 // | | | | 30 // |Context ctx; | | | 31 // |BigNum p = | | | 32 // | ctx.GenerateSafePrime(512) | | | 33 // |BigNum q = | | | 34 // | ctx.GenerateSafePrime(512) | n and s | | 35 // |BigNum n = p * q; +---------->Context ctx; | 36 // | | | | 37 // |PrivatePaillier pp(&ctx, n, s);| |PublicPaillier pp(&ctx, n, s);| 38 // | | | | 39 // |String ct1 = pp.Encrypt(m1); | | | 40 // |... | ct1..k | | 41 // |String ctk = pp.Encrypt(mk); +---------->Shuffle ct1..k | 42 // | | |Generate random BigNum r1..k | 43 // | | |such that mi+ri is less than | 44 // | | |n^s for any i in 1..k | 45 // | | |BigNum rcti = pp.Encrypt( | 46 // | | | ri.ToBytes()) for i in 1..k| 47 // | | ct1..k |cti = pp.Add(cti, rcti) | 48 // |BigNum mri = pp.Decrypt(cti) <----------+ for i in 1..k | 49 // | for i in 1..k | | | 50 // |// mri = mj + ri | | | 51 // |// where only Bob knows i->j | | | 52 // +-------------------------------+ +------------------------------+ 53 54 #ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PAILLIER_H_ 55 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PAILLIER_H_ 56 57 #include <memory> 58 #include <string> 59 #include <utility> 60 #include <vector> 61 62 #include "private_join_and_compute/crypto/big_num.h" 63 #include "private_join_and_compute/crypto/context.h" 64 #include "private_join_and_compute/crypto/paillier.pb.h" 65 #include "private_join_and_compute/util/status.inc" 66 67 namespace private_join_and_compute { 68 69 // A helper class for doing Paillier crypto for only one of the primes forming 70 // the composite number n. 71 class PrimeCrypto; 72 // A helper class that wraps a PrimeCrypto, that can additionally return the 73 // random number (used in an encryption) with the ciphertext. 74 class PrimeCryptoWithRand; 75 76 class FixedBaseExp; 77 class TwoModulusCrt; 78 79 // Holds the resulting ciphertext from a Paillier encryption as well as the 80 // random number used. 81 struct PaillierEncAndRand { 82 BigNum ciphertext; 83 BigNum rand; 84 }; 85 86 // Returns a Paillier public key and private key. The Paillier modulus n will be 87 // generated to be the product of safe primes p and q, each of modulus_length/2 88 // bits. "s" is the Damgard-Jurik parameter: the corresponding message space is 89 // n^s, and the ciphertext space is n^(s+1). 90 StatusOr<std::pair<PaillierPublicKey, PaillierPrivateKey>> 91 GeneratePaillierKeyPair(Context* ctx, int32_t modulus_length, int32_t s); 92 93 // The class defining Damgaard-Jurik cryptosystem operations that can be 94 // performed with the public key. 95 // Example: 96 // std::unique_ptr<Context> ctx; 97 // BigNum n = ctx->CreateBigNum(n_in_bytes); 98 // std::unique_ptr<PublicPaillier> public_paillier( 99 // new PublicPaillier(ctx.get(), n, 2)); 100 // BigNum ciphertext = public_paillier->Encrypt(message); 101 // 102 // This class is not thread-safe since Context is not thread-safe. 103 // Note that this class does *not* take the ownership of Context. 104 class PublicPaillier { 105 public: 106 // Creates a generic PublicPaillier with the public key n and s. 107 // n is a composite number equals to p * q where p and q are safe primes and 108 // private. 109 // n^s is the plaintext size and n^(s+1) is the ciphertext size. 110 PublicPaillier(Context* ctx, const BigNum& n, int s); 111 112 // Creates a PublicPaillier equivalent to the original Paillier cryptosystem 113 // (i.e., s = 1) 114 // n is the plaintext size and n^2 is the ciphertext size. 115 PublicPaillier(Context* ctx, const BigNum& n); 116 117 // Creates a PublicPaillier from the given proto. 118 PublicPaillier(Context* ctx, const PaillierPublicKey& public_key_proto); 119 120 // PublicPaillier is neither copyable nor movable. 121 PublicPaillier(const PublicPaillier&) = delete; 122 PublicPaillier& operator=(const PublicPaillier&) = delete; 123 124 ~PublicPaillier(); 125 126 // Adds two ciphertexts homomorphically such that the result is an 127 // encryption of the sum of the two plaintexts. 128 BigNum Add(const BigNum& ciphertext1, const BigNum& ciphertext2) const; 129 130 // Multiplies a ciphertext homomorphically such that the result is an 131 // encryption of the product of the plaintext and the multiplier. 132 // Note that multiplier should *not* be encrypted. 133 BigNum Multiply(const BigNum& ciphertext, const BigNum& multiplier) const; 134 135 // Left shifts a ciphertext homomorphically such that the result is an 136 // encryption of the plaintext left shifted by shift_amount. 137 BigNum LeftShift(const BigNum& ciphertext, int shift_amount) const; 138 139 // Encrypts the message and returns the ciphertext equivalent to: 140 // (1+n)^message * g^random mod n^(s+1), where g is the generator chosen 141 // during setup. 142 // Returns INVALID_ARGUMENT status when the message is < 0 or >= n^s. 143 StatusOr<BigNum> Encrypt(const BigNum& message) const; 144 145 // Encrypts the message similar to Encrypt, but uses a provided random 146 // value. It uses the generator g for a subgroup of n^s-th residues to speed 147 // up encryption, by computing (1+n)^message * generator^random mod n^(s+1). 148 // See DJN section 4.2 for more details. 149 // Returns INVALID_ARGUMENT if rand is not less than or equal to n. 150 // Assumes the message is already in the right range. 151 // It is the caller's responsibility to ensure the randomness of rand. 152 StatusOr<BigNum> EncryptUsingGeneratorAndRand(const BigNum& message, 153 const BigNum& rand) const; 154 155 // Encrypts the message similar to Encrypt, but uses a provided random 156 // value. It computes the ciphertext directly (without the generator), as 157 // (1+n)^message * random^(n^s) mod n^(s+1). 158 // It contains an expensive exponentiation since n^s is large 159 // Returns INVALID_ARGUMENT if rand is not in Zn*. 160 // Assumes the message is already in the right range. 161 // It is the caller's responsibility to ensure the randomness of rand. 162 StatusOr<BigNum> EncryptWithRand(const BigNum& message, 163 const BigNum& rand) const; 164 165 // Encrypts the message by generating a random number and using 166 // EncryptWithRand, additionally retaining the random number used and 167 // returning it with the ciphertext. 168 StatusOr<PaillierEncAndRand> EncryptAndGetRand(const BigNum& message) const; 169 n()170 const BigNum& n() const { return n_; } s()171 int s() const { return s_; } 172 173 private: 174 // Factory class for creating BigNums and holding the temporary values for 175 // the BigNum arithmetic operations. Ownership is not taken. 176 Context* const ctx_; 177 // Composite BigNum of two large primes. 178 const BigNum n_; 179 const int s_; 180 // Vector containing the n powers upto s+1 for faster computation. 181 const std::vector<BigNum> n_powers_; 182 // n^(s+1) 183 const BigNum modulus_; 184 // generator of the subgroup of n^s-th residues mod n^s+1. Used for faster 185 // computation of the random component r of the ciphertext. 186 std::unique_ptr<FixedBaseExp> g_n_fbe_; 187 // The vector holding values that are computed repeatedly when encrypting 188 // arbitrary messages via computing the binomial expansion of (1+n)^message. 189 // The binomial expansion of (1+n) to some arbitrary exponent has constant 190 // factors depending on only 1, n, and s regardless of the exponent value, 191 // this vector holds each of these fixed values for faster computation. 192 // Refer to Section 4.2 "Optimization of Encryption" from the 193 // Damgaard-Jurik-Nielsen paper for more information. 194 const std::vector<BigNum> precomp_; 195 }; 196 197 // The class defining Damgaard-Jurik cryptosystem operations that can be 198 // performed with the private key. 199 // This does not include the homomorphic operations as they are irrelevant when 200 // the private key is present. Use PublicPaillier for these operations. 201 // Example: 202 // std::unique_ptr<Context> ctx; 203 // BigNum p = ctx->CreateBigNum(p_in_bytes); 204 // BigNum q = ctx->CreateBigNum(q_in_bytes); 205 // std::unique_ptr<PrivatePaillier> private_paillier( 206 // new PrivatePaillier(ctx.get(), p, q, 2)); 207 // BigNum ciphertext = private_paillier->Encrypt(message); 208 // BigNum message_as_bignum = private_paillier->Decrypt(ciphertext); 209 // 210 // This class is not thread-safe since Context is not thread-safe. 211 // Note that this class does *not* take the ownership of Context. 212 class PrivatePaillier { 213 public: 214 // Creates a PrivatePaillier using the s value and the private key p and q. 215 // p and q are safe primes and (p*q)^s is the plaintext size and (p*q)^(s+1) 216 // is the ciphertext size. 217 PrivatePaillier(Context* ctx, const BigNum& p, const BigNum& q, int s); 218 219 // Creates a PrivatePaillier equivalent to the original Paillier cryptosystem 220 // (i.e., s = 1) 221 PrivatePaillier(Context* ctx, const BigNum& p, const BigNum& q); 222 223 // Creates a PrivatePaillier from the supplied key proto. 224 PrivatePaillier(Context* ctx, const PaillierPrivateKey& private_key_proto); 225 226 // PrivatePaillier is neither copyable nor movable. 227 PrivatePaillier(const PrivatePaillier&) = delete; 228 PrivatePaillier& operator=(const PrivatePaillier&) = delete; 229 230 // Needed to avoid default inline one so that forward declaration works. 231 ~PrivatePaillier(); 232 233 // Encrypts the message and returns the ciphertext equivalent (in security) to 234 // (1+n)^message * random^(n^s) mod n^(s+1). 235 // This is more efficient than the encryption using the PublicPaillier due to: 236 // 1) Doing computation on each safe prime (half the size of n) and combine 237 // the two result with Chinese Remainder Theorem. 238 // 2) For each safe prime part, we can convert random^(n^s) into g^random 239 // where g is a fixed generator. This decreases the number of modular 240 // multiplications done from O(slogn) to O(logn). Given a fast fixed based 241 // exponentiation is used rather than naively computing g^random in each 242 // time Encrypt is called, this O(logn) complexity can be further improved 243 // relatively to the used method effectiveness. 244 // 245 // Returns INVALID_ARGUMENT status when the message is < 0 or >= n^s. 246 StatusOr<BigNum> Encrypt(const BigNum& message) const; 247 248 // Decrypts the ciphertext and returns the message inside as a BigNum. 249 // Uses the algorithm from the Theorem 1 in Damgaard-Jurik-Nielsen paper. 250 // This method also benefits from computing the decryption for each safe prime 251 // part separately and then combining them together with the Chinese Remainder 252 // Theorem. 253 // Returns INVALID_ARGUMENT status when the ciphertext is < 0 or >= n^(s+1). 254 StatusOr<BigNum> Decrypt(const BigNum& ciphertext) const; 255 256 private: 257 friend class PrivatePaillierWithRand; 258 // Factory class for creating BigNums and holding the temporary values for 259 // the BigNum arithmetic operations. Ownership is not taken. 260 Context* const ctx_; 261 // (p*q)^s 262 const BigNum n_to_s_; 263 // (p*q)^(s+1) 264 const BigNum n_to_s_plus_one_; 265 // Helper defining Encrypt and Decrypt for the safe prime, p. 266 std::unique_ptr<PrimeCrypto> p_crypto_; 267 // Helper defining Encrypt and Decrypt for the safe prime, q. 268 std::unique_ptr<PrimeCrypto> q_crypto_; 269 // Helper for combining two encryption computed with the above PrimeCrypto 270 // helpers. 271 std::unique_ptr<TwoModulusCrt> two_mod_crt_encrypt_; 272 // Helper for combining two decryption computed with the above PrimeCrypto 273 // helpers. 274 std::unique_ptr<TwoModulusCrt> two_mod_crt_decrypt_; 275 }; 276 277 // This class is similar to PrivatePaillier, but it can additionally report 278 // the last random used in encryption. 279 class PrivatePaillierWithRand { 280 public: 281 // Creates a PrivatePaillierWithRand from the given PrivatePaillier. 282 explicit PrivatePaillierWithRand(PrivatePaillier* private_paillier); 283 284 // PrivatePaillier is neither copyable nor movable. 285 PrivatePaillierWithRand(const PrivatePaillierWithRand&) = delete; 286 PrivatePaillierWithRand& operator=(const PrivatePaillierWithRand&) = delete; 287 288 ~PrivatePaillierWithRand(); 289 290 // Encrypt with the underlying PrivatePaillier. 291 StatusOr<BigNum> Encrypt(const BigNum& message) const; 292 293 // Encrypts and returns the random used in the encryption. 294 // Internally two random numbers are used which must be combined with a crt 295 // calculation. 296 // 297 // crt((g_p^r1)^(n^s), (g_q^r2)^(n^s)) = r^(n^s) where crt coprimes are 298 // p^(s+1) and q^(s+1). This can be rewritten as 299 // crt(g_p^r1, g_q^r2) = r where crt coprimes are p and q. 300 StatusOr<PaillierEncAndRand> EncryptAndGetRand(const BigNum& message) const; 301 302 // Decrypt with the underlying PrivatePaillier. 303 StatusOr<BigNum> Decrypt(const BigNum& ciphertext) const; 304 305 private: 306 Context* const ctx_; 307 const PrivatePaillier* const private_paillier_; 308 // Helper to combine the two random numbers kept in the two PrimeCrypto 309 // instances within the PrivatePaillier. 310 std::unique_ptr<TwoModulusCrt> two_mod_crt_rand_; 311 // Helpers defining Encrypt and Decrypt for the safe primes p and q, that can 312 // additionally return the random number (used in an encryption) with the 313 // ciphertext. 314 std::unique_ptr<PrimeCryptoWithRand> p_crypto_; 315 std::unique_ptr<PrimeCryptoWithRand> q_crypto_; 316 }; 317 318 } // namespace private_join_and_compute 319 320 #endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PAILLIER_H_ 321