Chà, tôi nghĩ rằng nếu bạn Thực ra cắt bớt mọi thứ [1], bạn có thể giảm chữ ký xuống dưới 100 byte. Đây là cách tôi điều chỉnh yêu cầu của bạn:
Tôi muốn bảo mật 128 bit trở lên (mặc dù đó không phải là một yêu cầu khó).
Vì bạn nói rằng đó không phải là một yêu cầu khó, nên tôi đã đặt lại yêu cầu đó thành bảo mật 80 bit (nếu bạn làm điều này với bảo mật 128 bit, bạn sẽ nhận được chữ ký khoảng 200 byte). Bằng cách nhắm mục tiêu bảo mật 80 bit, chúng tôi có thể sử dụng hàm băm 80 bit (ví dụ: SHA-256 bị cắt bớt thành 80 bit - chúng tôi có thể thử sử dụng hàm băm nhanh hơn với mức độ bảo mật thấp hơn, tuy nhiên, điều đó chỉ tăng tốc mọi thứ lên một yếu tố khiêm tốn, vì vậy tôi không mong đợi điều đó sẽ mua cho chúng tôi nhiều).
Tôi sẽ ký các khối dữ liệu có kích thước 128 byte hoặc nhỏ hơn.
Không phải là một vấn đề
Lược đồ chữ ký không cần phải được sử dụng rộng rãi, được tiêu chuẩn hóa bởi bất kỳ cơ quan có thẩm quyền nào hoặc tương thích với bất kỳ hệ thống nào khác.
Không ai đủ điên để chuẩn hóa phương pháp này
Hiệu quả của việc tính toán các khóa hoặc chữ ký không phải là yếu tố chính, miễn là không mất nhiều hơn một hoặc hai phút để thực hiện đối với khối 128 byte.
Chà, tính toán khóa công khai là một vấn đề lâu dài ở đây, vì vậy tôi sẽ giới hạn 2 phút cho việc đó. Tuy nhiên, bạn đã không nói phần cứng là gì, vì vậy tôi sẽ cho rằng phần cứng mạnh mẽ ở đó - 8 lõi nhanh với phần cứng AVX512 (thực ra, chúng tôi có thể tích cực hơn với phần cứng chuyên dụng, tuy nhiên điều đó sẽ không cho phép chúng tôi thu nhỏ chữ ký nhiều thế)
Giả sử rằng tôi chỉ muốn cấp khoảng 10~20 chữ ký và sau đó vứt bỏ khóa riêng tư mãi mãi.
Tôi cho rằng 20 chữ ký là tối đa (tối đa 16 chữ ký sẽ cho phép chúng tôi giảm kích thước chữ ký thêm 10 byte).
Ok, đây là những gì chúng tôi làm: chúng tôi bắt đầu với thiết kế LMS/XMSS (hoặc sửa đổi LMS để cho phép hệ số W lớn hơn hoặc loại bỏ mặt nạ bit của XMSS và khuấy vị trí theo cách khác); sau đó:
Chúng tôi có mục tiêu là 20 chữ ký; điều này ngụ ý chiều cao Merkle là 5 (chúng tôi có thể giảm xuống còn 4 nếu chúng tôi có thể giả định tối đa 16 chữ ký)
Một phép đo trên bộ xử lý Xeon của tôi cho thấy rằng một lõi đơn có thể, với các lệnh AVX2 của nó, tính toán 6,6 triệu giá trị băm mỗi giây; nếu chúng tôi sử dụng bộ xử lý nhanh hơn với hướng dẫn AVX512, chúng tôi có thể nhận được tới 20 triệu băm mỗi giây. Chúng tôi có 8 lõi và chúng tôi có 120 giây để tính toán các khóa, vì vậy chúng tôi có thời gian để tính toán không quá 20 tỷ giá trị băm.
Bây giờ, chúng tôi cần tạo 20 khóa công khai chữ ký một lần [2] (và mọi thứ khác tương đối tầm thường) - vì vậy, chúng tôi có thời gian cho gần 1 tỷ giá trị băm trên mỗi chữ ký một lần
Nếu chúng ta sử dụng một giá trị Winternitz của $W \khoảng 200.000.000$, điều đó sẽ cho phép chúng tôi mã hóa khoảng 27 bit. Bây giờ, hàm băm mà chữ ký một lần ký là 80 bit; điều đó có nghĩa là, với mã hóa tổng không đổi, chúng ta có thể dễ dàng tạo 4 chữ số cơ sở 200.000.000 (phương pháp; nạp giá trị được ký vào SHAKE; tạo 3 chữ số cơ sở 200.000.000; xem liệu có chữ số thứ tư sao cho tổng là mục tiêu ; nếu không, hãy quay lại và tạo thêm chữ số)
- Trên thực tế, do việc tính toán các chuỗi winternitz riêng lẻ không thể song song hóa, nên thời gian thực hiện (với ước tính phần cứng đã cho) thực tế sẽ là khoảng 2 phút 40 giây. Tôi cảm thấy điều đó vẫn nằm trong yêu cầu "[không] hơn một hoặc hai phút" (và nếu không, hãy mua phần cứng nhanh hơn một chút...)
Vì vậy, chữ ký sẽ bao gồm:
Chữ ký một lần của hàm băm; 4 giá trị băm 10 byte mỗi giá trị = 40 byte
Đường dẫn xác thực; 5 giá trị băm 10 byte mỗi giá trị = 50 byte
Trình băm ngẫu nhiên (mà bạn cần để ngăn chặn các cuộc tấn công va chạm có thể xảy ra; đây là tính ngẫu nhiên mà bạn khuấy vào tin nhắn khi bạn băm nó); 40 bit = 5 byte
Chỉ mục (trên thực tế, bạn có thể bỏ phần này và chỉ cần nhờ người xác minh kiểm tra tất cả các chỉ mục có thể có; tôi không nghĩ rằng khoản tiết kiệm 1 byte là xứng đáng); 1 byte
Tổng cộng: 96 byte (có thể là 86 byte nếu bạn chỉ cần tạo 16 chữ ký)
[1]: Bạn đã xem bộ phim "The Martian" chưa (hoặc tốt hơn là đọc cuốn sách - nó đi vào chi tiết hơn)? Nếu vậy, những gì tôi đang làm giống như những gì Mark Watney đã làm với MAV...
[2]: Đối với những nút lá Merkle mà chúng tôi sẽ không bao giờ sử dụng, chúng tôi thực sự không phải tính toán các khóa công khai một lần đó - thay vào đó, chúng tôi chỉ có thể đặt các giá trị giả. Chúng tôi sẽ không thể ký hợp đồng với họ - chúng tôi không bao giờ có ý định
