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/pedersen_over_zn.h"
17
18 #include <gmock/gmock.h>
19 #include <gtest/gtest.h>
20
21 #include <cstdint>
22 #include <memory>
23 #include <utility>
24 #include <vector>
25
26 #include "private_join_and_compute/crypto/context.h"
27 #include "private_join_and_compute/crypto/proto/pedersen.pb.h"
28 #include "private_join_and_compute/crypto/proto/proto_util.h"
29 #include "private_join_and_compute/util/status.inc"
30 #include "private_join_and_compute/util/status_testing.inc"
31
32 namespace private_join_and_compute {
33 namespace {
34
35 using ::testing::HasSubstr;
36 using testing::IsOkAndHolds;
37 using testing::StatusIs;
38
39 const uint64_t P = 5;
40 const uint64_t Q = 7;
41 const uint64_t N = P * Q;
42 const uint64_t H = 31; // corresponds to -(2^2) mod N.
43 const uint64_t R = 5;
44 const uint64_t G = 26; // G = H^R mod N
45 const uint64_t G2 = 6;
46 const uint64_t P_XL = 35879;
47 const uint64_t Q_XL = 63587;
48 const uint64_t N_XL = P_XL * Q_XL;
49
50 const uint64_t NUM_REPETITIONS = 20;
51 const uint64_t CHALLENGE_LENGTH = 4;
52 const uint64_t ZK_QUALITY = 4;
53
54 // A test fixture for PedersenOverZn.
55 class PedersenOverZnTest : public ::testing::Test {
56 protected:
SetUp()57 void SetUp() override {
58 std::vector<BigNum> bases = {ctx_.CreateBigNum(G)};
59 pedersen_ = PedersenOverZn::Create(&ctx_, bases, ctx_.CreateBigNum(H),
60 ctx_.CreateBigNum(N))
61 .value();
62 }
63
64 Context ctx_;
65 std::unique_ptr<PedersenOverZn> pedersen_;
66 };
67
TEST_F(PedersenOverZnTest,SplitVector)68 TEST_F(PedersenOverZnTest, SplitVector) {
69 Context ctx;
70 int subvector_size = 7;
71 int num_inputs = 1000;
72
73 // Generate a random vector of BigNums.
74 BigNum bound = ctx.CreateBigNum(100000);
75 std::vector<BigNum> input;
76 for (int i = 0; i < num_inputs; i++) {
77 input.push_back(ctx.GenerateRandLessThan(bound));
78 }
79
80 // Split the vector into subvectors.
81 auto output = SplitVector(input, subvector_size);
82
83 // Expect that the splitting happened properly.
84 // Correct number of subvectors.
85 int expected_num_subvectors =
86 (num_inputs + subvector_size - 1) / subvector_size;
87 EXPECT_EQ(output.size(), expected_num_subvectors);
88
89 // Last subvector has the expected size.
90 if (num_inputs % subvector_size != 0) {
91 EXPECT_EQ(output[expected_num_subvectors - 1].size(),
92 num_inputs % subvector_size);
93 }
94
95 // Each entry of each subvector is correct.
96 for (int i = 0; i < num_inputs; i++) {
97 EXPECT_EQ(input[i], output[i / subvector_size][i % subvector_size]);
98 }
99 }
100
TEST_F(PedersenOverZnTest,TestFromProto)101 TEST_F(PedersenOverZnTest, TestFromProto) {
102 proto::PedersenParameters parameters_proto;
103 parameters_proto.set_n(pedersen_->n().ToBytes());
104 parameters_proto.set_h(pedersen_->h().ToBytes());
105 *parameters_proto.mutable_gs() = BigNumVectorToProto(pedersen_->gs());
106
107 ASSERT_OK_AND_ASSIGN(std::unique_ptr<PedersenOverZn> from_proto,
108 PedersenOverZn::FromProto(&ctx_, parameters_proto));
109 EXPECT_EQ(from_proto->n(), pedersen_->n());
110 EXPECT_EQ(from_proto->h(), pedersen_->h());
111 EXPECT_EQ(from_proto->gs(), pedersen_->gs());
112 }
113
TEST_F(PedersenOverZnTest,TestGeneratePedersenOverZnParametersWithLargeModulus)114 TEST_F(PedersenOverZnTest,
115 TestGeneratePedersenOverZnParametersWithLargeModulus) {
116 BigNum n = ctx_.CreateBigNum(N_XL);
117 int64_t num_gs = 5;
118 PedersenOverZn::Parameters params =
119 PedersenOverZn::GenerateParameters(&ctx_, n, num_gs);
120 // n copied correctly
121 EXPECT_EQ(params.n, n);
122 // g = h^r mod n
123 for (int i = 0; i < num_gs; i++) {
124 EXPECT_EQ(params.gs[i], params.h.ModExp(params.rs[i], params.n));
125 }
126
127 // test that g and h are actually generators, that is:
128 // (i) they are each in Z*n
129 for (int i = 0; i < num_gs; i++) {
130 EXPECT_EQ(ctx_.One(), params.gs[i].Gcd(n));
131 }
132 EXPECT_EQ(ctx_.One(), params.h.Gcd(n));
133
134 // (ii) they are not generators of the smaller subgroups of order 2, (p-1)/2
135 // and (q-1)/2 respectively
136 for (int i = 0; i < num_gs; i++) {
137 EXPECT_NE(ctx_.One(), params.gs[i].ModExp(ctx_.Two(), n));
138 }
139 EXPECT_NE(ctx_.One(), params.h.ModExp(ctx_.Two(), n));
140
141 BigNum bn_i = ctx_.CreateBigNum((P_XL - 1) / 2);
142 for (int i = 0; i < num_gs; i++) {
143 EXPECT_NE(ctx_.One(), params.gs[i].ModExp(bn_i, n));
144 }
145 EXPECT_NE(ctx_.One(), params.h.ModExp(bn_i, n));
146
147 bn_i = ctx_.CreateBigNum((Q_XL - 1) / 2);
148 for (int i = 0; i < num_gs; i++) {
149 EXPECT_NE(ctx_.One(), params.gs[i].ModExp(bn_i, n));
150 }
151 EXPECT_NE(ctx_.One(), params.h.ModExp(bn_i, n));
152
153 // (iii) g^i and h^i = 1 for i = the order of the subgroup of quadratic
154 // residues
155 bn_i = ctx_.CreateBigNum(((P_XL - 1) * (Q_XL - 1)) / 4);
156 for (int i = 0; i < num_gs; i++) {
157 EXPECT_EQ(ctx_.One(), params.gs[i].ModExp(bn_i, n));
158 }
159 EXPECT_EQ(ctx_.One(), params.h.ModExp(bn_i, n));
160 }
161
TEST_F(PedersenOverZnTest,TestCommitFailsWithInvalidMessage)162 TEST_F(PedersenOverZnTest, TestCommitFailsWithInvalidMessage) {
163 // Negative value.
164 BigNum neg_one = ctx_.Zero() - ctx_.One();
165 auto maybe_result = pedersen_->Commit({neg_one});
166 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
167 EXPECT_THAT(maybe_result.status().message(),
168 HasSubstr("cannot commit to negative value."));
169
170 // Should work fine.
171 EXPECT_FALSE(
172 IsInvalidArgument(pedersen_->Commit({ctx_.CreateBigNum(8)}).status()));
173 }
174
TEST_F(PedersenOverZnTest,TestVerifyComplainsOnInvalidArguments)175 TEST_F(PedersenOverZnTest, TestVerifyComplainsOnInvalidArguments) {
176 PedersenOverZn::Commitment com = ctx_.Zero();
177
178 // Negative message
179 PedersenOverZn::Opening open = ctx_.Zero();
180 auto maybe_result = pedersen_->Verify(com, {-ctx_.One()}, open);
181 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
182 EXPECT_THAT(maybe_result.status().message(),
183 HasSubstr("message in the opening is negative"));
184
185 // Negative randomness
186 open = -ctx_.One();
187 maybe_result = pedersen_->Verify(com, {ctx_.Zero()}, open);
188 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
189 EXPECT_THAT(maybe_result.status().message(),
190 HasSubstr("randomness in the opening is negative"));
191 }
192
TEST_F(PedersenOverZnTest,TestCommitAndVerifyZero)193 TEST_F(PedersenOverZnTest, TestCommitAndVerifyZero) {
194 ASSERT_OK_AND_ASSIGN(auto commit_and_open, pedersen_->Commit({ctx_.Zero()}));
195 PedersenOverZn::Commitment com = std::move(commit_and_open.commitment);
196 PedersenOverZn::Opening open = std::move(commit_and_open.opening);
197 EXPECT_THAT(pedersen_->Verify(com, {ctx_.Zero()}, open), IsOkAndHolds(true));
198 }
199
TEST_F(PedersenOverZnTest,TestCommitAndVerifyTwo)200 TEST_F(PedersenOverZnTest, TestCommitAndVerifyTwo) {
201 ASSERT_OK_AND_ASSIGN(auto commit_and_open, pedersen_->Commit({ctx_.Two()}));
202 PedersenOverZn::Commitment com = std::move(commit_and_open.commitment);
203 PedersenOverZn::Opening open = std::move(commit_and_open.opening);
204 EXPECT_THAT(pedersen_->Verify(com, {ctx_.Two()}, open), IsOkAndHolds(true));
205 }
206
TEST_F(PedersenOverZnTest,VerifyFailsOnIncorrectOpening)207 TEST_F(PedersenOverZnTest, VerifyFailsOnIncorrectOpening) {
208 BigNum message = ctx_.Two();
209 ASSERT_OK_AND_ASSIGN(auto commit_and_open, pedersen_->Commit({message}));
210 PedersenOverZn::Commitment com = std::move(commit_and_open.commitment);
211 PedersenOverZn::Opening open = std::move(commit_and_open.opening);
212
213 BigNum wrong_message = ctx_.Zero();
214 EXPECT_THAT(pedersen_->Verify(com, {wrong_message}, open),
215 IsOkAndHolds(false));
216
217 PedersenOverZn::Opening wrong_random = open + ctx_.One();
218 EXPECT_THAT(pedersen_->Verify(com, {message}, wrong_random),
219 IsOkAndHolds(false));
220 }
221
TEST_F(PedersenOverZnTest,TestGenerateLargeParamsCommitAndVerify)222 TEST_F(PedersenOverZnTest, TestGenerateLargeParamsCommitAndVerify) {
223 PedersenOverZn::Parameters params =
224 PedersenOverZn::GenerateParameters(&ctx_, ctx_.CreateBigNum(N_XL));
225 ASSERT_OK_AND_ASSIGN(
226 pedersen_, PedersenOverZn::Create(&ctx_, params.gs, params.h, params.n));
227
228 BigNum n_by_four = params.n.DivAndTruncate(ctx_.CreateBigNum(4));
229 BigNum m = ctx_.GenerateRandLessThan(n_by_four);
230
231 ASSERT_OK_AND_ASSIGN(auto commit_and_open, pedersen_->Commit({m}));
232 PedersenOverZn::Commitment com = std::move(commit_and_open.commitment);
233 PedersenOverZn::Opening open = std::move(commit_and_open.opening);
234 EXPECT_THAT(pedersen_->Verify(com, {m}, open), IsOkAndHolds(true));
235 }
236
TEST_F(PedersenOverZnTest,TestCommitWithRandAndVerifyZero)237 TEST_F(PedersenOverZnTest, TestCommitWithRandAndVerifyZero) {
238 ASSERT_OK_AND_ASSIGN(PedersenOverZn::Commitment com,
239 pedersen_->CommitWithRand({ctx_.Zero()}, ctx_.Three()));
240 EXPECT_THAT(pedersen_->Verify(com, {ctx_.Zero()}, ctx_.Three()),
241 IsOkAndHolds(true));
242 }
243
TEST_F(PedersenOverZnTest,TestCommitWithRandAndVerifyTwo)244 TEST_F(PedersenOverZnTest, TestCommitWithRandAndVerifyTwo) {
245 ASSERT_OK_AND_ASSIGN(PedersenOverZn::Commitment com,
246 pedersen_->CommitWithRand({ctx_.Two()}, ctx_.Three()));
247 EXPECT_THAT(pedersen_->Verify(com, {ctx_.Two()}, ctx_.Three()),
248 IsOkAndHolds(true));
249 }
250
TEST_F(PedersenOverZnTest,TestCommitWithRandComplainsOnNegativeMessageAndRandomness)251 TEST_F(PedersenOverZnTest,
252 TestCommitWithRandComplainsOnNegativeMessageAndRandomness) {
253 // Negative message
254 auto maybe_result = pedersen_->CommitWithRand({-ctx_.Two()}, ctx_.One());
255 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
256 EXPECT_THAT(maybe_result.status().message(),
257 HasSubstr("cannot commit to negative value."));
258
259 // Negative randomness
260 maybe_result = pedersen_->CommitWithRand({ctx_.Two()}, -ctx_.One());
261 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
262 EXPECT_THAT(maybe_result.status().message(),
263 HasSubstr("randomness must be nonnegative."));
264 }
265
TEST_F(PedersenOverZnTest,TestAdd)266 TEST_F(PedersenOverZnTest, TestAdd) {
267 ASSERT_OK_AND_ASSIGN(auto commit_and_open_1, pedersen_->Commit({ctx_.One()}));
268 ASSERT_OK_AND_ASSIGN(auto commit_and_open_2, pedersen_->Commit({ctx_.Two()}));
269 auto commit_3 = pedersen_->Add(commit_and_open_1.commitment,
270 commit_and_open_2.commitment);
271
272 // Verifies that the opening randomness of commit_3 is the sum of the
273 // opening randomness in commit_and_open_1 and commit_and_open_2.
274 auto randomness_in_commit_3 =
275 commit_and_open_1.opening + commit_and_open_2.opening;
276 EXPECT_TRUE(
277 pedersen_->Verify(commit_3, {ctx_.Three()}, randomness_in_commit_3).ok());
278 }
279
TEST_F(PedersenOverZnTest,TestMultiply)280 TEST_F(PedersenOverZnTest, TestMultiply) {
281 ASSERT_OK_AND_ASSIGN(auto commit_and_open_2, pedersen_->Commit({ctx_.Two()}));
282 auto commit_6 =
283 pedersen_->Multiply(commit_and_open_2.commitment, ctx_.Three());
284
285 // Verifies that the opening randomness of commit_6 is 3 times the opening
286 // randomness in commit_and_open_2.
287 auto randomness_in_commit_6 = commit_and_open_2.opening * ctx_.Three();
288 EXPECT_TRUE(
289 pedersen_
290 ->Verify(commit_6, {ctx_.CreateBigNum(6)}, randomness_in_commit_6)
291 .ok());
292 }
293
TEST_F(PedersenOverZnTest,TestCommitFailsWithTooManyMessages)294 TEST_F(PedersenOverZnTest, TestCommitFailsWithTooManyMessages) {
295 // Commit with the default parameters can handle at most 1 message, 2
296 // provided.
297 auto maybe_result = pedersen_->Commit({ctx_.One(), ctx_.Zero()});
298 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
299 EXPECT_THAT(maybe_result.status().message(),
300 HasSubstr("too many messages provided"));
301 }
302
TEST_F(PedersenOverZnTest,TestVerifyFailsWithTooManyMessages)303 TEST_F(PedersenOverZnTest, TestVerifyFailsWithTooManyMessages) {
304 ASSERT_OK_AND_ASSIGN(auto commit_and_rand, pedersen_->Commit({ctx_.One()}));
305 // Verify can handle at most 1 message, 2 provided.
306 auto maybe_result =
307 pedersen_->Verify(commit_and_rand.commitment, {ctx_.One(), ctx_.Zero()},
308 commit_and_rand.opening);
309 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
310 EXPECT_THAT(maybe_result.status().message(),
311 HasSubstr("too many messages provided"));
312 }
313
TEST_F(PedersenOverZnTest,TestCommitAndVerifyWithMultipleGs)314 TEST_F(PedersenOverZnTest, TestCommitAndVerifyWithMultipleGs) {
315 // Two gs, two messages.
316 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
317 std::vector<BigNum> messages = {ctx_.Two(), ctx_.Three()};
318 ASSERT_OK_AND_ASSIGN(auto multi_pedersen,
319 PedersenOverZn::Create(&ctx_, gs, ctx_.CreateBigNum(H),
320 ctx_.CreateBigNum(N)));
321
322 ASSERT_OK_AND_ASSIGN(auto commit_and_rand, multi_pedersen->Commit(messages));
323 EXPECT_THAT(multi_pedersen->Verify(commit_and_rand.commitment, messages,
324 commit_and_rand.opening),
325 IsOkAndHolds(true));
326 }
327
TEST_F(PedersenOverZnTest,TestCommitAndVerifyWithFewerMessagesThanGs)328 TEST_F(PedersenOverZnTest, TestCommitAndVerifyWithFewerMessagesThanGs) {
329 // Two gs, one message.
330 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
331 std::vector<BigNum> messages = {ctx_.Two()};
332 ASSERT_OK_AND_ASSIGN(auto multi_pedersen,
333 PedersenOverZn::Create(&ctx_, gs, ctx_.CreateBigNum(H),
334 ctx_.CreateBigNum(N)));
335
336 ASSERT_OK_AND_ASSIGN(auto commit_and_rand, multi_pedersen->Commit(messages));
337 EXPECT_THAT(multi_pedersen->Verify(commit_and_rand.commitment, messages,
338 commit_and_rand.opening),
339 IsOkAndHolds(true));
340 }
341
TEST_F(PedersenOverZnTest,TestCommitAndVerifyWifDifferentPrecomputation)342 TEST_F(PedersenOverZnTest, TestCommitAndVerifyWifDifferentPrecomputation) {
343 // Two gs, two messages.
344 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
345 std::vector<BigNum> messages = {ctx_.Two(), ctx_.Three()};
346 ASSERT_OK_AND_ASSIGN(
347 auto multi_pedersen_1,
348 PedersenOverZn::Create(&ctx_, gs, ctx_.CreateBigNum(H),
349 ctx_.CreateBigNum(N),
350 /*num_simultaneous_exponentiations= */ 1));
351
352 ASSERT_OK_AND_ASSIGN(
353 auto multi_pedersen_2,
354 PedersenOverZn::Create(&ctx_, gs, ctx_.CreateBigNum(H),
355 ctx_.CreateBigNum(N),
356 /*num_simultaneous_exponentiations= */ 2));
357
358 // Test consistency between commitments with the two different pedersen
359 // objects. This will imply consistency of verification as well.
360 ASSERT_OK_AND_ASSIGN(auto commit_and_rand_1,
361 multi_pedersen_1->Commit(messages));
362 ASSERT_OK_AND_ASSIGN(auto commit_2, multi_pedersen_2->CommitWithRand(
363 messages, commit_and_rand_1.opening));
364 EXPECT_EQ(commit_and_rand_1.commitment, commit_2);
365 }
366
TEST_F(PedersenOverZnTest,SerializeAndDeserializeParameters)367 TEST_F(PedersenOverZnTest, SerializeAndDeserializeParameters) {
368 // Two gs, two messages.
369 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
370 PedersenOverZn::Parameters parameters{
371 std::move(gs), ctx_.CreateBigNum(H), ctx_.CreateBigNum(N), {}};
372
373 proto::PedersenParameters parameters_proto =
374 PedersenOverZn::ParametersToProto(parameters);
375 ASSERT_OK_AND_ASSIGN(
376 PedersenOverZn::Parameters parameters_deserialized,
377 PedersenOverZn::ParseParametersProto(&ctx_, parameters_proto));
378
379 EXPECT_EQ(parameters.gs, parameters_deserialized.gs);
380 EXPECT_EQ(parameters.h, parameters_deserialized.h);
381 EXPECT_EQ(parameters.n, parameters_deserialized.n);
382 }
383
TEST_F(PedersenOverZnTest,DeserializingParametersFailsWhenGsOutOfBounds)384 TEST_F(PedersenOverZnTest, DeserializingParametersFailsWhenGsOutOfBounds) {
385 // Two gs, two messages.
386 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
387 PedersenOverZn::Parameters parameters{
388 gs, ctx_.CreateBigNum(H), ctx_.CreateBigNum(N), {}};
389
390 proto::PedersenParameters parameters_proto =
391 PedersenOverZn::ParametersToProto(parameters);
392
393 BigNum out_of_bounds = ctx_.CreateBigNum(N) + ctx_.One();
394
395 // g out of bounds
396 proto::PedersenParameters parameters_proto_gs_out_of_bounds =
397 parameters_proto;
398 std::vector<BigNum> gs_out_of_bounds = gs;
399 gs_out_of_bounds[0] = out_of_bounds;
400 *parameters_proto_gs_out_of_bounds.mutable_gs() =
401 BigNumVectorToProto(gs_out_of_bounds);
402 EXPECT_THAT(PedersenOverZn::ParseParametersProto(
403 &ctx_, parameters_proto_gs_out_of_bounds),
404 StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr(" g ")));
405 }
406
TEST_F(PedersenOverZnTest,DeserializingParametersFailsWhenHOutOfBounds)407 TEST_F(PedersenOverZnTest, DeserializingParametersFailsWhenHOutOfBounds) {
408 // Two gs, two messages.
409 std::vector<BigNum> gs = {ctx_.CreateBigNum(G), ctx_.CreateBigNum(G2)};
410 PedersenOverZn::Parameters parameters{
411 gs, ctx_.CreateBigNum(H), ctx_.CreateBigNum(N), {}};
412
413 proto::PedersenParameters parameters_proto =
414 PedersenOverZn::ParametersToProto(parameters);
415
416 BigNum out_of_bounds = ctx_.CreateBigNum(N) + ctx_.One();
417
418 // h out of bounds
419 proto::PedersenParameters parameters_proto_h_out_of_bounds = parameters_proto;
420 parameters_proto_h_out_of_bounds.set_h(out_of_bounds.ToBytes());
421 EXPECT_THAT(PedersenOverZn::ParseParametersProto(
422 &ctx_, parameters_proto_h_out_of_bounds),
423 StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr(" h ")));
424 }
425
426 // A test fixture for proofs that PedersenOverZn parameters were correctly
427 // generated, for the case when the modulus is not known to be the product of
428 // 2 safe primes. The proof is automatically reset between tests.
429 class PedersenOverZnGenProofTest : public ::testing::Test {
430 protected:
PedersenOverZnGenProofTest()431 PedersenOverZnGenProofTest()
432 : ctx_(),
433 g_(ctx_.CreateBigNum(G)),
434 h_(ctx_.CreateBigNum(H)),
435 n_(ctx_.CreateBigNum(N)),
436 r_(ctx_.CreateBigNum(R)),
437 num_repetitions_(NUM_REPETITIONS),
438 zk_quality_(ZK_QUALITY),
439 proof_() {}
440
SetUp()441 void SetUp() override {
442 proof_ = std::make_unique<PedersenOverZn::ProofOfGen>(
443 PedersenOverZn::ProveParametersCorrectlyGenerated(
444 &ctx_, g_, h_, n_, r_, num_repetitions_, zk_quality_)
445 .value());
446 }
447
448 Context ctx_;
449 BigNum g_;
450 BigNum h_;
451 BigNum n_;
452 BigNum r_;
453 int num_repetitions_;
454 int zk_quality_;
455 std::unique_ptr<PedersenOverZn::ProofOfGen> proof_;
456 };
457
TEST_F(PedersenOverZnGenProofTest,TestHonestProofVerifies)458 TEST_F(PedersenOverZnGenProofTest, TestHonestProofVerifies) {
459 EXPECT_TRUE(
460 PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_).ok());
461 }
462
TEST_F(PedersenOverZnGenProofTest,TestChallengesAreBinaryAndDifferent)463 TEST_F(PedersenOverZnGenProofTest, TestChallengesAreBinaryAndDifferent) {
464 std::vector<uint8_t> challenges = PedersenOverZn::GetGenProofChallenge(
465 &ctx_, g_ + ctx_.One(), h_, n_, proof_->dummy_gs,
466 proof_->num_repetitions);
467 int sum_of_challenges = 0;
468 for (auto& challenge : challenges) {
469 EXPECT_TRUE(challenge == 0 || challenge == 1);
470 sum_of_challenges += challenge;
471 }
472 // Use the sum to test that the challenges are not all 0 and not all 1.
473 EXPECT_TRUE(sum_of_challenges > 0 &&
474 sum_of_challenges < proof_->num_repetitions);
475 }
476
TEST_F(PedersenOverZnGenProofTest,TestProofGenerationFailsOnInvalidInputs)477 TEST_F(PedersenOverZnGenProofTest, TestProofGenerationFailsOnInvalidInputs) {
478 auto maybe_result = PedersenOverZn::ProveParametersCorrectlyGenerated(
479 &ctx_, g_, h_, n_, r_, 0, zk_quality_);
480 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
481 EXPECT_THAT(maybe_result.status().message(),
482 HasSubstr("number of repetitions must be positive."));
483
484 maybe_result = PedersenOverZn::ProveParametersCorrectlyGenerated(
485 &ctx_, g_, h_, n_, r_, num_repetitions_, 0);
486 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
487 EXPECT_THAT(maybe_result.status().message(),
488 HasSubstr("zk_quality parameter must be positive."));
489
490 maybe_result = PedersenOverZn::ProveParametersCorrectlyGenerated(
491 &ctx_, g_, ctx_.CreateBigNum(20), n_, r_, num_repetitions_, zk_quality_);
492 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
493 EXPECT_THAT(maybe_result.status().message(),
494 HasSubstr("h is not relatively prime to n."));
495
496 maybe_result = PedersenOverZn::ProveParametersCorrectlyGenerated(
497 &ctx_, ctx_.CreateBigNum(2), h_, n_, r_, num_repetitions_, zk_quality_);
498 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
499 EXPECT_THAT(maybe_result.status().message(), HasSubstr("g != h^r mod n."));
500
501 maybe_result = PedersenOverZn::ProveParametersCorrectlyGenerated(
502 &ctx_, g_, h_, n_, ctx_.CreateBigNum(2), num_repetitions_, zk_quality_);
503 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
504 EXPECT_THAT(maybe_result.status().message(), HasSubstr("g != h^r mod n."));
505 }
506
TEST_F(PedersenOverZnGenProofTest,TestProofVerificationFailsOnInvalidInputs)507 TEST_F(PedersenOverZnGenProofTest, TestProofVerificationFailsOnInvalidInputs) {
508 Status status;
509 // Proof contains invalid number of repetitions parameter
510 proof_->num_repetitions = 0;
511 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_);
512 EXPECT_TRUE(IsInvalidArgument(status));
513 EXPECT_THAT(status.message(),
514 ::testing::HasSubstr("number of repetitions must be positive."));
515 proof_->num_repetitions = NUM_REPETITIONS;
516
517 // Proof does not contain exactly "number of repetitions" dummy_gs
518 proof_->dummy_gs.push_back(std::make_unique<BigNum>(ctx_.One()));
519 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_);
520 EXPECT_TRUE(IsInvalidArgument(status));
521 EXPECT_THAT(
522 status.message(),
523 ::testing::HasSubstr("proof is not valid: number of dummy_gs is "
524 "different from number of repetitions specified."));
525 proof_->dummy_gs.pop_back();
526
527 // Proof does not contain exactly "number of repetitions" responses
528 proof_->responses.push_back(std::make_unique<BigNum>(ctx_.One()));
529 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_);
530 EXPECT_TRUE(IsInvalidArgument(status));
531 EXPECT_THAT(
532 status.message(),
533 ::testing::HasSubstr("proof is not valid: number of responses is "
534 "different from number of repetitions specified."));
535 proof_->responses.pop_back();
536
537 // h is not relatively prime to modulus.
538 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, ctx_.CreateBigNum(20),
539 n_, *proof_);
540 EXPECT_TRUE(IsInvalidArgument(status));
541 EXPECT_THAT(status.message(),
542 ::testing::HasSubstr("h is not relatively prime to n."));
543 }
544
TEST_F(PedersenOverZnGenProofTest,TestProofVerificationFailsOnIncorrectProof)545 TEST_F(PedersenOverZnGenProofTest, TestProofVerificationFailsOnIncorrectProof) {
546 Status status;
547
548 // Change a response
549 *(proof_->responses[2]) = (*proof_->responses[2]) + ctx_.One();
550 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_);
551 EXPECT_TRUE(IsInvalidArgument(status));
552 EXPECT_THAT(
553 status.message(),
554 ::testing::HasSubstr("the proof verification formula fails at index 2"));
555 *(proof_->responses[2]) = (*proof_->responses[2]) - ctx_.One();
556
557 // Change g to g+1
558 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_ + ctx_.One(), h_, n_,
559 *proof_);
560 EXPECT_TRUE(IsInvalidArgument(status));
561 EXPECT_THAT(status.message(),
562 ::testing::HasSubstr("the proof verification formula fails at "));
563
564 // Change a dummy_g
565 // Note here that changing "dummy_gs" potentially changes the challenge in
566 // every repetition, so we cannot guarantee which repetition is the first to
567 // fail.
568 *(proof_->dummy_gs[3]) = (*proof_->dummy_gs[3]) + ctx_.One();
569 status = PedersenOverZn::VerifyParamsProof(&ctx_, g_, h_, n_, *proof_);
570 EXPECT_TRUE(IsInvalidArgument(status));
571 EXPECT_THAT(status.message(),
572 ::testing::HasSubstr("the proof verification formula fails at "));
573 }
574
575 // A test fixture for proofs that PedersenOverZn parameters were correctly
576 // generated, for the case when the modulus is already believed to be the
577 // product of 2 safe primes The proof is automatically reset between tests.
578 class PedersenOverZnGenProofForTrustedModulusTest : public ::testing::Test {
579 protected:
PedersenOverZnGenProofForTrustedModulusTest()580 PedersenOverZnGenProofForTrustedModulusTest()
581 : ctx_(),
582 g_(ctx_.CreateBigNum(G)),
583 h_(ctx_.CreateBigNum(H)),
584 n_(ctx_.CreateBigNum(N)),
585 r_(ctx_.CreateBigNum(R)),
586 challenge_length_(CHALLENGE_LENGTH),
587 zk_quality_(ZK_QUALITY),
588 safe_modulus_proof_() {}
589
SetUp()590 void SetUp() override {
591 safe_modulus_proof_ =
592 std::make_unique<PedersenOverZn::ProofOfGenForTrustedModulus>(
593 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
594 &ctx_, g_, h_, n_, r_, challenge_length_, zk_quality_)
595 .value());
596 }
597
598 Context ctx_;
599 BigNum g_;
600 BigNum h_;
601 BigNum n_;
602 BigNum r_;
603 int challenge_length_;
604 int zk_quality_;
605 std::unique_ptr<PedersenOverZn::ProofOfGenForTrustedModulus>
606 safe_modulus_proof_;
607 };
608
TEST_F(PedersenOverZnGenProofForTrustedModulusTest,TestHonestProofVerifies)609 TEST_F(PedersenOverZnGenProofForTrustedModulusTest, TestHonestProofVerifies) {
610 EXPECT_TRUE(PedersenOverZn::VerifyParamsProofForTrustedModulus(
611 &ctx_, g_, h_, n_, *safe_modulus_proof_)
612 .ok());
613 }
614
TEST_F(PedersenOverZnGenProofForTrustedModulusTest,TestProofGenerationFailsOnInvalidInputs)615 TEST_F(PedersenOverZnGenProofForTrustedModulusTest,
616 TestProofGenerationFailsOnInvalidInputs) {
617 auto maybe_result =
618 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
619 &ctx_, g_, h_, n_, r_, 0, zk_quality_);
620 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
621 EXPECT_THAT(maybe_result.status().message(),
622 HasSubstr("challenge length must be positive."));
623
624 maybe_result =
625 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
626 &ctx_, g_, h_, n_, r_, challenge_length_, 0);
627 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
628 EXPECT_THAT(maybe_result.status().message(),
629 HasSubstr("zk_quality parameter must be positive."));
630
631 maybe_result =
632 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
633 &ctx_, g_, ctx_.CreateBigNum(20), n_, r_, challenge_length_,
634 zk_quality_);
635 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
636 EXPECT_THAT(maybe_result.status().message(),
637 HasSubstr("h is not relatively prime to n."));
638
639 maybe_result =
640 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
641 &ctx_, ctx_.CreateBigNum(2), h_, n_, r_, challenge_length_,
642 zk_quality_);
643 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
644 EXPECT_THAT(maybe_result.status().message(), HasSubstr("g != h^r mod n."));
645
646 maybe_result =
647 PedersenOverZn::ProveParametersCorrectlyGeneratedForTrustedModulus(
648 &ctx_, g_, h_, n_, ctx_.CreateBigNum(2), challenge_length_,
649 zk_quality_);
650 EXPECT_TRUE(IsInvalidArgument(maybe_result.status()));
651 EXPECT_THAT(maybe_result.status().message(), HasSubstr("g != h^r mod n."));
652 }
653
TEST_F(PedersenOverZnGenProofForTrustedModulusTest,TestProofVerificationFailsOnInvalidInputs)654 TEST_F(PedersenOverZnGenProofForTrustedModulusTest,
655 TestProofVerificationFailsOnInvalidInputs) {
656 Status status;
657 // Proof contains invalid challenge length
658 safe_modulus_proof_->challenge_length = 0;
659 status = PedersenOverZn::VerifyParamsProofForTrustedModulus(
660 &ctx_, g_, h_, n_, *safe_modulus_proof_);
661 EXPECT_TRUE(IsInvalidArgument(status));
662 EXPECT_THAT(status.message(),
663 ::testing::HasSubstr("challenge length must be positive."));
664 safe_modulus_proof_->challenge_length = CHALLENGE_LENGTH;
665
666 // h is not relatively prime to modulus.
667 status = PedersenOverZn::VerifyParamsProofForTrustedModulus(
668 &ctx_, g_, ctx_.CreateBigNum(20), n_, *safe_modulus_proof_);
669 EXPECT_TRUE(IsInvalidArgument(status));
670 EXPECT_THAT(status.message(),
671 ::testing::HasSubstr("h is not relatively prime to n."));
672 }
673
TEST_F(PedersenOverZnGenProofForTrustedModulusTest,TestProofVerificationFailsOnIncorrectProof)674 TEST_F(PedersenOverZnGenProofForTrustedModulusTest,
675 TestProofVerificationFailsOnIncorrectProof) {
676 Status status;
677 // Change g to g+1
678 status = PedersenOverZn::VerifyParamsProofForTrustedModulus(
679 &ctx_, g_ + ctx_.One(), h_, n_, *safe_modulus_proof_);
680 EXPECT_TRUE(IsInvalidArgument(status));
681 EXPECT_THAT(status.message(),
682 ::testing::HasSubstr("the proof verification formula fails."));
683
684 // Change dummy_g
685 safe_modulus_proof_->dummy_g = safe_modulus_proof_->dummy_g + ctx_.One();
686 status = PedersenOverZn::VerifyParamsProofForTrustedModulus(
687 &ctx_, g_, h_, n_, *safe_modulus_proof_);
688 EXPECT_TRUE(IsInvalidArgument(status));
689 EXPECT_THAT(status.message(),
690 ::testing::HasSubstr("the proof verification formula fails."));
691 }
692
693 } // namespace
694 } // namespace private_join_and_compute
695