На страже информации
(опубликовано в https://scientificrussia.ru/articles/na-strazhe-informatsii )
Ученые КФУ проводят длительные исследования по разработке концепции квантового хеширования – математического алгоритма, опирающегося на законы квантовой физики. Предлагаемые аналитические модели – весомый вклад в развитие квантовой криптографии. Криптографические хеш-функции проверяют целостность информации и открывают потенциальные возможности для систем цифровой подписи.
При помощи классических методов дактилоскопии (fingerprinting) возможно создание эффективных вычислительных алгоритмов, особенно востребованных в глобальных системах хранения различных баз данных и баз знаний. Квантовая дактилоскопия (Quantum Fingerprinting), появившаяся в начале 2000-х годов, предлагает новый способ идентифицирования – отображать классические данные информации в квантовых состояниях. Это направление активно развивается современными специалистами в сфере информационной безопасности. Например, российские специалисты изучают методы квантовой дактилоскопии (методы квантовых отпечатков или quantum fingerprint).
Для защиты от взлома информации идеи quantum fingerprinting применяют в конструкциях квантовых алгоритмов. В криптографии идеи технологии quantum fingerprinting трансформируются в идеи квантового хеширования. Назначение квантовой криптографии – построение защищенных систем передачи информации на основе квантовых технологий. Конструкции квантовых хеш-функций (quantum hash function), т.е. преобразования массива данных, основаны на классическом универсальном хешировании и должны удовлетворять, в частности, требованиям однонаправленности (one-way) и требованиям устойчивости к фальсификации (коллизия устойчивости). Сегодня экспертами рассматриваются различные подходы к построению понятия квантовой хеш-функции (например, функция на основе двоичных кодов, на основе квантового преобразования Фурье).
Ученые Казанского федерального университета начали исследования классически-квантовой хеш-функции и предложили свой метод квантового хеширования. Прежде всего, математики изучили криптографические свойства этой хеш-функции. В основу аналитических расчетов легли дискретные преобразования Фурье, так как они смогут быстро реализовываться в квантовых вычислителях и системах квантового преобразования информации уже в ближайшем будущем. Кроме того, ученые определили квантовые хеш-функции, основанные на известных конструкциях квантовых методов отпечатков (quantum fingerprint) и выяснили, что такие функции хешируют сообщения в квантовые состояния из небольшого числа кубитов (это гарантирует свойство однонаправленности функции) и обеспечивает «почти ортогональность» квантовых хеш-кодов (это гарантирует коллизия устойчивость функции). Авторское понятие аналитиков КФУ о квантовом хеш-генераторе строится на технологии EQ ? E-QUANTIZER, которая обеспечивает высокий уровень криптографической защиты компьютерных систем. В её основу заложен результат туннелирования отдельного электрона через диэлектрический барьер.
На фото Фарид Мансурович Аблаев – профессор, доктор физ.-мат. наук, заведующий кафедрой теоретической кибернетики Института вычислительной математики и информационных технологий Казанского (Приволжского) федерального университета (КФУ) (г. Казань)
Фарид Мансурович Аблаев – профессор, доктор физ.-мат. наук, заведующий кафедрой теоретической кибернетики Института вычислительной математики и информационных технологий Казанского (Приволжского) федерального университета (г. Казань) – поделился результатами многолетней работы и раскрыл понятия, являющиеся ключевыми в исследованиях по квантовой дактилоскопии и квантовому хешированию
«Квантовая дактилоскопия (Quantum Fingerprinting) – есть некий математический метод, который позволяет эффективно представлять информацию для квантовых алгоритмов. В настоящее время разработано уже много квантовых алгоритмов различного типа (см., например здесь и их список постоянно пополняется). Большинство из квантовых алгоритмов выполняется на теоретических квантовых вычислительных моделях. Хотя есть уже и практические, в частности, в конце 2019 года прошумела очень известная конструкция, которая предложена группой Google, с которой конкурирует и соревнуется группа IBM. Оказалось, что они предложили: квантовый вычислитель, который работает более чем на 50 кубитах – на 53-54-х кубитах. И на этих 53-54-х кубитах они могут сейчас выполнять некую задачу, для решения которой, предполагалось, понадобится около 10 000 лет самому быстрому компьютеру. Сейчас для суперкомпьютера Summit IBM это возможно за 1, 5 дня. (https://en.wikipedia.org/wiki/Summit_(supercomputer)) А квантовый вычислитель Google решает эту задачу за сотни (не более 300) секунд. Это есть то, что называется в нашей среде квантовым превосходством (Quantum Supremacy). Квантовое превосходство – это есть нахождение некой, может быть, искусственной задачи, которая окажется для квантового вычислителя по силам, а классическому суперкомпьютеру – она не по силам. И как раз такой шаг в этом направлении был сделан, –
профессор Фарид Аблаев пояснил, что представляет собой квантовая дактилоскопия и какие её вычислительные аспекты выяснены казанскими учеными. –
В нашей среде шло обсуждение и выясняется, что может, да, 54 кубита пока не смогут окончательно победить суперкомпьютер Summit IBM. Но этот суперкомпьютер с гигантскими (на наш обыденный взгляд) характеристиками: например, его оперативная память 300 Тбит. Это гигантская сумма – миллиарды гигабайт. Но! Как образно сказал Скот Аарансон (специалист по квантовым алгоритмам): «Когда речь пойдет о 70-ти и более кубитах, тогда такой классический компьютер как Summit IBM, чтобы бороться с квантовым, должен быть размером с город. А нынешний компьютер равен двум баскетбольным площадкам».
Для того чтобы эффективно решать задачи на квантовом компьютере, нужны специальные методы. Почему специальные? Потому что квантовый компьютер достаточно быстро «выходит из строя». Этот процесс называется процессом декогеренции. Например, классический компьютер мы выключили, а потом включили, и он может простоять какое-то время. А декогеренция наступает достаточно быстро. Пока речь идет о долях секунд на самом деле. Поэтому и нужны специальные методы. Один из таких, который мы называем отпечаток, или quantum fingerprint. В чем он состоит? Содержательно – это типичный математический метод отпечатков пальцев. Потому что для вычислений мы должны внутри вычислительной системы хорошо идентифицировать объект. Объект – это база данных или данные, которыми мы оперируем. Они должны быть устойчиво представлены в машине. Хороший пример – это отпечатки пальцев. Это достаточно экономное и быстрое представление о каждом человеке. В этом смысле также работает fingerprint, но это математическая аналогия. Отпечатки пальцев обладают таким свойством: даже повреждение на пальце сохраняет индивидуальную информацию о человеке. Это происходит и с данными, которые представлены в виде fingerprint. В каком-то смысле случаи повреждения – это зависимые порции информации, которые в совокупности дают информацию об объекте. Повреждения – это например, кубит неправильно сработал, размылся или распался раньше времени, хотя в совокупности информация сохраняется».
Квантовая дактилоскопия решает проблему построения квантовых хеш-функций, то есть проблему преобразования длинных данных в короткие хеш-коды.
«Хеш-функции – это краткая характеристика объекта, это близко к fingerprint. Например, информация о человеке – это его телефонный номер, номер паспорта, это однозначно определяет человека, позволяет его идентифицировать. Хеш-функции используются для экономного предоставления информации в больших данных и для поиска больших объектов по их хеш-образу. А в криптографии хеширование используется и для организации цифровой подписи, в, частности, можно грубо сказать, что современные системы блокчейн – это распределённые базы данных, которые снабжены криптографическими хеш-функциями. То есть на самом деле криптографические хеш-функции обладают следующим свойством: какой-то длинный объект (текст) отображается в короткий и есть вполне конкретные размеры, в которые требуется длинную информацию захешировать. Причем сам процесс хешировании информации должен быть очень быстрым. По объекту мы должны быстро найти его образ. А по хешу (образу) объект найти должно быть очень сложно. Это и есть криптографическое хеширование, оно срабатывает в цифровой подписи, в системах блокчейна. Это очень важная вещь. Или есть еще одно свойство. Раз мы отображаем большие объекты в короткие записи, то обязательно будут ситуации, которые называются коллизии. Это когда два разных объекта отображаются в один и тот же короткий хеш. Просто коротких строк гораздо меньше, чем длинных. Но коллизии должно быть очень сложно найти. Эта проблема называется сложностью нахождения коллизий. Содержательно возможность нахождения коллизии можно интерпретировать как возможность фальсификации. Это достаточно сложные требования, которое лежат в основе криптографических хеш-функций, –
Фарид Аблаев дал определение понятию квантовой хеш-функции, отметил её важные свойства и подчеркнул, что было достигнуто в этом направлении, –
Что нам удалось сделать? Мы сделали такой шаг. Мы сказали: давайте мы будем отображать длинные слова не в короткие, а длинные слова будем отображать в квантовых состояниях. Квантовое хеширование – это когда длинное слово отображается в какую-то небольшую группу кубитов по сравнении с длиной исходного слова. Мы сказали, давайте мы будем использовать 15-16 кубит, в которых мы будем их отображать. Причем все эти отображения должны удовлетворять всем свойствам криптографических отображений: во-первых, отображение должно быть просто реализовано; во-вторых, восстановить по образу достаточно сложно; в-третьих, коллизии должно быть сложно находить».
Тем не менее, в настоящее время перед учеными остаются нерешенные вопросы. По замечанию профессора Аблаева, «оказывается, первые свойства хеширования (легко вычисляться в одну сторону по исходному тексту) реализуется просто. А вот математически доказать, что некое такое придуманное математиком отображение сложно обращается (т.е., что находить по хешу его прообраз сложно), пока невозможно. Это пока проблема, которая напрямую связана с открытой математической проблемой столетия. Эта проблема формулируется математиками как проблема выяснения «P равно NP» или «P не равно NP», где P и NP – это специальные классы алгоритмов. Это одна из 7 открытых задач столетия. Современных средств математического аппарата пока не хватает для решения этой проблемы. Собственно поэтому все современные криптографические хеш-функции условно односторонние. Есть много потенциально хороших современных конструкций, которые на практике трудно обратить. Но по мере развития технологий современные потенциально односторонние хеш-функции раскалываются, поэтому постоянно идет соревнование между криптографами и криптоаналитиками».
Каковы уникальные свойства квантовой хеш-функции?
«Квантовые хеш-функции гарантированно односторонние и они обеспечиваются не математическими алгоритмами, а законами квантовой физики. Известен результат, который был получен еще в 70-е годы российским математиком Александром Семёновичем Хóлево который показал, что из квантового объекта, который предоставляет информацию, можно, например, использовать 16 кубит, то измеряя эти 16 кубит, можно извлечь только 16 классических единиц информации. Эта теория получила впоследствии название граница или теорема Холево», – объяснил Фарид Аблаев и указал, в чем заключается подход их исследовательской группы для построения квантовых хеш-функций, –
А мы сумели предложить алгоритмы квантового хеширования, которые позволили строить такие квантовые хеш-функции. Разные объекты должны быть устойчивы к коллизиям – нам удается это сделать!».
Казанские ученые планируют изложить теоретический обзор, в котором продемонстрировали свой вариант того, как представляется и реализуется хеш-функция, на 15-м Международном симпозиуме по информатике в России (CSR 2020), который должен состояться в Екатеринбурге под эгидой Европейской ассоциации теоретических компьютерных наук (EATCS).
Но есть ли здесь в теории какие-то «подводные камни»? Как это работает?
«Во-первых, когда мы захешировали (классически) информацию и отправили хеш по оптоволокну, он пришел и хранится. Вы открываете его и работаете. Но дело в том, что квантовое хеш-состояние быстро распадается. Но в таких случаях физики работают с квантовой памятью. Ждем их продвижения в развитии квантовой памяти. Простейшая квантовая память хранит доли секунд, но можно работать с хеш-памятью. Во-вторых, оказалось, что ансамбль этих кубит, которые мы хешируем в эту информацию, как говорят физики, должны быть сцеплены. Кубиты не должны быть разрознены. Физики говорят в таком случае о так называемой квантовой запутанности /перепутанности. То, чего нет в классической науке», –
комментирует Фарид Аблаев и выражает надежду на преимущество разработки казанских специалистов, –
Один из шагов, который был нами предложен, и над этим мы сейчас работаем – мы решили строить не чисто квантовую хеш-функцию, классическую последовательность хешируют в квантовое состояние, а получив квантовый хеш, решили извлечь из неё некое классическое описание. И тогда получается, что квантовый процесс кодирования классической информации хешируется в короткий классический. Возможностями такого построения – мы занимаемся и рассматриваем. Некоторые такого рода попытки предпринимаются у зарубежного научного сообщества. Мы надеемся, что наш метод приведет нас к успеху».
Итак, предложенные учеными КФУ квантовые алгоритмы показали коллизия устойчивость квантового хеширования. Это свойство имеет важное прикладное значение. Простой пример применения хеширования:
«Есть длинный текст, и мы по нему строим хеш. Например, 250 символов и отправляем его. Алгоритм есть. Используя хеш-функцию, адресат хеширует текст. Таким образом, текст и его хеш – это единое целое. Получатель по тексту вычисляет хеш и сранивает его с приложенным хешем. Если совпадают, то все в порядке: нет ошибок и фальсификаций в тексте. А если кто-то перехватывает текст и меняет фразы – значит меняется прообраз хеша и получатель обнаружит факт подделки. Здесь в этом примере хеширование – это проверка целостности информации документа. Здесь важна коллизеустойчивость. Сложно подделать текст так, чтобы хеш оказался прежним – это важно и для того, кто проверяет, и для того, кто отправляет. Короткий хеш используют для передачи информации в самолетах и спутниках: цифровое слово хешируется и отправляется в радиогруппу. Здесь используют короткий хеш такого же рода, как и в автомобильных замках», – пояснил Фарид Аблаев.
Для обеспечения безопасности данных (банкоматы, автоматизированные системы или системы аутентификации) используют последовательность случайных чисел.
Что такое квантовый генератор случайных чисел? Для чего нужны последовательности случайных символов в криптографии?
По словам Фарида Аблаева, «все ключи и пароли должны быть максимально случайно подобраны и они не должны угадываться. Потом их надо часто менять. Паролей должно быть много, и они должны быть абсолютно случайными. Для этого нужен генератор случайных чисел. Есть много классических алгоритмов, которые порождают последовательности чисел и внешне они кажутся случайными. Их называют генераторы псевдослучайных чисел. Случайные числа широко используются, например, в банковских операциях. Проблема последовательностей псевдослучайных чисел в том, что через какое-то время они начинают повторяться. Они очень хороши, но они «впадают в период».
Как заметил профессор Аблаев, «в поисках истиной случайности человечество пришло к пониманию, что истинные случайные процессы происходят именно на квантовом уровне. Возникает другая проблема – как извлекать эту случайность? Потому что последовательность измерений действует на эти процессы. В квантовых исследовательских группах, как правило, ведется и разработка квантовых генераторов случайных чисел. Генератор должен представлять собой устройство не больше телефона. Например, в квантовом центре МГУ (руководитель Сергей Кулик) был предложен хороший генератор. Группа ученых Женевского университета предложила квантовый генератор ID Quantique в 2001 году (скорость генерации 4 Мbps).
Мы предложили свой квантовый генератор на основе фиксации туннельного эффекта. Туннельный эффект порождает лавину электронов и дает оклик в макромир. Это эффективное и быстрое, с нашей точки зрения, извлечение случайностей на квантовом уровне. Как прошло его тестирование? Легко. Мы генерировали много гегабайтов-терабайтов. Есть специальный набор тестов (например, НИСТ 2018, Национальный институт стандартов и технологий), который проверяет последовательность случайных чисел, и тесты показали, что наша разработка хорошо удовлетворяет этим системным требованиям».
Можно ли абсолютно надежно шифровать тексты и сообщения?
«Зашифровать какой-то текст, оказывается, можно абсолютно надежно, если длина ключа совпадает с длиной слова. Эта теорема было доказана Клодом Шеноном в 1947 году. Суть в том, что есть способ шифрования, который устроен так: если мы используем длину ключа, такую же, как длина текста, то шифрование абсолютно надежно. Но есть требование к такому шифрованию: ключ можно использовать только 1 раз. Шифр разведчика (принятое название «одноразовый блокнот»). В чем фишка такого типа шифрования? Например, есть частотные характеристики появления в каждом тексте буквы, скажем для букв О или К. Для каждого языка есть такая частотная характеристика появления в тексте. Если мы устраиваем перестановки букв, то такое шифрование легко разрушается на основе частного анализа букв текста. На этом строился подход расшифрования зашифрованных писем Шерлоком Холмсом в рассказе «Пляшущие человечки». Но если мы сумеем сделать так, что каждая буква шифруется по-разному в разных местах в шифруемом тексте, то статистика нарушается. Доказано, что такое шифрование абсолютно надежно. Но такого типа шифрования требуют длины ключа равного длине шифруемого текста. При этом ключ для шифрования должен быть абсолютно случайным. Для выработки таких ключей нужны хорошие генераторы случайных чисел. Далее оказывается, что для дешифровки сообщения, зашифрованного таким способом, нужен в точности такой же ключ!
В XX веке эта проблема решалась путем выработки ключей заранее в разведцентре и секретной доставки ключей нашему разведчику курьером. В век компьютерных сетей стоит задача секретной выработки ключа и секретной доставки его адресату по Интернету. Эти задачи решаются современной криптографией, в том числе, и на квантовом уровне. Для серьезных сообщений на высоком уровне по-прежнему используют именно такое шифрование Клода Шенона, надежность которого доказана. Это достаточно дорогостоящая операция. Все, что более экономно, при приложении определенных усилий подвержено расшифрованию», – прояснил Фарид Аблаев.
Квантовая хеш-функция, которая основана по аналогии на квантовой функции снятия отпечатков пальцев, рассмотренная учеными-математиками КФУ, проявляет свойства устойчивости информации при помощи квантовых систем и доказывает надежный уровень защиты.
