Tham gia Đăng nhập
Điểm:1
James avatar Crypto

zk-STARK có thực sự kháng lượng tử không?

lá cờ br
James

Tôi thấy rất nhiều đề cập rằng các bằng chứng zk-STARK đang được phát triển đặc biệt để sử dụng trong các mạng chuỗi khối được dán nhãn là "kháng lượng tử". Nhiều bài báo và báo cáo nêu rõ điều này, tuyên bố như vậy dựa trên ý tưởng rằng zk-STARK dựa trên các hàm băm chống va chạm. Mặc dù vậy, tôi hiểu rằng không bao giờ có thể có một hàm băm chống va chạm hoàn hảo - và việc một máy tính lượng tử cố gắng tìm ra một xung đột trong bất kỳ hàm băm nào là chuyện nhỏ. Có phần nào mà tôi không hiểu khiến zk-STARK có khả năng kháng lượng tử không?

274
1 + 0
Geoffroy Couteau avatar
lá cờ cn
Geoffroy Couteau
Câu hỏi liên quan: [Các hàm băm mật mã có an toàn lượng tử không?](https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure/44390#44390)
1
Hồi đáp
Điểm:1
Mark avatar Crypto
lá cờ ng
Mark

Đối với nhiều hàm băm, các cuộc tấn công lượng tử được biết đến nhiều nhất dựa trên Tìm kiếm Grover. Điều này tăng tốc một $O(N)$ hoạt động để $O(\sqrt{N})$, tăng tốc cũng vậy, nhưng chỉ theo hệ số "đa thức" (không tăng tốc $O(2^N)$ hoạt động để $O(N)$, hay đại loại thế).

Mặc dù vậy, tôi hiểu rằng không bao giờ có thể có một hàm băm chống va chạm hoàn hảo - và việc một máy tính lượng tử cố gắng tìm ra một xung đột trong bất kỳ hàm băm nào là chuyện nhỏ.

Phần bạn không hiểu là tuyên bố thứ hai. Nếu bạn nghĩ đến một cuộc tấn công cụ thể (đánh bại mọi thứ dựa trên tìm kiếm của Grover), bạn nên thử tìm hiểu chi tiết, vì đó sẽ là một kết quả khá tốt.

0 + 5
poncho avatar
lá cờ my
poncho
@James: lưu ý rằng tìm kiếm của Grover có thể chứng minh được trong một hệ số không đổi (không xa 1) của giá trị tối ưu có thể chứng minh được, nếu bạn xem hàm băm là một đối tượng mờ. Do đó, bất kỳ kết quả nào bạn có thể nhận được tốt hơn đáng kể so với kết quả của Grover sẽ phụ thuộc vào nội tại của chính hàm băm.
0
Hồi đáp
James avatar
lá cờ br
James
Vì máy tính cổ điển có thể tìm thấy xung đột ngẫu nhiên đối với hàm băm trong $O(\sqrt{N})$, điều đó có nghĩa là cả máy tính cổ điển và máy tính lượng tử đều thực hiện số bước xấp xỉ như nhau để thực hiện điều này? Hay tìm kiếm của Grover sẽ thực hiện các bước $O(\sqrt{\sqrt{N}})$ thay vì tìm một xung đột ngẫu nhiên?
0
Hồi đáp
James avatar
lá cờ br
James
Tôi cũng có ấn tượng rằng máy tính lượng tử có thể kiểm tra nhiều kết quả đầu ra khả dĩ hơn trên mỗi bước phụ thuộc vào số lượng qubit - mặc dù kiến ​​thức chính xác của tôi về lĩnh vực này hơi mờ nhạt.
0
Hồi đáp
Mark avatar
lá cờ ng
Mark
@James [Những ghi chú này](https://www.scottaaronson.com/qclec/24.pdf) có vẻ như câu trả lời là $O(N^{1/3})$. Bất kể số mũ chính xác là bao nhiêu, điện toán lượng tử không được biết là có được sự cải tiến siêu đa thức ở đây. Và ấn tượng thứ hai của bạn là một sự hiểu lầm phổ biến về máy tính lượng tử. Xem ví dụ [huyền thoại 2 của bài viết này](https://cacm.acm.org/magazines/2019/4/235578-cyber-security-in-the-quantum-era/fulltext), đó (đại khái) là gì bạn đang ám chỉ.
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@Mark: đối với tìm kiếm xung đột, câu trả lời được biết là nằm trong khoảng từ $O(N^{1/3})$ đến $O(N^{1/2})$. Nếu bạn chỉ tính các truy vấn Oracle, thì giới hạn dưới được biết là có thể đạt được; tuy nhiên, điều đó đi kèm với chi phí mạch khá cao (cao đến mức đối với các hàm băm thực tế, sẽ rẻ hơn nếu thực hiện song song với thuật toán $O(N^{1/2})$). Người ta không biết liệu có tồn tại một thuật toán ít tốn kém hơn mà đạt được (hoặc gần) với giới hạn dưới hay không.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.