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 #ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_DODIS_YAMPOLSKIY_PRF_DY_VERIFIABLE_RANDOM_FUNCTION_H_ 17 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_DODIS_YAMPOLSKIY_PRF_DY_VERIFIABLE_RANDOM_FUNCTION_H_ 18 19 #include <stdint.h> 20 21 #include <memory> 22 #include <optional> 23 #include <string> 24 #include <tuple> 25 #include <utility> 26 #include <vector> 27 28 #include "private_join_and_compute/crypto/big_num.h" 29 #include "private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.pb.h" 30 #include "private_join_and_compute/crypto/ec_point.h" 31 #include "private_join_and_compute/crypto/pedersen_over_zn.h" 32 33 namespace private_join_and_compute { 34 35 // Implements a Verifiable Random Function that allows provable evaluations of 36 // the Dodis Yampolskiy (DY) PRF with key k on a point x, 37 // where k and x are both committed to using a Pedersen commitment. The 38 // Dodis-Yampolskiy PRF is defined as F_k(x) = g^(1/(k+x)). This class assumes 39 // the DY PRF is implemented over an elliptic curve group, and that commitments 40 // are over Zn. 41 // 42 // The verification protocol is achieved by proving knowledge of the exponent 43 // k+x. Specifically, the prover commits to k+x and provides a sigma-protocol 44 // proving that F_k(x)^(k+x) = g. This sigma-protocol can be made 45 // non-interactive using the Fiat-Shamir heuristic (namely generating the 46 // verifier's random challenge by hashing the prover's first message). 47 class DyVerifiableRandomFunction { 48 public: 49 struct GenerateKeysProof {}; 50 51 // Creates a VRF object from the supplied parameters. 52 // 53 // "pedersen" should be created externally using the PedersenParameters from 54 // parameters_proto. 55 // 56 // Does not take ownership of context, ec_group or pedersen. 57 static StatusOr<std::unique_ptr<DyVerifiableRandomFunction>> Create( 58 proto::DyVrfParameters parameters_proto, Context* context, 59 ECGroup* ec_group, PedersenOverZn* pedersen); 60 61 // Generates a new public/private keypair for the DY VRF together with a proof 62 // that each entry of the commitment is the same key. 63 StatusOr<std::tuple<proto::DyVrfPublicKey, proto::DyVrfPrivateKey, 64 proto::DyVrfGenerateKeysProof>> 65 GenerateKeyPair(); 66 67 // Verifies that the public key has a bounded key, and commits to the same key 68 // in each component of the Pedersen batch commitment. 69 Status VerifyGenerateKeysProof(const proto::DyVrfPublicKey& public_key, 70 const proto::DyVrfGenerateKeysProof& proof); 71 72 // Applies the DY VRF to a given batch of messages. 73 StatusOr<std::vector<ECPoint>> Apply( 74 absl::Span<const BigNum> messages, 75 const proto::DyVrfPrivateKey& private_key); 76 77 // Generates a proof that prf_evaluations were generated by applying the VRF 78 // to the supplied messages. A commitment and opening to the messages can 79 // optionally be provided. 80 StatusOr<proto::DyVrfApplyProof> GenerateApplyProof( 81 absl::Span<const BigNum> messages, 82 absl::Span<const ECPoint> prf_evaluations, 83 const proto::DyVrfPublicKey& public_key, 84 const proto::DyVrfPrivateKey& private_key, 85 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages); 86 87 // Verifies that prf_evaluations was produced by applying a DY VRF with the 88 // supplied public key on the supplied committed messages. "Ok" status 89 // corresponds to a passing proof. "Non-ok" status contains an error 90 // specifying which check failed. 91 // 92 // Assumes that the Pedersen commitment parameters and the prover's Public Key 93 // are already verified or trustworthy. 94 // 95 // The challenge can optionally be injected manually into the proof struct. If 96 // not, the challenge is generated using the Fiat-Shamir heuristic. 97 Status VerifyApplyProof(absl::Span<const ECPoint> prf_evaluations, 98 const proto::DyVrfPublicKey& public_key, 99 const PedersenOverZn::Commitment& commit_messages, 100 const proto::DyVrfApplyProof& proof); 101 102 // Generates the challenge for the ApplyProof using the Fiat-Shamir heuristic. 103 // Exposed for testing and special cases such as enclosing proofs. 104 StatusOr<BigNum> GenerateApplyProofChallenge( 105 absl::Span<const ECPoint> prf_evaluations, 106 const proto::DyVrfPublicKey& public_key, 107 const PedersenOverZn::Commitment& commit_messages, 108 const proto::DyVrfApplyProof::Message1& message_1); 109 110 private: 111 struct PublicKey { 112 PedersenOverZn::Commitment commit_key; 113 }; 114 115 struct PrivateKey { 116 BigNum key; 117 PedersenOverZn::Opening commit_key_opening; 118 }; 119 120 // Container for proof elements showing that a particular value is the result 121 // of applying the DY VRF on committed messages with a particular key. Also 122 // has structs for various helpful intermediates. 123 struct ApplyProof { 124 struct Message1 { 125 PedersenOverZn::Commitment commit_dummy_messages_plus_key; 126 std::vector<ECPoint> dummy_dy_prf_base_gs; 127 }; 128 129 struct Message1PrivateState { 130 std::vector<BigNum> dummy_messages_plus_key; 131 BigNum dummy_key; 132 PedersenOverZn::Opening dummy_opening; 133 }; 134 135 struct Message2 { 136 std::vector<BigNum> masked_dummy_messages_plus_key; 137 PedersenOverZn::Opening masked_dummy_opening; 138 }; 139 }; 140 DyVerifiableRandomFunction(proto::DyVrfParameters parameters_proto,Context * context,ECGroup * ec_group,ECPoint dy_prf_base_g,PedersenOverZn * pedersen)141 DyVerifiableRandomFunction(proto::DyVrfParameters parameters_proto, 142 Context* context, ECGroup* ec_group, 143 ECPoint dy_prf_base_g, PedersenOverZn* pedersen) 144 : parameters_proto_(std::move(parameters_proto)), 145 context_(context), 146 ec_group_(ec_group), 147 dy_prf_base_g_(std::move(dy_prf_base_g)), 148 pedersen_(pedersen) {} 149 150 // Produces the first message of the proof that prf_evaluations is the result 151 // of a VRF applied to a given set of messages. 152 StatusOr<std::pair<std::unique_ptr<ApplyProof::Message1>, 153 std::unique_ptr<ApplyProof::Message1PrivateState>>> 154 GenerateApplyProofMessage1( 155 absl::Span<const BigNum> messages, 156 absl::Span<const ECPoint> prf_evaluations, 157 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages, 158 const PublicKey& public_key, const PrivateKey& private_key); 159 160 // Produces the second message of the proof that prf_evaluations is the result 161 // of a VRF applied to a given set of messages. 162 // 163 // The challenge can be optionally generated using the Fiat-Shamir heuristic. 164 StatusOr<std::unique_ptr<ApplyProof::Message2>> GenerateApplyProofMessage2( 165 absl::Span<const BigNum> messages, 166 absl::Span<const ECPoint> prf_evaluations, 167 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages, 168 const PublicKey& public_key, const PrivateKey& private_key, 169 const ApplyProof::Message1& message_1, 170 const ApplyProof::Message1PrivateState& private_state, 171 const BigNum& challenge); 172 173 proto::DyVrfPublicKey DyVrfPublicKeyToProto( 174 const DyVerifiableRandomFunction::PublicKey& public_key); 175 proto::DyVrfPrivateKey DyVrfPrivateKeyToProto( 176 const DyVerifiableRandomFunction::PrivateKey& private_key); 177 StatusOr<proto::DyVrfApplyProof::Message1> DyVrfApplyProofMessage1ToProto( 178 const DyVerifiableRandomFunction::ApplyProof::Message1& message_1); 179 proto::DyVrfApplyProof::Message2 DyVrfApplyProofMessage2ToProto( 180 const DyVerifiableRandomFunction::ApplyProof::Message2& message_2); 181 182 StatusOr<DyVerifiableRandomFunction::PublicKey> ParseDyVrfPublicKeyProto( 183 Context* ctx, const proto::DyVrfPublicKey& public_key_proto); 184 StatusOr<DyVerifiableRandomFunction::PrivateKey> ParseDyVrfPrivateKeyProto( 185 Context* ctx, const proto::DyVrfPrivateKey& private_key_proto); 186 StatusOr<DyVerifiableRandomFunction::ApplyProof::Message1> 187 ParseDyVrfApplyProofMessage1Proto( 188 Context* ctx, ECGroup* ec_group, 189 const proto::DyVrfApplyProof::Message1& message_1_proto); 190 StatusOr<DyVerifiableRandomFunction::ApplyProof::Message2> 191 ParseDyVrfApplyProofMessage2Proto( 192 Context* ctx, const proto::DyVrfApplyProof::Message2& message_2_proto); 193 194 // Generates the challenge for the GenerateKeysProof using the Fiat-Shamir 195 // heuristic. 196 StatusOr<BigNum> GenerateChallengeForGenerateKeysProof( 197 const proto::DyVrfGenerateKeysProof::Statement& statement, 198 const proto::DyVrfGenerateKeysProof::Message1& message_1); 199 200 proto::DyVrfParameters parameters_proto_; 201 Context* context_; 202 ECGroup* ec_group_; 203 ECPoint dy_prf_base_g_; 204 PedersenOverZn* pedersen_; 205 }; 206 207 } // namespace private_join_and_compute 208 209 #endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_DODIS_YAMPOLSKIY_PRF_DY_VERIFIABLE_RANDOM_FUNCTION_H_ 210