In SIS based scheme, there is a matrix $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, and $n$ is the security parameter. I want to ask that why $n=1$ is also okay for the scheme (in "A framework for building composable zero-knowledge proofs" the authors choose the following parameters for the Ajtai hash function, see the following picture). At this time, the security of the Ajtai hash function is based on the SVP problem with dimension 1.

  • Is SVP with $n=1$ hard?
  • And n is a small positive integer is also OK for SIS based scheme in lattice-based cryptography?

enter image description here

I also see that "$n = 1024$, which is a typical choice for lattice-based schemes targeting medium or high-security levels" in the paper "Blaze: practical lattice-based blind signature for privacy-preserving application".

  • So how to explain this? I say that why there is a preference choosing for $n$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.