Vấn đề SIS vs LWE

Hàm một chiều Ajtai được xác định bởi

$$f_A(x)= Rìu \; mod\; q $$ nơi x $\in \{0,1\}^m$ và A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ là hàm một chiều ( Ajtai 96)

Trong khi hàm Regev One way(Regev 05) được định nghĩa trên x $\in \mathbb{Z_q}^k$ và $e \in \mathscr{E}^m$ và A $\in \mathbb{Z_q}^{m \times k}$ .Hàm một chiều được định nghĩa là

$$g_A(x,e) =Ax +e \; mod\; q \; (LWE) $$

$g_A(x,e)$ là hàm một chiều.Câu hỏi của tôi là chức năng Một chiều của Regev có mang lại lợi thế hơn chức năng Một chiều của Ajtai về mặt thiết kế các sơ đồ mã hóa mới hay chúng tương đương với các trường hợp sử dụng của chúng? Ngoài ra chúng có tương đương với độ cứng không?

Có những ràng buộc quan trọng trong các tham số cho chức năng của Ajtai, khiến nó có tính phỏng đoán cao (mỗi hình ảnh có nhiều tiền ảnh). Chúng tôi không biết cách lấy sơ đồ mã hóa từ đó.

Ngược lại, Regev thường được sử dụng trong chế độ tiêm. Và chúng tôi biết cách xây dựng và mã hóa sơ đồ từ nó.

Về Độ cứng, giải quyết SIS hơn $A^t$ khá trực tiếp cho phép giải quyết LWE trên $A$. Theo một hướng khác, cũng có một sự giảm lượng tử. Vì vậy, ít nhất là đối với máy tính lượng tử, các vấn đề là tương đương nhau.

Điều này nên được coi là muối bỏ bể: có những tổn thất rất lớn trong việc giảm này. Đặc biệt, LWE đồng hành cùng một số các tham số lớn có thể chứng minh là khó hơn về mặt lượng tử so với SIS với một số tham số hợp lý hơn.