Let $q \geq 2$ be a prime integer. Consider two functions, given by:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
where we have:
\begin{align}
b &\in \{0, 1\}, \\
x &\in \mathbb{Z}_{q}^{n}, \\
s &\in \mathbb{Z}_{q}^{m}, \\
A &\in \mathbb{Z}_{q}^{n \times m}, \\
e' &\in \mathbb{Z}_{q}^{m}, \\
u &\in \mathbb{Z}_{q}^{m},
\end{align}
$e$ is sampled from the distribution:
\begin{equation}
D_{\mathbb{Z}_q, B^{'}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{'2}}}}{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}},
\end{equation}
where
$$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$
$C_{T}$ is a fixed constant.
In this paper, the functions are defined in equation 29 and it is mentioned that in the worst case over $A$, $u$ and $e'$, assuming LWE is hard for polynomial time classical algorithms, distinguishing between $f$ and $g$ is also hard, given $A$ and given (polynomially many) "samples" (since $e$ is a probability distribution, outputs of $f$ or $g$ are samples) from either $f$ or $g$.
The LWE reduction also holds for average case.
The paper also mentions that these two functions are a family of "extended trap-door claw free functions (Definition 5, 6, 7.)"
As a reference to the proof of these above facts, the paper references this paper (Lemma 9.3). However, while proving Lemma 9.3, the second paper also references some other papers, like this one. The proof was not clear to me in any of the papers.
I wanted to ask how to reduce the task of distinguishing between $f$ and $g$ to LWE. I also wanted to ask about the importance of the function being "extended trap-door claw free" in that reduction.
From my understanding, the hardness of LWE says that if we are given $A$, distinguishing between uniformly random samples and samples from $As + e'$ is hard. I am not sure how $b$ and $x$ or the other parameters factor into that fact. Is that where we need the extended-trap-door-claw-free proof?
