Очевидно чем сложнее и уникальнее схема, тем меньше тех, кто разберется во всех тонкостях, и тем вероятнее наличие в ней опасных уязвимостей, как например было с zk-SNARK.
Данный баг вроде как пофиксили, но кто поручится, что багов в этой схеме (и др. сложных) не осталось?
Так изначально здесь и спрашивали в т.ч. за Гровера, правда относительно «реверса хеш-функций» (см. по ветке выше) ;).
Разумеется GSA (в отличие от алгоритма Шора) не даст «экспоненциального ускорения» (и вообще вряд ли потянет), необходимого при факторизации (дискретном логарифмировании/соотв. EC-задачах) на размерностях порядка современных ключей. Речь не про это.
«Измененный алгоритм Гровера» из статьи (хотя повторяю, к нему есть вопросы например в части масштабируемости, универсализации, скорости и т.д.) на реальных примерах показывает, что требуемое число кубитов может быть существенно меньше, чем «длина ключа (в битах)». Хотя бы для некоторых (частных) задач определенной размерности.
Как мы можем быть уверены, что невозможны подобные (или иные) оптимизации алгоритмов Гровера и/или Шора (или их модификации или вообще новые квантовые алгоритмы) для эффективного решения «серьезных» полноразмерных задач, но с «пониженным потреблением» кубитов? Имеются ли принципиальные препятствия к этому?
КМК, вы не учитываете, что квантовые алгоритмы постоянно совершенствуются.
Например здесь пишут, что даже на 2 и 4 кубитах на реальном КК можно разлагать на сомножители достаточно большие числа:
we have experimentally factorized the integers 4088459 and 966887, using 2 and 4
qubits respectively
Конкретно к данному алгоритму есть вопросы, но тем не менее. К тому же есть и другие, где число используемых кубитов меньше чем размер ключа (в битах).
Хм…
Вообще-то математическое доказательство абсолютной криптостойкости шифра Вернама от К. Шеннона давно опубликовано, считается без тени сомнения полным, строгим и верным (по крайней мере среди профессиональных криптографов и ни кем из них ни когда серьезно не оспаривалось), более того, это азы криптографии.
Сравните это доказательство с частичными исследованиями на криптостойкость по определенным параметрам/от определенных (известных) атак для гост, aes, dsa, ecdsa и т.п.
И надо ли еще риторический вопрошать: где в этом ряду находятся доводы типа «одна тетка сказала» или там «мамой клянусь» например в пользу того же госта?
только ГОСТы математически доказаны, как криптостойкие, для остальных математического доказательства нет
Про госты, aes, dsa и т.п. вряд ли можно сказать, что они имеют математическое док–во криптостойкости, скорее они исследованы на криптостойкость по ряду параметров/на защиту от некоторых (известных) атак. А вот например шифр Вернама считается системой с абсолютной криптографической стойкостью. Квантовая криптография так же считается доказанно защищенной законами квантовой физики.
Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. В ближайшее время исследователи собираются изготовить чипы с десятками тысяч каналов, чтобы амёба могла попробовать решить задачу коммивояжера на сотнях городов
Мне одному кажется, что «линейный рост» до 8 городов — это «ниачем»? ;)
Нет, я вполне согласен с тем, что амебы, пчелы, муравьи за многие миллионы лет эволюции могли выработать эффективные алгоритмы поведения, которые интересно изучать и в определенных случаях извлекать пользу от их применения. Но насколько хватит условных ресурсов амеб (пчел, муравьев) для сохранения «линейного роста» при практически значимых действительно больших N, когда «количество вариантов решения увеличивается экспоненциально» (от N)?
К сожалению ответа в статье нет и нам предлагается лишь ждать (надеяться и верить), когда они «изготовят чипы»,
чтобы «амёба могла попробовать решить задачу коммивояжера на сотнях городов»…
Вполне возможно, что ssl/tls до появления эффективных КК успеет перейти на постквантовые алгоритмы (см. к примеру https://openquantumsafe.org/). Однако нужно уже сейчас (и в общем-то давно пора) принимать во внимание, что квантово уязвимый ssl/tls трафик может быть записан некой «Евой» с целью расшифровки с помощью КК в будущем (вдруг зашифрованная информация не потеряет актульности к тому времени).
Именно так. Т.е. если будет взломано шифрование на открытых ключах, используемое для обмена ключами для последующего симметричного шифрования, то симметричное шифрование конечно уже не спасет (
Эверетт — это интерпретация квантовой механики, а в посте про космологию
Вроде бы принципы КМ вполне используются в современной космологии (даже есть термин «квантовая космология», известные труды в этой области А.Д. Линде, Лоуренса Краусса и т.д.). Почему интерпретация Эверетта (я не говорю верная ли она или нет) или другие интерпретации КМ не могут иметь отношения к космологии?
Квантовый блокчейн за счет параллелизма может мгновенно найти такое число, при котором хеш блока будет недосягаемо мал для классических вычислителей/blockquote>
С помощью какого именного квантового алгоритма авторы статьи считают, что «можно мгновенно найти такое число» (в допущении, что есть доступ к универсальныму КК с тысячами или сколько нужно кубитов)?
Когда вы двигаетесь со скоростью света, то это значит, что:
• Вы в принципе не можете обладать массой. Если бы вы ею обладали, вы бы переносили бесконечное количество энергии. Вы обязаны быть безмассовым.
Правильно ли я понимаю, что измеряя насколько макс. скорость некой частицы меньше скорости света, можно судить о ее массе? Например, нейтрино?
В последнее время квантовые идеи помогли исследователям доказать безопасность многообещающих технологий шифрования под названием «криптография на решётках»
… британские криптографы уже давно, с начала 2000-х годов, занимаются разработкой квантово-безопасных алгоритмов, но и в подробностях описал одну из особо удачных, как казалось, схем такого рода – построенную в 2007 году на основе так называемых числовых циклических решеток. К сожалению, затем выяснилось, что данный криптоалгоритм – получивший от авторов имя Soliloquy – далеко не так силен, как предполагалось. В течение 2010-2013 годов для его эффективного взлома была придумана теоретическая атака с помощью квантового компьютера, а потому в итоге от алгоритма пришлось полностью отказаться.
При этом важно, что решение о полном отказе – а не об усилении-модернизации красивой конструкции – было в основном принято спецслужбой из-за очень мощной и сильно впечатлившей англичан атаки, разработанной в 2013 году группой исследователей открытого академического сообщества. В работе этих авторов (K. Eisentraeger, S. Hallgren, A. Kitaev, and F. Song. «A quantum algorithm for computing the unit group of an arbitrary degree number field». In STOC ACM, 2014) описывается существенно новая квантовая атака весьма общего типа, накрывающая, в частности, широкий круг «постквантовых» криптосхем, включая и никому неведомый в ту пору Soliloquy…
Лично мне не особо понятно, всю ли «криптографию на решетках» накрывает эта атака, если она действительно существует (сцылки в статье битые, да и сам этот Берд Киви не особо внушает...),
но если из присутсвующих кто-нибудь в теме, помогите разобраться, «где тут правда, а где истина»? )
1. С какой целью Вы хотите применить XOR? Он конечно легко применяется, в качестве проверки Ваших идей я бы посоветовал воспользоваться любым эмулятором квантового компьютера или например, настоящим КК от IBM.
2. Пусть меня поправят знатоки КМ, но разве для получения
условно бесконечного
набора скореллированных случайных значений в удаленных точках А и Б не нужно будет разносить в эти точки
«На свалке» могут оказаться некоторые ассиметричные криптоалгоритмы например RSA, ElGamal и соотв. аналоги на эллептических кривых, см. алгоритм Шора для эффективного (в приемлемое время, без полного перебора) их «взлома» при наступлении «эры квантовых вычислений». Предел Бремермана (а также см. теорему Марголуса — Левитина) скорее «полезен» для многих используемых в настоящее время сильных симметричных криптоалгоритмов, время «взлома» которых приближается к полному перебору.
Если это впн только по 80 и 443 портам работает, то не совсем понятно, чем от турбо и еже с ними в лучшую сторону отличается (кроме выбора из списка точки выхода)?
Очевидно чем сложнее и уникальнее схема, тем меньше тех, кто разберется во всех тонкостях, и тем вероятнее наличие в ней опасных уязвимостей, как например было с zk-SNARK.
Данный баг вроде как пофиксили, но кто поручится, что багов в этой схеме (и др. сложных) не осталось?
Так изначально здесь и спрашивали в т.ч. за Гровера, правда относительно «реверса хеш-функций» (см. по ветке выше) ;).
Разумеется GSA (в отличие от алгоритма Шора) не даст «экспоненциального ускорения» (и вообще вряд ли потянет), необходимого при факторизации (дискретном логарифмировании/соотв. EC-задачах) на размерностях порядка современных ключей. Речь не про это.
«Измененный алгоритм Гровера» из статьи (хотя повторяю, к нему есть вопросы например в части масштабируемости, универсализации, скорости и т.д.) на реальных примерах показывает, что требуемое число кубитов может быть существенно меньше, чем «длина ключа (в битах)». Хотя бы для некоторых (частных) задач определенной размерности.
Как мы можем быть уверены, что невозможны подобные (или иные) оптимизации алгоритмов Гровера и/или Шора (или их модификации или вообще новые квантовые алгоритмы) для эффективного решения «серьезных» полноразмерных задач, но с «пониженным потреблением» кубитов? Имеются ли принципиальные препятствия к этому?
Например здесь пишут, что даже на 2 и 4 кубитах на реальном КК можно разлагать на сомножители достаточно большие числа:
Конкретно к данному алгоритму есть вопросы, но тем не менее. К тому же есть и другие, где число используемых кубитов меньше чем размер ключа (в битах).
Вообще-то математическое доказательство абсолютной криптостойкости шифра Вернама от К. Шеннона давно опубликовано, считается без тени сомнения полным, строгим и верным (по крайней мере среди профессиональных криптографов и ни кем из них ни когда серьезно не оспаривалось), более того, это азы криптографии.
Сравните это доказательство с частичными исследованиями на криптостойкость по определенным параметрам/от определенных (известных) атак для гост, aes, dsa, ecdsa и т.п.
И надо ли еще риторический вопрошать: где в этом ряду находятся доводы типа «одна тетка сказала» или там «мамой клянусь» например в пользу того же госта?
Про госты, aes, dsa и т.п. вряд ли можно сказать, что они имеют математическое док–во криптостойкости, скорее они исследованы на криптостойкость по ряду параметров/на защиту от некоторых (известных) атак. А вот например шифр Вернама считается системой с абсолютной криптографической стойкостью. Квантовая криптография так же считается доказанно защищенной законами квантовой физики.
Мне одному кажется, что «линейный рост» до 8 городов — это «ниачем»? ;)
Нет, я вполне согласен с тем, что амебы, пчелы, муравьи за многие миллионы лет эволюции могли выработать эффективные алгоритмы поведения, которые интересно изучать и в определенных случаях извлекать пользу от их применения. Но насколько хватит условных ресурсов амеб (пчел, муравьев) для сохранения «линейного роста» при практически значимых действительно больших N, когда «количество вариантов решения увеличивается экспоненциально» (от N)?
К сожалению ответа в статье нет и нам предлагается лишь ждать (надеяться и верить), когда они «изготовят чипы»,
чтобы «амёба могла попробовать решить задачу коммивояжера на сотнях городов»…
Почему «теоретически»? Каких именно возможностей существующих КК не хватает для этого?
Вроде бы принципы КМ вполне используются в современной космологии (даже есть термин «квантовая космология», известные труды в этой области А.Д. Линде, Лоуренса Краусса и т.д.). Почему интерпретация Эверетта (я не говорю верная ли она или нет) или другие интерпретации КМ не могут иметь отношения к космологии?
Правильно ли я понимаю, что измеряя насколько макс. скорость некой частицы меньше скорости света, можно судить о ее массе? Например, нейтрино?
А вот например тут некоторые утверждают, что:
Лично мне не особо понятно, всю ли «криптографию на решетках» накрывает эта атака, если она действительно существует (сцылки в статье битые, да и сам этот Берд Киви не особо внушает...),
но если из присутсвующих кто-нибудь в теме, помогите разобраться, «где тут правда, а где истина»? )
2. Пусть меня поправят знатоки КМ, но разве для получения набора скореллированных случайных значений в удаленных точках А и Б не нужно будет разносить в эти точки количество пар запутанных фотонов?
К тому же это тянет на гнусное предательство Вашей профессии!
Ирония конечно )