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 // Implementation of simultaneous fixed bases exponentation. 17 // 18 // As input, we receive a set of fixed bases b1, ..., bn. On each input of 19 // exponents e1, ..., en, we want to compute b1^e1 * ... * bn^en. This problem 20 // is commonly referred to as the simultaneous exponentiation problem. 21 // 22 // Our algorithm uses Straus's algorithm. See [1] for a full description. 23 // 24 // For any set of fixed bases, Straus's algorithm performs a precomputation 25 // based on the b1, ..., bn. The precomputation may be used multiple times 26 // for each many sets of exponents. 27 // 28 // [1] https://cr.yp.to/papers/pippenger.pdf 29 30 #ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_SIMULTANEOUS_FIXED_BASES_H_ 31 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_SIMULTANEOUS_FIXED_BASES_H_ 32 33 #include <cstddef> 34 #include <memory> 35 #include <vector> 36 37 #include "private_join_and_compute/crypto/big_num.h" 38 #include "private_join_and_compute/crypto/ec_point.h" 39 #include "private_join_and_compute/util/status.inc" 40 41 namespace private_join_and_compute { 42 43 // Template type definitions for elements of the multiplicative group mod n. 44 using ZnElement = BigNum; 45 struct ZnContext { 46 private_join_and_compute::BigNum modulus; 47 }; 48 49 template <typename Element, typename Context> 50 class SimultaneousFixedBasesExp { 51 public: 52 // Constructs an object that will return the product of several 53 // exponentiations with respect to b1, ..., bn specified in bases. 54 // 55 // The bases vector represents the bases b1, ..., bn, which will be used for 56 // simultaneous exponentiation. For each instantiation, the Mul, IsZero and 57 // Clone operations need to be specified. 58 // 59 // The "zero" parameter should be a multiplicative identity for the 60 // underlying group (e.g. what you could get if you exponentiate any of the 61 // bases to 0). 62 // 63 // The num_simultaneous parameter determines amount of precomputation 64 // that will be performed. The precomputed table will require 65 // O(2^num_simultaneous * bases / num_simultaneous) elliptic curve additions 66 // to construct. As a result, simultaneous exponents for any set of exponents 67 // only O((bases * max_bit_length) / num_simultaneous) elliptic curve 68 // additions are required to compute the simultaneous exponentiation where 69 // max_bit_length is the maximum bit length of any exponent. The parameter 70 // num_simultaneous may be independent of the number of bases. However, the 71 // total precomputation is capped at 2^{number of bases}. 72 // 73 // Returns INVALID_ARGUMENT if num_simultaneous is larger than the number of 74 // bases. 75 static StatusOr<std::unique_ptr<SimultaneousFixedBasesExp>> Create( 76 const std::vector<Element>& bases, const Element& zero, 77 size_t num_simultaneous, std::unique_ptr<Context> context); 78 79 // SimultaneousFixedBasesExp is not copyable. 80 SimultaneousFixedBasesExp(const SimultaneousFixedBasesExp&) = delete; 81 SimultaneousFixedBasesExp& operator=(const SimultaneousFixedBasesExp&) = 82 delete; 83 84 // Computes the product of b1^e1, ..., bn^en where b1, ..., bn are specified 85 // in the Create function and e1, ..., en are arguments to SimultaneousExp. 86 // 87 // Returns INVALID_ARGUMENT if number of exponents is different than the 88 // number of bases. 89 StatusOr<Element> SimultaneousExp( 90 const std::vector<private_join_and_compute::BigNum>& exponents) const; 91 92 private: 93 SimultaneousFixedBasesExp( 94 size_t num_bases, size_t num_simultaneous, size_t num_batches, 95 std::unique_ptr<Element> zero, std::unique_ptr<Context> context, 96 std::vector<std::vector<std::unique_ptr<Element>>> table); 97 98 // Precomputes a table. Splits bases into groups of num_simultaneous. The last 99 // group may be smaller and contain all leftovers. For each group consisting 100 // of bases b1, ..., bk, we precompute c1b1 + c2b2 + ... + ckbk over all 2^k 101 // possible values of (c1, ..., ck) in {0, 1}^k. 102 static StatusOr<std::vector<std::vector<std::unique_ptr<Element>>>> 103 Precompute(const std::vector<Element>& bases, const Element& zero, 104 const Context& context, size_t num_simultaneous, 105 size_t num_batches); 106 107 const size_t num_bases_; 108 const size_t num_simultaneous_; 109 const size_t num_batches_; 110 const std::unique_ptr<Element> zero_; 111 const std::unique_ptr<Context> context_; 112 113 const std::vector<std::vector<std::unique_ptr<Element>>> precomputed_table_; 114 }; 115 116 } // namespace private_join_and_compute 117 118 #endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_SIMULTANEOUS_FIXED_BASES_H_ 119