We have SampleLeft function in lattice trapdoors as

Algorithm $\textbf{SampleLeft}(A,M_1,T_A,u,\sigma)$:

$\textbf{Input}$: a rank $n$ matrix $A$ in $\mathbb{Z}^{n×m}_q$ and a matrix $M_1$ in $\mathbb{Z}^{n×m_1}_q$ , a “short” basis $T_A$ of $\Lambda^{\perp}_q(A)$ and a vector $u \in \mathbb{Z}^n_q$, a gaussian parameter $\sigma > \|\widetilde{T_A}\|.\omega(\sqrt{\log(m+m_1)}$

$\textbf{Output}$: Let $F_1$ := $(A | M_1)$. The algorithm outputs a vector $e \in \mathbb{Z}^{m+m_1}$ sampled from a distribution statistically close to $\mathcal{D}_{\Lambda^{u}_q(F_1),\sigma}$ such that $F_1 . e = u$

My question is can we sample a vector $e$ using the above algorithm(or making some changes) such that $e . F_1 = u$ holds? The dimensions of the matrices change accordingly.

  • $\begingroup$ I think I didn't understand it well... Why transposing both sides to get $e^TF_1^T = u^T$ doesn't work? Also, could you provide a link to the article where you took this function from? $\endgroup$ – Hilder Vitor Lima Pereira Aug 24 '18 at 19:06
  • $\begingroup$ You're right. This exact thought came to my mind after I posted this question. Maybe we could do $t^T \left arrow SampleLeft(A, M_1^T,T_A,u^T,\sigma)$ and then return $t$ as the output. $\endgroup$ – chelsea Aug 24 '18 at 22:18
  • $\begingroup$ This function was not taken from any article. It was just a random thought that came to my mind. $\endgroup$ – chelsea Aug 24 '18 at 22:19

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.