In the following paper, the authors provide a lattice-based ring signature from a 1-out-of-N proof, copied below.


They illustrate their discovery with a table on the bottom of page 28, summarizing the parameters choices and sizes of keys / signatures:


While I could compute myself the length of the secret key ($md\log_2(2\mathcal{B}) = 3,072b = 0.38KB$) and the public key ($nd\log_2(q) = 6.63KB$) for the first column for instance, I cannot get even close to the sizes given for the signature length.

According to the completeness proof of the underlying 1-out-of-N protocol, we have that $\mathbf{z,z_b,z_c} \in RSP$ all have norm $\leq 2\sqrt{3}\phi_2Bmdw^kp^k$ which is in size $\approx 1,169KB$, way larger than the estimate signature length and we do not have a "better" bound on them.

Is my understanding correct, or have I made a mistake somewhere?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.