xref: /aosp_15_r20/external/private-join-and-compute/private_join_and_compute/crypto/pedersen_over_zn.h (revision a6aa18fbfbf9cb5cd47356a9d1b057768998488c)

/*
 * 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 Pedersen's commitment scheme over Z_n.
// Pedersen, Torben Pryds. "Non-interactive and information-theoretic secure
// verifiable secret sharing." (1998).
//
// A commitment scheme allows a party to commit to a message, and later open the
// commitment to reveal the message underlying the commitment. It has two key
// security properties: hiding, meaning that given only the commitment, the
// message is hidden, and binding, which means that once a commitment to m has
// been created, it is hard for the creator to open it to a different value m'.
//
// Pedersen commitments can be created over any group where discrete logarithm
// is hard. The example below is in terms of the group Z*_n, for n the product
// of two large primes p and q. An alternative is to use the modulus n = p, a
// safe prime.
//
// Usage pattern:
// Let P1 and P2 be two parties.
// P1 : n                       <-  GenerateSafeModulus(ctx, modulus_length);
//      {g, h, n, r}            <-  PedersenOverZn::GenerateParams(ctx, n);
//      proof                   <-  PedersenOverZn::
//                                    ProveParamsCorrectlyGenerated (
//                                    ctx, g, h, n, r)
//                                  OR
//                                  Pedersen::ProveParamsCorrectlyGeneratedFor
//                                  TrustedModulus(ctx, g, h, n, r)
//      Send (g, h, n) and proof to P2.
//      (NOTE: params.r should be kept secret, see security note below)
//
// P2 : Check PedersenOverZn::VerifyParamsProof(ctx, g, h, n, proof).ok()
//      pedersen                <-  new Pedersen(ctx, g, h, n)
//      commitment, opening     <-  pedersen.Commit(m)
//      Send commitment to P1
//
//    < P1 and P2 do some work>
//
// P2 : Send opening to P1
//
// P1 : Reads m from open
//      b                       <-  pedersen.Verify(commitment, opening)
//      If b is true, P1 accepts that "commitment" contained m.
//
// Variant: the parameters could be selected such that there are multiple gs. In
// this case, each g_i should be in <h>, and the discrete log of g_i with
// respect to h should be hidden from the committing party. If this is the case,
// when we use k gs, we can commit k messages in a single commitment. We call
// these vector-commitments.
//
// Important Security Notes:
// It is important above that the commitment parameters should be generated by
// someone other than the committing party, or in some oblivious manner. In
// particular, in order to guarantee binding, it is important that the
// committing party not know "r", the discrete logarithm of h with respect to g.
// In the case where n is the product of 2 primes, the committing party should
// also not know the prime decomposition of n, or it can break the binding
// property of the commitment scheme.
//
// For the case where n is composite, it is also usually appropriate for the
// party generating the parameters (P1 in the example above) to send a proof
// that the parameters g,h,n were correctly generated, and in particular, that g
// is in <h>. This is important because if g is not in <h>, then P1 can
// potentially break the hiding property of commitments sent by P2. A sigma
// protocol of knowledge of r such that g = h^r mod n is sufficient to prove g
// is in <h>, and there are two implementations provided here, one when the
// modulus is completely untrusted, and one when the modulus has previously been
// proven to be the product of 2 safe primes. (See go/untrusted_sigma_protocols
// for a more detailed discussion of sigma protocols when the modulus is
// untrusted)

#ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PEDERSEN_OVER_ZN_H_
#define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PEDERSEN_OVER_ZN_H_

#include <memory>
#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/proto/pedersen.pb.h"
#include "private_join_and_compute/crypto/simultaneous_fixed_bases_exp.h"
#include "private_join_and_compute/util/status.inc"

namespace private_join_and_compute {

// Splits vector into subvectors of size subvector_size. Requires copy
// constructor. This is helpful for splitting a long vector into subvectors
// small enough to each fit into a single commitment.
template <typename T>
std::vector<std::vector<T>> SplitVector(std::vector<T> input,
                                        int subvector_size) {
  int num_batches = (input.size() + subvector_size - 1) / subvector_size;

  std::vector<std::vector<T>> output;
  output.reserve(num_batches);

  for (int i = 0; i < num_batches; i++) {
    size_t start_offset = i * subvector_size;
    size_t end_offset = std::min(input.size(), start_offset + subvector_size);
    output.emplace_back(input.begin() + start_offset,
                        input.begin() + end_offset);
  }

  return output;
}

// Class to allowing committing to and verifying Pedersen's commitments over Zn.
class PedersenOverZn {
 public:
  // Will compute ((2^num_simultaneous * number_of_bases) / num_simultaneous) -
  // sized table for fixed base exponentiation.
  static const size_t kDefaultMaxNumSimultaneousExponentiations = 10;

  typedef BigNum Commitment;
  typedef BigNum Opening;

  struct CommitmentAndOpening {
    Commitment commitment;
    Opening opening;
  };

  struct Parameters {
    std::vector<BigNum> gs;  // generators for the messages.
    BigNum h;                // generator for randomness
    BigNum n;                // modulus
    // secret parameters used to prove that each entry of gs is in <h>.
    // Optional.
    std::vector<BigNum> rs;
  };

  // This proof has several repetitions, each with a boolean challenge.
  // The challenges are implicit, and must be reconstructed at verification time
  // as the output of RandomOracle(g, h, n, dummy_gs).
  struct ProofOfGen {
    int num_repetitions;
    std::vector<std::unique_ptr<BigNum>> dummy_gs;
    std::vector<std::unique_ptr<BigNum>> responses;
  };

  // This proof has a single, long challenge of "challenge_length" bits.
  // The challenge is implicit, and must be reconstructed at verification time
  // as the output of RandomOracle(g, h, n, dummy_g).
  struct ProofOfGenForTrustedModulus {
    int challenge_length;
    BigNum dummy_g;
    BigNum response;
  };

  // Takes a Context, a modulus n, generators gs and h for the large subgroup
  // of Z*n such that each g is in <h>. Does not take ownership of the Context.
  // n may be either a safe prime ( n = 2q + 1 for some prime q), or the product
  // of 2 safe primes (n = pq, where p = 2p' +1 and q = 2q'+1). h should be a
  // generator.
  //
  // Note: when gs and h are supplied by a different party, it is appropriate to
  // require a proof that each g is in <h> before using them for commitments,
  // otherwise the secrecy of the commitment can be compromised. When n is a
  // safe prime with n = 2q+1, this is equivalent to checking that g_i^q ==1 and
  // h^q == 1.
  //
  // num_simultaneous_exponentiations (k for short) controls the amount of
  // precomputation performed. If there are fewer bases than this value, it will
  // be reset to gs.size(). It will result in (2^k)*(gs.size()/k) amount of
  // precomputation, which speeds up commitment by a factor of k.
  //
  // Returns INTERNAL if any of the precomputation operations fail.
  static StatusOr<std::unique_ptr<PedersenOverZn>> Create(
      Context* ctx, std::vector<BigNum> gs, const BigNum& h, const BigNum& n,
      size_t num_simultaneous_exponentiations =
          kDefaultMaxNumSimultaneousExponentiations);

  // Parses parameters and creates a Pedersen object. Fails when the underlying
  // "Create" call fails.
  static StatusOr<std::unique_ptr<PedersenOverZn>> FromProto(
      Context* ctx, const proto::PedersenParameters& parameters_proto,
      size_t num_simultaneous_exponentiations =
          kDefaultMaxNumSimultaneousExponentiations);

  // Pedersen is neither copyable nor movable.
  PedersenOverZn(const PedersenOverZn&) = delete;
  PedersenOverZn& operator=(const PedersenOverZn&) = delete;

  virtual ~PedersenOverZn();

  // Getters
  inline const std::vector<BigNum>& gs() { return gs_; }
  inline const BigNum& h() { return h_; }
  inline const BigNum& n() { return n_; }

  // Creates a commitment to a vector of messages m, returning the commitment
  // and the corresponding opening. If fewer than gs.size() messages are
  // provided, the remaining messages are assumed to be 0.
  //
  // Returns "INVALID_ARGUMENT" status if any m is not >= 0, or if
  // messages.size() > gs.size().
  //
  // Note: a commitment creating using this method has perfect secrecy if each
  // g is in <h>, but is binding ONLY if for all g, the committing party does
  // not know r such that g = h^r mod n, and also the committing party does not
  // know the factorization of n.
  //
  // Additionally, the binding property only holds relative to the order of g.
  // So if n is a safe prime 2q +1, binding holds only relative to messages < q,
  // and if n is the product of safe primes, binding holds only relative to
  // messages less than n/4. The size of messages is not checked in this method.
  StatusOr<CommitmentAndOpening> Commit(
      const std::vector<BigNum>& messages) const;

  // Creates a commitment to a vector of messages m, together with the
  // corresponding opening, using the specified randomness for commitment. If
  // fewer than gs.size() messages are provided, the remaining messages are
  // assumed to be 0.
  //
  // Returns "INVALID_ARGUMENT" status if any m or r is not >= 0, or if
  // messages.size() > gs.size().
  //
  // This method allows the messages and randomness to be larger than normal,
  // and is intended to be used only for proofs of knowledge and equality of a
  // committed message. As part of such a proof, the prover sends large values
  // r1 and r2 (the prover's responses to the verifier's challenge), such that
  // the verifier needs to create a commitment to r1 using randomness r2 in
  // order to check the proof.
  //
  // This method should be avoided in all scenarios other than the one
  // described above, and Pedersen::Commit should be used instead.
  StatusOr<Commitment> CommitWithRand(const std::vector<BigNum>& messages,
                                      const BigNum& rand) const;

  // Homomorphically adds two commitments.
  // The opening randomness of the resulting commitment is the sum of the
  // opening randomness of com1 and com2.
  Commitment Add(const Commitment& com1, const Commitment& com2) const;

  // Homomorphically multiplies a commitment with a given scalar.
  // The opening randomness of the resulting commitment is scalar times the
  // opening randomness of com.
  Commitment Multiply(const Commitment& com, const BigNum& scalar) const;

  // Verifies an opening to a given commitment.
  //
  // The commitment binding property only holds relative to the order of each g.
  // So if n is a safe prime 2q +1, binding holds only relative to messages < q,
  // and if n is the product of safe primes, binding holds only relative to
  // messages less than n/4.
  //
  // Returns "INVALID_ARGUMENT" status if either of m or r in the opening is
  // negative.
  StatusOr<bool> Verify(const Commitment& com,
                        const std::vector<BigNum>& messages,
                        const BigNum& opening) const;

  /////////////////////////////////////////////////////////////////////////////
  // Static methods to generate fresh parameters, and prove that they were
  // correctly generated.
  /////////////////////////////////////////////////////////////////////////////

  // Create parameters for Pedersen's commitment scheme, given a modulus n that
  // is assumed to be the product of 2 safe primes. num_gs is the number of
  // "gs" to have in the parameters, which corresponds to the number of messages
  // that can be simultaneously vector-committed.
  static Parameters GenerateParameters(Context* ctx, const BigNum& n,
                                       int64_t num_gs = 1);

  // Creates a proof that the parameters were correctly generated, namely that
  // g = h^r mod n for some r. The proof is a set of Schnorr sigma protocols,
  // repeated in parallel, in the random oracle model, using the Fiat-Shamir
  // heuristic. It is designed specifically for the case when n is NOT known to
  // be a safe modulus. To deal with the possible unsafety of the modulus, each
  // repetition of the sigma protocol has a boolean challenge. This maintains
  // soundness of the proof even when the modulus is untrusted.
  // The num_repetitions parameter specifies the number of parallel repetitions
  // of the sigma protocol to perform. The soundness error of the protocol is
  // 2^(-num_repetitions). A larger value implies better soundness, but note
  // that the size of the proof grows linearly with the number of repetitions.
  // Suggested value is 128 repetitions.
  // The zk_quality parameter tunes the size of the prover's response in the
  // sigma protocol. A large zk_quality parameter increases the length of the
  // response relative to the size of the challenge, which improves how well the
  // proof hides the secret exponent r. Suggested value is 128 bits.
  // Returns INVALID_ARGUMENT if the inputs do not correspond to correctly
  // generated parameters, or if either of num_repetitions or zk_quality are
  // nonpositive.
  static StatusOr<ProofOfGen> ProveParametersCorrectlyGenerated(
      Context* ctx, const BigNum& g, const BigNum& h, const BigNum& n,
      const BigNum& r, int num_repetitions = 128, int zk_quality = 128);

  // Returns OK if the proof verifies, and a descriptive INVALID_ARGUMENT error
  // if it doesn't.
  static Status VerifyParamsProof(Context* ctx, const BigNum& g,
                                  const BigNum& h, const BigNum& n,
                                  const ProofOfGen& proof);

  // Creates a proof that the parameters were correctly generated, namely that
  // g = h^r mod n for some r. The proof is a Schnorr sigma protocol in the
  // random oracle model, using the Fiat-Shamir heuristic. It is designed
  // specifically for the case when n is known to be a safe modulus.
  // The zk_quality parameter tunes the size of the prover's response in the
  // sigma protocol. A large zk_quality parameter increases the length of the
  // response relative to the size of the challenge, which improves how well the
  // proof hides the secret exponent r. Suggested value is 128 bits.
  // Returns INVALID_ARGUMENT if the inputs do not correspond to correctly
  // generated parameters, or if either of challenge_length or zk_quality are
  // nonpositive.
  static StatusOr<ProofOfGenForTrustedModulus>
  ProveParametersCorrectlyGeneratedForTrustedModulus(
      Context* ctx, const BigNum& g, const BigNum& h, const BigNum& n,
      const BigNum& r, int challenge_length = 128, int zk_quality = 128);

  // Returns OK if the proof verifies, and a descriptive INVALID_ARGUMENT
  // error if it doesn't.
  static Status VerifyParamsProofForTrustedModulus(
      Context* ctx, const BigNum& g, const BigNum& h, const BigNum& n,
      const ProofOfGenForTrustedModulus& proof);

  // Helper method that generates the Fiat-Shamir random oracle challenge
  // for the proof that the Pedersen parameters were generated correctly, for
  // the case of a potentially unsafe modulus.
  // Exposed for testing only.
  static std::vector<uint8_t> GetGenProofChallenge(
      Context* ctx, const BigNum& g, const BigNum& h, const BigNum& n,
      const std::vector<std::unique_ptr<BigNum>>& dummy_gs,
      int num_repetitions);

  // Helper method that generates the Fiat-Shamir random oracle challenge for
  // the proof that the Pedersen parameters were generated correctly for the
  // case of a modulus known to be the product of 2 safe primes.
  // Exposed for testing only.
  static BigNum GetTrustedGenProofChallenge(Context* ctx, const BigNum& g,
                                            const BigNum& h, const BigNum& n,
                                            const BigNum& dummy_g,
                                            int challenge_length);

  // Serializes the parameters to a proto (does not serialize rs if provided).
  static proto::PedersenParameters ParametersToProto(
      const Parameters& parameters);

  // Serializes the parameters to a proto (does not deserialize rs since these
  // are not stored).
  static StatusOr<Parameters> ParseParametersProto(
      Context* ctx, const proto::PedersenParameters& parameters);

 private:
  PedersenOverZn(
      Context* ctx, std::vector<BigNum> gs, const BigNum& h, const BigNum& n,
      std::unique_ptr<SimultaneousFixedBasesExp<ZnElement, ZnContext>>
          simultaneous_fixed_bases_exp);

  Context* ctx_;
  const std::vector<BigNum> gs_;
  const BigNum h_;
  const BigNum n_;
  std::unique_ptr<SimultaneousFixedBasesExp<ZnElement, ZnContext>>
      simultaneous_fixed_bases_exp_;
};

}  // namespace private_join_and_compute

#endif  // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_PEDERSEN_OVER_ZN_H_