В поисках постквантового биткойна

На Хабре уже не впервые поднимается проблема постквантового шифрования, в том числе в контексте криптовалют. Из последнего – около двух месяцев назад тут публиковали новость c FAQ, выпущенном АНБ США о будущем постквантовой криптографии, завершая

Агентство подчеркивает, что его «намерение состоит в том, чтобы… удалить квантово-уязвимые алгоритмы и заменить их подмножеством квантово-устойчивых алгоритмов, выбранных NIST».

Проходив неделю в раздумьях и нагуглив NIST список, меня таки осенила мысль поискать реализации подобных криптовалют.

Я прошерстил списки монет и на большую нашёл работы. Пройдясь поиском по ним на наличие вхождения quant* — как ни странно обнаружил потенциального кандидата с постквантовым шифрованием. Имя мопеду — Tidecoin и согласно Whitepaper он использует алгоритм подписи Falcon, он же кандидат того самого NIST. В 2016 году NIST (англ.: Национальный институт стандартов и технологий) запустил конкурс таких алгоритмов, результаты которого будут объявлены к 2022 году.

Альтернативные варианты

И да, кратко почему не Bitcoin

Bitcoin использует ECDSA, уязвимый к модифицированному алгоритму Шора.

Elliptic curve cryptography is vulnerable to a modified Shor’s algorithm for solving the discrete logarithm problem on elliptic curves.

Bitcoinpq

Немного отходит от стандартов, но крутится около

According to the PQCRYPTO recommendations [18], the digital signature scheme XMSS [19] with parameters from RFC 8391 [20] is used to achieve 128-bit post-quantum cryptography in Bitcoin Post-Quantum. The drawback of the XMSS scheme is that it can generate a limited number of signatures, which depends on the height of the Merkle tree used. In addition to XMSS, the PQCRYPTO recommendations include the SPHINCS [21] scheme, which has no restrictions on the number of signatures. However, for a 128-bit security level, the size of such a signature is about 41 kB, which is too expensive to use in a blockchain and is more suitable for authentication systems. The size of the XMSS signature is about 2.5 kB, which is quite large compared with the ECDSA signature (71 bytes), and requires an increase in the block size; however, this is the most appropriate option for post-quantum signature in a blockchain.

source

Но если глянуть на SPHINCS+ и того самого Андреаса Хёльсинга (Andreas Hülsing), которого активно цитирует Bitcoinpq в своей работе, то кажется, пути начинают расходиться.

SPHINCS+ – The smaller SPHINCS

Over the two years since we published SPHINCS, we collected a lot of nice ideas to reduce the signature size and to speed up the scheme. So, for the NIST submission we reviewed all of them and built SPHINCS+ in the process. SPHINCS+ is SPHINCS in terms of high level scheme design but we tweaked some of the internals — especially the few-times signature scheme.

source

И даже тут (на сайте NIST) в случае Сфинкса как алгоритма цифровой подписи он отнесён к альтернативным вариантам, в то время как Falcon входит в основной список. Сам же Хёльсинг трудится над NTRU (Public-key Encryption and Key-establishment Algorithms) входящий в кандидаты, а также основанной на той самой Криптографии на решётках что и Falcon.

Также проект кажется Bitcoinpq мёртвым (в футере сайта ещё маячит 2018-2019).

Monero — постквант вроде бы осознан.

Но на будущее. Так как я не эксперт в криптографии, мне сложно оценить насколько просто наслоить новое на старое c эллиптическими кривыми, но обещают с минимальными откатами. Что бы это значило — понятия не имею. Призываю сообщество.

Thankfully, post-quantum cryptography has been extensively studied, and we found several schemes to which Monero can be eventually adapted. We identify and describe several promising replacements that offer post-quantum security and privacy with minimal drawbacks, and we note some tradeoffs required for implementation.

source

Lattice-based cryptography stands as the likeliest contender for eventually replacing the now-widespread RSA protocol system, and so should also be looked at as a possible replacement for ECC used in Monero.

Lattice cryptography is not the most disruptive among the range of plausible future-oriented methods.

source

Не конкретная криптовалюта, но платформа IBM Komodo

“Globally, we have around 30 production blockchains that are being run on Komodo platform. However, Komodo also has other blockchains which are not on the Komodo platform but use Komodo exchange for security. We can give any blockchain an additional layer of security. Even Ethereum-based platforms can use Komodo technology,” he said.

source

Входит в NIST как CRYSTALS-DILITHIUM по соседству с Falcon. Также присутствует CRYSTALS-KYBER (Round 3 Finalists: Public-key Encryption and Key-establishment Algorithms)

Почему я вцепился в NIST

NIST — законодатель моды. Это минимум вопрос стандартизации и доверия. Это вопрос репутации, а она как мы знаем важна в финансовых вопросах.

Насколько актуален постквантовый вопрос

Я не знаю насколько хороша Ванга из меня, но мне кажется что хоть постквантовый биткойн это и фантазии, а кто-то и вовсе пишет про плавный приход квантовых компьютеров которые не обрушат Bitcoin рынок (а позволят плавно перейти на новые рельсы)

“quantum supremacy” now doesn’t mean that your encryption or the security of bitcoin is at risk right at this moment.

The real threat is when quantum computers become many scales larger than they currently are

source

Тем не менее ситуация такова, что по факту мы видим инвестиции в квантовые компьютеры, а также обострение напряжения и гонку вооружений Китай-США в отрасли ИИ и аппаратного обеспечения, погоняемые потенциально закрытыми Манхэттенскими проектами и всякими полуоткрытыми DARPA. Про гонку со стороны см. тут.

А также держим в голове наших любимых Чёрных Лебедей Нассима Талеба.

Черный лебель подкрался незаметно (by @brucebmax)

А на вопрос

Ну и когда взломают биткоин?

Наверное это один из главных вопросов, которые возникают при чтении подобных статей. И ответим сразу: взломают нескоро, времени еще много, 10 лет точно есть.

https://habr.com/ru/company/ods/blog/571012/

Времени ещё много, дело понятное, но не когда это просто 10 лет пролетающих как мгновение. Также мы не знаем насколько сильна маркетинговая составляющая того же Google/IBM, способная колыхнуть рынки с потенциально новым кубитным^прыжком. В то время как существует потенциально новый биткойн уже набирающий обороты мегахешами и уже являющийся достаточной альтернативой о которой мы услышим опосля.

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

Хабр же я люблю за его подход к анализу со всех сторон и открытый подход. Собственно буду рад предложениям – наверняка у вас есть что рассказать на эту тему.

NIST кандидаты https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU https://falcon-sign.info/

Tidecoin https://tidecoin.org/

Whitepaper https://raw.githubusercontent.com/tidecoin/whitepaper/master/tidecoin.pdf

 

Источник

Читайте также