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_BB_OBLIVIOUS_SIGNATURE_H_ 17 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_DODIS_YAMPOLSKIY_PRF_BB_OBLIVIOUS_SIGNATURE_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/camenisch_shoup.h" 30 #include "private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.pb.h" 31 #include "private_join_and_compute/crypto/ec_point.h" 32 #include "private_join_and_compute/crypto/pedersen_over_zn.h" 33 34 namespace private_join_and_compute { 35 36 // Implements an oblivious signing protocol for the Boneh-Boyen signature [1] 37 // with private-key-verification. The Boneh-Boyen scheme is defined over a group 38 // where the q-SDHI assumption holds. Let g be a generator for this group. Then 39 // the signing/verification key consists of a pair (k,y), each consisting of 40 // secret exponents in the group. A signature is provided on a pair (m,r) where 41 // m is a message and r is a nonce. The signature has the form g^1/(m + k + yr). 42 // As discussed in [1], this signature is unforgeable as long as r is chosen at 43 // random. 44 // 45 // We implement an oblivious evaluation protocol for this signature on committed 46 // m and r. We also support batched signature issuance. 47 // 48 // To compute it obliviously, the server generates keys k and y, and encrypts 49 // them using a variant of the Camenisch-Shoup encryption scheme to get ct_k. 50 // When the receiver wants the signature evaluated on (m,r), the receiver 51 // homomorphically computes ct_(masked_(m+k+yr)) from ct_k and ct_y, and proves 52 // that ct_(masked_(m+k+yr)) was correctly generated with appropriately chosen 53 // masks. The server decrypts this ciphertext and computes 54 // g^(1/masked_(m+k+yr)), sending this back to the receiver with a proof that it 55 // was computed correctly. The client unmasks this value to recover the 56 // signature, namely g^1/(m + k + yr). 57 // 58 // The concrete masking is masked_(m+k+yr) = (m+k+yr)*a + b*q, where a and b are 59 // two random numbers of particular bitlengths, and where q is the order of g. 60 // The proofs sent by the sender and receiver are each sigma protocols that can 61 // be made non-interactive using the Fiat-Shamir heuristic. 62 // 63 // Note that this library has an important caveat: it does not enforce that r is 64 // generated randomly by the signature receiver. It is up to the user of this 65 // library to ensure that the enclosing context guarantees that r is randomly 66 // generated. 67 // 68 // [1] "Short Signatures Without Random Oracles", Boneh D., Boyen X. 69 // https://ai.stanford.edu/~xb/eurocrypt04a/bbsigs.pdf 70 class BbObliviousSignature { 71 public: 72 // Creates an object for producing Boneh-Boyen signatures. Fails if the 73 // provided pointers are nullptr, or if the Pedersen commitment scheme is 74 // inconsistent with the Camenisch-Shoup encryption scheme. The max number 75 // of messages in a batch will be the Pedersen Batch size. 76 static StatusOr<std::unique_ptr<BbObliviousSignature>> Create( 77 proto::BbObliviousSignatureParameters parameters_proto, Context* ctx, 78 ECGroup* ec_group, PublicCamenischShoup* public_camenisch_shoup, 79 PedersenOverZn* pedersen); 80 81 // Generates a new key pair for this BB Oblivious Signature scheme. The 82 // modulus n for Camenisch Shoup will be pulled from the parameters. 83 // 84 StatusOr<std::tuple<proto::BbObliviousSignaturePublicKey, 85 proto::BbObliviousSignaturePrivateKey>> 86 GenerateKeys(); 87 88 // Generates an oblivious signature request on a batch of messages. An 89 // important security caveat is that each r should be collaboratively 90 // generated or generated honestly somehow by the enclosing protocol. 91 StatusOr<std::tuple<proto::BbObliviousSignatureRequest, 92 proto::BbObliviousSignatureRequestProof, 93 proto::BbObliviousSignatureRequestPrivateState>> 94 GenerateRequestAndProof( 95 const std::vector<BigNum>& messages, const std::vector<BigNum>& rs, 96 const proto::BbObliviousSignaturePublicKey& public_key, 97 const PedersenOverZn::CommitmentAndOpening& commit_and_open_messages, 98 const PedersenOverZn::CommitmentAndOpening& commit_and_open_rs); 99 100 // Verifies a signature request and proof. 101 Status VerifyRequest( 102 const proto::BbObliviousSignaturePublicKey& public_key, 103 const proto::BbObliviousSignatureRequest& request, 104 const proto::BbObliviousSignatureRequestProof& request_proof, 105 const PedersenOverZn::Commitment& commit_messages, 106 const PedersenOverZn::Commitment& commit_rs); 107 108 // Generates an BB Oblivious Signature Response and proof. 109 StatusOr<std::tuple<proto::BbObliviousSignatureResponse, 110 proto::BbObliviousSignatureResponseProof>> 111 GenerateResponseAndProof( 112 const proto::BbObliviousSignatureRequest& request, 113 const proto::BbObliviousSignaturePublicKey& public_key, 114 const proto::BbObliviousSignaturePrivateKey& private_key, 115 const PedersenOverZn::Commitment& commit_messages, 116 const PedersenOverZn::Commitment& commit_rs, 117 PrivateCamenischShoup* private_camenisch_shoup); 118 119 Status VerifyResponse( 120 const proto::BbObliviousSignaturePublicKey& public_key, 121 const proto::BbObliviousSignatureResponse& response, 122 const proto::BbObliviousSignatureResponseProof& response_proof, 123 const proto::BbObliviousSignatureRequest& request, 124 const PedersenOverZn::Commitment& commit_messages, 125 const PedersenOverZn::Commitment& commit_rs); 126 127 // Extracts the signatures values. Assumes the response proof has already been 128 // verified. Each response is a signature on corresponding (m, r) committed by 129 // the requester. 130 StatusOr<std::vector<ECPoint>> ExtractResults( 131 const proto::BbObliviousSignatureResponse& response, 132 const proto::BbObliviousSignatureRequest& request, 133 const proto::BbObliviousSignatureRequestPrivateState& request_state); 134 135 private: BbObliviousSignature(proto::BbObliviousSignatureParameters parameters_proto,Context * ctx,ECGroup * ec_group,ECPoint base_g,PublicCamenischShoup * public_camenisch_shoup,PedersenOverZn * pedersen)136 BbObliviousSignature(proto::BbObliviousSignatureParameters parameters_proto, 137 Context* ctx, ECGroup* ec_group, ECPoint base_g, 138 PublicCamenischShoup* public_camenisch_shoup, 139 PedersenOverZn* pedersen) 140 : parameters_proto_(std::move(parameters_proto)), 141 ctx_(ctx), 142 ec_group_(ec_group), 143 base_g_(std::move(base_g)), 144 public_camenisch_shoup_(public_camenisch_shoup), 145 pedersen_(pedersen) {} 146 147 // Generates the challenge for the Request proof using the Fiat-Shamir 148 // heuristic. 149 StatusOr<BigNum> GenerateRequestProofChallenge( 150 const proto::BbObliviousSignatureRequestProof::Statement& proof_statement, 151 const proto::BbObliviousSignatureRequestProof::Message1& proof_message_1); 152 153 // Generates the challenge for the Response proof using the Fiat-Shamir 154 // heuristic. 155 StatusOr<BigNum> GenerateResponseProofChallenge( 156 const proto::BbObliviousSignaturePublicKey& public_key, 157 const PedersenOverZn::Commitment& commit_messages, 158 const PedersenOverZn::Commitment& commit_rs, 159 const proto::BbObliviousSignatureRequest& request, 160 const proto::BbObliviousSignatureResponse& response, 161 const PedersenOverZn::Commitment& commit_betas, 162 const proto::BbObliviousSignatureResponseProof::Message1& 163 proof_message_1); 164 165 proto::BbObliviousSignatureParameters parameters_proto_; 166 Context* ctx_; 167 ECGroup* ec_group_; 168 ECPoint base_g_; 169 PublicCamenischShoup* public_camenisch_shoup_; 170 PedersenOverZn* pedersen_; 171 }; 172 173 } // namespace private_join_and_compute 174 175 #endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_DODIS_YAMPOLSKIY_PRF_BB_OBLIVIOUS_SIGNATURE_H_ 176