private_join_and_compute/crypto/camenisch_shoup.h - platform/external/private-join-and-compute - Git at Google

 /*
  * Copyright 2019 Google LLC.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     https://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 // Implementation of the Camenisch-Shoup cryptosystem.
 //
 // Jan Camenisch, Victor Shoup. "Practical verifiable
 // encryption and decryption of discrete logarithms"
 // Advances in Cryptology - CRYPTO 2003.
 // This header defines the class CamenischShoup, representing a key for the
 // Camenisch Shoup cryptosystem. It can be initialized with or without the
 // private (decryption) key.
 // The class, once initialized, allows encryption and decryption of messages.
 // The implementation here does not include the portion of the ciphertext,
 // corresponding to non-malleability, as described in [CS'03].
 //
 // Example Usage:
 //  Context ctx;
 //  CamenischShoupKey key  = GenerateCamenischShoupKey(&ctx, n_length_bits, s,
 //    vector_encryption_length);
 //  PrivateCamenischShoup private_key(&ctx, key.n, key.s, key.g, key.xs,
 //    key.ys);
 //  CamenischShoupCiphertext ct = key.Encrypt(ms);

 #ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_
 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_

 #include <cstdint>
 #include <map>
 #include <memory>
 #include <utility>
 #include <vector>

 #include "private_join_and_compute/crypto/big_num.h"
 #include "private_join_and_compute/crypto/context.h"
 #include "private_join_and_compute/crypto/fixed_base_exp.h"
 #include "private_join_and_compute/crypto/proto/camenisch_shoup.pb.h"
 #include "private_join_and_compute/util/status.inc"

 namespace private_join_and_compute {

 struct CamenischShoupCiphertext {
   // For public key (g,ys,n), messages ms, and randomness r and power s:
   // u =  g^r mod n^(s+1)
   // es[i] =  (1+n)^ms[i] * ys[i]^r mod n^(s+1)
   BigNum u;
   std::vector<BigNum> es;
 };

 // Holds a single Camenisch-Shoup ciphertext, together with the randomness used
 // to encrypt.
 struct CamenischShoupCiphertextWithRand {
   CamenischShoupCiphertext ct;
   BigNum r;
 };

 // Returns a BigNum g that is a random (n^s)-th residue modulo
 // n^(s+1). Computed as g = x^(2n^s) mod n^(s+1) for random x in Z_(n^(s+1)).
 // Assumes that n is a product of 2 safe primes.
 BigNum GetGeneratorForCamenischShoup(Context* ctx, const BigNum& n, uint64_t s);

 struct CamenischShoupKey {
   BigNum p;                           // A safe prime.
   BigNum q;                           // A different safe prime.
   BigNum n;                           // p * q
   uint64_t s;                         // n^(s+1) is the modulus for the scheme.
   uint64_t vector_encryption_length;  // The number of ys and xs per ciphertext.
   BigNum g;                           // A random 2(n^s)-th residue mod n^(s+1).
   std::vector<BigNum> ys;             // ys[i] = g^xs[i] mod n^(s+1)
   // Each x in xs is a secret key, a random value between 0 and n, relatively
   // prime to n.
   std::vector<BigNum> xs;
 };

 struct CamenischShoupPublicKey {
   BigNum n;                           // p * q, for secret p and q.
   uint64_t s;                         // n^(s+1) is the modulus for the scheme.
   uint64_t vector_encryption_length;  // The number of ys and xs per ciphertext.
   BigNum g;                           // A random 2(n^s)-th residue mod n^(s+1).
   // ys[i] = g^xs[i] mod n^(s+1) for xs in the secret key
   std::vector<BigNum> ys;
 };

 struct CamenischShoupPrivateKey {
   // ys[i] = g^xs[i] mod n^(s+1) for all other values in the public key.
   std::vector<BigNum> xs;
 };

 // Generates a new key for the Camenisch-Shoup cryptosystem.
 CamenischShoupKey GenerateCamenischShoupKey(Context* ctx, int n_length_bits,
                                             uint64_t s,
                                             uint64_t vector_encryption_length);

 // Generates a new key pair for the Camenisch-Shoup cryptosystem. Assumes that
 // the modulus n has been correctly generated elsewhere as the product of 2
 // sufficiently long safe (or pseudo-safe) primes.
 std::pair<std::unique_ptr<CamenischShoupPublicKey>,
           std::unique_ptr<CamenischShoupPrivateKey>>
 GenerateCamenischShoupKeyPair(Context* ctx, const BigNum& n, uint64_t s,
                               uint64_t vector_encryption_length);

 // Creates a proto from the PublicKey struct.
 proto::CamenischShoupPublicKey CamenischShoupPublicKeyToProto(
     const CamenischShoupPublicKey& public_key);
 // Parses PublicKey proto into a struct.
 StatusOr<CamenischShoupPublicKey> ParseCamenischShoupPublicKeyProto(
     Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto);
 // Creates a proto from the PrivateKey struct.
 proto::CamenischShoupPrivateKey CamenischShoupPrivateKeyToProto(
     const CamenischShoupPrivateKey& private_key);
 // Parses PrivateKey proto into a struct.
 StatusOr<CamenischShoupPrivateKey> ParseCamenischShoupPrivateKeyProto(
     Context* ctx, const proto::CamenischShoupPrivateKey& private_key_proto);
 // Creates a proto from the Ciphertext struct.
 proto::CamenischShoupCiphertext CamenischShoupCiphertextToProto(
     const CamenischShoupCiphertext& ciphertext);

 // The classes below implement the Camenisch-Shoup cryptosystem.
 // Does not include features of [CS'03] corresponding to non-malleability of
 // ciphertexts.

 class PublicCamenischShoup {
  public:
   // Initializes a public key for the Camenisch-Shoup cryptosystem.
   // Accepts modulus n which is the product of safe primes p and q, a power s,
   // random n-th residue g modulo n^(s+1), and y = g^x for unknown x. Also
   // accepts a Context, of which it doesn't take ownership.
   PublicCamenischShoup(Context* ctx, const BigNum& n, uint64_t s,
                        const BigNum& g, std::vector<BigNum> ys);

   // Parses the key proto and creates a PublicCamenischShoup. Fails when
   // parsing fails.
   static StatusOr<std::unique_ptr<PublicCamenischShoup>> FromProto(
       Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto);

   // PublicCamenischShoup is neither copyable nor movable.
   PublicCamenischShoup(const PublicCamenischShoup&) = delete;
   PublicCamenischShoup& operator=(const PublicCamenischShoup&) = delete;
   PublicCamenischShoup(PublicCamenischShoup&&) = delete;
   PublicCamenischShoup& operator=(PublicCamenischShoup&&) = delete;
   ~PublicCamenischShoup() = default;

   // Encrypts a message as (u = g^r mod n^(s+1), es) where es[i] = ys[i]^r *
   // (1+n)^ms[i] mod n^(s+1)). If |ms| < |ys_|, the remaining messages are
   // implicitly 0.
   //
   // Returns INVALID_ARGUMENT if the message is not >= 0, or if |ms| is > |ys_|.
   StatusOr<CamenischShoupCiphertext> Encrypt(const std::vector<BigNum>& ms);

   // Encrypts a message as in Encrypt, and also returns the randomness used for
   // encryption.
   StatusOr<CamenischShoupCiphertextWithRand> EncryptAndGetRand(
       const std::vector<BigNum>& ms);

   // Encrypts a message as (u = g^r mod n^(s+1), v = y^r * (1+n)^m mod n^(s+1)),
   // using the randomness supplied. If |ms| < |ys_|, the remaining messages are
   // implicitly 0.
   //
   // Returns INVALID_ARGUMENT if the message or randomness is not >= 0, or if
   // |ms| is > |ys_|.
   StatusOr<CamenischShoupCiphertext> EncryptWithRand(
       const std::vector<BigNum>& ms, const BigNum& r);

   // Homomorphically adds two ciphertexts mod n^(s+1).
   CamenischShoupCiphertext Add(const CamenischShoupCiphertext& ct1,
                                const CamenischShoupCiphertext& ct2);

   // Homomorphically multiplies a ciphertexts with a given scalar mod n.
   CamenischShoupCiphertext Multiply(const CamenischShoupCiphertext& ct,
                                     const BigNum& scalar);

   // Parses a CamenischShoupCiphertext if it appears to be consistent with the
   // key.
   //
   // Fails with INVALID_ARGUMENT if the ciphertext does not match the modulus,
   // or has too many components.
   StatusOr<CamenischShoupCiphertext> ParseCiphertextProto(
       const proto::CamenischShoupCiphertext& ciphertext_proto);

   // Getters
   inline const BigNum& g() const { return g_; }                 // generator
   inline const std::vector<BigNum>& ys() const { return ys_; }  // public keys
   inline const BigNum& n() const { return n_; }
   inline uint64_t s() const { return s_; }
   inline uint64_t vector_encryption_length() const {
     return vector_encryption_length_;
   }
   inline const BigNum& modulus() const { return modulus_; }  // = n^(s+1)
   inline const BigNum& message_upper_bound() const { return n_to_s_; }
   inline const BigNum& randomness_upper_bound() const { return n_; }

  private:
   Context* const ctx_;
   const BigNum n_;
   const uint64_t s_;
   const uint64_t vector_encryption_length_;  // = |ys|.
   // Vector containing the n powers up to s+1 for faster computation.
   const std::vector<BigNum> powers_of_n_;
   // The vector holding values that are computed repeatedly when encrypting
   // arbitrary messages via computing the binomial expansion of (1+n)^message.
   // The binomial expansion of (1+n) to some arbitrary exponent has constant
   // factors depending on only 1, n, and s regardless of the exponent value,
   // this vector holds each of these fixed values for faster computation.
   // Refer to Section 4.2 "Optimization of Encryption" from the
   // Damgaard-Jurik-Nielsen paper for more information.
   const std::vector<BigNum> encryption_precomp_;
   const BigNum n_to_s_;
   const BigNum modulus_;  // equal to n^(s+1)
   const BigNum g_;
   const std::vector<BigNum> ys_;
   // For fast computation of g^r mod n^(s+1).
   const std::unique_ptr<FixedBaseExp> g_fbe_;
   // For fast computation of y^r mod n^(s+1).
   std::vector<std::unique_ptr<FixedBaseExp>> ys_fbe_;
 };

 class PrivateCamenischShoup {
  public:
   // Initializes a private key for the Camenisch-Shoup cryptosystem.
   // Accepts modulus n which is the product of safe primes p and q, a power s,
   // and a random n-th residue g modulo n^(s+1).
   // Also accepts x and y = g^x mod n^(s+1) for randomly selected x, where x
   // serves as the secret key. x should be randomly chosen between 0 and n and
   // relatively prime to n (i.e. x is in Z*n).
   // Also accepts a Context, of which it doesn't take ownership.
   // Returns a CHECK error if |ys| != |xs|.
   PrivateCamenischShoup(Context* ctx, const BigNum& n, uint64_t s,
                         const BigNum& g, std::vector<BigNum> ys,
                         std::vector<BigNum> xs);

   // Parses the key protos and creates a PrivateCamenischShoup. Fails when
   // parsing fails.
   static StatusOr<std::unique_ptr<PrivateCamenischShoup>> FromProto(
       Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto,
       const proto::CamenischShoupPrivateKey& private_key_proto);

   // PrivateCamenischShoup is neither copyable nor movable.
   PrivateCamenischShoup(const PrivateCamenischShoup&) = delete;
   PrivateCamenischShoup& operator=(const PrivateCamenischShoup&) = delete;
   PrivateCamenischShoup(PrivateCamenischShoup&&) = delete;
   PrivateCamenischShoup& operator=(PrivateCamenischShoup&&) = delete;
   ~PrivateCamenischShoup() = default;

   // Encrypts a message as (u = g^r mod n^2, v = y^r * (1+n)^m mod n^2). If |ms|
   // < |ys_|, the remaining messages are implicitly 0.
   //
   // Returns INVALID_ARGUMENT if some message is not >= 0, or if |ms| > |ys_|.
   StatusOr<CamenischShoupCiphertext> Encrypt(const std::vector<BigNum>& ms);

   // Encrypts a message as in Encrypt, and also returns the randomness used for
   // encryption.
   StatusOr<CamenischShoupCiphertextWithRand> EncryptAndGetRand(
       const std::vector<BigNum>& ms);

   // Encrypts a message as (u = g^r mod n^2, v = y^r * (1+n)^m mod n^2), using
   // the randomness supplied. If |ms| < |ys_|, the remaining messages are
   // implicitly 0.
   //
   // Returns INVALID_ARGUMENT if some message or the randomness not >= 0, or if
   // |ms| > |ys_|.
   StatusOr<CamenischShoupCiphertext> EncryptWithRand(
       const std::vector<BigNum>& ms, const BigNum& r);

   // Decrypts a given Camenisch-Shoup cipertext and returns the encrypted
   // message reduced mod n. Computes: ms such that (1+n)^ms[i] = (es[i] /
   // u^xs[i] mod n^(s+1)).
   //
   // Returns INVALID_ARGUMENT if the ciphertext is invalid/ cannot be decrypted.
   // Expects vector_encryption_length components in the ciphertext.
   StatusOr<std::vector<BigNum>> Decrypt(const CamenischShoupCiphertext& ct);

   // Parses a CamenischShoupCiphertext if it appears to be consistent with the
   // key.
   //
   // Fails with INVALID_ARGUMENT if the ciphertext does not match the modulus,
   // or has too many components.
   StatusOr<CamenischShoupCiphertext> ParseCiphertextProto(
       const proto::CamenischShoupCiphertext& ciphertext_proto);

   // Getters
   inline const BigNum& g() { return g_; }                 // generator
   inline const std::vector<BigNum>& ys() { return ys_; }  // public keys
   inline const std::vector<BigNum>& xs() { return xs_; }  // secret keys
   inline const BigNum& n() { return n_; }
   inline uint64_t s() { return s_; }
   inline const BigNum& modulus() { return modulus_; }
   inline uint64_t vector_encryption_length() {
     return vector_encryption_length_;
   }

  private:
   Context* const ctx_;
   const BigNum n_;
   const uint64_t s_;
   const uint64_t vector_encryption_length_;  // = |ys| = |xs|.
   // Vector containing the n powers up to s+1 for faster computation.
   const std::vector<BigNum> powers_of_n_;
   // The vector holding values that are computed repeatedly when encrypting
   // arbitrary messages via computing the binomial expansion of (1+n)^message.
   // The binomial expansion of (1+n) to some arbitrary exponent has constant
   // factors depending on only 1, n, and s regardless of the exponent value,
   // this vector holds each of these fixed values for faster computation.
   // Refer to Section 4.2 "Optimization of Encryption" from the
   // Damgaard-Jurik-Nielsen paper for more information.
   const std::vector<BigNum> encryption_precomp_;
   // Intermediate values used repeatedly in decryption.
   std::map<std::pair<int, int>, BigNum> decryption_precomp_;
   const BigNum n_to_s_;
   const BigNum modulus_;  // equal to n^(s+1)
   const BigNum g_;
   const std::vector<BigNum> ys_;
   const std::vector<BigNum> xs_;  // secret key
   std::unique_ptr<FixedBaseExp> g_fbe_;
   std::vector<std::unique_ptr<FixedBaseExp>> ys_fbe_;
 };

 }  // namespace private_join_and_compute

 #endif  // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_
	/*
	* Copyright 2019 Google LLC.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* https://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	// Implementation of the Camenisch-Shoup cryptosystem.
	//
	// Jan Camenisch, Victor Shoup. "Practical verifiable
	// encryption and decryption of discrete logarithms"
	// Advances in Cryptology - CRYPTO 2003.
	// This header defines the class CamenischShoup, representing a key for the
	// Camenisch Shoup cryptosystem. It can be initialized with or without the
	// private (decryption) key.
	// The class, once initialized, allows encryption and decryption of messages.
	// The implementation here does not include the portion of the ciphertext,
	// corresponding to non-malleability, as described in [CS'03].
	//
	// Example Usage:
	// Context ctx;
	// CamenischShoupKey key = GenerateCamenischShoupKey(&ctx, n_length_bits, s,
	// vector_encryption_length);
	// PrivateCamenischShoup private_key(&ctx, key.n, key.s, key.g, key.xs,
	// key.ys);
	// CamenischShoupCiphertext ct = key.Encrypt(ms);

	#ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_
	#define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_

	#include <cstdint>
	#include <map>
	#include <memory>
	#include <utility>
	#include <vector>

	#include "private_join_and_compute/crypto/big_num.h"
	#include "private_join_and_compute/crypto/context.h"
	#include "private_join_and_compute/crypto/fixed_base_exp.h"
	#include "private_join_and_compute/crypto/proto/camenisch_shoup.pb.h"
	#include "private_join_and_compute/util/status.inc"

	namespace private_join_and_compute {

	struct CamenischShoupCiphertext {
	// For public key (g,ys,n), messages ms, and randomness r and power s:
	// u = g^r mod n^(s+1)
	// es[i] = (1+n)^ms[i] * ys[i]^r mod n^(s+1)
	BigNum u;
	std::vector<BigNum> es;
	};

	// Holds a single Camenisch-Shoup ciphertext, together with the randomness used
	// to encrypt.
	struct CamenischShoupCiphertextWithRand {
	CamenischShoupCiphertext ct;
	BigNum r;
	};

	// Returns a BigNum g that is a random (n^s)-th residue modulo
	// n^(s+1). Computed as g = x^(2n^s) mod n^(s+1) for random x in Z_(n^(s+1)).
	// Assumes that n is a product of 2 safe primes.
	BigNum GetGeneratorForCamenischShoup(Context* ctx, const BigNum& n, uint64_t s);

	struct CamenischShoupKey {
	BigNum p; // A safe prime.
	BigNum q; // A different safe prime.
	BigNum n; // p * q
	uint64_t s; // n^(s+1) is the modulus for the scheme.
	uint64_t vector_encryption_length; // The number of ys and xs per ciphertext.
	BigNum g; // A random 2(n^s)-th residue mod n^(s+1).
	std::vector<BigNum> ys; // ys[i] = g^xs[i] mod n^(s+1)
	// Each x in xs is a secret key, a random value between 0 and n, relatively
	// prime to n.
	std::vector<BigNum> xs;
	};

	struct CamenischShoupPublicKey {
	BigNum n; // p * q, for secret p and q.
	uint64_t s; // n^(s+1) is the modulus for the scheme.
	uint64_t vector_encryption_length; // The number of ys and xs per ciphertext.
	BigNum g; // A random 2(n^s)-th residue mod n^(s+1).
	// ys[i] = g^xs[i] mod n^(s+1) for xs in the secret key
	std::vector<BigNum> ys;
	};

	struct CamenischShoupPrivateKey {
	// ys[i] = g^xs[i] mod n^(s+1) for all other values in the public key.
	std::vector<BigNum> xs;
	};

	// Generates a new key for the Camenisch-Shoup cryptosystem.
	CamenischShoupKey GenerateCamenischShoupKey(Context* ctx, int n_length_bits,
	uint64_t s,
	uint64_t vector_encryption_length);

	// Generates a new key pair for the Camenisch-Shoup cryptosystem. Assumes that
	// the modulus n has been correctly generated elsewhere as the product of 2
	// sufficiently long safe (or pseudo-safe) primes.
	std::pair<std::unique_ptr<CamenischShoupPublicKey>,
	std::unique_ptr<CamenischShoupPrivateKey>>
	GenerateCamenischShoupKeyPair(Context* ctx, const BigNum& n, uint64_t s,
	uint64_t vector_encryption_length);

	// Creates a proto from the PublicKey struct.
	proto::CamenischShoupPublicKey CamenischShoupPublicKeyToProto(
	const CamenischShoupPublicKey& public_key);
	// Parses PublicKey proto into a struct.
	StatusOr<CamenischShoupPublicKey> ParseCamenischShoupPublicKeyProto(
	Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto);
	// Creates a proto from the PrivateKey struct.
	proto::CamenischShoupPrivateKey CamenischShoupPrivateKeyToProto(
	const CamenischShoupPrivateKey& private_key);
	// Parses PrivateKey proto into a struct.
	StatusOr<CamenischShoupPrivateKey> ParseCamenischShoupPrivateKeyProto(
	Context* ctx, const proto::CamenischShoupPrivateKey& private_key_proto);
	// Creates a proto from the Ciphertext struct.
	proto::CamenischShoupCiphertext CamenischShoupCiphertextToProto(
	const CamenischShoupCiphertext& ciphertext);

	// The classes below implement the Camenisch-Shoup cryptosystem.
	// Does not include features of [CS'03] corresponding to non-malleability of
	// ciphertexts.

	class PublicCamenischShoup {
	public:
	// Initializes a public key for the Camenisch-Shoup cryptosystem.
	// Accepts modulus n which is the product of safe primes p and q, a power s,
	// random n-th residue g modulo n^(s+1), and y = g^x for unknown x. Also
	// accepts a Context, of which it doesn't take ownership.
	PublicCamenischShoup(Context* ctx, const BigNum& n, uint64_t s,
	const BigNum& g, std::vector<BigNum> ys);

	// Parses the key proto and creates a PublicCamenischShoup. Fails when
	// parsing fails.
	static StatusOr<std::unique_ptr<PublicCamenischShoup>> FromProto(
	Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto);

	// PublicCamenischShoup is neither copyable nor movable.
	PublicCamenischShoup(const PublicCamenischShoup&) = delete;
	PublicCamenischShoup& operator=(const PublicCamenischShoup&) = delete;
	PublicCamenischShoup(PublicCamenischShoup&&) = delete;
	PublicCamenischShoup& operator=(PublicCamenischShoup&&) = delete;
	~PublicCamenischShoup() = default;

	// Encrypts a message as (u = g^r mod n^(s+1), es) where es[i] = ys[i]^r *
	// (1+n)^ms[i] mod n^(s+1)). If \|ms\| < \|ys_\|, the remaining messages are
	// implicitly 0.
	//
	// Returns INVALID_ARGUMENT if the message is not >= 0, or if \|ms\| is > \|ys_\|.
	StatusOr<CamenischShoupCiphertext> Encrypt(const std::vector<BigNum>& ms);

	// Encrypts a message as in Encrypt, and also returns the randomness used for
	// encryption.
	StatusOr<CamenischShoupCiphertextWithRand> EncryptAndGetRand(
	const std::vector<BigNum>& ms);

	// Encrypts a message as (u = g^r mod n^(s+1), v = y^r * (1+n)^m mod n^(s+1)),
	// using the randomness supplied. If \|ms\| < \|ys_\|, the remaining messages are
	// implicitly 0.
	//
	// Returns INVALID_ARGUMENT if the message or randomness is not >= 0, or if
	// \|ms\| is > \|ys_\|.
	StatusOr<CamenischShoupCiphertext> EncryptWithRand(
	const std::vector<BigNum>& ms, const BigNum& r);

	// Homomorphically adds two ciphertexts mod n^(s+1).
	CamenischShoupCiphertext Add(const CamenischShoupCiphertext& ct1,
	const CamenischShoupCiphertext& ct2);

	// Homomorphically multiplies a ciphertexts with a given scalar mod n.
	CamenischShoupCiphertext Multiply(const CamenischShoupCiphertext& ct,
	const BigNum& scalar);

	// Parses a CamenischShoupCiphertext if it appears to be consistent with the
	// key.
	//
	// Fails with INVALID_ARGUMENT if the ciphertext does not match the modulus,
	// or has too many components.
	StatusOr<CamenischShoupCiphertext> ParseCiphertextProto(
	const proto::CamenischShoupCiphertext& ciphertext_proto);

	// Getters
	inline const BigNum& g() const { return g_; } // generator
	inline const std::vector<BigNum>& ys() const { return ys_; } // public keys
	inline const BigNum& n() const { return n_; }
	inline uint64_t s() const { return s_; }
	inline uint64_t vector_encryption_length() const {
	return vector_encryption_length_;
	}
	inline const BigNum& modulus() const { return modulus_; } // = n^(s+1)
	inline const BigNum& message_upper_bound() const { return n_to_s_; }
	inline const BigNum& randomness_upper_bound() const { return n_; }

	private:
	Context* const ctx_;
	const BigNum n_;
	const uint64_t s_;
	const uint64_t vector_encryption_length_; // = \|ys\|.
	// Vector containing the n powers up to s+1 for faster computation.
	const std::vector<BigNum> powers_of_n_;
	// The vector holding values that are computed repeatedly when encrypting
	// arbitrary messages via computing the binomial expansion of (1+n)^message.
	// The binomial expansion of (1+n) to some arbitrary exponent has constant
	// factors depending on only 1, n, and s regardless of the exponent value,
	// this vector holds each of these fixed values for faster computation.
	// Refer to Section 4.2 "Optimization of Encryption" from the
	// Damgaard-Jurik-Nielsen paper for more information.
	const std::vector<BigNum> encryption_precomp_;
	const BigNum n_to_s_;
	const BigNum modulus_; // equal to n^(s+1)
	const BigNum g_;
	const std::vector<BigNum> ys_;
	// For fast computation of g^r mod n^(s+1).
	const std::unique_ptr<FixedBaseExp> g_fbe_;
	// For fast computation of y^r mod n^(s+1).
	std::vector<std::unique_ptr<FixedBaseExp>> ys_fbe_;
	};

	class PrivateCamenischShoup {
	public:
	// Initializes a private key for the Camenisch-Shoup cryptosystem.
	// Accepts modulus n which is the product of safe primes p and q, a power s,
	// and a random n-th residue g modulo n^(s+1).
	// Also accepts x and y = g^x mod n^(s+1) for randomly selected x, where x
	// serves as the secret key. x should be randomly chosen between 0 and n and
	// relatively prime to n (i.e. x is in Z*n).
	// Also accepts a Context, of which it doesn't take ownership.
	// Returns a CHECK error if \|ys\| != \|xs\|.
	PrivateCamenischShoup(Context* ctx, const BigNum& n, uint64_t s,
	const BigNum& g, std::vector<BigNum> ys,
	std::vector<BigNum> xs);

	// Parses the key protos and creates a PrivateCamenischShoup. Fails when
	// parsing fails.
	static StatusOr<std::unique_ptr<PrivateCamenischShoup>> FromProto(
	Context* ctx, const proto::CamenischShoupPublicKey& public_key_proto,
	const proto::CamenischShoupPrivateKey& private_key_proto);

	// PrivateCamenischShoup is neither copyable nor movable.
	PrivateCamenischShoup(const PrivateCamenischShoup&) = delete;
	PrivateCamenischShoup& operator=(const PrivateCamenischShoup&) = delete;
	PrivateCamenischShoup(PrivateCamenischShoup&&) = delete;
	PrivateCamenischShoup& operator=(PrivateCamenischShoup&&) = delete;
	~PrivateCamenischShoup() = default;

	// Encrypts a message as (u = g^r mod n^2, v = y^r * (1+n)^m mod n^2). If \|ms\|
	// < \|ys_\|, the remaining messages are implicitly 0.
	//
	// Returns INVALID_ARGUMENT if some message is not >= 0, or if \|ms\| > \|ys_\|.
	StatusOr<CamenischShoupCiphertext> Encrypt(const std::vector<BigNum>& ms);

	// Encrypts a message as in Encrypt, and also returns the randomness used for
	// encryption.
	StatusOr<CamenischShoupCiphertextWithRand> EncryptAndGetRand(
	const std::vector<BigNum>& ms);

	// Encrypts a message as (u = g^r mod n^2, v = y^r * (1+n)^m mod n^2), using
	// the randomness supplied. If \|ms\| < \|ys_\|, the remaining messages are
	// implicitly 0.
	//
	// Returns INVALID_ARGUMENT if some message or the randomness not >= 0, or if
	// \|ms\| > \|ys_\|.
	StatusOr<CamenischShoupCiphertext> EncryptWithRand(
	const std::vector<BigNum>& ms, const BigNum& r);

	// Decrypts a given Camenisch-Shoup cipertext and returns the encrypted
	// message reduced mod n. Computes: ms such that (1+n)^ms[i] = (es[i] /
	// u^xs[i] mod n^(s+1)).
	//
	// Returns INVALID_ARGUMENT if the ciphertext is invalid/ cannot be decrypted.
	// Expects vector_encryption_length components in the ciphertext.
	StatusOr<std::vector<BigNum>> Decrypt(const CamenischShoupCiphertext& ct);

	// Parses a CamenischShoupCiphertext if it appears to be consistent with the
	// key.
	//
	// Fails with INVALID_ARGUMENT if the ciphertext does not match the modulus,
	// or has too many components.
	StatusOr<CamenischShoupCiphertext> ParseCiphertextProto(
	const proto::CamenischShoupCiphertext& ciphertext_proto);

	// Getters
	inline const BigNum& g() { return g_; } // generator
	inline const std::vector<BigNum>& ys() { return ys_; } // public keys
	inline const std::vector<BigNum>& xs() { return xs_; } // secret keys
	inline const BigNum& n() { return n_; }
	inline uint64_t s() { return s_; }
	inline const BigNum& modulus() { return modulus_; }
	inline uint64_t vector_encryption_length() {
	return vector_encryption_length_;
	}

	private:
	Context* const ctx_;
	const BigNum n_;
	const uint64_t s_;
	const uint64_t vector_encryption_length_; // = \|ys\| = \|xs\|.
	// Vector containing the n powers up to s+1 for faster computation.
	const std::vector<BigNum> powers_of_n_;
	// The vector holding values that are computed repeatedly when encrypting
	// arbitrary messages via computing the binomial expansion of (1+n)^message.
	// The binomial expansion of (1+n) to some arbitrary exponent has constant
	// factors depending on only 1, n, and s regardless of the exponent value,
	// this vector holds each of these fixed values for faster computation.
	// Refer to Section 4.2 "Optimization of Encryption" from the
	// Damgaard-Jurik-Nielsen paper for more information.
	const std::vector<BigNum> encryption_precomp_;
	// Intermediate values used repeatedly in decryption.
	std::map<std::pair<int, int>, BigNum> decryption_precomp_;
	const BigNum n_to_s_;
	const BigNum modulus_; // equal to n^(s+1)
	const BigNum g_;
	const std::vector<BigNum> ys_;
	const std::vector<BigNum> xs_; // secret key
	std::unique_ptr<FixedBaseExp> g_fbe_;
	std::vector<std::unique_ptr<FixedBaseExp>> ys_fbe_;
	};

	} // namespace private_join_and_compute

	#endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_CAMENISCH_SHOUP_H_