cmz/src/ggm.rs

// Implementation of CMZ14 credentials (GGM version, which is more
// efficient, but makes a stronger security assumption): "Algebraic MACs
// and Keyed-Verification Anonymous Credentials" (Chase, Meiklejohn,
// and Zaverucha, CCS 2014)

// The notation follows that of the paper "Hyphae: Social Secret
// Sharing" (Lovecruft and de Valence, 2017), Section 4.

#![allow(non_snake_case)]
#![allow(non_camel_case_types)]

use sha2::Sha512;

use curve25519_dalek::constants as dalek_constants;
use curve25519_dalek::ristretto::RistrettoPoint;
use curve25519_dalek::ristretto::RistrettoBasepointTable;
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::traits::IsIdentity;

use zkp::CompactProof;
use zkp::ProofError;
use zkp::Transcript;

use lazy_static::lazy_static;

lazy_static! {
    pub static ref CMZ_A: RistrettoPoint =
        RistrettoPoint::hash_from_bytes::<Sha512>(b"CMZ Generator A");
    pub static ref CMZ_B: RistrettoPoint =
        dalek_constants::RISTRETTO_BASEPOINT_POINT;
    pub static ref CMZ_A_TABLE: RistrettoBasepointTable =
        RistrettoBasepointTable::create(&CMZ_A);
    pub static ref CMZ_B_TABLE: RistrettoBasepointTable =
        dalek_constants::RISTRETTO_BASEPOINT_TABLE;
}

#[derive(Clone,Debug)]
pub struct IssuerPrivKey {
    x0tilde: Scalar,
    x: Vec<Scalar>,
}

impl IssuerPrivKey {
    // Create an IssuerPrivKey for credentials with the given number of
    // attributes.
    pub fn new(n: u16) -> IssuerPrivKey {
        let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
        let x0tilde: Scalar = Scalar::random(&mut rng);
        let mut x: Vec<Scalar> = Vec::with_capacity((n+1) as usize);

        // Set x to a vector of n+1 random Scalars
        x.resize_with((n+1) as usize, || { Scalar::random(&mut rng) });

        IssuerPrivKey { x0tilde, x }
    }
}

#[derive(Clone,Debug)]
pub struct IssuerPubKey {
    X: Vec<RistrettoPoint>,
}

impl IssuerPubKey {
    // Create an IssuerPubKey from the corresponding IssuerPrivKey
    pub fn new(privkey: &IssuerPrivKey) -> IssuerPubKey {
        let Atable : &RistrettoBasepointTable = &CMZ_A_TABLE;
        let Btable : &RistrettoBasepointTable = &CMZ_B_TABLE;
        let n_plus_one: usize = privkey.x.len();
        let mut X: Vec<RistrettoPoint> = Vec::with_capacity(n_plus_one);

        // The first element is a special case; it is
        // X[0] = x0tilde*A + x[0]*B
        X.push(&privkey.x0tilde * Atable + &privkey.x[0] * Btable);

        // The other elements (1 through n) are X[i] = x[i]*A
        for i in 1..n_plus_one {
            X.push(&privkey.x[i] * Atable);
        }
        IssuerPubKey { X }
    }
}

#[derive(Debug)]
pub struct Issuer {
    privkey: IssuerPrivKey,
    pub pubkey: IssuerPubKey,
}

define_proof! {
    issue_nonblind_5,
    "Nonblind 5 issuing proof",
    (x0, x0tilde, x1, x2, x3, x4, x5),
    (P, Q, X0, X1, X2, X3, X4, X5, P1, P2, P3, P4, P5),
    (A, B) :
    X1 = (x1*A),
    X2 = (x2*A),
    X3 = (x3*A),
    X4 = (x4*A),
    X5 = (x5*A),
    X0 = (x0*B + x0tilde*A),
    Q = (x0*P + x1*P1 + x2*P2 + x3*P3 + x4*P4 + x5*P5)
}

impl Issuer {
    // Create an issuer for credentials with the given number of
    // attributes
    pub fn new(n: u16) -> Issuer {
        let privkey = IssuerPrivKey::new(n);
        let pubkey = IssuerPubKey::new(&privkey);
        Issuer { privkey, pubkey }
    }

    // Issue a credential with (for example) 5 given attributes.  In
    // this (nonblinded) version, the issuer sees all of the attributes.
    pub fn issue_nonblind_5(&self, req: &CredentialRequest_Nonblind_5)
            -> CredentialResponse_Nonblind_5 {
        let A : &RistrettoPoint = &CMZ_A;
        let B : &RistrettoPoint = &CMZ_B;

        let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
        let b: Scalar = Scalar::random(&mut rng);
        let P: RistrettoPoint = b * B;
        // There is a typo in the Hyphae paper: in Section 4.1, Q should
        // also have an x0*P term (also in Q').  (You can see that term
        // in Section 4.2.)
        let Q: RistrettoPoint = (self.privkey.x[0] + (
            self.privkey.x[1] * req.m1 +
            self.privkey.x[2] * req.m2 +
            self.privkey.x[3] * req.m3 +
            self.privkey.x[4] * req.m4 +
            self.privkey.x[5] * req.m5)) * P;

        let mut transcript = Transcript::new(b"Nonblind 5 issuing proof");
        let pi: CompactProof = issue_nonblind_5::prove_compact(
            &mut transcript,
            issue_nonblind_5::ProveAssignments {
                A: &A,
                B: &B,
                P: &P,
                Q: &Q,
                X0: &self.pubkey.X[0],
                X1: &self.pubkey.X[1],
                X2: &self.pubkey.X[2],
                X3: &self.pubkey.X[3],
                X4: &self.pubkey.X[4],
                X5: &self.pubkey.X[5],
                P1: &(&req.m1 * &P),
                P2: &(&req.m2 * &P),
                P3: &(&req.m3 * &P),
                P4: &(&req.m4 * &P),
                P5: &(&req.m5 * &P),
                x0: &self.privkey.x[0],
                x1: &self.privkey.x[1],
                x2: &self.privkey.x[2],
                x3: &self.privkey.x[3],
                x4: &self.privkey.x[4],
                x5: &self.privkey.x[5],
                x0tilde: &self.privkey.x0tilde
            }).0;

        CredentialResponse_Nonblind_5 { P, Q, pi }
    }
}

#[derive(Debug)]
pub struct CredentialRequest_Nonblind_5 {
    m1: Scalar,
    m2: Scalar,
    m3: Scalar,
    m4: Scalar,
    m5: Scalar,
}

pub struct CredentialResponse_Nonblind_5 {
    P: RistrettoPoint,
    Q: RistrettoPoint,
    pi: CompactProof,
}

// Example of a 5-attribute credential where the issuer sees attributes
// 3 and 5, but attributes 1, 2, and 4 are blinded.
pub struct CredentialRequest_Blind124_5 {
    D: RistrettoPoint,
    Encm1B: (RistrettoPoint, RistrettoPoint),
    Encm2B: (RistrettoPoint, RistrettoPoint),
    m3: Scalar,
    Encm4B: (RistrettoPoint, RistrettoPoint),
    m5: Scalar,
    piUserBlinding: CompactProof,
}

#[derive(Debug)]
pub struct CredentialRequestState_Blind124_5 {
    d: Scalar,
    D: RistrettoPoint,
    Encm1B: (RistrettoPoint, RistrettoPoint),
    Encm2B: (RistrettoPoint, RistrettoPoint),
    Encm4B: (RistrettoPoint, RistrettoPoint),
    m1: Scalar,
    m2: Scalar,
    m3: Scalar,
    m4: Scalar,
    m5: Scalar,
}

pub struct CredentialResponse_Blind124_5 {
    P: RistrettoPoint,
    EncQ: (RistrettoPoint, RistrettoPoint),
    T1: RistrettoPoint,
    T2: RistrettoPoint,
    T4: RistrettoPoint,
    piBlindIssue: CompactProof,
}

#[derive(Debug)]
pub struct Credential_5 {
    P: RistrettoPoint,
    Q: RistrettoPoint,
    m1: Scalar,
    m2: Scalar,
    m3: Scalar,
    m4: Scalar,
    m5: Scalar,
}

pub fn request_nonblind_5(m1: &Scalar, m2: &Scalar, m3: &Scalar,
        m4: &Scalar, m5: &Scalar) -> CredentialRequest_Nonblind_5 {
    // For nonblind requests, just send the attributes in the clear
    CredentialRequest_Nonblind_5 {
        m1: *m1,
        m2: *m2,
        m3: *m3,
        m4: *m4,
        m5: *m5
    }
}

pub fn verify_nonblind_5(req: &CredentialRequest_Nonblind_5,
        resp: CredentialResponse_Nonblind_5, pubkey: &IssuerPubKey)
        -> Result<Credential_5, ProofError> {
    let A : &RistrettoPoint = &CMZ_A;
    let B : &RistrettoPoint = &CMZ_B;

    if resp.P.is_identity() {
        return Err(ProofError::VerificationFailure);
    }
    let mut transcript = Transcript::new(b"Nonblind 5 issuing proof");
    issue_nonblind_5::verify_compact(
        &resp.pi,
        &mut transcript,
        issue_nonblind_5::VerifyAssignments {
            A: &A.compress(),
            B: &B.compress(),
            P: &resp.P.compress(),
            Q: &resp.Q.compress(),
            X0: &pubkey.X[0].compress(),
            X1: &pubkey.X[1].compress(),
            X2: &pubkey.X[2].compress(),
            X3: &pubkey.X[3].compress(),
            X4: &pubkey.X[4].compress(),
            X5: &pubkey.X[5].compress(),
            P1: &(&req.m1 * &resp.P).compress(),
            P2: &(&req.m2 * &resp.P).compress(),
            P3: &(&req.m3 * &resp.P).compress(),
            P4: &(&req.m4 * &resp.P).compress(),
            P5: &(&req.m5 * &resp.P).compress(),
        }
    )?;
    Ok(Credential_5 {
        P: resp.P,
        Q: resp.Q,
        m1: req.m1,
        m2: req.m2,
        m3: req.m3,
        m4: req.m4,
        m5: req.m5,
    })
}

// The client-created proof that the blinded attributes in the request
// to issue a credential are well formed.  If you want the client to
// prove other statements about the blinded attributes (m1, m2, m4 in
// this example), this is where to add them (and in the code that
// creates and verifies this proof of course).
define_proof! {
    userblinding_124_5,
    "Blind124 5 userblind proof",
    (d, e1, e2, e4, m1, m2, m4),
    (Encm1B0, Encm1B1, Encm2B0, Encm2B1, Encm4B0, Encm4B1, D),
    (B) :
    Encm1B0 = (e1*B),
    Encm1B1 = (m1*B + e1*D),
    Encm2B0 = (e2*B),
    Encm2B1 = (m2*B + e2*D),
    Encm4B0 = (e4*B),
    Encm4B1 = (m4*B + e4*D),
    D = (d*B)
}

// The issuer-created proof for the same scenario
define_proof! {
    blindissue_124_5,
    "Blind124 5 issuing proof",
    (x0, x0tilde, x1, x2, x3, x4, x5, s, b, t1, t2, t4),
    (P, EncQ0, EncQ1, X0, X1, X2, X3, X4, X5, P3, P5, T1, T2, T4, D,
        Encm1B0, Encm1B1, Encm2B0, Encm2B1, Encm4B0, Encm4B1),
    (A, B) :
    X1 = (x1*A),
    X2 = (x2*A),
    X3 = (x3*A),
    X4 = (x4*A),
    X5 = (x5*A),
    X0 = (x0*B + x0tilde*A),
    P = (b*B),
    T1 = (b*X1),
    T2 = (b*X2),
    T4 = (b*X4),
    T1 = (t1*A),
    T2 = (t2*A),
    T4 = (t4*A),
    EncQ0 = (s*B + t1*Encm1B0 + t2*Encm2B0 + t4*Encm4B0),
    EncQ1 = (s*D + t1*Encm1B1 + t2*Encm2B1 + t4*Encm4B1 +
            x0*P + x3*P3 + x5*P5)
}

pub fn request_blind124_5(m1: &Scalar, m2: &Scalar, m3: &Scalar,
        m4: &Scalar, m5: &Scalar) -> (CredentialRequest_Blind124_5,
        CredentialRequestState_Blind124_5) {
    let B : &RistrettoPoint = &CMZ_B;
    let Btable : &RistrettoBasepointTable = &CMZ_B_TABLE;

    // Pick an ElGamal keypair
    let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
    let d: Scalar = Scalar::random(&mut rng);
    let D: RistrettoPoint = &d * Btable;

    let e1: Scalar = Scalar::random(&mut rng);
    let e2: Scalar = Scalar::random(&mut rng);
    let e4: Scalar = Scalar::random(&mut rng);
    let Encm1B = (&e1 * Btable, m1 * Btable + &e1 * D);
    let Encm2B = (&e2 * Btable, m2 * Btable + &e2 * D);
    let Encm4B = (&e4 * Btable, m4 * Btable + &e4 * D);

    let mut transcript = Transcript::new(b"Blind124 5 userblind proof");
    let piUserBlinding: CompactProof = userblinding_124_5::prove_compact(
        &mut transcript,
        userblinding_124_5::ProveAssignments {
            B: &B,
            Encm1B0: &Encm1B.0,
            Encm1B1: &Encm1B.1,
            Encm2B0: &Encm2B.0,
            Encm2B1: &Encm2B.1,
            Encm4B0: &Encm4B.0,
            Encm4B1: &Encm4B.1,
            D: &D,
            d: &d,
            e1: &e1,
            e2: &e2,
            e4: &e4,
            m1: &m1,
            m2: &m2,
            m4: &m4,
        }).0;
    (
        CredentialRequest_Blind124_5 {
            D: D,
            Encm1B, Encm2B, Encm4B, piUserBlinding,
            m3: *m3,
            m5: *m5,
        },
        CredentialRequestState_Blind124_5 {
            d, D, Encm1B, Encm2B, Encm4B,
            m1: *m1,
            m2: *m2,
            m3: *m3,
            m4: *m4,
            m5: *m5,
        }
    )
}

impl Issuer {
    // Issue a credential with 5 attributes, of which attributes 1, 2,
    // and 4 are blinded from the issuer, and 3 and 5 are visible.
    pub fn issue_blind124_5(&self, req: &CredentialRequest_Blind124_5)
            -> Result<CredentialResponse_Blind124_5, ProofError> {
        let A : &RistrettoPoint = &CMZ_A;
        let B : &RistrettoPoint = &CMZ_B;

        // First check the proof in the request
        let mut transcript = Transcript::new(b"Blind124 5 userblind proof");
        userblinding_124_5::verify_compact(
            &req.piUserBlinding,
            &mut transcript,
            userblinding_124_5::VerifyAssignments {
                B: &B.compress(),
                Encm1B0: &req.Encm1B.0.compress(),
                Encm1B1: &req.Encm1B.1.compress(),
                Encm2B0: &req.Encm2B.0.compress(),
                Encm2B1: &req.Encm2B.1.compress(),
                Encm4B0: &req.Encm4B.0.compress(),
                Encm4B1: &req.Encm4B.1.compress(),
                D: &req.D.compress(),
            }
        )?;

        // Compute the MAC on the visible attributes
        let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
        let b: Scalar = Scalar::random(&mut rng);
        let P: RistrettoPoint = b * B;
        let QHc: RistrettoPoint = (self.privkey.x[0] + (
            self.privkey.x[3] * req.m3 +
            self.privkey.x[5] * req.m5)) * P;

        // El Gamal encrypt it to the public key req.D
        let s: Scalar = Scalar::random(&mut rng);
        let EncQHc = (s*B, QHc + s*req.D);

        // Homomorphically compute the part of the MAC corresponding to
        // the blinded attributes
        let t1 = self.privkey.x[1] * b;
        let T1 = t1 * A;
        let EncQ1 = ( t1 * req.Encm1B.0, t1 * req.Encm1B.1 );
        let t2 = self.privkey.x[2] * b;
        let T2 = t2 * A;
        let EncQ2 = ( t2 * req.Encm2B.0, t2 * req.Encm2B.1 );
        let t4 = self.privkey.x[4] * b;
        let T4 = t4 * A;
        let EncQ4 = ( t4 * req.Encm4B.0, t4 * req.Encm4B.1 );

        let EncQ = ( EncQHc.0 + EncQ1.0 + EncQ2.0 + EncQ4.0,
                     EncQHc.1 + EncQ1.1 + EncQ2.1 + EncQ4.1 );

        let mut transcript = Transcript::new(b"Blind124 5 issuing proof");
        let piBlindIssue: CompactProof = blindissue_124_5::prove_compact(
            &mut transcript,
            blindissue_124_5::ProveAssignments {
                A: &A,
                B: &B,
                P: &P,
                EncQ0: &EncQ.0,
                EncQ1: &EncQ.1,
                X0: &self.pubkey.X[0],
                X1: &self.pubkey.X[1],
                X2: &self.pubkey.X[2],
                X3: &self.pubkey.X[3],
                X4: &self.pubkey.X[4],
                X5: &self.pubkey.X[5],
                P3: &(&req.m3 * &P),
                P5: &(&req.m5 * &P),
                T1: &T1,
                T2: &T2,
                T4: &T4,
                D: &req.D,
                Encm1B0: &req.Encm1B.0,
                Encm1B1: &req.Encm1B.1,
                Encm2B0: &req.Encm2B.0,
                Encm2B1: &req.Encm2B.1,
                Encm4B0: &req.Encm4B.0,
                Encm4B1: &req.Encm4B.1,
                x0: &self.privkey.x[0],
                x0tilde: &self.privkey.x0tilde,
                x1: &self.privkey.x[1],
                x2: &self.privkey.x[2],
                x3: &self.privkey.x[3],
                x4: &self.privkey.x[4],
                x5: &self.privkey.x[5],
                s: &s,
                b: &b,
                t1: &t1,
                t2: &t2,
                t4: &t4
            }).0;

        Ok(CredentialResponse_Blind124_5 {
            P, EncQ, T1, T2, T4, piBlindIssue
        })
    }
}

pub fn verify_blind124_5(state: CredentialRequestState_Blind124_5,
        resp: CredentialResponse_Blind124_5, pubkey: &IssuerPubKey)
        -> Result<Credential_5, ProofError> {
    let A : &RistrettoPoint = &CMZ_A;
    let B : &RistrettoPoint = &CMZ_B;

    if resp.P.is_identity() {
        return Err(ProofError::VerificationFailure);
    }

    let mut transcript = Transcript::new(b"Blind124 5 issuing proof");
    blindissue_124_5::verify_compact(
        &resp.piBlindIssue,
        &mut transcript,
        blindissue_124_5::VerifyAssignments {
            A: &A.compress(),
            B: &B.compress(),
            P: &resp.P.compress(),
            EncQ0: &resp.EncQ.0.compress(),
            EncQ1: &resp.EncQ.1.compress(),
            X0: &pubkey.X[0].compress(),
            X1: &pubkey.X[1].compress(),
            X2: &pubkey.X[2].compress(),
            X3: &pubkey.X[3].compress(),
            X4: &pubkey.X[4].compress(),
            X5: &pubkey.X[5].compress(),
            P3: &(&state.m3 * &resp.P).compress(),
            P5: &(&state.m5 * &resp.P).compress(),
            T1: &resp.T1.compress(),
            T2: &resp.T2.compress(),
            T4: &resp.T4.compress(),
            D: &state.D.compress(),
            Encm1B0: &state.Encm1B.0.compress(),
            Encm1B1: &state.Encm1B.1.compress(),
            Encm2B0: &state.Encm2B.0.compress(),
            Encm2B1: &state.Encm2B.1.compress(),
            Encm4B0: &state.Encm4B.0.compress(),
            Encm4B1: &state.Encm4B.1.compress(),
        }
    )?;

    // Decrypt EncQ
    let Q = &resp.EncQ.1 - (state.d * &resp.EncQ.0);

    Ok(Credential_5 {
        P: resp.P,
        Q: Q,
        m1: state.m1,
        m2: state.m2,
        m3: state.m3,
        m4: state.m4,
        m5: state.m5,
    })
}