Контакты
Подписка
МЕНЮ
Контакты
Подписка

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

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

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций

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

Квантовая криптография на наших глазах превращается из чисто теоретической науки в одно из первых практических приложений квантовой информатики. Это направление информатики бурно развивается в последние десятилетия на стыке квантовой механики и теории вычислений, информации и криптографии.
Фарид
Аблаев
Профессор, зав. кафедрой теоретической кибернетики, Казанский федеральный университет, д.ф.-м.н., fablayev@gmail.com
Марат
Аблаев
Научный сотрудник лаборатории квантовой информатики, Казанский федеральный университет, Казанский федеральный университет
Питер Шор (Peter Shor) родился 14 августа 1959 г., Нью-Йорк, США. Выдающийся американский ученый. Автор работ в области геометрии, теории вероятностей, комбинаторики, теории алгоритмов и квантовой информатики. Наиболее известен своими основополагающими результатами в теории квантовых вычислений.

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Хеширование широко используется в различных областях информатики. Само слово "хеширование" имеет кулинарное происхождение. В английском языке глагол 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функцию

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

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

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

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

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

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

В примере 1 представлена однонаправленная квантовая функция. Действительно, для задания чисел v ε {0,..., 2k- 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], в которой проводится анализ направлений развития квантовой криптографии, в частности, рассматриваются возможности квантового хеширования по организации систем цифровой подписи.

Авторы признательны коллегам из Академии криптографии РФ за постоянное внимание к нашей работе и РФФИ за поддержку исследований в рамках грантов 14-07-00878, 14-07-00557, 15-37-21160.

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

Литература

  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.

Опубликовано: Журнал "Information Security/ Информационная безопасность" #5, 2016
Посещений: 10606

Приобрести этот номер или подписаться
  Автор

 

Фарид Аблаев

Профессор, зав. кафедрой теоретической кибернетики, Казанский федеральный университет, д.ф.-м.н., fablayev@gmail.com

Всего статей:  1

  Автор

 

Марат Аблаев

Научный сотрудник лаборатории квантовой информатики, Казанский федеральный университет, Казанский федеральный университет

Всего статей:  1

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций