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 #include "private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.h"
17
18 #include <memory>
19 #include <string>
20 #include <tuple>
21 #include <utility>
22 #include <vector>
23
24 #include "absl/strings/str_cat.h"
25 #include "private_join_and_compute/crypto/big_num.h"
26 #include "private_join_and_compute/crypto/context.h"
27 #include "private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.pb.h"
28 #include "private_join_and_compute/crypto/ec_point.h"
29 #include "private_join_and_compute/crypto/pedersen_over_zn.h"
30 #include "private_join_and_compute/crypto/proto/proto_util.h"
31
32 #include "src/google/protobuf/io/coded_stream.h"
33 #include "src/google/protobuf/io/zero_copy_stream_impl_lite.h"
34
35 namespace private_join_and_compute {
36
37 StatusOr<std::unique_ptr<DyVerifiableRandomFunction>>
Create(proto::DyVrfParameters parameters_proto,Context * context,ECGroup * ec_group,PedersenOverZn * pedersen)38 DyVerifiableRandomFunction::Create(proto::DyVrfParameters parameters_proto,
39 Context* context, ECGroup* ec_group,
40 PedersenOverZn* pedersen) {
41 if (parameters_proto.security_parameter() <= 0) {
42 return absl::InvalidArgumentError(
43 "parameters.security_parameter must be >= 0");
44 }
45 if (parameters_proto.challenge_length_bits() <= 0) {
46 return absl::InvalidArgumentError(
47 "parameters.challenge_length_bits must be >= 0");
48 }
49
50 ASSIGN_OR_RETURN(ECPoint dy_prf_base_g,
51 ec_group->CreateECPoint(parameters_proto.dy_prf_base_g()));
52
53 return absl::WrapUnique(new DyVerifiableRandomFunction(
54 std::move(parameters_proto), context, ec_group, std::move(dy_prf_base_g),
55 pedersen));
56 }
57
58 StatusOr<std::tuple<proto::DyVrfPublicKey, proto::DyVrfPrivateKey,
59 proto::DyVrfGenerateKeysProof>>
GenerateKeyPair()60 DyVerifiableRandomFunction::GenerateKeyPair() {
61 // Generate a fresh key, and commit to it with respect to each Pedersen
62 // generator.
63 BigNum key = ec_group_->GeneratePrivateKey();
64
65 int num_copies = pedersen_->gs().size();
66 ASSIGN_OR_RETURN(PedersenOverZn::CommitmentAndOpening commit_and_open_key,
67 pedersen_->Commit(std::vector<BigNum>(num_copies, key)));
68
69 DyVerifiableRandomFunction::PublicKey public_key{
70 commit_and_open_key.commitment // commit_key
71 };
72 DyVerifiableRandomFunction::PrivateKey private_key{
73 key, // key
74 commit_and_open_key.opening // open_key
75 };
76
77 proto::DyVrfPublicKey public_key_proto = DyVrfPublicKeyToProto(public_key);
78 proto::DyVrfPrivateKey private_key_proto =
79 DyVrfPrivateKeyToProto(private_key);
80
81 // Generate the keys proof. This proof is a sigma protocol that proves
82 // knowledge of the key, and also that the same key has been committed in each
83 // component of the batched Pedersen commitment scheme. Furthermore, this
84 // proof shows that the key is bounded-with-slack, using the range proof
85 // feature of sigma protocols (i.e. checking the size of the masked dummy
86 // opening to the key). The proven bound on the key is ec_group_order *
87 // 2^(challenge_length + security_parameter).
88 //
89 // These properties are sufficient for the key to be safe for use downstream.
90 //
91 // As in all sigma protocols, this proof proceeds by the prover generating
92 // dummy values for all the secret exponents (here, these are the key and the
93 // commitment randomness), and then creating a dummy commitment to the key
94 // using the dummy values. The sigma protocol then hashes this dummy
95 // commitment together with the proof statement (i.e. the original commitment)
96 // to produce a challenge using the Fiat-Shamir heuristic. Given this
97 // challenge, the prover then sends the receiver "masked_dummy_values" as
98 // dummy_value + (challenge * real_value) for each of the secret exponents.
99 // The verifier can then use these masked_dummy_values to verify the proof.
100
101 // Generate dummy key and opening.
102 BigNum dummy_key_bound =
103 ec_group_->GetOrder().Lshift(parameters_proto_.challenge_length_bits() +
104 parameters_proto_.security_parameter());
105 BigNum dummy_opening_bound =
106 pedersen_->n().Lshift(parameters_proto_.challenge_length_bits() +
107 parameters_proto_.security_parameter());
108 BigNum dummy_key = context_->GenerateRandLessThan(dummy_key_bound);
109 BigNum dummy_opening = context_->GenerateRandLessThan(dummy_opening_bound);
110 std::vector<BigNum> dummy_key_vector =
111 std::vector<BigNum>(num_copies, dummy_key);
112 ASSIGN_OR_RETURN(PedersenOverZn::Commitment dummy_commit_prf_key,
113 pedersen_->CommitWithRand(dummy_key_vector, dummy_opening));
114
115 // Create Statement and first message, and generate the challenge.
116 proto::DyVrfGenerateKeysProof::Statement statement;
117 *statement.mutable_parameters() = parameters_proto_;
118 *statement.mutable_public_key() = public_key_proto;
119
120 proto::DyVrfGenerateKeysProof::Message1 message_1;
121 *message_1.mutable_dummy_commit_prf_key() = dummy_commit_prf_key.ToBytes();
122
123 ASSIGN_OR_RETURN(BigNum challenge,
124 GenerateChallengeForGenerateKeysProof(statement, message_1));
125
126 // Create the masked_dummy_opening values.
127 BigNum masked_dummy_prf_key = dummy_key + (key.Mul(challenge));
128 BigNum masked_dummy_opening =
129 dummy_opening + (commit_and_open_key.opening.Mul(challenge));
130
131 // Package the values into the proof proto.
132 proto::DyVrfGenerateKeysProof generate_keys_proof;
133
134 generate_keys_proof.set_challenge(challenge.ToBytes());
135 generate_keys_proof.mutable_message_2()->set_masked_dummy_prf_key(
136 masked_dummy_prf_key.ToBytes());
137 generate_keys_proof.mutable_message_2()->set_masked_dummy_opening(
138 masked_dummy_opening.ToBytes());
139
140 return {std::make_tuple(std::move(public_key_proto),
141 std::move(private_key_proto),
142 std::move(generate_keys_proof))};
143 }
144
145 // Verifies that the public key has a bounded key, and commits to the same key
146 // in each component of the Pedersen batch commitment.
VerifyGenerateKeysProof(const proto::DyVrfPublicKey & public_key,const proto::DyVrfGenerateKeysProof & proof)147 Status DyVerifiableRandomFunction::VerifyGenerateKeysProof(
148 const proto::DyVrfPublicKey& public_key,
149 const proto::DyVrfGenerateKeysProof& proof) {
150 // Deserialize components of the public key and proof
151 BigNum commit_prf_key = context_->CreateBigNum(public_key.commit_prf_key());
152 BigNum challenge_from_proof = context_->CreateBigNum(proof.challenge());
153 BigNum masked_dummy_prf_key =
154 context_->CreateBigNum(proof.message_2().masked_dummy_prf_key());
155 BigNum masked_dummy_opening =
156 context_->CreateBigNum(proof.message_2().masked_dummy_opening());
157
158 // Verify the bounds on masked_dummy values
159 BigNum masked_dummy_prf_key_bound =
160 ec_group_->GetOrder().Lshift(parameters_proto_.challenge_length_bits() +
161 parameters_proto_.security_parameter() + 1);
162 if (masked_dummy_prf_key > masked_dummy_prf_key_bound) {
163 return absl::InvalidArgumentError(absl::StrCat(
164 "DyVerifiableRandomFunction::VerifyGenerateKeysProof: "
165 "masked_dummy_prf_key is larger than the bound. Supplied value: ",
166 masked_dummy_prf_key.ToDecimalString(),
167 ". bound: ", masked_dummy_prf_key_bound.ToDecimalString()));
168 }
169
170 // Regenerate dummy values from the masked_dummy values and the challenge in
171 // the proof.
172 std::vector<BigNum> masked_dummy_prf_key_vector =
173 std::vector<BigNum>(pedersen_->gs().size(), masked_dummy_prf_key);
174 ASSIGN_OR_RETURN(PedersenOverZn::Commitment masked_dummy_prf_key_commitment,
175 pedersen_->CommitWithRand(masked_dummy_prf_key_vector,
176 masked_dummy_opening));
177
178 ASSIGN_OR_RETURN(PedersenOverZn::Commitment commit_keys_to_challenge_inverse,
179 pedersen_->Multiply(commit_prf_key, challenge_from_proof)
180 .ModInverse(pedersen_->n()));
181 PedersenOverZn::Commitment dummy_commit_prf_key = pedersen_->Add(
182 commit_keys_to_challenge_inverse, masked_dummy_prf_key_commitment);
183
184 // Regenerate the challenge and verify that it matches the challenge in the
185 // proof.
186 proto::DyVrfGenerateKeysProof::Statement statement;
187 proto::DyVrfGenerateKeysProof::Message1 message_1;
188
189 *statement.mutable_parameters() = parameters_proto_;
190 *statement.mutable_public_key() = public_key;
191
192 message_1.set_dummy_commit_prf_key(dummy_commit_prf_key.ToBytes());
193
194 ASSIGN_OR_RETURN(BigNum reconstructed_challenge,
195 GenerateChallengeForGenerateKeysProof(statement, message_1));
196
197 if (reconstructed_challenge != challenge_from_proof) {
198 return absl::InvalidArgumentError(absl::StrCat(
199 "DyVerifiableRandomFunction::VerifyGenerateKeysProof: Failed to verify "
200 " proof. Challenge in proof (",
201 challenge_from_proof.ToDecimalString(),
202 ") does not match reconstructed challenge (",
203 reconstructed_challenge.ToDecimalString(), ")."));
204 }
205
206 return absl::OkStatus();
207 }
208
209 // Generates the challenge for the GenerateKeysProof using the Fiat-Shamir
210 // heuristic.
211 StatusOr<BigNum>
GenerateChallengeForGenerateKeysProof(const proto::DyVrfGenerateKeysProof::Statement & statement,const proto::DyVrfGenerateKeysProof::Message1 & message_1)212 DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof(
213 const proto::DyVrfGenerateKeysProof::Statement& statement,
214 const proto::DyVrfGenerateKeysProof::Message1& message_1) {
215 // Note that the random oracle prefix is implicitly included as part of the
216 // parameters being serialized in the statement proto. We skip including it
217 // again here to avoid unnecessary duplication.
218 std::string challenge_string =
219 "DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof";
220 auto challenge_sos =
221 std::make_unique<google::protobuf::io::StringOutputStream>(
222 &challenge_string);
223 auto challenge_cos =
224 std::make_unique<google::protobuf::io::CodedOutputStream>(
225 challenge_sos.get());
226 challenge_cos->SetSerializationDeterministic(true);
227 challenge_cos->WriteVarint64(statement.ByteSizeLong());
228
229 challenge_cos->WriteString(SerializeAsStringInOrder(statement));
230
231 challenge_cos->WriteVarint64(message_1.ByteSizeLong());
232 challenge_cos->WriteString(SerializeAsStringInOrder(message_1));
233
234 BigNum challenge_bound =
235 context_->One().Lshift(parameters_proto_.challenge_length_bits());
236
237 // Delete the serialization objects to make sure they clean up and write.
238 challenge_cos.reset();
239 challenge_sos.reset();
240
241 return context_->RandomOracleSha512(challenge_string, challenge_bound);
242 }
243
244 // Applies the DY VRF to a given batch of messages.
Apply(absl::Span<const BigNum> messages,const proto::DyVrfPrivateKey & private_key)245 StatusOr<std::vector<ECPoint>> DyVerifiableRandomFunction::Apply(
246 absl::Span<const BigNum> messages,
247 const proto::DyVrfPrivateKey& private_key) {
248 std::vector<ECPoint> dy_prf_evaluations;
249 dy_prf_evaluations.reserve(messages.size());
250
251 ASSIGN_OR_RETURN(DyVerifiableRandomFunction::PrivateKey parsed_private_key,
252 ParseDyVrfPrivateKeyProto(context_, private_key));
253
254 for (const BigNum& message : messages) {
255 // f(m) = g^(1/(key+m))
256 ASSIGN_OR_RETURN(
257 BigNum key_plus_message_inverse,
258 (message + parsed_private_key.key).ModInverse(ec_group_->GetOrder()));
259 ASSIGN_OR_RETURN(ECPoint prf_evaluation,
260 dy_prf_base_g_.Mul(key_plus_message_inverse));
261 dy_prf_evaluations.push_back(std::move(prf_evaluation));
262 }
263
264 return std::move(dy_prf_evaluations);
265 }
266
267 StatusOr<std::pair<
268 std::unique_ptr<DyVerifiableRandomFunction::ApplyProof::Message1>,
269 std::unique_ptr<
270 DyVerifiableRandomFunction::ApplyProof::Message1PrivateState>>>
GenerateApplyProofMessage1(absl::Span<const BigNum> messages,absl::Span<const ECPoint> prf_evaluations,const PedersenOverZn::CommitmentAndOpening & commit_and_open_messages,const DyVerifiableRandomFunction::PublicKey & public_key,const DyVerifiableRandomFunction::PrivateKey & private_key)271 DyVerifiableRandomFunction::GenerateApplyProofMessage1(
272 absl::Span<const BigNum> messages,
273 absl::Span<const ECPoint> prf_evaluations,
274 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages,
275 const DyVerifiableRandomFunction::PublicKey& public_key,
276 const DyVerifiableRandomFunction::PrivateKey& private_key) {
277 BigNum dummy_message_bound =
278 ec_group_->GetOrder().Lshift(parameters_proto_.security_parameter() +
279 parameters_proto_.challenge_length_bits());
280 BigNum dummy_opening_bound =
281 pedersen_->n().Lshift(parameters_proto_.security_parameter() +
282 parameters_proto_.challenge_length_bits());
283
284 // The proof is relative to a homomorphically added commitment of k + m.
285
286 // Generate dummy values for each message and the key, and create a dummy
287 // commitment to the vector of dummy k+m values.
288
289 BigNum dummy_key = context_->GenerateRandLessThan(dummy_message_bound);
290
291 std::vector<BigNum> dummy_messages_plus_key;
292 dummy_messages_plus_key.reserve(messages.size());
293
294 for (size_t i = 0; i < pedersen_->gs().size(); ++i) {
295 if (i < messages.size()) {
296 dummy_messages_plus_key.push_back(
297 context_->GenerateRandLessThan(dummy_message_bound) + dummy_key);
298 } else {
299 // If there's fewer messages than the number of Pedersen generators,
300 // pretend the message was 0. Leveraging the fact that the same key is
301 // committed w.r.t each Pedersen generator in the VRF public key, it's
302 // sufficient to just use dummy_key here.
303 dummy_messages_plus_key.push_back(dummy_key);
304 }
305 }
306
307 PedersenOverZn::Opening dummy_opening =
308 context_->GenerateRandLessThan(dummy_opening_bound);
309 ASSIGN_OR_RETURN(
310 PedersenOverZn::Commitment commit_dummy_messages_plus_key,
311 pedersen_->CommitWithRand(dummy_messages_plus_key, dummy_opening));
312
313 // Generate dummy_dy_prf_base_gs as (prf_evaluation ^ dummy_message_plus_key)
314 std::vector<ECPoint> dummy_dy_prf_base_gs;
315 dummy_dy_prf_base_gs.reserve(messages.size());
316 for (size_t i = 0; i < messages.size(); ++i) {
317 ASSIGN_OR_RETURN(ECPoint dummy_dy_prf_base_g,
318 prf_evaluations[i].Mul(dummy_messages_plus_key[i]));
319 dummy_dy_prf_base_gs.push_back(std::move(dummy_dy_prf_base_g));
320 }
321
322 ApplyProof::Message1 message_1 = {std::move(commit_dummy_messages_plus_key),
323 std::move(dummy_dy_prf_base_gs)};
324
325 ApplyProof::Message1PrivateState private_state = {
326 std::move(dummy_messages_plus_key), std::move(dummy_key),
327 std::move(dummy_opening)};
328
329 return std::make_pair(
330 std::make_unique<ApplyProof::Message1>(std::move(message_1)),
331 std::make_unique<ApplyProof::Message1PrivateState>(
332 std::move(private_state)));
333 }
334
335 // Applies the DY VRF to a given batch of messages, producing the PRF output
336 // and proof. Allows injecting the commitment and opening to the messages.
337 StatusOr<std::unique_ptr<DyVerifiableRandomFunction::ApplyProof::Message2>>
GenerateApplyProofMessage2(absl::Span<const BigNum> messages,absl::Span<const ECPoint> prf_evaluations,const PedersenOverZn::CommitmentAndOpening & commit_and_open_messages,const DyVerifiableRandomFunction::PublicKey & public_key,const DyVerifiableRandomFunction::PrivateKey & private_key,const DyVerifiableRandomFunction::ApplyProof::Message1 & message_1,const DyVerifiableRandomFunction::ApplyProof::Message1PrivateState & private_state,const BigNum & challenge)338 DyVerifiableRandomFunction::GenerateApplyProofMessage2(
339 absl::Span<const BigNum> messages,
340 absl::Span<const ECPoint> prf_evaluations,
341 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages,
342 const DyVerifiableRandomFunction::PublicKey& public_key,
343 const DyVerifiableRandomFunction::PrivateKey& private_key,
344 const DyVerifiableRandomFunction::ApplyProof::Message1& message_1,
345 const DyVerifiableRandomFunction::ApplyProof::Message1PrivateState&
346 private_state,
347 const BigNum& challenge) {
348 BigNum masked_dummy_key =
349 private_state.dummy_key + (private_key.key.Mul(challenge));
350
351 PedersenOverZn::Opening masked_dummy_opening =
352 private_state.dummy_opening +
353 ((private_key.commit_key_opening + commit_and_open_messages.opening)
354 .Mul(challenge));
355 std::vector<BigNum> masked_dummy_messages_plus_key;
356 masked_dummy_messages_plus_key.reserve(pedersen_->gs().size());
357 for (size_t i = 0; i < pedersen_->gs().size(); ++i) {
358 if (i < messages.size()) {
359 masked_dummy_messages_plus_key.push_back(
360 private_state.dummy_messages_plus_key[i] +
361 ((messages[i] + private_key.key).Mul(challenge)));
362 } else {
363 masked_dummy_messages_plus_key.push_back(masked_dummy_key);
364 }
365 }
366
367 ApplyProof::Message2 message_2 = {std::move(masked_dummy_messages_plus_key),
368 std::move(masked_dummy_opening)};
369
370 return std::make_unique<ApplyProof::Message2>(std::move(message_2));
371 }
372
GenerateApplyProof(absl::Span<const BigNum> messages,absl::Span<const ECPoint> prf_evaluations,const proto::DyVrfPublicKey & public_key,const proto::DyVrfPrivateKey & private_key,const PedersenOverZn::CommitmentAndOpening & commit_and_open_messages)373 StatusOr<proto::DyVrfApplyProof> DyVerifiableRandomFunction::GenerateApplyProof(
374 absl::Span<const BigNum> messages,
375 absl::Span<const ECPoint> prf_evaluations,
376 const proto::DyVrfPublicKey& public_key,
377 const proto::DyVrfPrivateKey& private_key,
378 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages) {
379 ASSIGN_OR_RETURN(PublicKey public_key_parsed,
380 ParseDyVrfPublicKeyProto(context_, public_key));
381 ASSIGN_OR_RETURN(PrivateKey private_key_parsed,
382 ParseDyVrfPrivateKeyProto(context_, private_key));
383
384 proto::DyVrfApplyProof proof_proto;
385
386 std::unique_ptr<DyVerifiableRandomFunction::ApplyProof::Message1>
387 proof_message_1;
388 std::unique_ptr<DyVerifiableRandomFunction::ApplyProof::Message1PrivateState>
389 proof_message_1_private_state;
390
391 ASSIGN_OR_RETURN(std::tie(proof_message_1, proof_message_1_private_state),
392 GenerateApplyProofMessage1(
393 messages, prf_evaluations, commit_and_open_messages,
394 public_key_parsed, private_key_parsed));
395
396 ASSIGN_OR_RETURN(*proof_proto.mutable_message_1(),
397 DyVrfApplyProofMessage1ToProto(*proof_message_1));
398
399 ASSIGN_OR_RETURN(BigNum challenge, GenerateApplyProofChallenge(
400 prf_evaluations, public_key,
401 commit_and_open_messages.commitment,
402 proof_proto.message_1()));
403
404 ASSIGN_OR_RETURN(
405 std::unique_ptr<DyVerifiableRandomFunction::ApplyProof::Message2>
406 proof_message_2,
407 GenerateApplyProofMessage2(messages, prf_evaluations,
408 commit_and_open_messages, public_key_parsed,
409 private_key_parsed, *proof_message_1,
410 *proof_message_1_private_state, challenge));
411 *proof_proto.mutable_message_2() =
412 DyVrfApplyProofMessage2ToProto(*proof_message_2);
413
414 return std::move(proof_proto);
415 }
416
417 // Verifies that vrf_output was produced by applying a DY VRF with the
418 // supplied public key on the supplied committed messages.
VerifyApplyProof(absl::Span<const ECPoint> prf_evaluations,const proto::DyVrfPublicKey & public_key,const PedersenOverZn::Commitment & commit_messages,const proto::DyVrfApplyProof & proof)419 Status DyVerifiableRandomFunction::VerifyApplyProof(
420 absl::Span<const ECPoint> prf_evaluations,
421 const proto::DyVrfPublicKey& public_key,
422 const PedersenOverZn::Commitment& commit_messages,
423 const proto::DyVrfApplyProof& proof) {
424 ASSIGN_OR_RETURN(PublicKey public_key_parsed,
425 ParseDyVrfPublicKeyProto(context_, public_key));
426 ASSIGN_OR_RETURN(ApplyProof::Message1 message_1,
427 ParseDyVrfApplyProofMessage1Proto(context_, ec_group_,
428 proof.message_1()));
429 ASSIGN_OR_RETURN(
430 ApplyProof::Message2 message_2,
431 ParseDyVrfApplyProofMessage2Proto(context_, proof.message_2()));
432
433 // Check input sizes.
434 if (prf_evaluations.size() > pedersen_->gs().size()) {
435 return absl::InvalidArgumentError(
436 "DyVerifiableRandomFunction::VerifyApplyProof: Number of "
437 "prf_evaluations is "
438 "greater than the number of Pedersen generators.");
439 }
440 if (prf_evaluations.size() != message_1.dummy_dy_prf_base_gs.size()) {
441 return absl::InvalidArgumentError(
442 "DyVerifiableRandomFunction::VerifyApplyProof: Number of "
443 "prf_evaluations is different from the number of dummy_dy_prf_base_gs "
444 "in the proof.");
445 }
446 if (pedersen_->gs().size() !=
447 message_2.masked_dummy_messages_plus_key.size()) {
448 return absl::InvalidArgumentError(
449 "DyVerifiableRandomFunction::VerifyApplyProof: Number of pedersen_gs "
450 "is different from the number of masked_dummy_messages_plus_keys in "
451 "the proof.");
452 }
453
454 // Note that even if there were fewer messages than Pedersen generators, the
455 // logic below handles this completely dynamically and safely. This is
456 // because no matter what the prover does for the "extra" generators, it
457 // doesn't allow breaking soundness for the values committed in the other
458 // generators.
459
460 // Invoke GenerateApplyProofChallenge if challenge is not already specified
461 // as a parameter.
462 ASSIGN_OR_RETURN(BigNum challenge, GenerateApplyProofChallenge(
463 prf_evaluations, public_key,
464 commit_messages, proof.message_1()));
465
466 // Verify the bit lengths of the masked values in the proof.
467 for (const auto& masked_value : message_2.masked_dummy_messages_plus_key) {
468 // There is an extra "+1" to account for summation.
469 if (masked_value.BitLength() >
470 (ec_group_->GetOrder().BitLength() +
471 parameters_proto_.challenge_length_bits() +
472 parameters_proto_.security_parameter() + 2)) {
473 return absl::InvalidArgumentError(
474 "DyVerifiableRandomFunction::Verify: some masked value in the proof "
475 "is larger than the admissable amount.");
476 }
477 }
478
479 // Check properties hold for dummy_dy_prf_base_gs.
480 ASSIGN_OR_RETURN(ECPoint dy_prf_base_g_to_challenge,
481 dy_prf_base_g_.Mul(challenge));
482 for (size_t i = 0; i < prf_evaluations.size(); ++i) {
483 // Let sigma be the prf evaluation. Then we must check (in multiplicative
484 // notation):
485 // sigma^(masked_key_plus_message) =
486 // (dummy_dy_prf_base_gs * (dy_prf_base_g^challenge))
487 ASSIGN_OR_RETURN(
488 ECPoint check_prf_left_hand_side,
489 prf_evaluations[i].Mul(message_2.masked_dummy_messages_plus_key[i]));
490
491 ASSIGN_OR_RETURN(
492 ECPoint check_prf_right_hand_side,
493 message_1.dummy_dy_prf_base_gs[i].Add(dy_prf_base_g_to_challenge));
494 if (check_prf_left_hand_side != check_prf_right_hand_side) {
495 return absl::InvalidArgumentError(
496 absl::StrCat("DyVerifiableRandomFunction::Verify: failed to verify "
497 "prf_evaluations[",
498 i, "]."));
499 }
500 }
501 // Check properties hold for the commitments to dummy values.
502 PedersenOverZn::Commitment commit_messages_plus_key_to_challenge =
503 pedersen_->Multiply(
504 pedersen_->Add(commit_messages, public_key_parsed.commit_key),
505 challenge);
506
507 ASSIGN_OR_RETURN(
508 PedersenOverZn::Commitment masked_dummy_commitment,
509 pedersen_->CommitWithRand(message_2.masked_dummy_messages_plus_key,
510 message_2.masked_dummy_opening));
511 PedersenOverZn::Commitment commitment_check_right_hand_side =
512 pedersen_->Add(message_1.commit_dummy_messages_plus_key,
513 commit_messages_plus_key_to_challenge);
514
515 if (masked_dummy_commitment != commitment_check_right_hand_side) {
516 return absl::InvalidArgumentError(
517 "DyVerifiableRandomFunction::Verify: failed to verify "
518 "commitment to keys and messages are consistent with prfs.");
519 }
520
521 return absl::OkStatus();
522 }
523
GenerateApplyProofChallenge(absl::Span<const ECPoint> prf_evaluations,const proto::DyVrfPublicKey & public_key,const PedersenOverZn::Commitment & commit_messages,const proto::DyVrfApplyProof::Message1 & message_1)524 StatusOr<BigNum> DyVerifiableRandomFunction::GenerateApplyProofChallenge(
525 absl::Span<const ECPoint> prf_evaluations,
526 const proto::DyVrfPublicKey& public_key,
527 const PedersenOverZn::Commitment& commit_messages,
528 const proto::DyVrfApplyProof::Message1& message_1) {
529 // Generate the statement
530 proto::DyVrfApplyProof::Statement statement;
531 *statement.mutable_parameters() = parameters_proto_;
532 *statement.mutable_public_key() = public_key;
533 statement.set_commit_messages(commit_messages.ToBytes());
534 ASSIGN_OR_RETURN(*statement.mutable_prf_evaluations(),
535 ECPointVectorToProto(prf_evaluations));
536
537 // Note that the random oracle prefix is implicitly included as part of the
538 // parameters being serialized in the statement proto. We skip including it
539 // again here to avoid unnecessary duplication.
540 std::string challenge_string =
541 "DyVerifiableRandomFunction::GenerateApplyProofChallenge";
542 auto challenge_sos =
543 std::make_unique<google::protobuf::io::StringOutputStream>(
544 &challenge_string);
545 auto challenge_cos =
546 std::make_unique<google::protobuf::io::CodedOutputStream>(
547 challenge_sos.get());
548 challenge_cos->SetSerializationDeterministic(true);
549 challenge_cos->WriteVarint64(statement.ByteSizeLong());
550
551 challenge_cos->WriteString(SerializeAsStringInOrder(statement));
552
553 challenge_cos->WriteVarint64(message_1.ByteSizeLong());
554 challenge_cos->WriteString(SerializeAsStringInOrder(message_1));
555
556 BigNum challenge_bound =
557 context_->One().Lshift(parameters_proto_.challenge_length_bits());
558
559 // Delete the serialization objects to make sure they clean up and write.
560 challenge_cos.reset();
561 challenge_sos.reset();
562
563 return context_->RandomOracleSha512(challenge_string, challenge_bound);
564 }
565
DyVrfPublicKeyToProto(const DyVerifiableRandomFunction::PublicKey & public_key)566 proto::DyVrfPublicKey DyVerifiableRandomFunction::DyVrfPublicKeyToProto(
567 const DyVerifiableRandomFunction::PublicKey& public_key) {
568 proto::DyVrfPublicKey public_key_proto;
569 public_key_proto.set_commit_prf_key(public_key.commit_key.ToBytes());
570 return public_key_proto;
571 }
DyVrfPrivateKeyToProto(const DyVerifiableRandomFunction::PrivateKey & private_key)572 proto::DyVrfPrivateKey DyVerifiableRandomFunction::DyVrfPrivateKeyToProto(
573 const DyVerifiableRandomFunction::PrivateKey& private_key) {
574 proto::DyVrfPrivateKey private_key_proto;
575 private_key_proto.set_prf_key(private_key.key.ToBytes());
576 private_key_proto.set_open_commit_prf_key(
577 private_key.commit_key_opening.ToBytes());
578 return private_key_proto;
579 }
580 StatusOr<proto::DyVrfApplyProof::Message1>
DyVrfApplyProofMessage1ToProto(const DyVerifiableRandomFunction::ApplyProof::Message1 & message_1)581 DyVerifiableRandomFunction::DyVrfApplyProofMessage1ToProto(
582 const DyVerifiableRandomFunction::ApplyProof::Message1& message_1) {
583 proto::DyVrfApplyProof::Message1 message_1_proto;
584 message_1_proto.set_commit_dummy_messages_plus_key(
585 message_1.commit_dummy_messages_plus_key.ToBytes());
586 ASSIGN_OR_RETURN(*message_1_proto.mutable_dummy_dy_prf_base_gs(),
587 ECPointVectorToProto(message_1.dummy_dy_prf_base_gs));
588 return message_1_proto;
589 }
590 proto::DyVrfApplyProof::Message2
DyVrfApplyProofMessage2ToProto(const DyVerifiableRandomFunction::ApplyProof::Message2 & message_2)591 DyVerifiableRandomFunction::DyVrfApplyProofMessage2ToProto(
592 const DyVerifiableRandomFunction::ApplyProof::Message2& message_2) {
593 proto::DyVrfApplyProof::Message2 message_2_proto;
594 *message_2_proto.mutable_masked_dummy_messages_plus_key() =
595 BigNumVectorToProto(message_2.masked_dummy_messages_plus_key);
596 message_2_proto.set_masked_dummy_opening(
597 message_2.masked_dummy_opening.ToBytes());
598 return message_2_proto;
599 }
600
601 StatusOr<DyVerifiableRandomFunction::PublicKey>
ParseDyVrfPublicKeyProto(Context * ctx,const proto::DyVrfPublicKey & public_key_proto)602 DyVerifiableRandomFunction::ParseDyVrfPublicKeyProto(
603 Context* ctx, const proto::DyVrfPublicKey& public_key_proto) {
604 BigNum commit_key = ctx->CreateBigNum(public_key_proto.commit_prf_key());
605 return DyVerifiableRandomFunction::PublicKey{std::move(commit_key)};
606 }
607 StatusOr<DyVerifiableRandomFunction::PrivateKey>
ParseDyVrfPrivateKeyProto(Context * ctx,const proto::DyVrfPrivateKey & private_key_proto)608 DyVerifiableRandomFunction::ParseDyVrfPrivateKeyProto(
609 Context* ctx, const proto::DyVrfPrivateKey& private_key_proto) {
610 BigNum key = ctx->CreateBigNum(private_key_proto.prf_key());
611 BigNum commit_key_opening =
612 ctx->CreateBigNum(private_key_proto.open_commit_prf_key());
613 return DyVerifiableRandomFunction::PrivateKey{std::move(key),
614 std::move(commit_key_opening)};
615 }
616 StatusOr<DyVerifiableRandomFunction::ApplyProof::Message1>
ParseDyVrfApplyProofMessage1Proto(Context * ctx,ECGroup * ec_group,const proto::DyVrfApplyProof::Message1 & message_1_proto)617 DyVerifiableRandomFunction::ParseDyVrfApplyProofMessage1Proto(
618 Context* ctx, ECGroup* ec_group,
619 const proto::DyVrfApplyProof::Message1& message_1_proto) {
620 BigNum commit_dummy_messages_plus_key =
621 ctx->CreateBigNum(message_1_proto.commit_dummy_messages_plus_key());
622 ASSIGN_OR_RETURN(std::vector<ECPoint> dummy_dy_prf_base_gs,
623 ParseECPointVectorProto(
624 ctx, ec_group, message_1_proto.dummy_dy_prf_base_gs()));
625 return DyVerifiableRandomFunction::ApplyProof::Message1{
626 std::move(commit_dummy_messages_plus_key),
627 std::move(dummy_dy_prf_base_gs)};
628 }
629 StatusOr<DyVerifiableRandomFunction::ApplyProof::Message2>
ParseDyVrfApplyProofMessage2Proto(Context * ctx,const proto::DyVrfApplyProof::Message2 & message_2_proto)630 DyVerifiableRandomFunction::ParseDyVrfApplyProofMessage2Proto(
631 Context* ctx, const proto::DyVrfApplyProof::Message2& message_2_proto) {
632 std::vector<BigNum> masked_dummy_messages_plus_key = ParseBigNumVectorProto(
633 ctx, message_2_proto.masked_dummy_messages_plus_key());
634 BigNum masked_dummy_opening =
635 ctx->CreateBigNum(message_2_proto.masked_dummy_opening());
636 return DyVerifiableRandomFunction::ApplyProof::Message2{
637 std::move(masked_dummy_messages_plus_key),
638 std::move(masked_dummy_opening)};
639 }
640
641 } // namespace private_join_and_compute
642