1 /* 2 * Copyright 2018 Google LLC 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef FCP_SECAGG_SHARED_SHAMIR_SECRET_SHARING_H_ 18 #define FCP_SECAGG_SHARED_SHAMIR_SECRET_SHARING_H_ 19 20 #include <cstdint> 21 #include <string> 22 #include <vector> 23 24 #include "absl/status/statusor.h" 25 #include "fcp/secagg/shared/key.h" 26 27 namespace fcp { 28 namespace secagg { 29 30 // A ShamirShare represents one share of a shared secret, stored as binary data. 31 typedef struct ShamirShare { 32 std::string data; 33 } ShamirShare; 34 35 // This class encapsulates all of the logic needed to perform t-of-n Shamir 36 // Secret Sharing on arbitrary-size secrets. For efficiency, the secrets are 37 // subdivided into 31-bit chunks called "subsecrets" - this allows us to use 38 // native unsigned 64-bit integer multiplication without worrying about 39 // overflow. This should be invisible to users of this class, as one ShamirShare 40 // still holds one user's share of the secret, represented as one share of each 41 // subsecret. 42 // 43 // This class is not thread-safe. 44 45 class ShamirSecretSharing { 46 public: 47 // This is the smallest 32-bit prime, 2^31+11. Everything this class does is 48 // modulo kPrime. We need all values to be no more than 32 bits, so that we 49 // can multiply using native types without overflow. 50 static constexpr uint64_t kPrime = 2147483659L; 51 52 // Constructs the ShamirSecretSharing object. 53 ShamirSecretSharing(); 54 55 // Splits the arbitrary-length value stored in to_share into shares, following 56 // threshold-out-of-num_shares Shamir Secret Sharing. 57 // 58 // The output is a vector such that the i-th element of the vector is the i-th 59 // share of the secret. 60 std::vector<ShamirShare> Share(int threshold, int num_shares, 61 const std::string& to_share); 62 63 // Convenience method to share a key instead of an arbitrary string. Share(int threshold,int num_shares,const Key & to_share)64 inline std::vector<ShamirShare> Share(int threshold, int num_shares, 65 const Key& to_share) { 66 return Share(threshold, num_shares, to_share.AsString()); 67 } 68 69 // Reconstructs a secret, based on a vector of shares. The vector is 70 // interpreted such that the i-th element of the vector is the i-th share. If 71 // the i-th element of the vector is set to the default ShamirShare (an empty 72 // string), that share is considered not to be present. 73 // 74 // secret_length should be set to the expected length of the reconstructed 75 // secret, in bytes. 76 // 77 // At least threshold of the shares must be set to non-empty strings, or this 78 // operation will fail. 79 // 80 // Reconstruct is most efficient when consecutive calls to this method use 81 // shares with the same indices, because this allows for caching of 82 // intermediate values that depend only on the x-value of the Shamir shares. 83 absl::StatusOr<std::string> Reconstruct( 84 int threshold, const std::vector<ShamirShare>& shares, int secret_length); 85 86 private: 87 // Returns the modular inverse of n mod kPrime, getting the value from a cache 88 // if possible. If not, extends the cache to contain modular inverses from 89 // integers from 1 to n. 90 // 91 // Fails if n is not between 1 and kPrime-1, inclusive. 92 // 93 // For most efficiency, call this method using the largest value of n that 94 // will be needed before calling Reconstruct. 95 uint32_t ModInverse(uint32_t n); 96 97 // Returns the Lagrange coefficients needed to reconstruct secrets for this 98 // exact set of shares. The Lagrange coefficient for the i-th value is 99 // the product, for all j != i, of x_values[j] / (x_values[j] - x_values[i]). 100 // 101 // If this method is called twice in a row on the same input, the output is 102 // returned from cache instead of being recomputed. 103 std::vector<uint32_t> LagrangeCoefficients(const std::vector<int>& x_values); 104 105 // Divides a secret into subsecrets. This takes place when Share is called, 106 // before any further secret sharing work. 107 std::vector<uint32_t> DivideIntoSubsecrets(const std::string& to_share); 108 109 // Rebuilds a secret from subsecrets. This takes place at the end of 110 // the Reconstruct operation, after all the secret reconstruction is already 111 // finished. 112 std::string RebuildFromSubsecrets(const std::vector<uint32_t>& secret_parts, 113 int secret_length); 114 115 // We will split our secret into sub-secrets of no more than 31 bits each. 116 // This allows us to multiply two field elements using only native types. 117 static constexpr int kBitsPerSubsecret = 31; 118 119 // Returns a pseudorandom number uniformly between 0 and kPrime-1. 120 uint32_t RandomFieldElement(); 121 122 // Returns the evaluation of x on the specified polynomial. 123 // polynomial[i] is the i-degree coefficient of the polynomial. 124 uint32_t EvaluatePolynomial(const std::vector<uint32_t>& polynomial, 125 uint32_t x) const; 126 127 // Caches previously computed modular inverses. 128 // inverses_[i] = (i+1)^-1 mod kPrime 129 std::vector<uint32_t> inverses_; 130 131 // Store a copy of the last input/output from LagrangeCoefficients. 132 std::vector<int> last_lc_input_; 133 std::vector<uint32_t> last_lc_output_; 134 }; 135 136 } // namespace secagg 137 } // namespace fcp 138 139 #endif // FCP_SECAGG_SHARED_SHAMIR_SECRET_SHARING_H_ 140