Vấn đề Lattice Cứng là gì? Một chủ đề 🧵

Mật mã dựa trên lưới phụ thuộc vào một thách thức trung tâm: tìm một nghiệm vector ngắn s cho một hệ phương trình tuyến tính modulo một số nguyên q (thường là số nguyên tố hoặc lũy thừa của số nguyên tố). Điều này được gọi là bài toán SIS (Giải pháp Số Nguyên Ngắn), đơn giản về hình thức nhưng được cho là khó khăn trước các cuộc tấn công lượng tử/ cổ điển.

Có hai phiên bản chính: dạng không đồng nhất được sử dụng như hàm một chiều f_A(s) = A * s mod q trong các sơ đồ cam kết, nơi chúng ta giải A * s = t (mod q) với A và mục tiêu t...

...và bài toán SIS đồng nhất, yêu cầu tìm một s ngắn sao cho A * s = 0 (mod q) với A là một ma trận ngẫu nhiên.

Chương trình cam kết được đảm bảo là ràng buộc bởi độ khó của SIS. Nếu A * s = t = A * s', thì A * (s - s') = 0, điều này có nghĩa là việc tìm một s' khác giải quyết bài toán SIS đồng nhất khó.

Độ ngắn của s (chuẩn nhỏ) là rất quan trọng. Nếu không giới hạn s, các nghiệm sẽ trở nên tầm thường khi sử dụng đại số tuyến tính cổ điển. Sự hạn chế về chuẩn này là nền tảng cho tính chất khó giải của SIS, ngay cả trước các máy tính lượng tử.

Kết quả của Ajtai năm 1996 đã liên kết độ khó của bài toán SIS với việc giải quyết các bài toán lưới trong trường hợp xấu nhất, tạo thành nền tảng cho các giả định về mật mã hậu lượng tử.

Vấn đề SIS cho phép nén từ một vector bí mật lớn s (có kích thước M) thành một cam kết ngắn hơn t. Ma trận A có kích thước N x M, trong đó N thường liên quan đến tham số bảo mật, làm cho nó trở nên hấp dẫn cho các chứng minh không biết cần sự ngắn gọn.

Tổng hợp lại, SIS dễ nói nhưng cực kỳ khó giải quyết, đóng vai trò cơ bản trong các cam kết, chứng minh không biết và an ninh hậu lượng tử rộng hơn.