Sigma protocol用于one-out-of-many证明

2014年论文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中有提及One out of N commitments containing 0的证明，具体的代码实现可见：https://github.com/3for/libsigma 2015年论文《Short Accountable Ring Signatures Based on DDH》的具体代码实现仍然见：https://github.com/3for/libsigma

1. Commitment to m ∈ { 0 , 1 } m\in\{0,1\} m∈{0,1}

• 2014年论文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中的实现算法为：
• 2015年论文《Short Accountable Ring Signatures Based on DDH》中的实现算法为：【该论文中除了证明了任意的 b j , i ∈ { 0 , 1 } b_{j,i}\in \{0,1\} bj,i​∈{0,1}，还额外证明了每行仅有一个元素为1，每行的总和为】 Prover proof具体的代码实现见：https://github.com/3for/libsigma/blob/master/src/r1_proof_generator.hpp

namespace sigma {



template

R1ProofGenerator::R1ProofGenerator(

        const GroupElement& g,

        const std::vector& h_gens,

        const std::vector& b,

        const Exponent& r,

        int n ,

        int m)

    : g_(g)

    , h_(h_gens)

    , b_(b)

    , r(r)

    , n_(n)

    , m_(m)

{

    SigmaPrimitives::commit(g_, h_, b_, r, B_Commit);

}



template

const GroupElement& R1ProofGenerator::get_B() const {

    return B_Commit;

}



template

void R1ProofGenerator::proof(

        R1Proof& proof_out, bool skip_final_response) {

    std::vector a;

    proof(a, proof_out, skip_final_response);

}



template

void R1ProofGenerator::proof(

        std::vector& a_out,

        R1Proof& proof_out,

        bool skip_final_response) {

    a_out.resize(n_ * m_);

    for(int j = 0; j < m_; ++j) {

        for(int i = 1; i < n_; ++i) {

            a_out[j * n_ + i].randomize();

            a_out[j * n_] -= a_out[j * n_ + i];

        }

    }



    // proof_out.B_ = B_Commit;



    //compute A

    GroupElement A;

    while(!A.isMember() || A.isInfinity()) {

        rA_.randomize();

        SigmaPrimitives::commit(g_, h_, a_out, rA_, A);

    }

    proof_out.A_ = A;



    //compute C

    std::vector c;

    c.resize(n_ * m_);

    for(int i = 0; i < n_ * m_; ++i) {

        c[i] = (a_out[i] * (Exponent(uint64_t(1)) - (Exponent(uint64_t(2)) * b_[i])));

    }

    GroupElement C;

    while(!C.isMember() || C.isInfinity()) {

        rC_.randomize();

        SigmaPrimitives::commit(g_, h_, c, rC_, C);

    }

    proof_out.C_ = C;



    //compute D

    std::vector d;

    d.resize(n_ * m_);

    for(int i = 0; i < n_ * m_; i++) {

        d[i] = ((a_out[i].square()).negate());

    }

    GroupElement D;

    while(!D.isMember() || D.isInfinity()) {

        rD_.randomize();

        SigmaPrimitives::commit(g_, h_, d, rD_, D);

    }

    proof_out.D_ = D;



    if (!skip_final_response) {

        Exponent x;

        std::vector group_elements = {A, B_Commit, C, D};

        SigmaPrimitives::generate_challenge(group_elements, x);

        generate_final_response(a_out, x, proof_out);

    }

}



template

void R1ProofGenerator::generate_final_response(

        const std::vector& a,

        const Exponent& challenge_x,

        R1Proof& proof_out) {

    //f

    proof_out.f_.clear();

    proof_out.f_.reserve(m_ * (n_ - 1));

    for(int j = 0; j < m_; j++) {

        for(int i = 1; i < n_; i++)

        proof_out.f_.emplace_back(b_[(j * n_) + i] * challenge_x + a[(j * n_) + i]);

    }



    //zA

    proof_out.ZA_ = r * challenge_x + rA_;

    proof_out.ZC_ = rC_ * challenge_x + rD_;

}



} //namespace sigma

2. One out of N commitments containing 0

2014年论文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中有： 其中的 C o m c k ( 0 ; ρ k ) Com_{ck}(0; \rho_k) Comck​(0;ρk​)是对0的commit，只是增加了random noise值 ρ k \rho_k ρk​。 convert_to_sigma函数会将 n u m num num转化为mxn bit矩阵，该矩阵内所有元素均 ∈ { 0 , 1 } \in\{0,1\} ∈{0,1}，且每行仅有一个元素为1。

template
	void SigmaPrimitives::convert_to_sigma(
	        uint64_t num,
	        uint64_t n,
	        uint64_t m,
	        std::vector& out) {
	    uint64_t rem;
	    uint64_t j = 0;
	

	    for (j = 0; j < m; ++j)
	    {
	        rem = num % n;
	        num /= n;
	        for (uint64_t i = 0; i < n; ++i) {
	            if(i == rem)
	                out.push_back(Exponent(unsigned(1)));
	            else
	                out.push_back(Exponent(unsigned(0)));
	        }
	    }
	}

3. One out of N commitments containing 1

2015年论文《Short Accountable Ring Signatures Based on DDH》中有： 上图算法需要修订如下错误：

• Prover端有： G k = ∏ i = 0 N − 1 c i p i , k ⋅ E n c c k ( 0 ; ρ k ) G_k=\prod_{i=0}^{N-1}c_i^{p_{i,k}}\cdot Enc_{ck}(0;\rho_k) Gk​=∏i=0N−1​cipi,k​​⋅Encck​(0;ρk​)
• Verifier端有： ∏ i = 0 N − 1 c i ∏ j = 0 m − 1 f j , i j ⋅ ∏ k = 0 m − 1 G k − x k = E n c c k ( x m ; z ) \prod_{i=0}^{N-1}c_i^{\prod_{j=0}^{m-1}f_{j,i_j}}\cdot \prod_{k=0}^{m-1}G_k^{-x^k}=Enc_{ck}(x^m;z) ∏i=0N−1​ci∏j=0m−1​fj,ij​​​⋅∏k=0m−1​Gk−xk​=Encck​(xm;z)

在https://github.com/3for/libsigma/blob/master/tests/protocol_tests.cpp中的one_out_of_n_one测试用例中做了相应实现。

另外，实际代码实现时，为保证所提交的commitment list为n^m个，不足的会按最后一个commitment补齐，此即为one_out_of_n_padding测试用例的用意。

参考资料： [1] 2014年论文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》 [2] 2015年论文《Short Accountable Ring Signatures Based on DDH》