[GPV] và [MP] (tham khảo bên dưới) đưa ra cấu trúc của hàm cửa sập được xác định bởi
$$
f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x,
$$
ở đâu $\mathbf A \in \mathbb Z_q^{n \times m}$ là ngẫu nhiên thống nhất và tên miền là $\{ \mathbf x \in \mathbb Z^m \mid \lVert x \rVert \le \beta\}$. Đưa ra bất kỳ $\mathbf y \in \mathbb Z_q^n$, cửa sập bí mật cho phép tính toán tiền ảnh $\mathbf x$ của $\mathbf y$, I E. $\mathbf A \mathbf x = \mathbf y$ và $\lVert \mathbf x \rVert \le \beta$.
Cửa sập trong [GPV] là một bộ xếp hạng đầy đủ $\mathbf S \in \mathbb Z^{m \times m}$ như vậy mà $\mathbf A \mathbf S = 0$. Cửa sập trong [MP] là $\mathbf R$ như vậy mà $\mathbf A \begin{bmatrix} \mathbf R \ \mathbf I \end{bmatrix} = \mathbf G$, ở đâu $\mathbf G$ là một số ma trận tiện ích công cộng đặc biệt. Trong mọi trường hợp, mỗi cửa sập có một số lượng liên quan $s$ mô tả chất lượng của nó. Vì $\mathbf S$, $s =$ định mức tối đa của các cột Gram-Schmidt $\tilde{\mathbf S}$ của $\mathbf S$. Vì $\mathbf R$, $s = $ giá trị riêng lớn nhất của $\mathbf R$.
Đưa ra bất kỳ $\mathbf y$, cửa sập của chất lượng $s$ cho phép lấy mẫu từ phân phối Gaussian rời rạc trên $\{\mathbf{x} \mid \mathbf A\mathbf x = \mathbf y\}$ chiều rộng $\sigma \ge s\cdot\omega(\sqrt{\log m})$, mang lại $\lVert x \rVert \le \sigma\sqrt m$ (với xác suất áp đảo).
Câu hỏi của tôi là về đảo ngược. Giả sử chúng ta có một lời tiên tri cho việc lấy mẫu tiền ảnh Gaussian đưa ra các giải pháp cho $\mathbf A \mathbf x = \mathbf y$ với $\lVert x \rVert \le \beta$ cho tùy ý chọn $\mathbf y$. Chúng ta có thể phục hồi một số loại cửa sập cho $\mathbf A$ cho phép chúng tôi tính toán một tiền ảnh $\mathbf x'$ ngẫu nhiên $\mathbf y'$ điều đó không được truy vấn đến nhà tiên tri, với xác suất không đáng kể?
Một nỗ lực rõ ràng là để truy vấn cho $\mathbf A \mathbf x = \mathbf 0$ để thử khôi phục một bộ xếp hạng đầy đủ "ngắn" $\mathbf S$ như vậy mà $\mathbf A \mathbf S = \mathbf 0$. Nhưng điều này $\mathbf S$ dường như không đủ ngắn để tính toán các nghiệm có độ dài $\le \beta$. Chúng ta có thể thử giảm mạng. Nhưng tôi không biết giảm mạng tinh thể hiện đại là gì cho vấn đề này khi cố gắng lấy cơ sở ngắn hơn từ cơ sở vốn đã ngắn.
- [GPV] https://eprint.iacr.org/2007/432
- [MP] https://eprint.iacr.org/2011/501
