Tác phẩm "Một thuật toán lượng tử hiệu quả cho các vấn đề về mạng đạt được hệ số xấp xỉ theo cấp số nhân" nghĩa là gì?

Trong Một thuật toán lượng tử hiệu quả cho các bài toán mạng đạt được hệ số xấp xỉ dưới cấp số nhân, tác giả tuyên bố họ đưa ra thuật toán lượng tử thời gian đa thức để giải bài toán Giải mã khoảng cách giới hạn với hệ số xấp xỉ cấp số nhân trên một lớp các mạng số nguyên. Không kết quả này có ý nghĩa gì? Nó sẽ ngụ ý sự không an toàn của mật mã mạng? Nó có quan trọng như thuật toán lượng tử để bao thanh toán của Peter Shor?

Chưa có bài báo công khai nào, vì vậy câu trả lời này là sơ bộ và dựa trên những gì đã được trình bày trong buổi nói chuyện và cuộc thảo luận tiếp theo. Không thể đạt được sự hiểu biết đầy đủ cho đến khi có một bài báo để xác minh, đánh giá và so sánh với công việc trước đó và các kết quả đã biết. Tuy nhiên, một sự hiểu biết tốt về tình hình dường như đã xuất hiện.

tl; dr là: vấn đề đặc biệt mà các tác giả giải quyết là cổ điển dễ dàng giải quyết bằng thuật toán mạng tiêu chuẩn (không cần lượng tử), như được hiển thị trong ghi chú này. Hơn nữa, bước lượng tử cốt lõi mới thay vào đó cũng có thể được triển khai theo cách cổ điển (và đơn giản và hiệu quả hơn nhiều). Vì vậy, công trình không cho thấy bất kỳ lợi thế lượng tử nào so với những gì chúng ta đã biết cách làm cổ điển, cũng như không có gì mới về những gì chúng ta có thể làm theo cách cổ điển. Chi tiết theo sau.

Mệnh đề âtrên một lớp lưới số nguyênâ là một hạn định rất quan trọng. Vấn đề BDD mà các tác giả giải quyết là vấn đề mà mạng là â$q$-aryâ và được tạo bởi một $n$-mô-đun chiều-$q$ vectơ (hoặc một số ít trong số chúng), mô đun $q \gg 2^{\sqrt{n}}$, và vectơ mục tiêu nằm trong một $\ll 2^{-\sqrt{n}}$ hệ số khoảng cách tối thiểu của mạng tinh thể. Cài đặt này khác xa với bất kỳ thứ gì đã từng được sử dụng trong mật mã mạng (theo hiểu biết của tôi), vì vậy kết quả sẽ không có bất kỳ ảnh hưởng trực tiếp nào đến các hệ thống mạng được đề xuất. Tất nhiên, câu hỏi rộng hơn là liệu các kỹ thuật này có thể dẫn đến kết quả mạnh mẽ hơn có ảnh hưởng đến tiền điện tử mạng hay không.

Dựa trên mô tả được đưa ra trong buổi nói chuyện, một số chuyên gia tham dự tin rằng rất có thể vấn đề về mạng đặc biệt mà các tác giả giải quyết đã có thể giải quyết dễ dàng bằng cách sử dụng đã biết. cổ điển kỹ thuật (không cần lượng tử). CẬP NHẬT: điều này đã xảy ra và được chứng minh trong lưu ý này. Nói cách khác, dạng cụ thể của bài toán BDD giúp dễ dàng giải quyết theo những cách đã biết và không gây ngạc nhiên. Thuật toán chỉ đơn thuần là trình tự giảm cơ sở LLL tiêu chuẩn, tiếp theo là giải mã mặt phẳng gần nhất của Babai, nhưng cho thấy rằng điều này thực sự hoạt động dựa trên một số thuộc tính sâu hơn (nhưng đã biết trước đây) của LLL so với các thuộc tính thường được gọi.

Thế còn câu hỏi rộng hơn: các kỹ thuật chính có thể dẫn đến kết quả tốt hơn mà hiện tại chúng ta không thể đạt được theo cách cổ điển không? Nó chỉ ra rằng những gì mà bước lượng tử cốt lõi hoàn thành, phép biến đổi “trường hợp xấu nhất thành trường hợp trung bình”, có thể được thực hiện cổ điển (và đơn giản hơn và hiệu quả hơn) bằng cách sử dụng một kỹ thuật ngẫu nhiên hóa nổi tiếng—cái được gọi là “Tự khử LWE” hoặc â($q$-ary) Rút gọn từ BDD sang LWE.â Xem Mục 5 và Định lý 5.3 của tờ giấy này và các tác phẩm trước đó được trích dẫn trong đó để biết chi tiết.

Chính xác hơn, $n$-chiều $q$-ary BDD cho khoảng cách tương đối $\alpha$ (vấn đề được các tác giả xem xét) thường giảm xuống LWE với tỷ lệ lỗi $\alpha \cdot O(\sqrt{n})$. Mặc dù mức giảm này có vẻ không cần thiết để giải quyết vấn đề BDD ban đầu đang được đề cập, nhưng nó cho thấy rằng bước lượng tử mới cốt lõi có thể được thay thế bằng một thứ gì đó cổ điển ít nhất cũng hoạt động tốt (và thậm chí có thể tốt hơn về mặt tham số). Điều này chỉ ra rằng kỹ thuật lượng tử chính có thể không nắm giữ bất kỳ sức mạnh mới lạ hay đáng ngạc nhiên nào trong bối cảnh này.

Tôi đã tạo một trang web để thu thập thông tin từ cộng đồng về các thuật toán cho các vấn đề về mạng trong NP giao nhau với CoNP:

https://latticealgorithms.xyz

Giấy của chúng tôi là lên:

https://arxiv.org/abs/2201.13450

Đối với hồ sơ, đây là dòng thời gian chúng tôi theo dõi:

Cho đến ngày 17/8/21, chúng tôi đã xem qua văn học cổ điển khá thông suốt. Một thuật toán cổ điển cũng sẽ ổn để chúng ta có thể đưa nó trở lại các thuật toán lượng tử. Nhưng vì trường hợp cơ bản là loại trường hợp xấu nhất của bài toán ẩn số đã được nghiên cứu kỹ lưỡng, nên có vẻ hợp lý là không có gì được biết.

17/8/21-21/9/21: Chúng tôi đã hỏi một nhóm gồm 5 chuyên gia về những gì được biết về vấn đề này. Trong một trường hợp, chúng tôi chỉ ra cách tiếp cận cổ điển tốt nhất mà chúng tôi có thể tìm thấy. Chúng tôi không nhận được phản hồi với thông tin mới.

21/9/21: Quyết định đưa ra trường hợp cơ sở đặc biệt với một vectơ trong bài nói chuyện vì (1) nó sẽ hỗ trợ mọi người giải quyết vấn đề đó và (2) đó là bài nói chuyện chuyên đề trong hội thảo lượng tử và do đó cần để có thể tiếp cận với nhiều đối tượng. Một cuộc nói chuyện chỉ với lưới hoặc chỉ lượng tử đã là một thách thức, và để kết hợp cả hai, tốt, hãy thử nó! 21/9/21: Thảo luận sôi nổi về các khả năng trong hội thảo, nhưng không có thuật toán.

22/9/21: Chúng tôi được liên hệ với một thuật toán cổ điển mới cho trường hợp đặc biệt và sau khi chúng tôi làm rõ thuật toán của chúng tôi có thể làm gì, một bản sửa đổi phác thảo cách nhận được trường hợp tổng quát hơn bằng cách phân tích LLL.

31/1/22: Chưa nhận được câu trả lời cổ điển nào cho giới hạn Schnorr của chúng tôi.

Sean

Người ta có thể đưa ra câu trả lời dài hơn nhiều cho câu hỏi này (và tôi sẽ khá thích thú khi nhìn thấy ai đó giống như quan điểm của Chris), nhưng hai điểm sau đây có lẽ đủ cho một người không phải là chuyên gia.

các yếu tố gần đúng: Cách chính mà cuộc tấn công này nên được coi là (có khả năng) đe dọa đến mật mã dựa trên mạng là thông qua khả năng cải tiến trong tương lai. Hệ số gần đúng mà mục tiêu này nhắm đến (mà tôi tin là $2^{n^{1/2}}$) đủ lớn để ngay cả khi LWE cổ điển yếu trong phạm vi này, người ta vẫn có thể xây dựng những thứ như:

• PKE
• Chữ ký số
• FHE

Ví dụ. hầu hết những gì bạn có thể quan tâm sẽ vẫn tồn tại. Vì vậy, bản thân cuộc tấn công hiện tại không thực sự tác động đến phần chính của mật mã dựa trên mạng "thực tế", mặc dù tất nhiên là có thể cải thiện cuộc tấn công trong tương lai.

Khả năng Dequantization: Cuộc tấn công có hai phần:

1. Bước giảm kích thước (lượng tử) (từ $n\to \sqrt{n}$)
2. Sử dụng các kỹ thuật cổ điển tiêu chuẩn để giải quyết $\sqrt{n}$-dấu hiệu kích thước.

Một số người đã đề xuất khả năng phi lượng tử hóa bước đầu tiên, thông qua những việc như thực hiện các tổ hợp tuyến tính ngẫu nhiên (giả sử với hệ số Gaussian) của các vectơ cơ sở. Nếu việc giảm kích thước này hoạt động, người ta sẽ nhận được BDD với hệ số xấp xỉ $2^{n^{1/2}}$ trong thời gian đa thức (tôi tin).

Trong khi điều này sẽ làm cho chính thuật toán mạnh mẽ hơn, nó cũng sẽ làm cho nó ít liên quan hơn theo một nghĩa nào đó. Điều này là do chúng tôi (về mặt kinh điển) có một ý tưởng khá đúng đắn về mức độ khó của các vấn đề về mạng tinh thể. Bằng cách này, tôi đặc biệt nghĩ về những thứ như:

1. Các kết quả độ cứng "chi tiết" khác nhau tồn tại (giả sử theo Giả thuyết thời gian theo cấp số nhân, hoặc các biến thể của nó),
2. gần đây lưới lọc giới hạn dưới, và
3. kết quả độ cứng khi có sự hiện diện của tiền xử lý (ví dụ kết quả độ cứng CVPP).

Tất nhiên những điều này không loại trừ tất cả các cuộc tấn công có thể xảy ra, nhưng chúng nên được đề cập đến như một bằng chứng chính thức ngày càng tăng về độ cứng cổ điển của các vấn đề về mạng. Điều này có nghĩa là điều liên quan chính về cuộc nói chuyện được liên kết là sự tồn tại của một tăng tốc lượng tử không tầm thường --- nếu điều này bị phi lượng tử hóa, thì chúng ta đang quay trở lại bối cảnh của máy tính cổ điển, nơi hiểu biết của chúng ta về độ cứng của các bài toán mạng tốt hơn.