Proof(ofknowledge)ofexponentiation

1. Proof of exponentiation

Proof of exponentiation是基于adaptive root assumption&＃xff08;充分必要条件&＃xff09;的。


特别适合当$x$很大时&＃xff0c;计算r&＃61;xmodl,urr&＃61;x\ mod\ l,\ u^rr&＃61;x mod l, ur将大量节约verifier直接计算uxu^xux的时间。

借助Fiat-Shamir heuristic&＃xff0c;可将上面的交互式PoE转化为NI-PoE&＃xff1a;

对应在https://github.com/dignifiedquire/rust-accumulators/blob/master/src/proofs.rs中的实现为&＃xff1a;

/// NI-PoE Prove
/// Assumes &＃96;u^x &＃61; w&＃96;
/// All operations are &＃96;mod n&＃96;.
pub fn ni_poe_prove(x: &BigUint, u: &BigUint, w: &BigUint, n: &BigUint) -> ExponentProof {debug_assert!(&u.modpow(x, n) &＃61;&＃61; w, "invalid input");// l <- H_prime(x, u, w)let mut to_hash &＃61; x.to_bytes_be();to_hash.extend(&u.to_bytes_be());to_hash.extend(&w.to_bytes_be());let l &＃61; hash_prime::<_, Blake2b>(&to_hash);// q <- floor(x/l)let q &＃61; x.div_floor(&l);//Prover sends Q <- u^q ∈ G to the Verifier.u.modpow(&q, n)
}/// NI-PoE Verify
/// Assumes &＃96;u^x &＃61; w&＃96;
/// All operations are &＃96;mod n&＃96;.
pub fn ni_poe_verify(x: &BigUint,u: &BigUint,w: &BigUint,q: &ExponentProof,n: &BigUint,
) -> bool {// l <- H_prime(x, u, w)let mut to_hash &＃61; x.to_bytes_be();to_hash.extend(&u.to_bytes_be());to_hash.extend(&w.to_bytes_be());let l &＃61; hash_prime::<_, Blake2b>(&to_hash);// r <- x mod llet r &＃61; x.mod_floor(&l);// Q^l u^r &＃61;&＃61; w&((q.modpow(&l, &n) * &u.modpow(&r, &n)) % n) &＃61;&＃61; w
}// 基于hash值来获取prime数值。
// When the proofs are made non-interactive, using the
// Fiat-Shamir heuristic the challenge is generated by hashing the previous transcript/// Hash the given numbers to a prime number.
/// Currently uses only 128bits.
pub fn hash_prime, D: Digest>(input: &[u8]) -> BigUint {let mut y &＃61; BigUint::from_bytes_be(&D::digest(input)[..16]);while !probably_prime(&y, 20) {y &＃61; BigUint::from_bytes_be(&D::digest(&y.to_bytes_be())[..16]);}y
}


2. Proof of knowledge of exponentiation

2.1 有安全攻击隐患的PoKE

此时&＃xff0c;verifier不需要自己计算余数$r$&＃xff0c;改由prover提供。同时注意&＃xff0c;此时要求discrete logarithm base $g$必须被包含在CRS中$\Rightarrow$ 存在安全攻击问题&＃xff0c;不是secure protocol&＃xff1a;

2.2 基于base $g$和$u$的两次PoKE

对witness $x$的证明&＃xff0c;做了两次PoKE证明&＃xff0c;一次是base $g$&＃xff0c;一次是base $u$。

以上&＃xff0c;proof中包含了两个group元素Q和Q′Q和Q&＃39;Q和Q′。如下&＃xff0c;通过增加一个challenge $\alpha$&＃xff0c;可以将proof中的group元素仍然减为1个$Q$&＃xff1a;

借助Fiat-Shamir heuristic&＃xff0c;可将上面的交互式PoKE2转化为NI-PoKE2&＃xff1a;

对应在https://github.com/dignifiedquire/rust-accumulators/blob/master/src/proofs.rs中的实现为&＃xff1a;

//proof of knowledge of exponent, i.e. a proof that a computationally bounded prover knows the discrete logarithm between two elements in a group of unknown order. The proof is succinct in that the proof size and verification time is independent of the size of the discrete-log./// NI-PoKE2 Prove
/// assumes &＃96;u^x &＃61; w&＃96;
/// All operations are &＃96;mod n&＃96;.
pub fn ni_poke2_prove(x: impl Into,u: &BigUint,w: &BigUint,n: &BigUint,
) -> (BigUint, BigUint, BigInt) {let x: BigInt &＃61; x.into();debug_assert!(&modpow_uint_int(u, &x, n).unwrap() &＃61;&＃61; w, "invalid input");// g <- H_G(u, w)let mut to_hash &＃61; u.to_bytes_be();to_hash.extend(&w.to_bytes_be());let g &＃61; hash_group::<_, Blake2b>(&to_hash, n);// z &＃61; g^xlet z &＃61; modpow_uint_int(&g, &x, n).expect("invalid state");// l <- H_prime(u, w, z)to_hash.extend(&z.to_bytes_be());let l: BigInt &＃61; hash_prime::<_, Blake2b>(&to_hash).into();// alpha &＃61; H(u, w, z, l)to_hash.extend(&l.to_bytes_be().1);let alpha &＃61; BigUint::from_bytes_be(&Blake2b::digest(&to_hash)[..]);// q <- floor(x/l)// r <- x % llet (q, r) &＃61; x.div_rem(&l);// Q <- (ug^alpha)^qlet q_big &＃61; modpow_uint_int(&(u * &g.modpow(&alpha, n)), &q, n).expect("invalid state");(z, q_big, r)
}/// NI-PoKE2 Verify
/// assumes &＃96;u^x &＃61; w&＃96;
/// All operations are &＃96;mod n&＃96;
pub fn ni_poke2_verify(u: &BigUint,w: &BigUint,pi: &(BigUint, BigUint, BigInt),n: &BigUint,
) -> bool {// {z, Q, r} <- pilet (z, q_big, r) &＃61; pi;// g <- H_G(u, w)let mut to_hash &＃61; u.to_bytes_be();to_hash.extend(&w.to_bytes_be());let g &＃61; hash_group::<_, Blake2b>(&to_hash, n);// l <- H_prime(u, w, z)to_hash.extend(&z.to_bytes_be());let l &＃61; hash_prime::<_, Blake2b>(&to_hash);// alpha &＃61; H(u, w, z, l)to_hash.extend(&l.to_bytes_be());let alpha &＃61; BigUint::from_bytes_be(&Blake2b::digest(&to_hash)[..]);// Q^l(ug^alpha)^rlet lhs: BigInt &＃61; ((q_big.modpow(&l, n)* modpow_uint_int(&(u * &g.modpow(&alpha, n)), &r, n).expect("invalid state"))% n).into();// wz^alphalet z_alpha &＃61; z.modpow(&alpha, n);let rhs: BigInt &＃61; ((w * z_alpha) % n).into();lhs &＃61;&＃61; rhs
}

3. Aggreating Knowledge of Co-prime Roots

在第2节中&＃xff0c;已可证明ux&＃61;wu^x&＃61;wux&＃61;w&＃xff0c;若有一系列的co-prime roots x1,...,xnx_1,...,x_nx1​,...,xn​满足wixi&＃61;αiw_i^{x_i}&＃61;\alpha_iwixi​​&＃61;αi​且gcd(xi,xj)&＃61;1∀i,j∈[1,n],i!&＃61;jgcd(x_i,x_j)&＃61;1\forall i,j\in[1,n],i!&＃61;jgcd(xi​,xj​)&＃61;1∀i,j∈[1,n],i!&＃61;j


https://github.com/cambrian/accumulator/中也有相应的代码实现&＃xff0c;且实现的性能要优于https://github.com/dignifiedquire/rust-accumulators/。
&＃96;&＃96;

#[allow(non_snake_case)]
#[derive(PartialEq, Eq, Hash, Clone, Debug)]
/// Struct for NI-PoKCR.
pub struct Pokcr {w: G::Elem,
}impl Pokcr {/// Generates an NI-PoKCR proof.pub fn prove(witnesses: &[G::Elem]) -> Self {Self {w: witnesses.iter().fold(G::id(), |a, b| G::op(&a, b)),}}/// Verifies an NI-PoKCR proof.pub fn verify(alphas: &[G::Elem], x: &[Integer], proof: &Self) -> bool {let y &＃61; multi_exp::(alphas, x);let lhs &＃61; G::exp(&proof.w, &x.iter().product());lhs &＃61;&＃61; y}
}


参考资料&＃xff1a;
[1] 2018年论文《Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains》
[2] 博客密码学中的各种假设——DL/SDH…