PRSONA/prsona/src/base.cpp

#include <iostream>

#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<Proof>& pi) const
{
    pi = elGamalBlindGeneratorProof;

    return elGamalBlindGenerator;
}

/***********************
 * PROTECTED FUNCTIONS *
 ***********************/

/*
 * PRIVATE ELEMENT SETTER
 */

bool PrsonaBase::set_EG_blind_generator(
    const std::vector<Proof>& pi,
    const Curvepoint& currGenerator,
    size_t numServers)
{
    if (!verify_generator_proof(pi, currGenerator, numServers))
        return false;

    elGamalBlindGeneratorProof = pi;
    elGamalBlindGenerator = currGenerator;
    return true;
}

/*
 * 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.basic = "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.basic == "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.basic = "PROOF";
        return retval;
    }

    Curvepoint nextGenerator = currGenerator * seed;
    retval = schnorr_generation(currGenerator, nextGenerator, seed);

    retval.partialUniversals.push_back(currGenerator);
    return retval;
}

bool PrsonaBase::verify_generator_proof(
    const std::vector<Proof>& 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].basic == "PROOF";

        return retval;
    }

    if (pi[0].partialUniversals[0] != EL_GAMAL_GENERATOR)
        return false;

    for (size_t i = 0; i < pi.size(); i++)
    {
        Curvepoint generator = pi[i].partialUniversals[0];
        Curvepoint commitment = (i == pi.size() - 1 ?
                                    currGenerator :
                                    pi[i + 1].partialUniversals[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<Proof> 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<Proof> 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<Scalar> 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.partialUniversals.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<Proof>& 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].basic == "PROOF";

    Scalar c, z;
    c = pi[0].challengeParts[0];
    z = pi[0].responseParts[0];

    // User should be able to prove they are who they say they are
    if (!schnorr_verification(generator, owner, c, z))
    {
        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].partialUniversals[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<Proof> PrsonaBase::generate_vote_proof(
    const Proof& ownershipProof,
    const CurveBipoint& g,
    const CurveBipoint& h,
    const std::vector<bool>& replaces,
    const std::vector<CurveBipoint>& oldEncryptedVotes,
    const std::vector<CurveBipoint>& newEncryptedVotes,
    const std::vector<Scalar>& seeds,
    const std::vector<Scalar>& votes) const
{
    std::vector<Proof> 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.partialUniversals.push_back(C_b[0]);
            currProof.partialUniversals.push_back(C_b[1]);

            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.partialUniversals.push_back(C_b[0]);
            currProof.partialUniversals.push_back(C_b[1]);

            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<Proof>& pi,
    const std::vector<CurveBipoint>& oldEncryptedVotes,
    const std::vector<CurveBipoint>& 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].basic == "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;
        Curvepoint C_b_0, C_b_1;
        C_b_0 = pi[i].partialUniversals[0];
        C_b_1 = pi[i].partialUniversals[1];

        CurveBipoint C_b(C_b_0, C_b_1);

        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;
}

/*
 * EPOCH PROOFS
 */

bool PrsonaBase::verify_update_proof(
    const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

/*
 * SERVER AGREEMENT PROOFS
 */

Proof PrsonaBase::generate_valid_default_tally_proof() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_valid_fresh_generator_proof() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_votes_valid_proof() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_proof_of_added_user() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_score_proof() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_proof_of_correct_tally() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_proof_of_correct_sum() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_proof_of_shuffle() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

Proof PrsonaBase::generate_valid_pseudonyms_proof() const
{
    Proof retval;

    if (!SERVER_IS_MALICIOUS)
    {
        retval.basic = "PROOF";
        return retval;
    }

    retval.basic = "PROOF";
    return retval;
}

bool PrsonaBase::verify_valid_tally_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

bool PrsonaBase::verify_score_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

bool PrsonaBase::verify_default_tally_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

bool PrsonaBase::verify_default_votes_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

bool PrsonaBase::verify_valid_votes_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}

bool PrsonaBase::verify_valid_pseudonyms_proof(const Proof& pi) const
{
    if (!SERVER_IS_MALICIOUS)
        return pi.basic == "PROOF";

    return pi.basic == "PROOF";
}