#include #include "base.hpp" extern const scalar_t bn_n; extern const curvepoint_fp_t bn_curvegen; /* These lines need to be here so these static variables are defined, * but in C++ putting code here doesn't actually execute * (or at least, with g++, whenever it would execute is not at a useful time) * so we have an init() function to actually put the correct values in them. */ Curvepoint PrsonaBase::EL_GAMAL_GENERATOR = Curvepoint(); Scalar PrsonaBase::SCALAR_N = Scalar(); Scalar PrsonaBase::DEFAULT_TALLY = Scalar(); Scalar PrsonaBase::DEFAULT_VOTE = Scalar(); bool PrsonaBase::SERVER_IS_MALICIOUS = false; bool PrsonaBase::CLIENT_IS_MALICIOUS = false; size_t PrsonaBase::MAX_ALLOWED_VOTE = 2; // Quick and dirty function to calculate ceil(log base 2) with mpz_class mpz_class log2(mpz_class x) { mpz_class retval = 0; while (x > 0) { retval++; x = x >> 1; } return retval; } mpz_class bit(mpz_class x) { return x > 0 ? 1 : 0; } /******************** * PUBLIC FUNCTIONS * ********************/ /* * SETUP FUNCTIONS */ // Must be called once before any usage of this class void PrsonaBase::init() { EL_GAMAL_GENERATOR = Curvepoint(bn_curvegen); SCALAR_N = Scalar(bn_n); DEFAULT_TALLY = Scalar(1); DEFAULT_VOTE = Scalar(1); } // Call this (once) if using malicious-security servers void PrsonaBase::set_server_malicious() { SERVER_IS_MALICIOUS = true; } // Call this (once) if using malicious-security clients void PrsonaBase::set_client_malicious() { CLIENT_IS_MALICIOUS = true; } /* * CONST GETTERS */ size_t PrsonaBase::get_max_allowed_vote() { return MAX_ALLOWED_VOTE; } Curvepoint PrsonaBase::get_blinding_generator() const { return elGamalBlindGenerator; } Curvepoint PrsonaBase::get_blinding_generator(std::vector& pi) const { pi = elGamalBlindGeneratorProof; return elGamalBlindGenerator; } /*********************** * PROTECTED FUNCTIONS * ***********************/ /* * PRIVATE ELEMENT SETTER */ bool PrsonaBase::set_EG_blind_generator( const std::vector& pi, const Curvepoint& currGenerator, size_t numServers) { if (!verify_generator_proof(pi, currGenerator, numServers)) return false; elGamalBlindGeneratorProof = pi; elGamalBlindGenerator = currGenerator; return true; } /* * BINARY SEARCH */ /* Completely normal binary search * There might be a standard function for this in ? * But it returns an iterator, not a size_t, so less useful. */ size_t PrsonaBase::binary_search( const std::vector list, const Curvepoint& index) const { size_t lo, hi; lo = 0; hi = list.size() - 1; while (lo < hi) { size_t mid = (lo + hi) / 2; if (list[mid] < index) lo = mid + 1; else if (index == list[mid]) return mid; else hi = mid - 1; } return lo; } /* * SCHNORR PROOFS */ Proof PrsonaBase::schnorr_generation( const Curvepoint& generator, const Curvepoint& commitment, const Scalar& log) const { Proof retval; std::stringstream oracleInput; Scalar r; r.set_random(); Curvepoint U = generator * r; oracleInput << generator << commitment << U; Scalar c = oracle(oracleInput.str()); Scalar z = r.curveAdd(c.curveMult(log)); retval.challengeParts.push_back(c); retval.responseParts.push_back(z); return retval; } bool PrsonaBase::schnorr_verification( const Curvepoint& generator, const Curvepoint& commitment, const Scalar& c, const Scalar& z) const { Curvepoint U = generator * z - commitment * c; std::stringstream oracleInput; oracleInput << generator << commitment << U; return c == oracle(oracleInput.str()); } /* * OWNERSHIP PROOFS */ // Prove ownership of the short term public key Proof PrsonaBase::generate_ownership_proof( const Curvepoint& generator, const Curvepoint& commitment, const Scalar& log) const { if (!CLIENT_IS_MALICIOUS) { Proof retval; retval.hbc = "PROOF"; return retval; } return schnorr_generation(generator, commitment, log); } bool PrsonaBase::verify_ownership_proof( const Proof& pi, const Curvepoint& generator, const Curvepoint& commitment) const { if (!CLIENT_IS_MALICIOUS) return pi.hbc == "PROOF"; Scalar c = pi.challengeParts[0]; Scalar z = pi.responseParts[0]; return schnorr_verification(generator, commitment, c, z); } /* * ITERATED SCHNORR PROOFS */ Proof PrsonaBase::add_to_generator_proof( const Curvepoint& currGenerator, const Scalar& seed) const { Proof retval; if (!CLIENT_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } Curvepoint nextGenerator = currGenerator * seed; retval = schnorr_generation(currGenerator, nextGenerator, seed); retval.curvepointUniversals.push_back(currGenerator); return retval; } bool PrsonaBase::verify_generator_proof( const std::vector& pi, const Curvepoint& currGenerator, size_t numServers) const { if (pi.size() != numServers || numServers == 0) return false; bool retval = true; if (!SERVER_IS_MALICIOUS) { for (size_t i = 0; i < pi.size(); i++) retval = retval && pi[i].hbc == "PROOF"; return retval; } if (pi[0].curvepointUniversals[0] != EL_GAMAL_GENERATOR) return false; for (size_t i = 0; i < pi.size(); i++) { Curvepoint generator = pi[i].curvepointUniversals[0]; Curvepoint commitment = (i == pi.size() - 1 ? currGenerator : pi[i + 1].curvepointUniversals[0]); Scalar c = pi[i].challengeParts[0]; Scalar z = pi[i].responseParts[0]; retval = retval && schnorr_verification(generator, commitment, c, z); if (!retval) std::cerr << "Error in index " << i+1 << " of " << pi.size() << std::endl; } return retval; } /* * REPUTATION PROOFS */ // A pretty straightforward range proof (generation) std::vector PrsonaBase::generate_reputation_proof( const Proof& ownershipProof, const EGCiphertext& commitment, const Scalar& currentScore, const Scalar& threshold, const Scalar& inverseKey, size_t numClients) const { std::vector retval; // Base case if (!CLIENT_IS_MALICIOUS) { retval.push_back(Proof("PROOF")); return retval; } // Don't even try if the user asks to make an illegitimate proof if (threshold.toInt() > (numClients * MAX_ALLOWED_VOTE)) return retval; // We really have two consecutive proofs in a junction. // The first is to prove that we are the stpk we claim we are retval.push_back(ownershipProof); // The value we're actually using in our proof mpz_class proofVal = currentScore.curveSub(threshold).toInt(); // Top of the range in our proof determined by what scores are even possible mpz_class proofBits = log2(numClients * MAX_ALLOWED_VOTE - threshold.toInt()); // Don't risk a situation that would divulge our private key if (proofBits <= 1) proofBits = 2; // This seems weird, but remember our base is A_t^r, not g^t std::vector masksPerBit; masksPerBit.push_back(inverseKey); for (size_t i = 1; i < proofBits; i++) { Scalar currMask; currMask.set_random(); masksPerBit.push_back(currMask); masksPerBit[0] = masksPerBit[0].curveSub(currMask.curveMult(Scalar(1 << i))); } // Taken from Fig. 1 in https://eprint.iacr.org/2014/764.pdf for (size_t i = 0; i < proofBits; i++) { Proof currProof; Curvepoint g, h, c, c_a, c_b; g = commitment.mask; h = elGamalBlindGenerator; mpz_class currBit = bit(proofVal & (1 << i)); Scalar a, s, t, m, r; a.set_random(); s.set_random(); t.set_random(); m = Scalar(currBit); r = masksPerBit[i]; c = g * r + h * m; currProof.curvepointUniversals.push_back(c); c_a = g * s + h * a; Scalar am = a.curveMult(m); c_b = g * t + h * am; std::stringstream oracleInput; oracleInput << g << h << c << c_a << c_b; Scalar x = oracle(oracleInput.str()); currProof.challengeParts.push_back(x); Scalar f, z_a, z_b; Scalar mx = m.curveMult(x); f = mx.curveAdd(a); Scalar rx = r.curveMult(x); z_a = rx.curveAdd(s); Scalar x_f = x.curveSub(f); Scalar r_x_f = r.curveMult(x_f); z_b = r_x_f.curveAdd(t); currProof.responseParts.push_back(f); currProof.responseParts.push_back(z_a); currProof.responseParts.push_back(z_b); retval.push_back(currProof); } return retval; } // A pretty straightforward range proof (verification) bool PrsonaBase::verify_reputation_proof( const std::vector& pi, const Curvepoint& generator, const Curvepoint& owner, const EGCiphertext& commitment, const Scalar& threshold) const { // Reject outright if there's no proof to check if (pi.empty()) { std::cerr << "Proof was empty, aborting." << std::endl; return false; } // If the range is so big that it wraps around mod n, // there's a chance the user actually made a proof for a very low reputation if (pi.size() > 256) { std::cerr << "Proof was too big, prover could have cheated." << std::endl; return false; } if (!CLIENT_IS_MALICIOUS) return pi[0].hbc == "PROOF"; Scalar ownerChallenge, ownerResponse; ownerChallenge = pi[0].challengeParts[0]; ownerResponse = pi[0].responseParts[0]; // User should be able to prove they are who they say they are if (!schnorr_verification(generator, owner, ownerChallenge, ownerResponse)) { std::cerr << "Schnorr proof failed, aborting." << std::endl; return false; } // X is the thing we're going to be checking in on throughout // to try to get our score commitment back in the end. Curvepoint X; for (size_t i = 1; i < pi.size(); i++) { Curvepoint c, g, h; c = pi[i].curvepointUniversals[0]; g = commitment.mask; h = elGamalBlindGenerator; X = X + c * Scalar(1 << (i - 1)); Scalar x, f, z_a, z_b; x = pi[i].challengeParts[0]; f = pi[i].responseParts[0]; z_a = pi[i].responseParts[1]; z_b = pi[i].responseParts[2]; // Taken from Fig. 1 in https://eprint.iacr.org/2014/764.pdf Curvepoint c_a, c_b; c_a = g * z_a + h * f - c * x; Scalar x_f = x.curveSub(f); c_b = g * z_b - c * x_f; std::stringstream oracleInput; oracleInput << g << h << c << c_a << c_b; if (oracle(oracleInput.str()) != pi[i].challengeParts[0]) { std::cerr << "0 or 1 proof failed at index " << i << " of " << pi.size() - 1 << ", aborting." << std::endl; return false; } } Scalar negThreshold; negThreshold = Scalar(0).curveSub(threshold); Curvepoint scoreCommitment = commitment.encryptedMessage + elGamalBlindGenerator * negThreshold; return X == scoreCommitment; } /* * VALID VOTE PROOFS */ std::vector PrsonaBase::generate_vote_proof( const Proof& ownershipProof, const CurveBipoint& g, const CurveBipoint& h, const std::vector& replaces, const std::vector& oldEncryptedVotes, const std::vector& newEncryptedVotes, const std::vector& seeds, const std::vector& votes) const { std::vector retval; // Base case if (!CLIENT_IS_MALICIOUS) { retval.push_back(Proof("PROOF")); return retval; } // The first need is to prove that we are the stpk we claim we are retval.push_back(ownershipProof); // Then, we iterate over all votes for the proofs that they are correct for (size_t i = 0; i < replaces.size(); i++) { std::stringstream oracleInput; oracleInput << g << h << oldEncryptedVotes[i] << newEncryptedVotes[i]; /* This proof structure is documented in my notes. * It's inspired by the proof in Fig. 1 at * https://eprint.iacr.org/2014/764.pdf, but adapted so that you prove * m(m-1)(m-2) = 0 instead of m(m-1) = 0. * * The rerandomization part is just a slight variation on an * ordinary Schnorr proof, so that part's less scary. */ if (replaces[i]) // CASE: Make new vote { Proof currProof; Scalar c_r, z_r, a, s, t_1, t_2; c_r.set_random(); z_r.set_random(); a.set_random(); s.set_random(); t_1.set_random(); t_2.set_random(); CurveBipoint U = h * z_r + oldEncryptedVotes[i] * c_r - newEncryptedVotes[i] * c_r; CurveBipoint C_a = g * a + h * s; Scalar power = (a.curveAdd(a)).curveMult(votes[i].curveMult(votes[i])); power = power.curveSub((a.curveAdd(a).curveAdd(a)).curveMult(votes[i])); CurveBipoint C_b = g * power + h * t_1; currProof.curveBipointUniversals.push_back(C_b); CurveBipoint C_c = g * a.curveMult(a.curveMult(votes[i])) + h * t_2; oracleInput << U << C_a << C_b << C_c; Scalar c = oracle(oracleInput.str()); Scalar c_n = c.curveSub(c_r); currProof.challengeParts.push_back(c_r); currProof.challengeParts.push_back(c_n); Scalar f = (votes[i].curveMult(c_n)).curveAdd(a); Scalar z_na = (seeds[i].curveMult(c_n)).curveAdd(s); Scalar t_1_c_n_t_2 = (t_1.curveMult(c_n)).curveAdd(t_2); Scalar f_c_n = f.curveSub(c_n); Scalar c_n2_f = c_n.curveAdd(c_n).curveSub(f); Scalar z_nb = (seeds[i].curveMult(f_c_n).curveMult(c_n2_f)).curveAdd( t_1_c_n_t_2); currProof.responseParts.push_back(z_r); currProof.responseParts.push_back(f); currProof.responseParts.push_back(z_na); currProof.responseParts.push_back(z_nb); retval.push_back(currProof); } else // CASE: Rerandomize existing vote { Proof currProof; Scalar u, commitmentLambda_1, commitmentLambda_2, c_n, z_na, z_nb, f; u.set_random(); commitmentLambda_1.set_random(); commitmentLambda_2.set_random(); c_n.set_random(); z_na.set_random(); z_nb.set_random(); f.set_random(); CurveBipoint U = h * u; CurveBipoint C_a = g * f + h * z_na - newEncryptedVotes[i] * c_n; CurveBipoint C_b = g * commitmentLambda_1 + h * commitmentLambda_2; currProof.curveBipointUniversals.push_back(C_b); Scalar f_c_n = f.curveSub(c_n); Scalar c_n2_f = c_n.curveAdd(c_n).curveSub(f); CurveBipoint C_c = h * z_nb - newEncryptedVotes[i] * f_c_n.curveMult(c_n2_f) - C_b * c_n; oracleInput << U << C_a << C_b << C_c; Scalar c = oracle(oracleInput.str()); Scalar c_r = c.curveSub(c_n); currProof.challengeParts.push_back(c_r); currProof.challengeParts.push_back(c_n); Scalar z_r = u.curveAdd(c_r.curveMult(seeds[i])); currProof.responseParts.push_back(z_r); currProof.responseParts.push_back(f); currProof.responseParts.push_back(z_na); currProof.responseParts.push_back(z_nb); retval.push_back(currProof); } } return retval; } bool PrsonaBase::verify_vote_proof( const CurveBipoint& g, const CurveBipoint& h, const std::vector& pi, const std::vector& oldEncryptedVotes, const std::vector& newEncryptedVotes, const Curvepoint& freshGenerator, const Curvepoint& owner) const { // Reject outright if there's no proof to check if (pi.empty()) { std::cerr << "Proof was empty, aborting." << std::endl; return false; } // Base case if (!CLIENT_IS_MALICIOUS) return pi[0].hbc == "PROOF"; // User should be able to prove they are who they say they are if (!verify_ownership_proof(pi[0], freshGenerator, owner)) { std::cerr << "Schnorr proof failed, aborting." << std::endl; return false; } /* This proof structure is documented in my notes. * It's inspired by the proof in Fig. 1 at * https://eprint.iacr.org/2014/764.pdf, but adapted so that you prove * m(m-1)(m-2) = 0 instead of m(m-1) = 0. * * The rerandomization part is just a slight variation on an * ordinary Schnorr proof, so that part's less scary. */ for (size_t i = 1; i < pi.size(); i++) { size_t voteIndex = i - 1; CurveBipoint C_b; C_b = pi[i].curveBipointUniversals[0]; Scalar c_r, c_n, z_r, f, z_na, z_nb; c_r = pi[i].challengeParts[0]; c_n = pi[i].challengeParts[1]; z_r = pi[i].responseParts[0]; f = pi[i].responseParts[1]; z_na = pi[i].responseParts[2]; z_nb = pi[i].responseParts[3]; CurveBipoint U, C_a, C_c; U = h * z_r + oldEncryptedVotes[voteIndex] * c_r - newEncryptedVotes[voteIndex] * c_r; C_a = g * f + h * z_na - newEncryptedVotes[voteIndex] * c_n; Scalar f_c_n = f.curveSub(c_n); Scalar c_n2_f = c_n.curveAdd(c_n).curveSub(f); C_c = h * z_nb - newEncryptedVotes[voteIndex] * f_c_n.curveMult(c_n2_f) - C_b * c_n; std::stringstream oracleInput; oracleInput << g << h << oldEncryptedVotes[voteIndex] << newEncryptedVotes[voteIndex] << U << C_a << C_b << C_c; if (oracle(oracleInput.str()) != c_r.curveAdd(c_n)) return false; } return true; } /* * NEW USER PROOFS */ std::vector PrsonaBase::generate_proof_of_added_user( const Scalar& twistBipointSeed, const Scalar& EGCiphertextSeed, const std::vector& curveBipointSelfSeeds, const std::vector& curveBipointOtherSeeds) const { std::vector retval; if (!SERVER_IS_MALICIOUS) { retval.push_back(Proof("PROOF")); return retval; } Proof currProof; currProof.responseParts.push_back(twistBipointSeed); retval.push_back(currProof); currProof.responseParts.clear(); currProof.responseParts.push_back(EGCiphertextSeed); retval.push_back(currProof); currProof.responseParts.clear(); for (size_t i = 0; i < curveBipointSelfSeeds.size(); i++) currProof.responseParts.push_back(curveBipointSelfSeeds[i]); retval.push_back(currProof); currProof.responseParts.clear(); for (size_t i = 0; i < curveBipointOtherSeeds.size(); i++) currProof.responseParts.push_back(curveBipointOtherSeeds[i]); retval.push_back(currProof); return retval; } bool PrsonaBase::verify_proof_of_added_user( const std::vector& pi, const Curvepoint& currentFreshGenerator, const Curvepoint& shortTermPublicKey, const Curvepoint& elGamalBlindGenerator, const CurveBipoint& curveG, const CurveBipoint& curveH, const TwistBipoint& twistG, const TwistBipoint& twistH, size_t selfIndex, const EGCiphertext& userEncryptedScore, const TwistBipoint& serverEncryptedScore, const std::vector> encryptedVoteMatrix) const { if (pi.empty()) { std::cerr << "Proof empty." << std::endl; return false; } if (!SERVER_IS_MALICIOUS) return pi[0].hbc == "PROOF"; Scalar currSeed = pi[0].responseParts[0]; if (serverEncryptedScore != twistG * DEFAULT_TALLY + twistH * currSeed) { std::cerr << "Issue in server encrypted score." << std::endl; return false; } currSeed = pi[1].responseParts[0]; if (userEncryptedScore.mask != shortTermPublicKey * currSeed) { std::cerr << "Issue in user encrypted score: mask." << std::endl; return false; } if (userEncryptedScore.encryptedMessage != currentFreshGenerator * currSeed + elGamalBlindGenerator * DEFAULT_TALLY) { std::cerr << "Issue in user encrypted score: value." << std::endl; return false; } for (size_t i = 0; i < pi[2].responseParts.size(); i++) { CurveBipoint currVote = encryptedVoteMatrix[selfIndex][i]; currSeed = pi[2].responseParts[i]; if (i == selfIndex) { if (currVote != curveG * Scalar(MAX_ALLOWED_VOTE) + curveH * currSeed) { std::cerr << "Issue in self vote." << std::endl; return false; } } else { if (currVote != curveG * DEFAULT_VOTE + curveH * currSeed) { std::cerr << "Issue in vote by verifier for user " << i + 1 << " of " << pi[2].responseParts.size() << "." << std::endl; return false; } } } for (size_t i = 0; i < pi[3].responseParts.size(); i++) { CurveBipoint currVote = encryptedVoteMatrix[i][selfIndex]; currSeed = pi[3].responseParts[i]; if (i != selfIndex) { if (currVote != curveG * DEFAULT_VOTE + curveH * currSeed) { std::cerr << "Issue in vote for verifier by user " << i + 1 << " of " << pi[3].responseParts.size() << "." << std::endl; return false; } } } return true; } /* * EPOCH PROOFS */ Proof PrsonaBase::generate_proof_of_correct_tally() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_proof_of_correct_sum() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_proof_of_shuffle() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } bool PrsonaBase::verify_update_proof( const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; } /* * SERVER AGREEMENT PROOFS */ Proof PrsonaBase::generate_valid_user_tally_proof() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_valid_server_tally_proof() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_valid_vote_row_proof() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_valid_vote_matrix_proof() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } Proof PrsonaBase::generate_valid_pseudonyms_proof() const { Proof retval; if (!SERVER_IS_MALICIOUS) { retval.hbc = "PROOF"; return retval; } retval.hbc = "PROOF"; return retval; } bool PrsonaBase::verify_valid_user_tally_proof(const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; } bool PrsonaBase::verify_valid_server_tally_proof(const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; } bool PrsonaBase::verify_valid_vote_row_proof(const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; } bool PrsonaBase::verify_valid_vote_matrix_proof(const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; } bool PrsonaBase::verify_valid_pseudonyms_proof(const Proof& pi) const { if (!SERVER_IS_MALICIOUS) return pi.hbc == "PROOF"; return pi.hbc == "PROOF"; }