Квантове хешування. Лекція в Яндексі

Фарід Мансурович Аблаєв — завідувач кафедри теоретичної кібернетики Казанського федерального університету. Приїхавши в московський офіс Яндекса, Фарід Мансурович розповів про алгоритми, потенційно придатних для запуску на квантових комп'ютерах. Таких пристроїв поки дуже мало, і вони толком не освоєні навіть самими передовими компаніями. Але коли вони почнуть дешевшати, у фахівців вже будуть напрацювання, що дозволяють приступити до їх використання.


Одна зі сфер, де з появою квантових систем можуть відбутися серйозні зміни, — механізми цифрового підпису. У доповіді розкривається алгоритм хешування, радикально перевершує аналоги для класичних комп'ютерів. Під катом — детальна розшифровка і слайди.

Велика частина слайдів буде англійською мовою, але я думаю, що колеги мене вибачать. Не завжди вдається все перекладати, ну і не завжди є необхідність.



Цей звіт базується на роботах, які тут представлені. З першою нашою роботою — я сам математик — нас запросили в журнал Laser Physics Letters, який, на відміну від математичних високорейтингових журналів, що мають відповідний індекс трохи менше 1, має індекс 3,2. Зараз, коли враховуються всі Індекси Хірша та інші, виявляється корисним публікуватися в таких журналах — фізичних.

Один з останніх результатів був опублікований на семінарі Algebra in Computational Complexity, є такий німецький центр. Ці результати можна там подивитися. Архів — зрозуміла річ.



Почну з мотивації. Данило пожартував, що скоро буде квантовий комп'ютер, і ми всі будемо ним користуватися. У Казані є група, яка збирає комп'ютери, і директор, Дяків Віктор Васильович. Він сам з Тамбова, дуже енергійний. Як мене зустріне, каже: «Фарід, коли ми з тобою будемо продавати квантовий комп'ютер?»

Канадці вже продають. Ви знаєте про комп'ютері D-Wave, його періодично тестують, канадці оголошували, що він спочатку був 500-кубитный, а зараз в ньому 1024 кубіта. Періодично під час тестування то виявляється, що все це можна зробити на локальному комп'ютері, то знову квантовий комп'ютер у них хороший. Але це все поки що в такому стані…

Можна сказати, що, напевно, окремі кубіти — і 500, і 1024, і далі — можна ліпити. Але справа в тому, що квантовий комп'ютер стане гарним і виробляє, дуже потужним тільки в тому випадку, якщо ці кубіти будуть знаходитися в зчепленому перепутанном стані, стані entangled. Змістовно кажучи, це ситуація, коли система може програмуватися таким чином, щоб кубіти відчували один одного. Це майже не вдається зробити.

Якщо вдасться створити такий квантовий регістр — навіть не говорив би про квантовому комп'ютері, — де зчеплені стану будуть близько 500, це вже буде гарантувати таку продуктивність, при якій можна одночасно працювати з станами 2500. Це число частинок у Всесвіті, і це є добре. Тоді дана система поб'є всі існуючі комп'ютери.

Алгоритм Шора, який тут згадується, — перший результат 1994 року. Напевно багато хто знає, що якщо у Google або Яндекса запитати, що таке Quantum algorithm zoo, то він відразу викотить сторінку, де понад 50 квантових алгоритмів, які на порядок краще існуючих класичних алгоритмів. Потенційно вже є набір алгоритмів, які можна буде запускати на квантових машинах. І першим стоїть алгоритм Шора, алгоритм факторизації. Весь пафос цієї справи якраз і почався, коли з'явився алгоритм Шора. Факторизація означає, що класичні алгоритми RSA будуть побиті квантовим комп'ютером.

У відповідь на це відразу виникло таке напрям в співтоваристві криптографії — post quantum cryptography. Є і книжка така, тут вказана. В ній криптографічне співтовариство запропонувало цілий набір засобів, які б боролися з потенційним квантовим комп'ютером.

Криптографи в тому числі говорять про такому моменті — що, наприклад, схеми підготовки цифрового підпису на основі хешування, такі як системи підпису Лампорта, не будуть битися і квантовим комп'ютером.



Я згадаю про те, що таке цифровий підпис Лампорта. Це досить проста річ, була запропонована в 1979 році. Леслі Лампорт відомий як творець LaTeX, і він найбільш цитований людина в області theoretical and practical computer science. Його вкрай цитують завдяки тому, що він один з творців LaTeX.

Цифровий підпис Лампорта — система, яка дозволяє добре підписати біти 0 і 1. З 0 асоціюється якесь слово w, з одиницею інше слово v. Це два закритих ключів 0 і 1. Аліса готує значення функцій f(w) і f(v). Передбачається, що потрібно взяти односторонню функцію і ці пари переслати Бобу. Якщо Аліса хоче підписати 1, то вона направляє вихідне слово v і 1 Бобу, а Боб, швидко обчислюючи по v значення f(v), перевіряє, чи дійсно це так.

Однобічність дуже грубо змістовна. Це означає, що за значенням функції аргумент знайти складно, а по аргументу значення функції знайти легко. На основі нього можна проробляти те ж саме і з довгими повідомленнями…



Наступний крок, який нам знадобиться: ми згадаємо, що таке епсилон-універсальне хеш-сімейство.

Візьмемо набір N хеш-функцій. Під хеш-функцією будемо розуміти функцію, яка стискає слова довжини До довжини слова М. До > M, тут можливі колізії — ситуації, коли два різних слова відображаються в одне слово. Таке трапляється, коли K > M.

Зберемо набір таких хеш-функцій. F буде називатися епсилон-універсальним, якщо виконується наступне: в ситуації, коли f вибирається равновероятностно з цього безлічі, ймовірність того, що два різних слова дадуть однаковий спосіб, буде невеликий — не більше епсилон. Таке сімейство називається епсилон-універсальним хеш-сімейством. А в разі, коли епсилон є 1/N, це общеуниверсальное сімейство.



Використовуючи сімейство епсилон-універсальних хеш-сімейств, можна влаштовувати системи цифрового підпису. Не буду на цьому детально зупинятися. Поговорю про математичної частини, розповім, де це реалізується і що за співтовариства працюють в Росії.



Центральна ідея: ми узагальнюємо поняття хешування і хеш-родин функцій на квантовий випадок. А суть ось у чому: ми будемо відображати слова в квантові стани, в ансамбль кубіт. Одночасно ми хочемо, щоб виконувалися ці дві вимоги, щоб колізії були рідкісні. Тобто, змістовно, найменша зміна слів аргументу повинно вести до значного зміни хеш образу. Так і потрібно в класиці. І зрозуміло, функція повинна бути односторонньою.

Щодо однобічності я перескочив до класики. Поняття односторонньої функції, грубо кажучи, пов'язано з проблемою P ≠ NP. Якщо ця умова виконується, то одностороння функція існує, а в іншому випадку ми працюємо з потенційно односторонніми функціями. Така проблема є, ми все про неї знаємо.



Ми пропонуємо конструкцію, яка, в певному сенсі, дозволяє будувати оптимальні хеш-функції. Ми пропонуємо конструкцію, яка, використовуючи класичні коди, що виправляють помилки, дозволяє будувати цілі сімейства різних квантових хеш-функцій. Це якийсь внесок у постквантовую криптографію.

Якщо алгоритм Шора бореться з класикою, то тут квантова частина дозволяє в якомусь сенсі посилити боротьбу з майбутнім квантовим комп'ютером.



Дуже коротко про те, що таке кубіт тут. Кубіт — одиничний вектор у двовимірному гільбертовому комплексному просторі з такою властивістю, що координати вектора a0 і1 — комплексні числа, сума квадратів амплітуд яких дорівнює одиниці. Взагалі-то комплексне число — двовимірне. І, формально кажучи, це чотиривимірна точка. Але дане співвідношення зменшує розмірність до одиниці, і в підсумку кубіт можна представити як вектор у тривимірному просторі.

Причому це означає, що у нього дві ступеня свободи: кут ψ і кут Θ. Все відбувається в полярних координатах. Цей компонент називають амплітудою речової, де синус. А цей називають фазою — e.

a0 і1 — ймовірності того, що ми опинимося або нулю, або одиниці, якщо поміряємо кубіт.

У якомусь сенсі хороша аналогія кубіта — ситуація, коли ми взяли монетку, підкинули, і поки вона летить, вона одночасно перебуває в 0 і 1. Вона впала, ми її поміряли, класичний імовірнісний біт перестав жити і проявився або 0, або 1. Можна і дві монетки кинути, але тоді вони будуть незалежні. А система з квантових бітів, якщо вони зчеплені, — є те, чого немає аналога в класиці.



Як можна закодувати слово за допомогою одного кубіта? Двійкове слово ми інтерпретуємо як число. Мова йде тільки про речові частинах, тут немає фазової частини. Зрозуміло, що якщо ψ(w) є таке число, і якщо ми його розглядаємо як число за модулем 2k, то слово кодується в якийсь одиничний вектор, який визначається кутом, залежних від слова, яке ми прочитали. Тут все нормально. От вам спосіб закодувати слово одним кубитом.

Значить, фізично така кодування є одностороння функція. Існує результат Олександра Семеновича Холево — він працює в Стекловском інституті. В кінці 60-х він показав, що якщо у нас є ансамбль кубіт, то максимум класичної інформації, який можна отримати з S кубіт, — S біт. Я кажу дуже змістовно, на пальцях. За цим стоять чіткі формулювання.

Отже, якщо ми маємо один кубіт і таким чином загнали туди слово, то зі слів довжини До ми можемо отримати тільки 1 біт класичний інформації. Це як раз і є фізична однобічність. Тут два слова кодуються в різних станах, ось така інформація.

Що тут недобре? Два різних слова можуть кодуватися в близькі стану, можуть здаватися нерозрізненними. Одного кубіта мало.



Все, що я говорив, можна переписати і мовою фази. Тепер ми не будемо говорити про речові амплітудах, а візьмемо першу частину, вектор з амплітудою 0, другу — з амплітудою 1, але тут додамо фазу. За допомогою фази можна працювати, однак тут нам це не знадобиться.

Як таке можна реалізовувати? Як можна один кубіт налаштувати таким чином? Насправді всі перетворення є повороти, вони унітарні. Починаємо з нульового стану і, прочитуючи на кожному кроці черговий біт…



R1, R2 і так далі потрібно вказувати різні. Кути виходять різними. Потихеньку наберемо кути і в результаті отримаємо те, що нам потрібно.

Вже маючи хорошу односторонню квантову функцію, як би ми могли підпис Лампорта перевести і зробити це квантово?

Раніше вибираємо слово w, пов'язуємо його з 0, а слово v пов'язуємо з 1. Це секретні ключі для 0 і 1. І — заготовляємо відкриті ключі. Це вже квантові стани, відповідні слова w: я показував, як його можна набрати на одному кубите. Слово v набирається так само.



Пересилаємо 0 і відповідне значення квантового стану 1 Бобу. Звернути процес неможливо в силу результату Калева. Потім, якщо хочемо, пересилаємо Бобу пару слів v і 1. Боб, маючи відповідний стан і слово v, може перевірити, чи вірно, що квантовий стан ψ(v) було отримано саме за допомогою цього слова. Ми пропонуємо тут реверс-тест.



Оскільки перетворення унітарна, тобто взаємно однозначне… Є слово w, заготовлено квантовий стан, починаємо з нуля, застосовуємо унітарне перетворення, накопичуємо потрібне перетворення. Вийшло відповідний стан. Тепер, коли ми отримали слово w, Боб, знаючи алгоритм, може організувати ось таке зворотне перетворення. Його легко виконати. І це перетворення він застосовує до отриманого квантовим станом. В результаті, якщо два слова однакові, то результатом має стати стан 0.

Ми знаємо, з якими статками порівнювати. Якщо слова рівні, то реверс-тест і відповідна ймовірність того, що вони рівні, визначаються за такою формулою: скалярний добуток вектора 0 на стан зворотного перетворення, яке ми отримали.

Якщо два слова однакові, це завжди 1 — тут ми не помилимося. А якщо стану не рівні, то, маючи справу тільки з одним кубитом, ми все одно можемо опинитися близькі до одиниці. Це в тому випадку, якщо два стани, ψ(v) і ψ(w), були близькі.

Нам потрібно придумати ситуацію, коли два різних слова переводили б статок у майже ортогональне йому. Це буде для нас оптимально.



Наступний крок — коли нам одного кубіта не вистачає і потрібний регістр з S кубіт.



Від одного кубіта ми можемо перейти до такої системи. Значить, ми працюємо в гільбертовому просторі розміру 2s і відповідний ансамбль описується так само, як у випадку з одним кубитом. aі є амплітуда, комплексні числа. Норма цього вектора — без змін 1. Норми цих чисел у квадраті є ймовірність отримати одне з базисних станів i, якщо ми його поміряємо.

Тобто можна говорити про те, що тепер ми будемо розглядати функції, які влаштовані таким чином: слова довжиною До відображаються в ансамбль з S кубіт. Запис буде ось така.



Не буду говорити, як це було організовано: таке можна зробити за аналогією з тим, як це було зроблено для одного кубіта.



Результат тепер такий. Чого ми будемо вимагати? Ми будемо називати функцію ψ, яка відображає слова довжиною k в ансамбль з S кубіт, δ-Resistant (|Σk|, s)-квантової функцією — якщо виконає умови, що два різних слова довжини k породжують стан, який майже ортогонально, дельта-ортогонально.

Ця ситуація буде забезпечувати наступну умову. Якщо ми потім, для перевірки, почнемо застосовувати до них так званий реверс-тест, то чи вірно, що два стани однакові? Ймовірність того, що ми скажемо «так» виявиться більше, ніж дельта-квадрат для різних слів. Якщо слова однакові, то ми будемо говорити «так» з ймовірністю 1. Це якраз те, що нам потрібно.

Теорема доводиться досить просто. Виявляється, якщо ми хочемо будувати такі δ-Resistant (|Σk|, s)-квантові функції, то s не може бути менше, ніж log(k) – log(log(1 + √(2/1 – δ))) – 1.

Нижня оцінка є. Можна будувати такі хороші дельта-стійкі квантові функції, які близькі до теоретичної нижньою оцінкою? Дивно, але виявляється — можна.



Забігаючи вперед, я оголошую результат, який говорить, що якщо у нас є виправляє помилки лінійний код, який влаштований так, що слова довжини k кодуються словами довжини n і ми працюємо у відповідному полі Fq, то тоді ми можемо для будь-якого заздалегідь обраного δ і для такого Δ, яке пов'язане з характеристиками цього коду d від хеммингового відстані n, побудувати довжину коду. При цьому число кубіт, що нам для цього потрібно, — не більше, ніж log(n).



Знову забігаючи вперед — результат ми реалізували, подивилися, як це буде виглядати на дуже красивому код Ріда-Соломона. І виявилося, що для нього виходять такі характеристики. Якщо довжина коду на константу більше довжини вихідного повідомлення, то для такого порогу помилки, як k-1/q + Θ, ми можемо побудувати відповідний квантовий хеш-код з характеристиками log(log q(q)) і таким собі доважком. І річ ця досить близька до нижньої оцінки, яка тут присутня.

Це виявилося для нас дивним. Коли я це розповідав на семінарі в фізико-технологічному інституті, Олександр Семенович Холево, почувши нижню оцінку, сказав: правдоподібно, так, — а як конструювати? Коли ми з ним обговорили варіант, що це, наприклад, можна зробити з використанням коду Ріда-Соломона, він погодився, що дещо в цьому напрямку зробити вдалося.



Це опис доповіді, який тут подається. А тепер я трохи більш докладно поговоримо ось про що…

Перший приклад був такий: маємо слово, хешируем його в один квантовий біт. Тепер потрібно, маючи ансамбль з s кубіт, визначити, яким чином туди всі це кодувати і хешировать. Що за механізм такий повинен бути? Для відповіді на таке питання ми пропонуємо поняття квантового хеш-генератора.

Перші приклади. Як завжди, виявляється, що в світі щось таке було, але говорилося трошки іншою мовою. Виникло таке поняття, як quantum fingerprinting або квантові відбитки пальців. Це було в 2002 році зроблено Гаррі Бурманом з співавторами для спеціальної комунікаційної моделі обчислення з арбітром. І виявилося, що це — спеціальний двійковий випадок квантового хешування.

Одна з задач в теорії кодування — перейти від двійкових кодів до більш ніж двійкового алфавіту. Коди Ріда-Соломона принципово не двійкові, тут гра якісна. Коли ми переходимо до поля іншої характеристики, більше ніж 2, то воно тут дійсно просувається.

Я покажу перші приклади того, що було зроблено. А потім покажу, як перейти від кодів, що виправляють помилки, і вкластися в цю конструкцію.



Є епсилон-універсальне хеш-сімейство. Використовуючи якесь сімейство функцій, я почну генерувати одну квантову функцію. Є набір класичних лінійних функцій, є поле Fq. З нього беремо коефіцієнти і маємо набір функцій H = {h1,..., hT}. Тепер за допомогою функції h ми генеруємо однокубитные квантові функції ось таким чином. Для простоти я буду працювати не з фазами, а з речовими амплітудами. У якомусь сенсі це інтуїтивно зрозуміло, хоча фізики для своєї реалізації попросили переписати все на мову фази, тому що фазову річ легше реалізовувати.

Тепер ми заготовляємо набір таких квантових функцій: |ψhj(w)⟩ = cos2πhj(w)/q|0⟩ + sin2πhj(w)/q|1⟩.

Потім збираємо ці функції в одну таким чином: |ψH(w)⟩ = 1/√T|j⟩|ψhj(w)⟩.

Змістовно ця запис означає, що ми равноамплитудно або равновероятностно одночасно запускаємо обчислення всіх цих T-функцій h. І вибудовуємо обчислення таким чином — квантова фізика дозволяє це зробити. Перед нами математична запис того, що фізика дозволяє зробити.

Регістр j потрібно трактувати як двійковий запис числа j. А раз так, то нам достатньо мати log(T) біт, їм відповідає стан кубіта. Не буду говорити детально, як це зроблено. І log(T) кубіт керують обчисленням останнього кубіта. У відповідному подпространстве кожне з подпространств управляє обертанням одного останнього кубіта — в якому загорнута вся інформація. Останній кубіт обертається усіма цими T можливостями — вони таким чином забезпечують log(T) квантових бітів.



Перейду до конкретного прикладу, який був запропонований Бурманом, Кливом, Уотросом і де Вольфом. Вони взяли довільний виправляє помилки двійковий код з хэмминговым відстанню d, слова довжини k в якому кодуються словами довжини n, та розглянули як раз те, що я показав на попередньому слайді.

Одночасно працює система з log(n) кубіт. Кожен регістр — такий, що він обертає останній кубіт у відповідності зі значенням Eі(w). Оскільки цей код — двійковий, то поворот здійснюється тільки на 90 градусів. Або останній кубіт залишається в нулі, або повертається на 90 градусів. І цей ансамбль загортається в систему з log(n+1) кубіта, який керує поведінкою останнього.

Але вони цією мовою не говорили, у них була інша задача, їх конструкція переписується таким ось чином. І виявилося, що ця функція хороша. Вона дельта-стійка для слів довжини k, якщо ми маємо s кубіт і якщо s ось таке. Тут все добре.



Наступний крок ми робили з Олександром Васильєвим. Він у 2009 році, використовуючи цю конструкцію, захистив дисертацію. Ми теж не знали тоді, що це хешування, а відображали квантові відбитки пальців на випадок довільного скінченного поля. Була придумана конструкція. Як завжди, виявилося, що ця конструкція, будучи зовсім іншою мовою, була використана Аві Угдерсоном і Разборовым в 1993 році для інших завдань. Фактично інтерпретуючи їх результат на нашій мові, ми говоримо, що можна підібрати якесь невелике безліч порядку log(q) з таких функцій: T = ⎡(2/δ2) ln(2q)⎤.

Тим самим безліч таких лінійних функцій, не дуже велика в порівнянні з log(k), дозволяє утворити дуже хорошу загальну квантову хеш-функцію. Вона дельта-стійка, і вона кодує слова у множині q, елементи поля інтерпретуються як слова довжиною log(k), і тут досить мати s кубіт.



Узагальнюючи ці конструкції, ми одержуємо наступне: з'являється поняття квантового хеш-генератора. Ми будемо говорити, що сімейство функцій G — квантовий хеш-функції генератор такого виду. Якщо ми можемо побудувати подібні для кожної функції і яким чином відобразити їх в ансамбль з l кубітів, а також, зібравши їх разом, отримати квантову хеш-функцію, яка є дельта-стійкою з такими характеристиками, що слова довжини k кодуються d+l квантум-біт, то таке сімейство ми будемо називати квантовим хеш-генератором.



Визначення таке, що конструкція Бурмана і його співавторів і наша конструкція 2008 року вкладаються в це поняття.

Якщо ми маємо квантовий хеш-генератор, ці функції можна будувати по-різному. Швидше за все, хеш-генератор неоднозначно визначає квантову хеш-функцію. На ці теми можна розмовляти далі.



Тепер — центральна теорема, яка пов'язує всі разом. Перша умова: ми беремо епсилон-універсальне хеш-сімейство, яке має такі характеристики, N функцій, і за допомогою них кодуємо слова довжини k в поле Fq. Друга умова: як Н ми беремо якийсь вже готовий квантовий хеш-генератор — а такі є. Зокрема, нам зручніше брати той квантовий хеш-генератор, який ми з Олександром Васильєвим придумали.

Влаштовуючи суперпозицію цих двох сімейств, ми спочатку застосовуємо функції сімейства F, а потім загортаємо їх функції з множини Н. Тоді нове сімейство є квантовим хеш-генератором з ось такими характеристиками. Воно дельта-стійке, воно кодує слова довжини k в ансамбль з s кубіт. Δ ≦ ε + δ — це відповідна характеристика епсилон-універсального хеш-сімейства і дельта-характеристика дельта-стійкості вже готового квантового хеш-генератора, який ми беремо. Ну і число кубіт залежить від числа функцій в епсилон-універсальному сімействі і від числа функцій в готовому квантовому хеш-генераторі.

Причому тут нам потрібні логарифми від числа відповідних функцій. Це в певному сенсі гарантує, що квантові хеш-функції експоненціально дешевше будувати, ніж мати такі речі початково.



З'явилася ціла група нових прикладів, яка використовувала конструкції, існуючі в computer science. Фрейволд, математик з Риги, в 1979 році запропонував функцію, яка називається «класичний fingerprinting», засновану на тому, що ми хочемо порівняти два різних слова і порівнюємо їх з різних модулів. Тут відіграє китайська теорема про залишки. Я про це багато говорити не буду, але якщо два слова рівні, то вони по кожному модулю pі дорівнюють невеликим модулем. А якщо два слова не рівні, то для більшості pі відповідні значення теж не рівні.

Перша робота була опублікована у збірнику «Проблеми кібернетики» на межі 70-80-х років і, я пам'ятаю, досить добре розповідалася на семінарі у Олега Борисовича Лупанова в МДУ.



Виявляється, що це сімейство є, звичайно, універсальним хеш-сімейством з такими характеристиками, 1/с-універсальним сімейством, де з — відповідний спосіб вибору числа всіх функцій. А раз це епсилон-універсальне хеш-сімейство, то, комбінуючи його з сімейством, яке ми з Олександром Васильєвим придумали і яке, у свою чергу, ґрунтується на результатах аналізу Вигдерсона, можна з'ясувати, що за допомогою класичного сімейства fingerprinting Фрейволда породжується квантова хеш-функція з такими характеристиками: дельта-стійка, слова довжини k відображаються в s кубіт. Дельта залежить таким чином: дельта маленька — це характеристика нашого сімейства, 1/с — характеристика Фрейволда, ось стільки кубіт достатньо і нижня оцінка — ось така. Нижня і верхня оцінка тут досить близькі. Виявилося, що конструкція Фрейволда хороша.

Класичні хеш-сімейства, засновані на конструкції Фрейволда, не використовують в практиці, тому що є багато простих чисел, треба їх все тримати. Використовуються дещо інші характеристики, наприклад дуже відоме сімейство — універсальне лінійне хеш-сімейство.



У всіх підручниках з алгоритмами є такий приклад. Він був запропонований творцем універсальних хеш-родин Калтором і Вегманом в 1979-1980-х роках — що сукупність таких лінійних функцій є універсальне класичне хеш-сімейство. Доказ просте і красиве.

Зрозуміло, ми беремо його, наше сімейство, яке ми з Сашею Васильєвим придумали. Ось воно. У результаті виходить така конструкція. Виходить квантовий хеш-генератор, який генерує квантову хеш-функцію з такими характеристиками. Це характеристика лінійного універсального сімейства, а дельта — наша характеристика. Верхня оцінка така, число кубіт — те, що тут потрібно.



І виявилося, що це сімейство експоненціально дорожче наявної нижньої оцінки. Нижня оцінка — log(k), а тут верхня оцінка — k. Такі відомі і використовуються речі, виявляється, у квантовому світі краще не застосовувати.



Ось і результат, який на початку анонсував. Якщо є виправляє помилки лінійний код n-k-d, який слова довжини k кодує в слова довжини n, працюючи в полі Fq, то тоді є квантовий хеш-генератор. А значить, ми можемо будувати відповідну квантову хеш-функцію, яка володіє такими властивостями, що стійкість визначається величиною Δ = (1 – d/n) + δ. Це характеристика коду, що виправляє помилки, а δ — характеристика сімейства, яке ми використовуємо. s, в свою чергу, ось таке: s ≦ log(n) + log(log(q)) + 2*log(1/δ) + 4.

Доказ засноване на результаті 1994 року, який говорить про те, що якщо ми маємо код, що виправляє помилки, з відповідними характеристиками, то тоді ми можемо побудувати і універсальне хеш-сімейство. І навпаки: якщо ми маємо універсальне хеш-сімейство з такими характеристиками, то ми можемо побудувати відповідний код, що виправляє помилки.

Універсальні хеш-сімейства визначилися і з'явилися на рубежі 70-80-х років. Коди, що виправляють помилки — це, в свою чергу, класика: всі іменні коди з'явилися на рубежі 50-60-х років. Дивно, що така дуже проста зв'язок була виявлена тільки в 1994 році. Хто знає, той знає, а якщо ні — корисно почитати. Буде цікаво.



Використовуючи цю теорему, беремо код Ріда-Соломона — він дуже красивий, у всіх підручниках і курсах розповідається і будуємо хеш-генератор, відповідну йому хеш-функцію.



Це те, що я анонсував у першій частині розповіді. Така конструкція виявилася оптимальною.
Отже, ми тепер можемо все це поширити і на інші конструкції. Їх багато. Зокрема, мене запитують, чому не Ріда-Маляра. Зрозуміло, його теж можна. Бодчи-Удхури — звичайно, теж все лягає, красиво. Але код Ріда-Соломона — дуже класичний. Хоч у школі розповідай.



Це можна розписати детальніше. Можна і почитати, немає сенсу говорити докладно.



Ось над чим ми працюємо і куди все це рухається. Я спеціально написав таку шпаргалку. Почати з того, що цей текст я, зрозуміло, залишаю і якщо є питання — скажу по ньому.

Які реальні фізичні проблеми тут з'являються? Фізики зараз працюють над так званої квантової пам'яттю. Вони розуміють її так, що носієм кубіта є фотон. Він прилітає в речовину, і речовина його поглинає. Через деякий час, впливаючи на це речовина, можна излучить фотон в точно такому ж стані. Стан фотона є стан кубіта.

І якщо такі речі шикуються, це є підсилювач сигналу, репітер. Зараз мова йде про побудову квантових репітерів. На 100 км по оптоволокну йдуть фотони, потім вони поглинаються, починають пропадати. Якщо через кожні 100 км поставити такий квантовий репітер, який повторює сигнал, вирішиться проблема передачі інформації. Отже, перша задача — побудова репітера.

До квантових комп'ютерів, на яких можна буде реалізовувати Шора, поки далеко. Перше завдання — вибудувати квантовий репітер. Що з квантовим repeater є можна зробити? Речовина поглинуло, перед випромінюванням можна на нього впливати, перетворити стан і отримати вже в новому стані. Зараз йде боротьба про те, що якщо з десяток кубіт, ансамбль, можна запам'ятати і витягти, то така кількість буде нормальним для побудови хеш-функції.

Дивіться, якщо s близько 10, то для яких полів це вже можна робити? Або якщо s близько 100? Технології зараз, схоже, наближаються до того, що при десятки і сотні вже можна буде працювати. Якщо s виявиться близько 100 з використанням такого суто теоретичного результату, як код Ріда-Соломона, то які функції можна буде стійко хешировать — і з якими полями?

Відразу можу сказати, з ким ми співпрацюємо. У Москві це МДУ і Міжнародний лазерний центр МДУ. На ВМК академік Валієв організував кафедру квантової інформатики, після його смерті утворилася кафедра… не пам'ятаю, як називається. Воєводін займається супервычислениями, суперкомп'ютерами. Всередині зберігається співтовариство, яке працює в області квантової інформатики.

У Стекловском інституті Семенов, Олександр Семенович Холево, зрозуміло. І центральним стає Фізико-технологічний інститут РАН. Він зараз добре курує ці питання, ми активно взаємодіємо. Але виходить, що всі, кого я перерахував, — це в основному люди, які прийшли сюди з фізики. Ми алгоритми можемо запропонувати, але до алгоритмів потрібна хороша фізика. Мова зараз йде про технології.

І є відповідна лабораторія, відділ в Академії криптографії РФ. Хороша група у Чорноголовці, в Новосибірську, в ІТМО. Є серія конференцій «Квантова криптографія» у світі. Цього року конференція проходила в Парижі, в майбутньому році пройде в Токіо, і т. д. В Цюріху проходила в Сінгапурі. Ком'юніті там складають групи, які займаються питанням квантової передачі ключа. Відомий такий квантовий протокол ВВ-84, Бене-Броссарда. Вони його в 1984 році винайшли, а зараз навколо нього ціла конференція: більше ста чоловік збирається і фізики змагаються в реалізації подібних речей.

Тут вже алгоритмів не так багато, відбувається фізичне вилизування всього цього. І зараз всі чекають, коли нарешті те, що називається квантовою пам'яттю, буде готове, коли можна буде це справа експериментально у багатьох місцях повторити, почати вибудовувати протоколи.

У Казані є група, яка займається саме питаннями квантової пам'яті. Їх зараз найбільше цікавить робота з фазами, вони на цьому мовою можуть влаштовувати досить хороші експерименти.

Лабораторії майже готові, але вийшло так, що долар став удвічі дорожче, і хороше обладнання, яке хлопці хотіли замовити раніше, тепер ніяк не виходить придбати. Але це наступне питання.

Мабуть, все. Спасибі.

— Як ви оцінюєте ймовірність перехоплення зашифрованої інформації у створенні алгоритму раскриптовки ключа?

— Я спілкуюся з Сергієм Куликом з Міжнародного лазерного центру. Я не фахівець в області фізики, але вже класичний алгоритм ВВ-84 — хлопці сказали, він повністю розвалюється. В області фізики є цілі групи робіт, на основі яких вони майже всі зробили заново. ВВ-84 хороший, щоб розповідати студентам принципи. Тобто, як завжди, є теоретична навчальна криптографія, а коли мова доходить до практичних речей — там все трохи по-іншому.

В цьому році мені пощастило приїхати на конференцію з квантової криптографії. І був там такий день, коли Пітера Шора посадили. Бене, Бросард — вони там п'ють каву і розповідають, як все чудово. Вони кажуть: це тече, розколюється, все по-іншому роблять. Виступали китайці. Кажуть, у них вже між Пекіном і Гонконгом мережа працює. Італійці розповідають, що опрацьовують канал з супутником. Він інший, не ВВ-84, але це саме квантове породження ключа. Проте вже інші речі працюють, все по-іншому робиться.

— Коли ви говорили, хто працює над цим, то, наскільки я зрозуміла, в основному згадали фізиків. А математики до вас доходять? Я розумію, що це досить складна фізика, але і математика тут досить складна.

— Так, я це теж собі заготовив. Цікаві групи — у нас в Росії їх поки немає. Річард Джоссе — людина з теоретичної фізики прийшов, але став фахівцем в області computer science. Він, напевно, трохи більше фізик. Але він прекрасно розуміє, що відбувається в computer science — не тільки в області квантової, але й взагалі в теорії складнощів, наприклад. Він в Кембриджі очолює відповідний центр. Такі люди є.

В Амстердамі Гаррі Бурман очолює відповідний центр в області квантової інформатики, але він не фізик, а більше математик.

Скотт Ааронсон в MIT. Він кінчав Берклі, молодий чоловік, один з найбільш визнаних людей в цій області.

Умеш Везеране в Берклі — Скотт Ааронсон є його учнем. Андрес Амбайнис в Ризі — як раз випускник Берклі. Приблизно така вона, середа математиків. У цій області, звичайно, багато алгоритмів. Коли Пітер Шор придумав цей алгоритм, наступним — тим, хто придумав швидкий пошук в квантової базі даних, — став Гровер. Мова йде про серйозне, але настільки теоретичному результаті! Уявіть: треба загнати велику базу даних в суперпозицію і тримати в квантовому регістрі. І тоді пошук у цій невпорядкованою базі можна зробити швидше на квадратний корінь з повного перебору. Математично — красиво. Зараз навколо нього багато чого накрутилось, інші завдання з'явилися, латвійські математики там багато і добре працюють.

З приводу математики я б сказав, що практично у всіх великих університетах є ці центри. Але, на жаль, не в Росії. У Росії це МДУ, кафедра квантової інформатики — вона зараз трохи по-іншому називається, на ВМК. Наша група складається з тих, хто займається алгоритмами і порівняльним аналізом. Відразу можу сказати, що Росія поки сильно відстає.

Що зробили в цьому плані в Сінгапурі? Відома країна. Вони зібрали європейців: хтось із Кембриджа очолює фізиків, хтось із математиків знаходиться на позиції principal investigator у Франції, Хартман Клаук з Франкфурта там працює. Це ком'юніті між собою досить добре спілкується, проводить конференції. У Цюріху хороша група в області квантової інформатики — математики працюють з фізиками, їздять один до одного. Росія поки трошки в стороні. З цією групою треба обов'язково почати взаємодіяти більш щільно.

— Хотів би додати про Скотта Ааронсона. Він приїжджав в Росію, читав доповідь на конференції Computer Science in Russia, отримав премію за кращу роботу. Крім того, у нього є дуже цікавий блог scottaaronson.com/blog. Там як раз про квантові обчислення багато чого написано в популярному викладі, він не тільки вчений, а й великий популяризатор науки. А ще у нього є цікава книжка, поки тільки англійською написана. Називається Quantum Computing since Демокріта, «Квантові обчислення починаючи з Демокріта». Я її читав, отримав велике задоволення.

— Так, і на днях я з розсилки отримав інформацію про те, що зараз обговорюється виникнення brain module або ще якоїсь сутності, яка намагається швидко вирішити NPPO-повну завдання. Йде суперечка, Ааронсон бере участь. Подивіться, це цікаво. До речі, complexity zoo саме він створив — де всі класи складності. Він був аспірантом в Берклі, потім у нього це купили. Добру справу зробили.

Спасибі.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.