Перевод Практические стратегии Monero в постквантовом мире

Тема в разделе "Статьи", создана пользователем Mr. Pickles, 16 май 2020.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    740
    Симпатии:
    223
    logo.png
    Причины исследования

    При создании транзакций Monero в период с 2014 по 2020 год использовались криптографические механизмы, не обеспечивающие должной приватности или защиты от квантовых компьютеров. Существуют алгоритмы, которые теоретически уже могли бы нейтрализовать некоторые из мер, используемых Monero в целях защиты и сохранения приватности пользователей. Примером могут служить алгоритм Шора (который разрушает защиту путём решения задачи дискретного логарифмирования) и алгоритм Гровера (который можно использовать для подделки блоков).

    Давайте определим гипотетический «практический» квантовый компьютер как любое устройство, по сути, позволяющее злоумышленнику справиться с ожидаемым уровнем безопасности, обеспечиваемым криптографическими механизмами. Такое устройство не определяется каким-то волшебным количеством кубитов или какой-либо конкретной конфигурацией; в данном случае речь идёт о способности использовать такие методы, как фишинг методом Фурье, алгоритм Гровера или алгоритм Шора, уровень сложности которых достаточен для того, чтобы справиться с современной криптографической защитой. Вероятность и время появления практических квантовых компьютеров в этом криптографическом исследовании не рассматриваются.

    Существует несколько способов, прибегнув к которым, опытный злоумышленник, использующий квантовое устройство, сможет получить доступ к финансовым средствам и чувствительной информации, которая в ином случае была бы криптографически скрыта от него:
    • Выведение приватных ключей на основе публичных. Злоумышленник, использующий квантовое устройство и знающий публичный адрес вашего кошелька, на основе этой информации может вывести и ваш приватный ключ. Это позволит такому злоумышленнику узнать всю (прошлую и последующую) историю ваших транзакций и похитить любые имеющиеся/будущие средства, подделав соответствующую транзакцию для перевода этих средств от вашего имени себе.
    • Выведение приватных ключей на основе образов ключей. Злоумышленник, использующий квантовое устройство, также может нарушить приватность некоторых данных транзакций, уже записанных в реестре, путём выведения приватных ключей транзакций на основе образов ключей.
    • Деобфускация графа транзакции. Каждая кольцевая подпись использует несколько (в настоящее время 11) прошлых выходов, только один из которых тратится на самом деле. Деобфускация предполагает анализ фактического потока средств с целью нейтрализации приватности, обеспечиваемой кольцевыми подписями и скрытыми адресами. Некоторые виды анализа, основанные на сопоставлении графов, уже являются параллелизуемыми для традиционных компьютеров, а значит, эта задача будет гораздо проще для квантовых устройств.
    • Механизм консенсуса и неизменяемость блокчейна. Алгоритм доказательства работы, используемый Monero (RandomX), предполагает выполнение VM цепочки из нескольких (в настоящее время 8) операций и работает как односторонняя функция (поэтому вход, необходимый для создания конкретного выхода, можно найти только методом перебора). Мы оценим, можно ли использовать этот подход в случае с квантовыми компьютерами, применяющими такие способы, как фишинг методом Фурье или алгоритм Гровера. Потенциальная возможность поделки блоков с определённым хешем ставит под угрозу неизменяемость блокчейна. Тем не менее этого можно избежать путём добавления (то есть последовательного включения) постквантовых хеш-функций и контрольных сумм.
    Возможность ретроактивной деанонимизации отдаёт безопасность уже существующих сегодня пользователей Monero в руки будущих [квантовых ли классических] злоумышленников. Если в какой-то момент в будущем появятся практически применимые квантовые компьютеры, способные взломать систему шифрования Monero, то абсолютно вся история транзакций пользователей станет публичной, и ею смогут воспользоваться представители AdTech индустрии, охотники за личной информацией, преступники и правительства. Не имеет значения, кто первым опубликует деанонимизированную копию блокчейна Monero — глобальный ущерб приватности станет неизбежным.

    К счастью, криптографами было разработано несколько схем обеспечения безопасности и приватности в постквантовом мире, и эти схемы могут быть использованы Monero. Среди перспективных технологий можно выделить криптографию на основе теории решёток с нулевым разглашением, базирующуюся на решении задачи нахождения кратчайшего вектора. Такие методы, как те, что предполагают использование кольцевых подписей на базе хешей, GLYPH (схемы подписи подобной подписи Шнорра, основанной на теории решёток), и целая когорта потенциальных постквантовых схем NIST, были разработаны специально в целях обеспечения безопасности в постквантовом мире. Устойчивый к применению квантовых устройств реестр представляет собой определённый интерес из-за возможности его расширения, неизменяемости и возможности реализации RandomX. Однако до этого момента ещё не было реализовано никаких возможностей, направленных на сохранение приватности. Рассматривались и другие варианты анонимной постквантовой криптовалюты, а рекурсивная система доказательства с нулевым разглашением Halo обеспечивает приемлемую постквантовую безопасность. Каждый из подходов обладает своими преимуществами, недостатками и характерными сложностями, связанными с требуемым местом/временем. В наших рекомендациях мы учитываем эти практические вопросы в сочетании с теоретической совместимостью.

    В рамках данного исследования мы (1) изучаем и моделируем перечисленные выше угрозы, чтобы оценить уязвимость Monero к применению квантовых компьютеров; (2) оцениваем возможные постквантовые криптографические схемы, чтобы создать дорожную карту усиления Monero против злоумышленников, использующих квантовые устройства; (3) открыто публикуем результаты для самой широкой аудитории.

    Появление мощных квантовых компьютеров принесёт разрушение практически для каждого аспекта нашей цифровой инфраструктуры. Доступ к твёрдой валюте (требующий анонимности) является фундаментальным человеческим правом и должен рассматриваться в качестве высокоприоритетной задачи при усилении мер противодействия «квантовым злоумышленникам». Насколько нам известно, в настоящее время в обращении не находится каких-либо действительно устойчивых к применению постквантовых устройств анонимных валют, а это означает, что при существующей технологии финансовая анонимность будет обеспечена лишь в краткосрочной, максимум среднесрочной, перспективе. Первая монета, в которой будут реализованы долгосрочные возможности противодействия применению постквантовых методов, займёт сильные позиции задолго до того, как появятся квантовые компьютеры.

    Обзор

    Научно-исследовательская организация: Insight

    Финансирование: Monero CCS

    Длительность исследования: 3 месяца (июнь-август 2020)

    Контрибьюторы:
    • Исследователь: Адам Корбо (Adam Corbo)
    • Исследователь проблемы децентрализованного консенсуса в Insight
    • Разработчик квантового опенсорс PoW майнера с доказательством концепции
    • Экспертный перевод результатов академических/математических исследований в код
    • 2 года исследовательской работы в области теории квантовой информации и вычислений в UC Berkley
    • Ведущий исследователь: Митчелл Кравиц-Тейер (Mitchell Krawiec-Thayer)
    • Ведущий исследователь и разработчик в Insight
    • Исследования в области данных для Исследовательской лаборатории Monero (Monero Research Lab)
    • Квантовые классы и вычисления, кандидатская работа (в контексте исследований по спектроскопии)
    • Другие контрибьюторы Insight
    • Редакторы кода и документации будут определены на более поздних этапах ближе к завершению проекта.
    • Отдельная благодарность сотрудникам офиса, бухгалтерии и всем остальным за создание продуктивной рабочей обстановки.
    Дорожная карта проекта

    Этап 1. Выявление и документирование существующих уязвимостей Monero

    На первом этапе решения этой проблемы наше внимание будет сфокусировано на идентификации тех механизмов обеспечения безопасности Monero, которые могут оказаться уязвимыми для злоумышленников, использующих квантовые устройства. Мы найдём слабые места с точки зрения применения таких известных инструментов, как алгоритм Шора (который позволяет вычислять дискретные логарифмы за полиномиальное время, что снимает защиту, связанную с решением задачи дискретного логарифмирования), алгоритм Гровера (который обеспечивает квадратическое ускорение при поиске входов, соответствующих определённому выходу для функций чёрного ящика), а также фишинг по методу Фурье в сочетании с алгоритмом Дойча-Йожи (который потенциально может выгодно для себя использовать метод доказательства работы Monero за квантовое полиномиальное время с ограничением ошибок).

    Нам уже известны некоторые уязвимости, как, например, то, что криптографические схемы на основе эллиптических кривых и задачи дискретного логарифмирования становятся небезопасны, если используется алгоритм Шора. Мы изучим протокол Monero, чтобы найти другие примеры, когда безопасность обеспечивается за счёт решения задач, которые трудно решаемы при помощи классических компьютеров, но с которыми с лёгкостью смогут справиться квантовые устройства. Некоторые из существующих возможностей обеспечения приватности считаются устойчивыми к решению при помощи квантовых компьютеров (такие как сокрытие сумм Monero), и мы тщательно проверим, насколько они защищены от алгоритмических инструментов, доступных злоумышленнику.

    Результаты реализации этапа 1
    • Формальное перечисление возможностей вредоносной модели: алгоритма Шора, алгоритма Гровера, фишинга по методу Фурье и т. д.
    • Перечисление механизмов Monero, представляющих интерес: кольцевых подписей, доказательств Bulletproofs, скрытых адресов, асимметричной криптографии, механизма консенсуса и т. д.
    • Систематическая оценка влияния каждого алгоритма на каждый из механизмов в следующей таблице:

    _Механизм Monero 1Механизм Monero 2...
    Алгоритм ШораПриемлемо безопасенПриемлемо безопасен...
    Алгоритм ГровераНеприменимоУЯЗВИМ...
    Фишинг методом ФурьеПриемлемо безопасенНеприменимо...
    ............
    Этап 2. Исследование совместимых с Monero методов постквантовой криптографии

    После выявления и документирования квантовых уязвимостей Monero мы займёмся поиском альтернативных криптографических схем, которые позволят устранить эти слабые стороны. Известные постквантовые системы будут исследованы на предмет совместимости с Monero (см. Приложение 1, в котором нами приводится список соответствующей литературы, требующей изучения). Помимо интероперабельности, нами также будут рассмотрены вопросы, связанные со временем верификации, размером подписи/доказательства и реализацией. В случае отсутствия каких-либо решений, позволяющих избежать определённой уязвимости, нами будут указаны ограничения, необходимые для разработки уникального решения.

    Существует три широкие категории воздействия, являющиеся взаимоисключающими:
    • деанонимизация (когда вам известно о чужих транзакциях больше, чем следовало бы);
    • кража (возможность хищения чужих средств);
    • ускорение майнинга (получение действительных нонсов с парадигматически более высокой скоростью).
    Уязвимым механизмам обеспечения приватности будет уделяться особое, приоритетное внимание, так как ретроактивная деанонимизация представляет собой угрозу для уже существующих на сегодняшний день пользователей, в то время как кража и майнинг не представляют собой проблемы до тех пор, пока уровень квантовых компьютеров не преодолеет пока ещё далёкого порога. Уязвимости, связанные с майнингом, имеют самый низкий приоритет, так как изменить механизмы консенсуса проще, чем реализовать новые криптографические схемы.

    Важно отметить, что многие из существующих сегодня возможных постквантовых криптографических схем требуют объёмного доказательства и значительных вычислительных ресурсов, и поэтому их нельзя будет реализовать сразу же. Поэтому понимание общих стратегий и связанных с ними компромиссов будет полезнее конкретных вариантов реализации. К счастью, возможности потребительских устройств растут с течением времени, и исследователи продолжают находить новые более быстрые/компактные системы доказательства, так что эти практические препятствия имеют временный характер.

    Результаты реализации этапа 2. Список уязвимостей (по возможности в приводимом ниже формате)
    Этап 3. Обратная связь и обучение

    В течение всей реализации проекта сообщество в рамках еженедельных встреч #monero-research-lab будет получать новости о последних обновлениях. Тем не менее во время этапа 3 будет опубликовано и выложено в общий доступ три документа (три ключевые результата этого исследования):

    Результаты реализации этапа 3
    1. Подробное удобочитаемое описание. Данное предназначенное для сообщества описание будет представлять собой понятное объяснение того, как гипотетические квантовые компьютеры могут повлиять на Monero, а также объяснение потенциальных вариантов защиты от такого воздействия. Описание должно будет свести к минимуму FUD (опасения, неуверенность и сомнения), а также обозначить контекст, в котором эти уязвимости будут соотноситься практически со всеми криптовалютами (не только Monero).

    2. Техническая документация. Докладная записка MRL будет содержать исключительно ключевую информацию для нынешних и будущих исследователей и разработчиков. В документе должны быть формально описаны уязвимости, а также должны быть указаны возможные стратегии и решения, равно как и связанные с ними компромиссы. При необходимости (в образовательных целях или для ясности) сюда могут быть включены отрывки кода.

    3. Нетехническая односторонняя презентация. Краткое ELI5/TL;DR описание для журналистов, команды Monero Outreach и т. д. В этой аннотации должны быть описаны соответствующие риски и мифы, ключевые отправные точки, и всё это должно быть написано нетехническим, понятным широкой аудитории языком.
    Информация по результатам и обновлениям также будет распространяться через Twitter, Reddit и в видеороликах Monero.

    Ресурсы

    Команда, которая занимается этим проектом, состоит из одного штатного исследователя, занимающегося исключительно этим предложением (Адам), и руководителя в лице Митчелла, который также занимается оформлением документации (занятость — 5-15 часов в неделю). Кроме того, нам помогают директор по безопасности и наши собственные редакторы. Мы планируем реализовать эту инициативу в течение двенадцати недель (с июня по август 2020) за 37 500 долларов США.

    Счета Insight и зарплата сотрудникам указываются в долларах, так как нам необходимо минимизировать риски, связанные с деноминацией. Для нас будут приемлемыми три подхода, и мы предлагаем сообществу выбрать любой из них:
    1. Если оплата может быть получена только по завершении работы, нам придётся добавить буфер с учётом волатильности (см. TL;DR пояснение и открытый код). С учётом данных, накопленных за последние два года, а также окна в 4 месяца (1 месяц для сбора средств + 3 месяца на исследования), буфер в размере 35% обеспечит 80% статистическую гарантию получения достаточной оплаты. Таким образом, сумма, которую необходимо собрать посредством CCS, составляет дополнительные 4375 USD в месяц.

    2. Если средства могут быть получены в начале исследований, то в буфере не будет никакой необходимости.

    3. Средства (во избежание рисков, связанных с волатильностью, в фиате) могут быть переданы на хранение какой-либо третьей доверенной стороне, а затем выплачены Insight за удовлетворительно проделанную работу.
    Приложения и литература

    Ниже приводится список литературы, которая будет изучена и аннотирована для дальнейшего использования Monero. Список составлен доктором Брэндоном Гудделом (Brandon Gooddell).
    • Джозеф К. Лиу (Liu, Joseph K.), Виктор К. Вей (Victor K. Wei) и Дункан С. Вонг (Duncan S. Wong), «Связываемая спонтанная анонимная групповая подпись для специальных (ad hoc) групп» (Linkable spontaneous anonymous group signature for ad hoc groups). Австралийская конференция по информационной безопасности и приватности данных (Australasian Conference on Information Security and Privacy). Springer, Берлин, Гейдельберг, 2004.
    • Жанг, Хуанг и др. (Zhang, Huang, et al.), «Анонимная постквантовая криптовалюта» (Anonymous post-quantum cryptocash). Международная конференция по финансовой криптографии и защите данных (International Conference on Financial Cryptography and Data Security). Springer, Берлин, Гейдельберг, 2018.
    • Торрес, Уилсон Абель Альберто и др. (Torres, Wilson Abel Alberto, et al.), «Постквантовая одноразовая связываемая кольцевая подпись и её применения в кольцевых конфиденциальных транзакциях в блокчейне (RingCT v1.0)» (Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice RingCT v1.0)). Австралийская конференция по информационной безопасности и приватности данных (Australasian Conference on Information Security and Privacy). Springer, Шам, 2018.
    • Грот, Йенс и Маркус Кёльвиц (Groth, Jens, and Markulf Kohlweiss), «Доказательства по одному из многих или как узнать секрет и потратить монету» (One-out-of-many proofs: Or how to leak a secret and spend a coin). Ежегодная международная конференция по теории и практическому применению криптографических методов (Annual International Conference on the Theory and Applications of Cryptographic Techniques). Springer, Берлин, Гейдельберг, 2015.
    • Чопра, Арджун (Chopra, Arjun), «GLYPH: новый вариант реализации схемы цифровой GLP подписи» (GLYPH: A New Instantiation of the GLP Digital Signature Scheme). Архив электронных документов по криптологии IACR 2017 (IACR Cryptology ePrint Archive 2017), (2017):766.
    • Доминик Унрух (Unruh, Dominique), «Постквантовый протокол безопасности Фиата-Шамира» (Post-quantum security of Fiat-Shamir). Международная конференция по теории и практическому применению криптологии и информационной безопасности (International Conference on the Theory and Application of Cryptology and Information Security). Springer, Берлин, Гейдельберг, 2017.
    • Окамото, Тацуаки и др. (Okamoto, Tatsuaki, et al.), «Новые варианты реализации статистически связанного хеширования и позиционных аккумуляторов» (New realizations of somewhere statistically binding hashing and positional accumulators). Международная конференция по теории и практическому применению криптологии и информационной безопасности (International Conference on the Theory and Application of Cryptology and Information Security). Springer, Берлин, Гейдельберг, 2015.
    • Ксинге Лю (Lu, Xingye), Мэн Хо О (Man Ho Au) и Женьфей Жанг (Zhenfei Zhang), «(Связываемая) кольцевая подпись на базе подписи с однонаправленным хешированием» ((Linkable) Ring Signature from Hash-Then-One-Way Signature), 18-я международная конференция по доверию, безопасности и приватности в вычислительной технике и коммуникациях 2019 / 13-я международная конференция IEEE по изучению и технологиям больших данных (TrustCom/BigDataSE) (2019 18th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/13th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE)). IEEE, 2019.
    • Майкл Бейкс и др. (Backes, Michael, et al.), «Кольцевые подписи: логарифмическое масштабирование при отсутствии настроек со стандартными допусками» (Ring signatures: Logarithmic-size, no setup—from standard assumptions). Ежегодная международная конференция по теории и практическому применению криптографических методов (Annual International Conference on the Theory and Applications of Cryptographic Techniques). Springer, Шам, 2019.
    • Рупенг Янг и др. (Yang, Rupeng, et al.), «Эффективные аргументы на основе теории решёток с нулевым разглашением и стандартной достоверностью: построение и применение» (Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications). Ежегодная международная конференция по криптологии (Annual International Cryptology Conference). Springer, Шам, 2019.
    • Мухаммед Ф. Эсгин и др. (Esgin, Muhammed F., et al.), «MatRiCT: протокол эффективных, масштабируемых постквантовых блокчейн-транзакций» (MatRiCT: Efficient, Scalable and Post-Quantum Blockchain Confidential Transactions Protocol). Материалы конференции ACM SIGSAC по компьютерной безопасности и безопасности передачи данных 2019 (Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security). 2019.
    • Торрес, Уилсон Альберто и др. (Torres, Wilson Alberto, et al.), «Кошельки, поддерживающие протокол RingCT v2.0 на основе теории решёток с множеством входов и выходов» (Lattice RingCT v2. 0 with Multiple Input and Multiple Output Wallets). Австралийская конференция по информационной безопасности и приватности данных (Australasian Conference on Information Security and Privacy). Springer, Шам, 2019.
    • Тим Руффинг и Джулио Малавольта (Ruffing, Tim, and Giulio Malavolta), «Коммутируемые обязательства: безопасная коммутация конфиденциальных транзакций» (Switch commitments: A safety switch for confidential transactions). Международная конференция по финансовой криптографии и защите данных (International Conference on Financial Cryptography and Data Security). Springer, Шам, 2017.
    • Жанг, Хуанг и др. (Zhang, Huang, et al.), «Анонимная постквантовая криптовалюта» (Anonymous post-quantum cryptocash). Международная конференция по финансовой криптографии и защите данных (International Conference on Financial Cryptography and Data Security). Springer, Берлин, Гейдельберг, 2018.
    • Жанг, Хуанг и др. (Zhang, Huang, et al.), «Реализация конфиденциальных транзакций с использованием технологий на основе теории решёток» (Implementing confidential transactions with lattice techniques). Информационная безопасность IET 14.1 (IET Information Security). 14.1 (2019):30-38.
    Источник: Research post-quantum strategies for Monero

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
    #1 Mr. Pickles, 16 май 2020
    Последнее редактирование: 16 май 2020
  • О нас

    Наш сайт является одним из уникальных мест, где русскоязычное сообщество Monero может свободно общаться на темы, связанные с этой криптовалютой. Мы стараемся публиковать полезные мануалы и статьи (как собственные, так и переводы с английского) о криптовалюте Monero. Если вы хорошо владеете английским (или можете писать собственные статьи/мануалы) и хотите помочь в переводах и общем развитии Monero для русскоязычной аудитории - свяжитесь с одним из администраторов.