Рейтинг:3

Какие существуют алгоритмы цифровой подписи на основе хэшей, которые имеют достаточно небольшие размеры подписи?

флаг cn

Какие существуют алгоритмы цифровой подписи на основе хэшей, которые имеют достаточно небольшие размеры подписи?

  • Под разумно маленьким я подразумеваю не намного больше, чем то, что вы получили бы с 256-битным ECDSA (который, как я полагаю, имеет сигнатуру около 64 байт). Если ничего близкого не существует, то какой наименьший размер подписи я могу получить?

  • Я хочу 128-битную безопасность или лучше (хотя это не является жестким требованием).

  • Я буду подписывать блоки данных размером 128 байт или меньше.

  • Эффективность вычисления ключей или подписи не является основным фактором, если только это не займет больше минуты или двух для блока размером 128 байт.

  • Схема подписи не обязательно должна быть широко используемой, стандартизированной каким-либо авторитетным органом или совместимой с какими-либо другими системами. Мне нужно только, чтобы копии моего собственного кода могли генерировать и проверять подписи. Так, например, приемлемо что-то из рецензируемой исследовательской работы.

  • Предположим, что я хочу выпустить около 10-20 подписей, а затем навсегда выбросить закрытый ключ.

Схемы, основанные на деревьях Меркла, казалось бы, исключены, потому что нужно включать много хэшей для узлов авторизации. И это имеет тенденцию делать подпись намного больше (много тысяч битов).

флаг cn
Дерево Меркла, поддерживающее 16 подписей (то есть в пределах вашего диапазона), будет иметь только высоту 4. Поэтому, если схема подписи может иметь состояние, это не должно быть так уж плохо.
user4574 avatar
флаг cn
@Maeher План состоял в том, чтобы один человек нажал кнопку и подписал сразу целую партию предметов, чтобы доказать, что все они получены из одного и того же источника. После этого закрытый ключ выбрасывается. Таким образом, не должно быть необходимости отслеживать состояние дольше, чем требуется программе для запуска после нажатия кнопки.
Рейтинг:3
флаг my

Ну, я полагаю, что если вы В самом деле обрежьте все [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]: Для тех листовых узлов Меркла, которые мы никогда не будем использовать, нам фактически не нужно вычислять эти одноразовые открытые ключи — вместо этого мы можем просто ввести фиктивные значения. Мы не сможем с ними подписать - мы никогда не собираемся

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.