Tìm kiếm Bernoulli đa giải pháp lượng tử với các ứng dụng cho bảo mật chống lượng tử của Bitcoin
Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin’s Post-Quantum Security.
Bằng chứng công việc (PoW) là một cấu trúc mật mã quan trọng cho phép một bên thuyết phục các bên khác rằng họ đã đầu tư một số nỗ lực vào việc giải quyết một nhiệm vụ tính toán. Tác động chính là trong việc thiết lập các Crypto như Bitcoin và giao thức Blockchain cơ bản, vốn đã nhận được sự chú ý đáng kể trong những năm gần đây do tiềm năng đối với các ứng dụng khác nhau cũng như giải quyết các câu hỏi điện toán phân tán cơ bản trong các mô hình mối đe dọa mới. PoW cho phép liên kết các Block trong cấu trúc dữ liệu Blockchain và do đó vấn đề quan tâm là tính khả thi của việc có được chuỗi của các bằng chứng đó. Đồng thời, sự phát triển nhanh chóng của điện toán lượng tử khiến các mối đe dọa đối với mật mã ngày càng đáng lo ngại. Trong công việc này, các tác giả kiểm tra mức độ khó của việc tìm kiếm chuỗi PoW như vậy dựa trên chiến lược lượng tử. Các tác giả chứng minh bài toán chuỗi PoW giảm xuống thành một vấn đề được gọi là tìm kiếm Bernoulli đa giải pháp, nhờ đó các tác giả thiết lập độ phức tạp của truy vấn lượng tử. Thực tế, đây là phần mở rộng của định lý phép nhân trực tiếp ngưỡng cho bài toán tìm kiếm phi cấu trúc trong trường hợp trung bình. Bằng chứng của các tác giả, bổ sung vào những nỗ lực tích cực gần đây, đơn giản hóa và khái quát hóa kỹ thuật ghi lại của Zhandry [Crypto 2019]. Với tư cách là một ứng dụng, các tác giả xem xét lại cách xử lý chính thức về bảo mật cốt lõi của giao thức đồng thuận Bitcoin, được gọi là Bitcoin Backbone [Eurocrypt 2015], trong môi trường mà bên tấn công có khả năng lượng tử trong khi các bên trung thực vẫn giữ nguyên tính cổ điển và cho thấy tính bảo mật của giao thức được giữ vững theo một sự tương tự lượng tử của giả định “đa số trung thực” cổ điển mà các tác giả xây dựng. Phân tích của họ cho thấy tính bảo mật của giao thức Bitcoin Backbone được đảm bảo với điều kiện số lượng truy vấn lượng tử đối nghịch bị giới hạn sao cho mỗi truy vấn lượng tử có giá trị O(p−1/2) truy vấn cổ điển, trong đó p là xác suất thành công của một truy vấn cổ điển đơn lẻ tới hàm Hash cơ bản của giao thức. Điều đáng ngạc nhiên là thời gian chờ để giải quyết an toàn các giao dịch trong trường hợp bên tấn công lượng tử phù hợp (lên đến một hằng số) với thời gian giải quyết an toàn trong trường hợp cổ điển.