Ну, я полагаю, что если вы В самом деле обрежьте все [1], вы можете уменьшить размер подписи чуть менее чем до 100 байт. Вот как я скорректировал ваши требования:
Я хочу 128-битную безопасность или лучше (хотя это не является жестким требованием).
Поскольку вы сказали, что это не было жестким требованием, я сбросил его на 80-битную безопасность (если вы сделаете это со 128-битной безопасностью, вы получите подпись размером около 200 байт). Ориентируясь на 80-битную безопасность, мы можем использовать 80-битные хэши (например, SHA-256, усеченный до 80 бит — мы могли бы попытаться использовать более быструю хеш-функцию с меньшим уровнем безопасности, однако это ускоряет работу лишь в незначительном разе, поэтому я не ожидаю, что это нас много купит).
Я буду подписывать блоки данных размером 128 байт или меньше.
Не ошибка
Схема подписи не обязательно должна быть широко используемой, стандартизированной каким-либо авторитетным органом или совместимой с какими-либо другими системами.
Никто не настолько безумен, чтобы стандартизировать этот подход
Эффективность вычисления ключей или подписи не является основным фактором, если только это не займет больше минуты или двух для блока размером 128 байт.
Что ж, вычисление открытого ключа — это длинный полюс, поэтому я возьму на это двухминутное ограничение. Тем не менее, вы не сказали, что это за железо, поэтому я предполагаю, что там достаточно агрессивное железо - 8 быстрых ядер с оборудованием AVX512 (на самом деле мы могли бы пойти более агрессивно с выделенным оборудованием, однако это не позволило бы нам уменьшить подпись такая)
Предположим, что я хочу выпустить около 10-20 подписей, а затем навсегда выбросить закрытый ключ.
Я предполагаю, что 20 подписей — это максимум (максимум 16 позволит нам уменьшить размер подписи еще на 10 байт).
Хорошо, вот что мы делаем: мы начинаем с дизайна LMS/XMSS (либо модифицируя LMS, чтобы обеспечить больший W-фактор, либо удаляя битовую маску XMSS и перемешивая местоположение другим способом); тогда:
У нас есть цель 20 подписей; это подразумевает высоту Меркла, равную 5 (которую мы могли бы сократить до 4, если бы мы могли предположить максимум 16 подписей)
Измерение на моем процессоре Xeon показывает, что одно ядро с его инструкциями AVX2 может вычислять 6,6 млн хэшей в секунду; если бы мы использовали более быстрый процессор с инструкциями AVX512, мы, вероятно, могли бы получить до 20 миллионов хэшей в секунду. У нас 8 ядер, и у нас есть 120 секунд на вычисление ключей, поэтому мы успеваем вычислить не совсем 20 миллиардов хэшей.
Теперь нам нужно сгенерировать 20 публичных ключей одноразовой подписи [2] (а все остальное сравнительно тривиально) — так что у нас есть время почти на 1 миллиард хэшей на одну одноразовую подпись.
Если мы используем значение Винтерница $W \приблизительно 200 000 000$, что позволило бы нам закодировать около 27 бит. Теперь хэш, который подписывает одноразовая подпись, составляет 80 бит; это означает, что при кодировании с постоянной суммой мы должны легко сгенерировать 4 цифры с основанием 200 000 000 (метод; передать значение, подписываемое в SHAKE; сгенерировать 3 цифры с основанием 200 000 000; посмотреть, есть ли четвертая цифра, такая, что сумма является целью ; если нет, то вернитесь назад и сгенерируйте больше цифр)
- На самом деле, поскольку вычисление отдельных цепей Винтернитца невозможно распараллелить, затраченное время (с заданными аппаратными оценками) фактически составит около 2 минут 40 секунд. Я чувствую, что это все еще в пределах требования «[не] более минуты или двух» (а если нет, получите немного более быстрое оборудование...)
Итак, подпись будет состоять из:
Одноразовая подпись хеша; 4 хэша по 10 байт = 40 байт
Путь аутентификации; 5 хэшей по 10 байт = 50 байт
Рандомизатор хэша (который вам нужен для предотвращения возможных атак столкновений; это случайность, которую вы добавляете в сообщение, когда хэшируете его); 40 бит = 5 байт
Индекс (на самом деле, вы можете отказаться от этого и просто попросить верификатора проверить все возможные индексы; я не думаю, что экономия в 1 байт того стоит); 1 байт
Итого: 96 байт (с возможностью 86 байт, если вам нужно сгенерировать только 16 подписей)
[1]: Вы смотрели фильм «Марсианин» (или, что еще лучше, читали книгу — в ней более подробно)? Если да, то то, что я делаю, очень похоже на то, что Марк Уотни сделал с MAV...
[2]: Для тех листовых узлов Меркла, которые мы никогда не будем использовать, нам фактически не нужно вычислять эти одноразовые открытые ключи — вместо этого мы можем просто ввести фиктивные значения. Мы не сможем с ними подписать - мы никогда не собираемся
