What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography? Restricting to dimension 3 for illustration, usually the basis is $(1,x,y)$ for uniform $x,y\in R$. I'm instead wondering about power basis $(1,x,x^2)$, and tensor basis $(1,x,x^2)\bigotimes(1,y,y^2)$. More generally, I'm wondering about higher powers and higher dimensions for these bases.

Are there any obvious attacks on RSIS with these bases? Has there been any analysis in this direction, or any works that make assumptions in this direction? If you read such a work, would it raise alarm for you? Do you have any intuitive idea how safe it would be to use such a basis, eg even just for dimensions 3 as above? It seems there are constructions that would benefit greatly.



Your Answer

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