I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of the elements in it should multiply $2$, which is not good enough. How to construct a good set (say, just exactly fits the requirement)?

  • $\begingroup$ $\mathbb{Z}[x]/(x^n+1)$ splits into a product of $\mathbb{Z}[\zeta_d]$ as $d$ varies over even divisors of $2n$ and $\zeta_d$ is a primitive $d$-th root of unity. The unit group of $\mathbb{Z}[\zeta_d]$ is known up to finite index to be "cyclotomic units" which are generated by the $(\zeta_d^a-1)/(\zeta_d-1)$ for suitable values of $a$. The index of this subgroup is a rather subtle invariant, but working only with these units could give you a partial answer. $\endgroup$ – Kapil Jun 26 at 2:46

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.