О квантовом хешировании в постквантовой криптографии

XIX и XX в. – эпоха революционных научных теорий и технологий. Электродинамика – одна из основополагающих наук – возникла в XIX в. XX в. можно считать веком триумфального вхождения электродинамики во все сферы нашей жизни. Аналогичная ситуация, похоже, происходит с квантовой механикой, которая как теория оформилась в XX в. Ряд квантовых технологий, такие как атомные, энергетические, лазерные и полупроводниковые технологии, уже активно развиваются с середины XX в., но наиболее глубинные положения квантовой механики лишь недавно оформились в направление, получившее название квантовая информатика.

Пожалуй, наиболее известными достижениями квантовой информатики являются квантовый алгоритм факторизации числа (разложения числа на простые множители) и алгоритм нахождения дискретного логарифма. Эти алгоритмы изобретены Питером Шором в 1994 г. Значимость их для криптографии трудно переоценить, и важность их заключена в следующем.

Алгоритмы

Криптографические системы с отрытым ключом основаны на так называемых однонаправленных (односторонних) функциях – функциях легко вычислимых, но трудно обращаемых. Например, такой функцией на сегодняшний день является функция умножения простых чисел. Два числа р и q легко умножить – достаточно порядка n2 операций в алгоритме школьного умножения, где n – длина двоичной записи чисел р и q. Но вот для факторизации числа а = pq, т.е. для нахождения одного из простых чисел р и q по а – сложно. В общем случае требуется перебирать простые числа до числа √а, проверяя для каждого такого р его делимость на а. Этот перебор требует примерно √2ⁿ операций и более быстрых (не переборных) классических алгоритмов, сегодня не известно. При этом математическая интрига заключается в том, что нет и доказательства, что факторизация в общем случае сложна (нельзя в принципе обойтись без перебора вариантов для факторизации числа). Такие функции называются условно однонаправленными.

Ситуация с односторонними функциями оказывается связана с известной открытой математической проблемой Р ≠ NP? Эта проблема объявлена одной из центральных открытых математических проблем столетия. Оказывается, что доказательство существования однонаправленных функций влечет доказательство того, что Р ≠ NP.

Так вот, Питер Шор предложил квантовый алгоритм факторизации, которому достаточно примерно n³ операций для факторизации числа а. Правда, это n³ операций квантового компьютера, над построением которого бьются многие научные коллективы мировых исследовательских центров.

Постквантовая криптография

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

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

Далее мы рассмотрим понятия хеширования и примеры его применения (классического и квантового) для проверки целостности передаваемой информации.

Классическое хеширование

Хеширование широко используется в различных областях информатики. Само слово "хеширование" имеет кулинарное происхождение. В английском языке глагол to hash означает мелко нарубить и перемешать. Математически хеш-функцию можно определить как сжимающую функцию с рядом свойств, определяемых областью применения хеширования. Пусть ∑ – алфавит, ∑^k – это множество слов длины k в алфавите ∑. Включив в алфавит символ пробела, мы под словом будем понимать и предложения в обыденном смысле слова. Пусть k > m. Функцию

h : ∑^k - > ∑^m,

сжимающую слова длинные (длины k) в короткие (длины m) называют хеш-функцией.

Проверка целостности информации

Криптографическая проверка целостности передаваемой информации от Алисы (А) к Бобу (В) заключается в вычислении Алисой хеша h(w) для передаваемого сообщения w и передачи пары (w, h(w)) Бобу. Боб, получив пару (w', h(w)), на своей стороне вычисляет значение h(w') и сравнивает значения h(w) и h(w').

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

• Хеш-функция h должна быть однонаправленной (точнее, условно однонаправленной на сегодняшний день).
• Хеш-функция h должна быть стойкой к коллизиям первого рода: для заданного сообщения w должно быть вычислительно сложно подобрать другое сообщение v, для которого h(w) = h(v).
• Хеш-функция h должна быть стойкой к коллизиям второго рода: должно быть вычислительно сложно подобрать такую пару сообщений (w, v), что h(w) = h(v).

Квантовое хеширование

В отличие от классического подхода, основанного на классических условно однонаправленных функциях, квантовая криптография при построении хеш-функций основывается на принципах квантовой механики и квантовой теории информации, гарантирующих физическую однонаправленность квантовых хеш-функций. Эта особенность квантовой механики является одним из центральных потенциальных преимуществ перед классическими хеш-конструкциями.

Основы квантовой информатики (немного математики)

С точки зрения дискретной математики и теории квантовых алгоритмов модели вычислений, основанные на квантово-механических принципах:

• по природе своих преобразований являются дискретными, детерминированными и обратимыми линейными моделями;
• позволяют реализовывать массивные параллельные вычисления;
• по способу извлечения результатов вычисления являются вероятностными.

Квантовый бит. Квантовый бит (кубит) - ключевое понятие теории квантовых вычислений. Кубит рассматривается как квантово-механическая система, состояние которой описывается комплексно значным вектором двумерного гильбертова пространства Н², т.е.

|ψ› = а|0› + β|1› ,

где векторы |0> и |1>образуют ортонормированный базис в Н², а комплексные числа α и β удовлетворяют условию |α|² + |β|² = 1. В отличие от классического бита кубит из квантового мира может одновременно находиться в своих базисных состояниях |0› и |1› с амплитудами α и β соответственно.

Многокубитные состояния. s-кубитные, s > 2, состояния задаются векторами 2s-мерного пространства H^2s . Другое (содержательное) обозначение (H²)^Οs этого пространства подчеркивает тот факт, что мы имеем дело с пространством s-кубитных состояний.

Произвольное состояние |ψ› ε H^Οs представимо в виде линейной комбинации своих базисных состояний:

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

• s-кубитное квантовое состояние |ψ› (1) одновременно находится во всех своих 2s базисных состояниях, а пребывание в каждом из /i› численно характеризуется величиной α_i.

• Преобразования состояний квантовой системы дискретны и линейны: если |ψ) - состояние квантовой системы на текущем шаге, то на следующем шаге состоянием будет |ψ'›, где |ψ'› = U|ψ› и U - 2^s х 2^s - унитарная матрица. С точки зрения теории вычислений обратимое преобразование U квантовой системы на каждом шаге одновременно (параллельно) изменяет распределение амплитуд всех базисных состояний системы.

• При измерении |ψ› ("извлечении информации" из |ψ›) состояние |ψ› "схлопывается" в одно из своих базисных состояний |i› с вероятностью |α_i|².

Такую "одновременность" (1) называют квантовой суперпозицией, или просто суперпозицией. Явление "одновременности" - единственное разумное объяснение многочисленных результатов экспериментов в области квантовой механики. Это явление, называемое также квантовый параллелизм, является в определенным смысле основным фактом квантовой информатики, обеспечивающим преимущества перед классическими моделями вычислений. Так, при s = 30 s-кубитная система определяет модель вычислений оперирующей одновременно с более чем 1 миллиардом (1 073 741 824) состояний, а при s = 500 число 2⁵⁰⁰ таких состояний превышает число элементарных частиц во Вселенной.

Квантовая хеш-функция

Функцию

отображающую слова длины k в s-кубитные состояния, будем называть (k; s) квантовой функцией.

Квантовая однонаправленная функция. Содержательно квантовое s-кубитное состояние |ψ› может на квантовом уровне "содержать огромный объем информации", при этом один из фундаментальных законов квантовой информатики, известный как nеорема Холево [7], утверждает, что при извлечении информации из состояния |ψ› можно получить не более s бит информации о |ψ›.

• Из теоремы Холево следует, что (k; s) квантовая функция является однонаправленной, если log k > s.

Пример 1. Рассмотрим квантовую функцию

отображающую числа v ε {0,..., 2^k- 1} в кубит по правилу:

В примере 1 представлена однонаправленная квантовая функция. Действительно, для задания чисел v ε {0,..., 2^k- 1} необходимо k бит информации. Согласно теореме Холево [7] из одного кубита можно извлечь не более одного бита информации.

Квантовые функции, устойчивые к коллизиям. Сразу отметим, что квантовые функции могут не иметь (на квантовом уровне!) коллизий. Так, в рассмотренном примере 1 функция ψ осуществляет взаимно однозначное отображение: различные слова отображаются в различные квантовые состояния. Однако поскольку процесс извлечения информации вероятностный и извлечь можно лишь s единиц информации (s - число кубит, составляющих квантовое состояние), то коллизии могут возникать. В рассмотренном примере 1 "близкие" слова v, v' будут с большой вероятностью считаться одинаковыми при извлечении информации (при измерении в базисе |0›, |1›) из состояний |ψ(v)› и |ψ(v')›.

Выход из такой ситуации есть, и он следующий. В квантовой механике хорошо различимы ортогональные и почти ортогональные состояния. Поэтому нужно уметь строить квантовые функции так, чтобы различные слова v и v' отображались в почти ортогональные состояния |ψ(v)› и |ψ(v')›.

Квантовые однонаправленные и устойчивые к коллизиям функции. Для получения квантовых криптографических хеш-функций необходимо объединить свойства квантовой однонаправленности и квантовой коллизии устойчивости квантовых функций. Это означает, что квантовую хеш-функцию

нужно строить так, чтобы число s задействованных кубит было много меньше длины k хешируемых слов: s << k. При этом для каждой пары различных слов v, v' ε ∑^k их квантовые образы |ψ(v)› и |ψ(v')› были почти ортогональны. Такие конструкции квантовых хеш-функций были недавно предложены [1, 2].

Оказалось, что такие квантовые хеш-функции должны порождать сильно сцепленные квантовые состояния. При соблюдении условия сильной сцепленности квантовых состояний порядка 10 кубит можно будет надежно квантово хешировать сообщения длины до 1000 бит, а при 20 кубитах - уже сообщения длины порядка сотен тысяч бит. Построение квантовых систем (квантовых регистров), устойчиво оперирующих с ансамблями более порядка сотни сцепленных кубит, - серьезная технологическая задача в современном мире.

Квантовая криптографическая проверка целостности информации. Такая проверка целостности передаваемой информации от Алисы (А) к Бобу (В) аналогична классической проверке и заключается в выборке квантовой криптографической хеш-функции ψ, в вычислении Алисой квантового хеша |ψ(w)› для передаваемого сообщения w и передачи пары (w, |ψ(w)›) Бобу. Боб, получив пару (w', |ψ(w)›) на своей стороне вычисляет значение |ψ(w')› и сравнивает значения |ψ(w)› и |ψ(w')›.

Заключение

Проверка целостности информации - не единственное возможное приложение квантового хеширования. В настоящее время идут разработки различных квантовых протоколов передачи информации с использованием квантового хеширования. Мы сошлемся на статью [6], в которой проводится анализ направлений развития квантовой криптографии, в частности, рассматриваются возможности квантового хеширования по организации систем цифровой подписи.

В криптографии постоянно идет борьба между конструкторами надежных криптографических систем, в частности, конструкторами хеш-функций и конструкторами атак на криптографические системы. Периодические смены криптографических ГОСТов свидетельствуют о высокой активности коллективов математиков-конструкторов в области информационных атак и информационной обороны. Нарождающаяся квантовая криптография добавляет еще больше интриги и другой уровень технологий в эту борьбу.

Литература

1. Аблаев Ф.М., Аблаев М.Ф., Васильев А.В. Универсальное квантовое хеширование // Ученые записки Казанского университета. Серия: Физико-математические науки 2014. – Т. 156, Книга 3. – С. 7–18.
2. Ablayev F., Ablayev M. Quantum Hashing via Classical e-universal Hashing Constructions // arXiv:1404.1503v2 [quant-ph] 2015.
3. Аблаев М.Ф. О построении квантовых хеш-функций // Труды IX Международной конференции "Дискретные модели в теории управляющих систем" Москва и Подмосковье. – 2015. – 20–22 мая. – С. 8–9.
4. Валиев К.А., Кокин А.А. Квантовые компьютеры: надежды и реальность. – Ижевск: НИЦ "Регулярная и хаотическая динамика, 2001. – 352 с.
5. Китаев А., Шенъ А., Вялый М. Классические и квантовые вычисления. – М.: МЦНМО, ЧеРО, 1999. – 192 с.
6. Корольков А.В. О некоторых прикладных аспектах квантовой криптографии в контексте развития квантовых вычислений и появления квантовых компьютеров // Вопросы кибербезопасно-сти. – 2015. – № 1(9). – С. 6–13.
7. Холево А.С. Некоторые оценки для количества информации, передаваемого квантовым каналом связи // Проблемы передачи информации. – 1973. – 9:3, 3–11.