Range Proof

based on Sigma Protocol

[前置知识]

u-ary representation: $\sigma=\sum_j(\sigma_j u^j)$

based on Boneh-Boyen signature scheme:

to show $\sigma_j\in\{0,1,…,u-1\}$ without revealing its value

  • $x$ is private key, $A_i=g^{\frac{1}{x+i}}$ (for $\forall i\in\{0,1,…,u-1\}$)
  • $V_j=A_{\sigma_j}^{v_j}$
  • $e(V_j,g^x)\overset{\text{?}}{=}e(V_j,g)^{-\sigma_j}\cdot e(g,g)^{v_j}$, ($\Sigma$ protocol format)

Obviously, $e(g,g)^{\frac{x\cdot v_j}{x+\sigma_j}}=e(g,g)^{\frac{-\sigma_j\cdot v_j}{x+\sigma_j}}\cdot e(g,g)^{v_j}$

[正式协议]

Prove $\{(g,h\in\mathbb{G},u,l;\sigma,r\in\mathbb{Z}_p):C=g^\sigma h^r\and \sigma\in[0,u^l]\}$

  • $\mathcal{V}\rightarrow\mathcal{P}:$

    picks random $x\in_R\mathbb{Z}_p$

    sends $y=g^x$ and $A_i=g^{\frac{1}{x+i}}$ (for $\forall i\in\{0,1,…,u-1\}$)

  • $\mathcal{P}\rightarrow\mathcal{V}:$

    picks $v_j\in_R\mathbb{Z}_p$

    sends $V_j=A_{\sigma_j}^{v_j}$ (for $\forall j\in\{0,1,…,l-1\}$)

Turn to Prove $\{(…,v_j):C=h^r\prod_j(g^{u^j})^{\sigma_j}\and V_j=g^{\frac{v_j}{x+\sigma_j}}\}$

($\Sigma$ protocol format)

  • $\mathcal{P}\rightarrow\mathcal{V}:$

    picks $s_j,t_j,m_j\in_R\mathbb{Z}_p$ (for $\forall j\in\{0,1,…,l-1\}$)

    sends $a_j=e(V_j,g)^{-s_j}e(g,g)^{t_j}$ and $D=\prod_j(g^{u^j})^{s_j}h^{m_j}$

  • $\mathcal{V}\rightarrow\mathcal{P}:$

    sends a random challenge $c\in_R\mathbb{Z}_p$

  • $\mathcal{P}\rightarrow\mathcal{V}:$

    sends $z_{\sigma_j}=s_j-\sigma_j c$, $z_{v_j}=t_j-v_j c$, $z_r=m-rc$

  • $\mathcal{V}:$

    checks that

    • $D\overset{\text{?}}{=}C^ch^{z_r}\prod_j(g^{u^j})^{z_{\sigma_j}}$

    • $a_j\overset{\text{?}}{=}e(V_j,y)^c\cdot e(V_j,g)^{-z_{\sigma_j}}\cdot e(g,g)^{z_{v_j}}$

      Obviously, $e(V_j,y)^c=e(V_j,g)^c\cdot e(g,g)^{x}$

image-20230321112444145

任意区间的范围证明转换对于Bullet Proof也同理

[参考文献]

Camenisch, J., Chaabouni, R., shelat, a. (2008). Efficient Protocols for Set Membership and Range Proofs. In: Pieprzyk, J. (eds) Advances in Cryptology - ASIACRYPT 2008. ASIACRYPT 2008. Lecture Notes in Computer Science, vol 5350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89255-7_15

Transform bilinear pairing into Sigma Protocol Format

$\Sigma=\{(w_a,w_b):e(a,b)=e(w_a,cg_2^{w_b})\}$

picks $r\in_{R}\mathbb{Z}_q$，computes $x=c^{r},y=w_ag_1^r,z=rw_b$

等价$\Sigma’=\{(z,w_b):\frac{e(y,c)}{e(a,b)}=\frac{e(g_1,xg_2^z)}{e(y,g_2)^{w_b}}\}$

假设$w_a=g_1^{w_a’},c=g_2^{c’}$，则（双线性对展开系数）有

$(w_a’+r)c’-w_a’(c’+w_b)=(c’r+rw_b)-(w_a’+r)w_b$显然成立

$\Sigma’$ is in Sigma Protocol Format (with $x,y$ public)

[参考文献]

Y. Yu, Y. Zhao, Y. Li, X. Du, L. Wang and M. Guizani, “Blockchain-Based Anonymous Authentication With Selective Revocation for Smart Industrial Applications,” in IEEE Transactions on Industrial Informatics, vol. 16, no. 5, pp. 3290-3300, May 2020, doi: 10.1109/TII.2019.2944678.

(page 5-6)