ML-GS: Module Lattice-Based Group Signature Scheme

Figures & Tables

Notations	Description
ZqnZ_q^n	n-dimensional vector over modulo q
Zqn×mZ_q^{n \times m}	n × m matrix over modulo q
R	polynomial Z[[x] / (x^d + 1)
R_q	quotient ring Z[_q[x] / (x^d + 1)
x ← D	x is sampled from the distribution D
∥a∥	∑ ai2\sqrt {\sum {a_i^2} }
∥a∥_∞	maxj\| aj \|\mathop {\max }\limits_j \left\| {{a_j}} \right\|
∥w∥	∑ ‖ wi ‖2\sqrt {\sum {{{\left\\| {{w_i}} \right\\|}^2}} } , where w = (w₀, …., w)∈ R^k
∥w∥_∞	maxj‖ wj ‖∞\mathop {\max }\limits_j {\left\\| {{w_j}} \right\\|_\infty }, where w = (w₀, …., w_k) ∈ R^k
⊥	the algorithm outputs fail
negl(λ)	a non-negligible function about λ
B	the set of integers representable by a single byte, i.e., {0,1,…,255}

	KeyGen	Signature	Verify	Security
[12]	T_Sample	3dT_Mul + T_S	dT_Mul + T_S	CPA-Anonymity
[23]	T_Sample	7dT_Mul + T_S	2dT_Mul + T_S	CPA-Anonymity
[ours]	T_M–Sample	5dT_Mul	3dT_Mul	CCA-Anonymity

	Setup	KeyGen	Sign	Verify
PARM I	248.09	56.54	89.04	57.24
PARM II	426.40	96.12	179.67	114.48

Notation	Description	Execution time
T_M–TrapGen	Trapdoor generation algorithm on module lattices	248.09
T_M–Sample	Trapdoor sampling algorithm on module lattices	31.10