2
$\begingroup$

I get a statistically close to random matrix $A$ and a trapdoor over $\mathbb Z_q^{n \times m}$ using a trapdoor preimage sampler. Lets say I want to sample a short preimage for some other matrix $U$ in $\mathbb Z_q^{n \times k}$. So I get a short preimage $X \in \mathbb Z_q^{m \times k}$. The guarantee you get is that sampling $X$ this way is statistically close to sampling from discrete Gaussians over a bunch of coset lattices (namely the $i$th column of $X$ is statistically close to a discrete Gaussian over the coset lattice $\Lambda_i + U_i$, where $\Lambda_i = \{x \in \mathbb Z^m: Ax = 0\}$ and $U_i$ is the $i$th column of $U$.

My question is what happens if I generate another close to random matrix $A' \in \mathbb Z_q^{n \times m}$ multiply it by $X$. ChatGPT said because the $X$ is short, you can use a "dual LWE" assumption to conclude its computationally indistinguishable from random. It also said you can't use the leftover hash lemma to show its statistically close to random because $X$ is short, and therefore won't have enough entropy. I believe the second part but I feel like its hallucinating on the first part, so I'd love some other opinions here!

$\endgroup$

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.