Восстановление строгих доказательств безопасности SPHINCS+

В 2020 году Кудинов, Киктенко и Федоров указали на недостаток в доказательстве надежности конструкции SPHINCS . В данной работе представлено новое доказательство надежности для SPHINCS . Недостаток можно проследить до доказательства надежности схемы одноразовой подписи Winternitz (WOTS), используемой в SPHINCS . В данной работе мы предоставляем самостоятельное описание варианта WOTS, используемого в SPHINCS , который мы называем WOTS-TW. Мы предлагаем доказательство надежности для WOTS-TW и многократного использования WOTS-TW против неадаптивных атак с выбранными сообщениями, где злоумышленник узнает только открытый ключ после запроса на подпись. Затем мы показываем, что это достаточно для получения доказательства надежности SPHINCS . Мы получаем почти такую же оценку для безопасности SPHINCS , с потерей только фактора w по сравнению с ранее заявленной оценкой, где w - параметр Winternitz, обычно установленный равным 16. На более техническом уровне мы вводим новые нижние оценки для квантовой сложности запроса для общих атак на свойства криптографических хэш-функций и анализируем построение изменяемых хэш-функций, используемых в SPHINCS , с учетом дополнительных свойств безопасности. Дата записи: 22 ноября 2023. Докладчик: Михаил Кудинов, аспирант Технического университета Эйндховена. Научный семинар организован совместными усилиями МФТИ, Сколтеха и ВШЭ и рассчитан как на специалистов в области блокчейна, так и интересующихся этим направлением исследователей. #blockchain #blockchaintechnology #блокчейн #MIPT #МФТИ #HSE #ВШЭ #Сколтех #Skoltech #sphincs #криптографическаяподпись #хэшфункция #дверевохэшей #одноразоваяподпись #постквантоваякриптография #квантоваяугроза #cryptographicsignature #hashfunction #merkletree #onetimesignature #postquantumcryptography #quantumthreat