Ring based signature.

Bilinear Mapping

就是个映射e(,){e(\cdot, \cdot)}, 对每个参数均为线性, e.g.Matrix multiplication, 用于测试 subset 的 membership 问题.

Symmetric type

Premise

  • G{\mathbb{G}} and GT{\mathbb{G_T}} are both cyclic multiplicative group with same order p{p}.(模 p 循环乘法群)
  • gG{g \leftarrow \mathbb{G}} g 为 G 的生成元(generator)

Thus,

bilinear pairing defined as e{e}

G×GGT with bilinearity,computability and nondegeneracy\mathbb{G} \times \mathbb{G} \to \mathbb{G_T} \ \textnormal{with} \ bilinearity, computability \ \textnormal{and} \ non-degeneracy

create accumulation value,

acc(L)=gaiL(ai+s){acc(L) = g^{\prod_{a_i \in L}(a_i +s)}}

  • L: {a1,a2,,an}Zp{\{a1,a2,\dots,an\} \leftarrow \mathbb{Z_p^*}}
  • s: randomly chose sZp{s \leftarrow \mathbb{Z_p^*}}

For any subset LL{L' \subseteq L},
get a witness: WitL,L=aiLL(ai+s){Wit_{L',L} = \prod_{a_i \in L-L'} (a_i + s)}

subset test by checking:

e(gaiL(ai+s),WitL,L)=?e(acc(L),g)e(g^{\prod_{a_i \in L'} (a_i + s)}, Wit_{L', L}) \xlongequal{?} e(acc(L), g)

More

参考 淺談 RSA Accumulator 與 Stateless Client @Anton Cheng