1
$\begingroup$

May I ask that in section 2.7 challenge space in the paper Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General

enter image description here

What is rot(c), why does rot(c) $\in Z^{d*d}$, and why |rot(u)|2 <= |u|2 ?
And may I also ask that what is $S_{k}^{\delta}$ Also, I am new to lattice crypto, I would truly appreciate it if someone pointed out some resources of learning the math behind ring theory that is essential to read these papers? Thanks a lot

$\endgroup$

2 Answers 2

1
$\begingroup$

$rot(c)$ is the matrix defined by the rotation matrix depending on the number field you are working in, in the paper the number field is $K = \mathbb{Q}[X]/(X^d+1)$ which has a ring of integers $R = \mathbb{Z}[X]/(X^d+1)$ and $R_q= \mathbb{Z}_q[X]/(X^d+1)$.

Let $\left\{X^i | i\in \left\{ 0,\ldots ,d-1 \right\}\right\}$ be a basis of $R_q$.

the $rot$ is defined to be the rotation matrix that send $a = \sum_{i=0}^{d-1}{a_iX^i} \in R_q$ to $$\begin{bmatrix} |&|&|&|\\ a*1 & a*X &\cdots& a*X^{d-1}\\ |&|&|&| \end{bmatrix}$$ such that $a*x^i = \begin{bmatrix} a_{0+i\mod d}\\ a_{1+i\mod d}\\ \vdots\\ a_{d+i\mod d}\\ \end{bmatrix}$

Example

if $d=4$ then

for an element $a = a_0+a_1X+a_2X^2+a_3X^3$ of $R_q$ $$rot(a)= \begin{bmatrix} a_0 & -a_3 & -a_2 & -a_1\\ a_1 & a_0 & -a_3 & -a_2 \\ a_2 & a_1 & a_0 & -a_3\\ a_3 & a_2 & a_1 & a_0\\ \end{bmatrix} $$

now it is clear why the $|rot(u)|_2 \leq |u|2$ from the definitions in page 11 and the fact that $\Vert u\Vert ^2 = \Vert rot(u) u \Vert $ which is smaller than $\Vert rot(u)\Vert \Vert u \Vert $ thus the result. for the last question you can find a good library in https://thelatticeclub.com/

I suggest to start with Basic by Basic Lattice Cryptography: Encryption and Fiat-Shamir Signatures Vadim Lyubashevsky

also check this A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption

I hope that I helped you.

$\endgroup$
2
$\begingroup$

My previous answer gives intuition on what $\mathbf{rot}(a)$ is, which you might find useful.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.