Xem xét sửa đổi sau đối với vấn đề Giải pháp số nguyên ngắn (SIS):
Để cho $n$ là một số nguyên và $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ là chức năng của $n$. Mẫu đồng phục $A\gets[-\alpha,\alpha]^{n\times m}$. Nhiệm vụ là tính toán vectơ "ngắn" $e\in\mathbb{Z}^m$ trong hạt nhân của $A$. Đó là:
- $|e| < \beta$.
- $A.e=0^n$. Ở đây, đẳng thức giữ trên các số nguyên
Phiên bản thông thường của SIS giống như trên, ngoại trừ trường hợp $A.e=0^n$ giữ chế độ $q$, và $q=2\alpha+1$ (để có thể $A$ là thống nhất trong $\mathbb{Z}_q^{n\times m}$). Biến thể này loại bỏ mô-đun.
Câu hỏi: Có bất kỳ kết quả độ cứng/độ dễ không tầm thường nào cho phiên bản SIS này không? Cài đặt tham số nào là dễ dàng và cài đặt nào (nếu có) có thể được chứng minh là khó dựa trên các sự cố mạng trong trường hợp xấu hơn, như trong phiên bản SIS thông thường?
Tấn công tầm thường: Có một thuật toán tầm thường trong trường hợp $\beta$ là rất lớn. Bạn có thể tính toán một vectơ hạt nhân trên các số nguyên bằng cách lấy phần phụ của ma trận $A$. Các phần phụ này, và do đó là vectơ nhân, có thể dễ dàng bị chặn trên bởi $(\alpha n)^{O(n)}$. Vì vậy trong chế độ $\beta= (\alpha n)^{O(n)}$, có một cuộc tấn công tầm thường.
Điều tôi tò mò nhất là trường hợp $\alpha,\beta$ là đa thức trong $n$. Có bất kỳ cuộc tấn công nào ở đây, hoặc bất kỳ độ cứng nào có thể được hiển thị không?
Tôi đã chọn phân phối cho $A$ trên để đưa ra một vấn đề cụ thể. Nhưng tôi cũng quan tâm đến các bản phân phối khác trên $A$. Ví dụ, điều gì sẽ xảy ra nếu các mục nhập của $A$ là Gaussian rời rạc, v.v?
Người ta cũng có thể xem xét một phiên bản không đồng nhất của biến thể SIS này, trong đó $A.e=u$, đối với một số vectơ $u$ (một lần nữa, không có mô-đun). Chúng ta phải cẩn thận, mặc dù đối với lớn $u$ sẽ không có giải pháp. Có lẽ chúng tôi hạn chế để ngẫu nhiên $u\in\{0,1\}$, hoặc trong $[-\gamma,\gamma]^n$. Tôi cũng sẽ quan tâm nếu có bất cứ điều gì có thể nói về vấn đề này, bên cạnh sự thích ứng đơn giản của cuộc tấn công tầm thường từ trên cao.
