Tác giả: Nhóm Blocksteam
Nguồn: https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained/
Lưu ý : Bài viết này là phần giới thiệu về nghiên cứu chuyên sâu và khóa học của chúng tôi. Để có giải thích kỹ thuật toàn diện, vui lòng đọc báo cáo nghiên cứu và xem các khóa học của chúng tôi.
Với việc Google công bố bài báo về trí tuệ nhân tạo lượng tử , trong đó đề cập đến điện toán lượng tử, các cuộc thảo luận xoay quanh thời điểm ra đời của một máy tính lượng tử có ý nghĩa về mặt mật mã (CRQC) đã trở nên sôi nổi hơn. Mặc dù các dự đoán về thời điểm ra mắt có sự khác nhau, nhưng sự đồng thuận trong cộng đồng mật mã học là rõ ràng: chúng ta nên bắt đầu chuẩn bị và nghiên cứu các thuật toán mật mã an toàn lượng tử ngay từ bây giờ.
Nhiệm nhiệm vụ chính là lựa chọn một lược đồ chữ ký điện tử an toàn lượng tử để thay thế mật mã đường cong elip dễ bị tổn thương lượng tử mà chúng ta đang sử dụng hiện nay trong Bitcoin. Tuy nhiên, vượt qua Schnorr và ECDSA không đơn giản như việc chuyển sang một thuật toán khác. Cộng đồng Bitcoin hiện đang tập trung vào hai vấn đề chính: làm thế nào để thực hiện quá trình chuyển đổi một cách an toàn; và nên chuyển sang lược đồ hậu lượng tử (PQ) nào . Bài viết này chỉ tập trung vào vấn đề thứ hai, với hy vọng xác định được nhóm chữ ký hậu lượng tử triển vọng nhất.
Sau đây là những quan sát của chúng tôi về lĩnh vực hậu lượng tử hiện nay. Những quan sát này cũng giải thích lý do tại sao Blockstream tập trung vào mật mã "dựa trên mạng lưới" và cách thức hoạt động của các lược đồ chữ ký này.
Kỷ nguyên hậu lượng tử
Đối với chữ ký hậu lượng tử, các nhà mật mã học thường tập trung vào bốn giả định (được cho là) khó phá vỡ bằng máy tính lượng tử.
1. Mật mã dựa trên hàm băm . Tính bảo mật của loại sơ đồ này dựa trên giả định rằng hàm băm không thể đảo ngược. Trong tất cả các thuật toán mật mã mà chúng ta sử dụng hiện nay, giả định này được cho rằng ổn định nhất.
Hơn nữa, các lược đồ có trạng thái (như SHRINCS ) đạt được chữ ký rất nhỏ gọn, chỉ 324 byte; tuy nhiên, sự nhỏ gọn này đạt được với cái giá là việc quản lý trạng thái tỉ mỉ. Ngược lại, việc tránh gánh nặng quản lý trạng thái này dẫn đến chữ ký không trạng thái với các tham chiếu chữ ký cuối cùng tương đối lớn. Cả hai đều gặp phải sự thiếu linh hoạt về mặt đại số: nghĩa là, việc phát triển các biến thể như chữ ký đa lớp hiệu quả và chữ ký ngưỡng hiện nay dường như là không thể.
Blockstream đã thực hiện một nghiên cứu toàn diện về loại mật mã này, như đã thấy trong " Nghiên cứu về các lược đồ chữ ký dựa trên hàm băm cho Bitcoin " (của Mikhail Kudinov và Jonas Nick) và " SHRIMPS " (của Jonas Nick). Giờ đây, chúng ta sẽ xem xét phương pháp dựa trên mạng lưới, có thể giải quyết một số vấn đề đã đề cập trước đó.
2. Mật mã dựa trên lưới . Tính bảo mật của các phương pháp này liên quan đến một vấn đề cụ thể liên quan đến một đối tượng toán học được gọi là " lưới ". Đối tượng này đã được các nhà toán học nghiên cứu từ thế kỷ 18. Bạn có thể hình dung một lưới như một ma trận gồm vô số điểm, như hình ảnh bên dưới. Cũng giống như việc cộng hai điểm trên một đường cong elip tạo ra một điểm thứ ba (trên cùng một đường cong elip), việc cộng hai điểm trên lưới này sẽ tạo ra một điểm hợp lệ khác trên cùng lưới đó.
Vì vậy, bạn có thể đặt một số câu hỏi về mạng lưới này, chẳng hạn như: Khoảng cách ngắn nhất giữa hai điểm trên mạng lưới này là bao nhiêu? Hoặc, nếu bạn chọn ngẫu nhiên một điểm trên mặt phẳng, điểm nào trên mạng lưới gần nhất với điểm đó? Đối với một mạng lưới được cấu hình đúng cách, máy tính lượng tử—mà không cần biết các chi tiết hình học cơ bản của mạng lưới—được cho rằng là gặp khó khăn trong việc trả lời tất cả các câu hỏi này.
So với các lược đồ dựa trên hàm băm và các chữ ký không trạng thái nhỏ hơn, đặc điểm chính của mạng lưới là tính linh hoạt về mặt đại số. Chúng ta sẽ giải thích chi tiết hơn về điều này trong chương tiếp theo.
3. Mật mã dựa trên mã hóa . Mã sửa lỗi (ECC) là một công cụ toán học được sử dụng rộng rãi khác trong lĩnh vực này. Có thể bạn đã nghe nói về chúng, ví dụ, vì chúng có ứng dụng riêng trong các hệ thống chứng minh hậu lượng tử như ZK-STARK. Tuy nhiên, các lược đồ chữ ký hiện tại dựa trên giả định ECC không thực tế (so với các đối thủ cạnh tranh dựa trên hàm băm và dựa trên mạng lưới) vì khóa công khai và chữ ký thu được quá lớn. Nói chung, các đối tượng này dễ dàng vượt quá 10 KB về kích thước; lược đồ ứng cử viên LESS của NIST là một ví dụ điển hình.
4. Mật mã tương đồng . Loại mật mã này có thể tạo ra các khóa công khai và chữ ký nhỏ hơn so với các phương án đã đề cập ở trên. Ví dụ, tổng kích thước của khóa công khai và chữ ký của SQISign là 213 byte (để so sánh, phương án chữ ký Schnorr là 96 byte), điều này rất ấn tượng. Tuy nhiên, toán học đằng sau nó dựa trên các khái niệm rất mới về hình học đại số. Trong mật mã học, độ phức tạp thường là kẻ thù của bảo mật vì các cấu trúc tập hợp cồng kềnh này có thể che giấu những lỗ hổng nhỏ. Các phương án này sẽ cần được kiểm tra độ bền lượng lớn trước khi chúng ta có thể tích hợp chúng vào Bitcoin .
Như bạn thấy, mỗi trong bốn mô hình được đề cập ở trên đều có những sự đánh đổi riêng: kích thước chữ ký, tính bảo mật và độ bền, và tính linh hoạt, có thể được tóm tắt trong sơ đồ sau.
Tóm lại, các chữ ký dựa trên mã hiện tại quá cồng kềnh so với những hạn chế nghiêm ngặt về không gian khối của Bitcoin. Toán học dựa trên nguồn gốc chung thì gọn nhẹ nhưng cực kỳ khó triển khai một cách an toàn và vẫn còn gây nhiều tranh cãi. Chữ ký dựa trên hàm băm rất an toàn và dễ hiểu, nhưng chúng lại "cứng nhắc" về mặt đại số.
Xét về tương lai lâu dài của Bitcoin, mật mã dựa trên mạng lưới đã nổi lên như một trong những ứng cử viên cân bằng và đầy triển vọng nhất.
Tại sao lại sử dụng chữ ký mạng lưới? Tính linh hoạt về mặt đại số.
Để hiểu tại sao mật mã mạng lưới lại hấp dẫn đối với Bitcoin, chúng ta cần xem xét các yếu tố làm cho các lược đồ chữ ký Bitcoin hiện tại (Schnorr và ECDSA) trở nên hiệu quả.
Hiện tại, tính bảo mật của các lược đồ chữ ký trên Bitcoin dựa trên bài toán Logarit rời rạc (DL). Một ưu điểm đáng kể của phương pháp DL là khung toán học được cấu trúc tốt. Ví dụ, việc kết hợp hai private key cũng cho phép tạo ra các tổ hợp có thể dự đoán được của các khóa công khai của chúng:
[x + y].G = [x].G + [y].GTính chất đồng cấu hình học này chính là lý do tại sao các nhà phát triển Bitcoin có thể phát triển các giao thức tiên tiến như chữ ký đa chữ ký (ví dụ: MuSig2 , từ Onas Nick, Tim Ruffing và Yannick Seurin), chữ ký ngưỡng, dẫn xuất xác định theo thứ bậc và "chữ ký bộ chuyển đổi".
Các hàm băm (như SHA256 và BLAKE) thì ngược lại; chúng hoạt động như những bộ trộn ngẫu nhiên. Nếu bạn có một hàm băm H , việc cộng hai đầu vào với nhau sẽ không tạo ra bất kỳ mối quan hệ nào giữa các đầu ra hàm băm của chúng: H(x+y) sẽ không bằng H(x)+H(y) . Mặc dù sự thiếu cấu trúc này chính xác là điều làm cho các hàm băm trở nên an toàn, nhưng nó cũng khiến việc phát triển các giao thức cấp cao dựa trên chúng trở nên vô cùng khó khăn.
Tuy nhiên, mật mã mạng lưới cũng cung cấp cho chúng ta cấu trúc toán học này. Thay vì nhân một số vô hướng với một điểm trên đường cong elip, mật mã mạng lưới nhân một lưới các số (ma trận) với một cột các số (vectơ). Nếu bạn có một ma trận công khai A và hai giá trị bí mật x và y , thì A(x+y) = Ax + Ay (tương tự như (x+y)G=xG+yG trong bối cảnh logarit rời rạc).
Một điểm quan trọng cần lưu ý là: trong mật mã mạng lưới, chúng ta thường sử dụng các giá trị bí mật ngắn . Khi kết hợp các phương trình mạng lưới (ví dụ: tính x+y ), độ dài của giá trị bí mật "tổng hợp" sẽ tăng lên. Tuy nhiên, miễn là chúng ta kiểm soát đúng mức độ của những lỗi này, các thuộc tính cấu trúc đã đề cập ở trên vẫn được giữ nguyên. Điều này có nghĩa là mạng lưới có tiềm năng cho phép cải tiến giao thức tiên tiến, chẳng hạn như chữ ký đa chữ ký hậu lượng tử, bằng chứng không tiết lộ thông tin và tài sản bí mật.
Cách thức hoạt động của các dấu hiệu mạng tinh thể: Schnorr với vectơ
Nếu bạn hiểu được chữ ký Schnorr trên Bitcoin, bạn đã nắm được 50% về chữ ký mạng lưới, chẳng hạn như Dilithium . Thiết kế chữ ký mạng lưới phổ biến nhất này sử dụng một kỹ thuật mà chúng ta gọi đùa là "phương pháp Schnorr với vectơ".
Trong chữ ký Schnorr truyền thống, quy trình ký private key x diễn ra như sau:
- Chọn một số ngẫu nhiên
r - Hãy tạo một "cam kết" cho con số này.
- Mã hóa lời hứa và dữ liệu cần ký để tạo ra giá trị thử thách ngẫu nhiên
e - Sử dụng giá trị thử thách này để che giấu private key của bạn, tạo ra giá trị phản hồi cuối cùng
z = r + xe
Trong các lược đồ chữ ký dựa trên mạng lưới, chúng ta thực hiện chính xác các bước tương tự, chỉ khác là sử dụng ma trận và vectơ. Các phương trình trông khá giống nhau: ví dụ, nhiều nghiên cứu ban đầu về chữ ký mạng lưới đã sử dụng phương trình z = r + Se , trong đó S là ma trận bí mật, e là vectơ thách thức và r là vectơ ngẫu nhiên.
Từ chối lấy mẫu*
Ở đây có một vấn đề an ninh đáng kể. Để làm cho các phương trình mạng lưới khó giải đối với máy tính lượng tử, các số trong vectơ z và r phải nhỏ (đây là cái gọi là vấn đề " giải pháp số nguyên ngắn ").
Tuy nhiên, khi ta tính z = r + Se , điều này tạo ra sự phụ thuộc thống kê giữa chữ ký z và giá trị bí mật S đằng sau nó (điều này không xảy ra với chữ ký Schnorr, vì r và e có thể là bất kỳ). Nếu kẻ tấn công có thể thu thập đủ chữ ký của bạn, chúng sẽ nhận thấy trong đó thiên lệch thống kê và có thể tiết lộ private key của bạn.
Để giải quyết vấn đề này, mật mã mạng lưới sử dụng một kỹ thuật khéo léo gọi là " biến đổi Fiat-Shamir với loại bỏ " (còn được gọi là "lấy mẫu loại bỏ").
Ý tưởng khá đơn giản: sau khi người ký tạo ra chữ ký z , họ kiểm tra xem việc thêm private key có gây ra sự thay đổi đáng kể nào trong giá trị này hay không. Nếu chữ ký có vẻ "thiên vị" và có khả năng tiết lộ private key(như trong sơ đồ trên), họ sẽ loại bỏ chữ ký đó và thử lại với một số ngẫu nhiên mới (tạo ra một chữ ký khác). Quá trình này được lặp lại lần cho đến khi chữ ký cuối cùng che giấu hoàn toàn private key(như đường chấm chấm trong sơ đồ trên).
Một lời nhắc nhở . Trên thực tế, giá trị trung bình Se bản thân nó là một phân phối ngẫu nhiên. Tuy nhiên, về nguyên tắc, không có sự khác biệt: độ lệch của phân phối sẽ tiết lộ một số thông tin về giá trị bí mật S cơ bản, vì vậy chúng ta phải loại bỏ độ lệch (điều này cũng bởi vì có thể chứng minh rằng việc này rất đơn giản để thực hiện).
Bước tiếp theo
Mật mã dựa trên mạng lưới là một chủ đề sâu sắc và là một hướng đi đầy hứa hẹn trong mật mã hậu lượng tử, vượt xa việc chỉ đơn thuần thay thế các lược đồ chữ ký số hiện tại. Nó cung cấp nền tảng toán học để đảm bảo tính bảo mật lượng tử của Bitcoin, đồng thời hứa hẹn nâng cấp lên các lược đồ tổng hợp và ngưỡng hiệu quả hơn.
Để hiểu rõ hơn, bao gồm cả toán học đằng sau "Hàm Gauss rời rạc", bài toán vectơ ngắn nhất và lấy mẫu loại bỏ, vui lòng đọc toàn bộ báo cáo nghiên cứu của chúng tôi và xem video minh họa đầy đủ.
(qua)
