Tác giả: Jonasnick
Tóm tắt : Chữ ký dựa trên hàm băm có trạng thái có thể rất hiệu quả nếu số lượng chữ ký được tạo ra từ khóa công khai là nhỏ. Một vấn đề chính của các lược đồ có trạng thái là cần phải sao lưu trạng thái và cập nhật nó một cách chính xác sau mỗi thao tác ký. Bằng cách kết hợp trực tiếp một lược đồ dựa trên hàm băm không trạng thái (chẳng hạn như một biến thể của SPHINCS+) với một cây XMSS không cân bằng (mang khóa công khai chữ ký một lần, tất nhiên là có trạng thái), chúng ta thu được một lược đồ gọi là "SHRINCS". Nó rất hiệu quả khi chỉ cần một số lượng nhỏ chữ ký và có thể được sao lưu bằng một seed tĩnh. Chính xác hơn, khóa công khai SHRINCS là một hàm băm của cả khóa công khai có trạng thái và không trạng thái. Chúng ta giả định rằng việc tạo khóa xảy ra trong một thiết bị ký có khả năng lưu trữ trạng thái một cách an toàn. Do đó, người ký này có thể sử dụng một lược đồ chữ ký có trạng thái hiệu quả để tạo chữ ký. Khi trạng thái được biết là bị hỏng hoặc bị mất (ví dụ, khi ví được khôi phục bằng seed tĩnh), chỉ có thể sử dụng lược đồ chữ ký không trạng thái. Do đó, SHRINCS tận dụng hiệu quả của các lược đồ chữ ký có trạng thái trong hoạt động bình thường, đồng thời vẫn duy trì các chữ ký không trạng thái mạnh mẽ như một phương án dự phòng.
TỦY
Phương thức SHRINCS đã được giới thiệu ngắn gọn trong phụ lục của báo cáo của tôi, " Các phương thức chữ ký dựa trên hàm băm áp dụng cho Bitcoin ". Bài viết này cung cấp một lời giải thích toàn diện hơn, và chúng tôi hoan nghênh mọi phản hồi.
Việc xây dựng SHRINCS đòi hỏi một lược đồ chữ ký không trạng thái và một lược đồ chữ ký có trạng thái (lược đồ sau có khả năng tạo ra các chữ ký nhỏ). SHRINCS bao gồm các thuật toán sau:
- $\textsf{KeyGen}() \rightarrow (\mathit{Seed}, \mathit{pk}, \mathit{state})$: Thuật toán tạo khóa này tạo ra một khóa gốc (master seed) và suy ra private key$\mathit{sk}_1$ và $\mathit{sk}_2$, được sử dụng cho các lược đồ chữ ký có trạng thái và không trạng thái tương ứng. Sử dụng hai private key này, nó tạo ra các khóa công khai $pk1$ và $pk2$, được sử dụng cho các chữ ký có trạng thái và không trạng thái tương ứng. Cuối cùng, $KeyGen$ trả về bộ giá trị $(\mathit{Seed}, \mathit{pk}, \mathit{state})$, trong đó$\mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2)$, và $state$ là trạng thái ban đầu cho chữ ký có trạng thái.
- $\textsf{Restore}(\mathit{Seed}) \rightarrow (\mathit{Seed}, \mathit{pk}, \mathit{state})$: Thuật toán khôi phục tạo lại khóa công khai SHRINCS từ một seed, đặt $state$ thành $\textsf{LOST}$, và trả về bộ $(\mathit{Seed}, \mathit{pk}, \mathit{state})$.
- $\textsf{Sign}(\mathit{Seed}, \mathit{state}, m) \rightarrow (\mathit{state}', \mathit{sig})$: Nếu $\mathit{state} \neq \textsf{LOST}$, thì thuật toán ký sẽ tạo lại private key$\mathit{sk}_1$ và khóa công khai $\mathit{pk}_2$, và chạy thuật toán ký $\textsf{Sign}$ với lược đồ ký có trạng thái sử dụng $\mathit{sk}_1$, $\mathit{state}$ và thông điệp $m$. Sau đó, nó trả về trạng thái được cập nhật $\mathit{state}'$ và chữ ký được nối với $\mathit{pk}_2$. Ngược lại (nếu trạng thái bị hỏng), thì hãy tạo lại private key$\mathit{sk}_2$ và khóa công khai $\mathit{pk}_1$, và chạy lược đồ chữ ký không trạng thái bằng cách sử dụng $\mathit{sk}_2$ và $m$, trả về $\mathit{state}' = \mathit{state}$ và một chữ ký được ghép nối với $\mathit{pk}_1$.
- $\textsf{Verify}(\mathit{pk}, m, \mathit{sig}) \rightarrow {\textsf{true}, \textsf{false}}$: Thuật toán xác thực, phân tích chữ ký $\mathit{sig}$ thành $\mathit{sig}' | \mathit{pk}'$, xác thực $\mathit{sig}'$ theo lược đồ không trạng thái hoặc có trạng thái (trong lược đồ chữ ký dựa trên hàm băm, điều này có nghĩa là khôi phục khóa công khai), và sau đó kiểm tra xem giá trị băm của hai khóa công khai có bằng $\mathit{pk}$ hay không.
Do đó, sau khi một trình ký có khả năng duy trì trạng thái được khởi tạo, nó sẽ ký bằng phương thức có trạng thái; tuy nhiên, bất cứ khi nào một thiết bị được khôi phục bằng khóa hạt giống, nó chỉ ký bằng phương thức không trạng thái. Vì chế độ ký có trạng thái hiệu quả hơn nhiều trong SHRINCS, việc ký bằng thiết bị đã được khôi phục sẽ tốn kém hơn nhiều so với việc ký bằng thiết bị đã chạy $\textsf{KeyGen}$ ban đầu.
Đối với các lược đồ chữ ký không trạng thái trong SHRINCS, các ứng cử viên bao gồm SLH-DSA, hoặc một biến thể của SPHINCS+ mà chúng tôi đã mô tả chi tiết trong báo cáo. Tùy thuộc vào các tham số, kích thước chữ ký dao động từ 3KB đến 8KB, trong khi khóa công khai là 16 byte (thuộc Cấp độ Bảo mật 1 của NIST). Còn đối với các lược đồ chữ ký có trạng thái, SHRINCS sử dụng cái mà chúng tôi gọi là "XMSS không cân bằng". Khóa công khai XMSS thông thường là gốc của Merkle trees được xây dựng từ nhiều khóa công khai chữ ký một lần (OTS). Các lược đồ chữ ký một lần chỉ cho phép một khóa công khai tạo ra một chữ ký; nếu không, khóa công khai đó không an toàn. Do đó, trạng thái chữ ký là số lượng chữ ký đã tạo ra, ban đầu $q=0$. Để ký một thông điệp bằng XMSS, người ký tăng $q$, ký bằng khóa công khai một lần thứ $q$ trong Merkle trees, và sau đó tính toán đường dẫn xác thực đến gốc (cái gọi là "bằng chứng Merkle"). Chữ ký cuối cùng về cơ bản là chữ ký dùng một lần cộng với đường dẫn xác thực.
SHRINCS không trực tiếp sử dụng Merkle trees không cân bằng được cấu tạo từ các chữ ký dùng một lần (khóa công khai). Thay vào đó, nó sử dụng một cây không cân bằng trong phần lược đồ chữ ký có trạng thái. Do đó, khóa công khai của chữ ký dùng một lần đầu tiên nằm ở độ sâu 1, khóa thứ hai ở độ sâu 2, v.v. Điều này giúp giảm thiểu độ dài của đường dẫn xác thực cho các chữ ký ban đầu, lý tưởng cho các trường hợp chỉ dự kiến một số lượng nhỏ chữ ký. Đối với lược đồ "XMSS không cân bằng" này, chữ ký thứ $q$ là chữ ký dùng một lần thứ $q$ và đường dẫn xác thực của nó. Theo tiêu chuẩn bảo mật NIST cấp 1, kích thước đường dẫn xác thực là $q \cdot 16$ byte, trong khi kích thước chữ ký dùng một lần là 292 byte. Cụ thể hơn, lược đồ chữ ký dùng một lần mà chúng tôi sử dụng là WOTS+C (xem bài báo để biết chi tiết).
Tóm lại, khi sử dụng chữ ký trạng thái không mất dữ liệu, kích thước chữ ký của SHRINCS là $\min(292 + q \cdot 16, s_l) + 16$, trong đó$q$ là số lượng chữ ký được tạo cho khóa công khai này ở chế độ có trạng thái, và $s_l$ là kích thước của chữ ký được tạo bằng lược đồ không trạng thái. Nếu $q = 1$, chữ ký sẽ nhỏ hơn 11 lần so với lược đồ tiêu chuẩn NIST (ML-DSA) với kích thước chữ ký nhỏ nhất. Tôi ước tính giá trị $q$ trung bình cho một ví Bitcoin thông thường nằm trong khoảng từ 1 đến 2. Nhược điểm chính của SHRINCS là tính bảo mật của nó yêu cầu quản lý trạng thái an toàn. Tuy nhiên, không giống như các lược đồ hoàn toàn có trạng thái (nơi một sự cố trong quản lý trạng thái có thể gây ra hậu quả thảm khốc), trong SHRINCS, bạn luôn có thể chuyển sang chế độ không trạng thái bất cứ khi nào bạn có nghi ngờ.
(qua)
