Comments 28
все меряются количеством кубитов… На самом деле – это лажа
Сильный аргумент от «профессора физики». Очень научно и корректно.
Поэтому мне кажется, что в XXI веке физика замедлит свое развитие и уступит таким наукам, как кибернетика и биология, потому что в этих науках тайны прямо перед нашим носом: как устроены клетки, как лечить болезни, наследственность и т.д. В технологических вопросах – кибернетика на стыке с биологией. Как работает мозг, как мы мыслим, как заставить машину мыслить, как человек?
Да.
И при этом будет гораздо более ощутимый (не для всех конечно, а для получателя плодов прогресса) эффект — не болеть и думать лучше.
В блокчейне используется криптографическая хеш-функция: каждый последующий блок содержит хеш-функцию предыдущего, благодаря чему сейчас невозможно изменить информацию, хранящуюся в одном из блоков, не нарушая целостности всей цепочки. Квантовый компьютер может сделать вычисление хеш-функции обратимым, то есть сможет подобрать изменение в блоке таким образом, чтобы хеш не изменился.
Странно. А у криптографов другое мнение.
In contrast to the threat quantum computing poses to current public-key algorithms, most current symmetric cryptographic algorithms and hash functions are considered to be relatively secure against attacks by quantum computers.
While the quantum Grover's algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks.
Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography.
вот доделают кубиты, и всем вашим средствам и существующей банковской системе в мировом масштабе наступит моментальный трындец
Я не думаю, что будет трындец, т.к. квантовые вычисления скорее всего будут регулироваться государствами и международными организациями, так же, как наркотики, оружие, атомные и ракетные технологии и т.п.
В первом случае важен контекст — функции используемые в частности в биткоине теоретически подвержены «взлому» со стороны квантовых компьютеров. Однако, да, симметричное шифрование никак не изменится с появлением КК, некоторые чисто хэш-функции — тоже.
Удвоение ключа временное и довольно тяжелое решение. Удвоение ключа дает линейное увеличение сложности для квантового компьютера который будет взламывать, и, квадратичное для всех, кто будет пользоваться этим ключом, если мне не изменяет память.
Существуют задачи, для которых появление КК пройдет почти незаметно. На них строятся системы постквантовой криптографии, даже не залезая на квантовое поле. Есть ли блокчейны на таких системах — я просто не знаю, но учитывая их зоопарк — скорее всего кто-то уже сделал, хотя бы из принципа )
Но при этом еще и экспоненциальное увеличение по времени взлома. Чего вполне достаточно для секьюрности.
Но при этом еще и экспоненциальное увеличение по времени взлома. Чего вполне достаточно для секьюрности.
С чего бы вдруг? Строго говоря, до возникновения настоящих КК разговоры о росте сложности весьма абстрактны, но вообще-то квантовая часть там, если память не изменяет тоже линейна (в ней всего три шага — инициация Уолш-Адамаром, унитарное преобразование вычисления значений и свертка Фурье), а в «классической» самое сложное — проверка результата, что тоже очень далеко от экспоненты.
Кто бы дергался с этими КК в криптографии, если бы рост был экспоненциальным…
симметричное шифрование… хэш-функции
Для симметричных алгоритмов и хэш-функций у КК есть http://ru.wikipedia.org/wiki/Алгоритм_Гровера, который дает лишь квадратичное ускорение. Для классического подбора ключа к aes-256 / прообраза к sha-256 требуется суммарно выполнить N порядка 2^255 операций шифрования/вычисления хэша; для КК — последовательно, точно, в рамках одного квантового регистра без декогеренции, 2^128 операций (sqrt(N)). Теоретически — это прорыв, но на практике таких длительно работающих КК ждать настолько долго, что классический полный перебор остается более приемлемой/практичной атакой в ближайшие десятилетия.
Для многих традиционных ассиметричных схем шифрования есть http://ru.wikipedia.org/wiki/Алгоритм_Шора, дающий экспоненциальное ускорение. Для защиты достаточно не использовать повторно один ключ (адрес), до использования он закрыт двумя хэш-функциями.
Обзор, прогнозы: https://arxiv.org/pdf/1710.10377.pdf Quantum attacks on Bitcoin, and how to protect against them 2017
https://arxiv.org/ftp/arxiv/papers/1711/1711.04235.pdf Bitcoin and quantum computing 2017
The Bitcoin protocol generates addresses by putting the public key through SHA-256 and then through RIPEMD-160. Since the public key is only revealed when the Bitcoins are spent, it becomes vulnerable to an attack by a quantum computer only after the public key is revealed in a transaction. This situation is readily remedied by generating a new address after each transaction (as is current best practice anyway).
Можно и параллельно — запустить алгоритм для набора независимых квантовых регистров, потом каждый промерить. При этом до конца алгоритм доводить не обязательно, тогда вероятность правильного ответа для отдельного регистра не будет максимальной, но, по идее, достаточно увеличится потом за счет того, что регистров много.
Можно и параллельно
От этой параллельности быстрее вычисление не станет.
Автор уже в курсе вашей идеи? https://arxiv.org/pdf/quant-ph/9605043.pdf "Let there be a unique state, say Sν, that satisfies the condition C(Sν) =1, whereas for all other states S, C(S) = 0" (после разбития пространства поиска на 4 части — фиксацией первых 2 битов — только в одной из них будет единица целевой функции и только в этой части сработает алгоритм Гровера. Только вот мы не знаем, в какой именно части он сработал, а в какой мы измеряем шум.)
При этом до конца алгоритм доводить не обязательно
Все равно требуется провести O(sqrt(N)) вычислений ("(the precise number of repetitions is important as discussed in BBHT96)"). Можно пропустить половину, чтобы целевая амплитуда была достаточно большой, ну значит 2^127 операций целевой функции (обратимо и точно). = https://arxiv.org/pdf/quant-ph/9605034.pdf "one must be careful in using his algorithm because the probability of success does not increase monotonically with the number of iterations"
Для нескольких функций с одной точкой f(x)=1 есть такое: http://cds.cern.ch/record/384473/files/9904039.pdf (https://arxiv.org/abs/quant-ph/9904039)
Я говорю про другое. Мы запускаем несколько копий алгоритма (не отдельные биты подбираем в каждой копии, а весь ключ целиком), например, 128. В каждом из 128 случаев не доводим алгоритм до конца, а доводим, например, до 0,1 правильного ответа. Тогда вероятность того, что среди эти 128 не окажется нужного нам ключа — меньше 10^-5, дальше перебираем 128 полученных потенциальных ключей классическим способом и находим среди них нужный.
доводим, например, до 0,1 правильного ответа.
Нельзя произвольно выполнять лишь малую долю от числа итераций целевой функции в алгоритме Гровера — теряется квантовое ускорение (вероятность правильного ответа снижается быстрее, до незначительных величин на фоне вероятностей неправильных ответов). Можно выполнить половину итераций для получения ответа с вероятностью 1/2, но если сделать 1/4 итераций, то вероятность ответа будет значительно ниже.
https://arxiv.org/pdf/quant-ph/9605043.pdf "Section 6 quotes the argument from [BBBV96] that it is not possible to identify the desired record in less than \Omega(sqrt(N)) steps"
BBBV96 — https://arxiv.org/pdf/quant-ph/9605034.pdf#page=2 "In his paper, Grover proves that there exists a number m less than sqrt(2N) such that the probability of success after m iterations is at least 1/2. This is correct, but one must be careful in using his algorithm because the probability of success does not increase monotonically with the number of iterations. By the time you have performed sqrt(2N) iterations, the probability of success has dropped down to less than 9.5% and it becomes vanishingly small after about 11% more iterations before it picks up again. This shows that it is not sufficient to know the existence of m in order to apply the algorithm in practice: its explicit value is needed.… integer number of iterations
… This is very close to (π/4)√N when N is large… It is sufficient to perform half this number of iterations, approximately (π/8)√N, if we are content with a 50% probability of success, as Grover considered in his original paper [4]."
Или вот, формула вероятности правильного ответа от числа итераций — https://en.wikipedia.org/wiki/Grover%27s_algorithm#Geometric_proof_of_correctness each "Grover iteration step rotates the state vector by an angle of \theta = 2 arcsin (1 / sqrt(N))… The exact probability of measuring the correct answer is ( sin( (r+1/2)*\theta ) )^2"
www.wolframalpha.com/input/?i=sin((x+%2B+1%2F2)*2*arcsin(1%2F2%5E128))%5E2,+x+from+10%5E34+to+2.7*10%5E37
получаем 0.025 на одно измерение, тогда для 300 измерений вероятность отсутствия верного ответа будет ~10^-5
Конечно, коэффициент ~10/300 (и с увеличение паралеллизации он будет только падать) не слишком хорош, но сам факт возможного ускорения есть.
Проблема современной квантовой связи в том, что она действует только на коротких дистанциях.
А китайцы блин не знают. Организуя спутниковые сеансы связи
http://russian.news.cn/2018-01/22/c_136914915.htm
2018-01-22
Хэфэй, 22 января /Синьхуа/ — На днях с помощью квантового спутника "Мо-цзы" удалось реализовать межконтинентальное квантовое распределение ключей на расстояние 7600 км между Китаем и Австрией и, тем самым, достичь передачи защищенных данных и установить видеосвязь. Об этом сообщили в Китайском научно-техническом университете /КНТУ/.
Это означает способность спутника "Мо-цзы" к осуществлению межконтинентальной квантовой засекреченной связи, что заложит основу для создания глобальной сети квантовых коммуникаций в будущем. Соответствующая статья была опубликована на днях в международном научном журнале Physical Review Letters — одном из самых престижных журналов в области физики.
Новые научные успехи были достигнуты командой китайских ученых из КНТУ, Шанхайского института технической физики при Академии наук Китая и Государственной астрономической обсерватории совместно с группой ученых из Академии наук Австрии под руководством Антона Цайлингера и др.
16 августа 2016 года Китай запустил спутник для квантовых экспериментов в космическом масштабе /QUESS/, названный "Мо-цзы" в честь китайского философа и ученого, жившего в 5-м веке до н.э.
Почему количество кубитов – «лажа», а квантовая связь действует только на коротких дистанциях