Вступ
У 1994 році комп'ютерник Пітер Шор відкритий що якби квантові комп’ютери були колись винайдені, вони знищили б значну частину інфраструктури, яка використовується для захисту інформації, що поширюється в Інтернеті. Ця лякаюча можливість змусила дослідників з усіх сил намагатися створити нові, «постквантові» схеми шифрування, щоб зберегти якомога більше інформації від потрапляння в руки квантових хакерів.
На початку цього року Національний інститут стандартів і технологій ім виявлено чотирьох фіналістів у пошуках стандарту постквантової криптографії. Три з них використовують «решіткову криптографію» — схему, натхненну ґратками, регулярним розташуванням точок у просторі.
Гратчаста криптографія та інші постквантові можливості кардинально відрізняються від поточних стандартів. Але всі вони покладаються на математичну асиметрію. Безпека багатьох сучасних криптографічних систем базується на множенні та розкладанні на множники: будь-який комп’ютер може швидко помножити два числа, але можуть знадобитися століття, щоб розкласти криптографічно велике число на його прості складові. Завдяки цій асиметрії секрети легко закодувати, але важко розшифрувати.
Те, що Шор виявив у своєму алгоритмі 1994 року, полягає в тому, що хитрість факторингу робить його вразливим для атак квантових комп’ютерів. «Це дуже специфічна, особлива річ, яку може зробити квантовий комп’ютер», — сказав Кетрін Штанге, математик в Університеті Колорадо, Боулдер. Тож після Шора криптографи отримали нову роботу: знайти новий набір математичних операцій, які легко виконати, але майже неможливо скасувати.
Гратчаста криптографія є однією з найуспішніших спроб на сьогодні. Спочатку розроблений у 1990-х роках, він покладається на складність зворотного проектування сум балів.
Ось один із способів описати гратчасту криптографію: уявіть, що у вашого друга є решітка, яка являє собою лише купу точок у регулярному повторюваному візерунку по всій площині. Ваш друг хоче, щоб ви назвали 10 із цих пунктів. Але йому складно, і він не намалює всю решітку. Натомість він перераховує лише два пункти — перший з an x-значення 101 і а y-значення 19, інше з координатами [235, 44].
На щастя, легко знайти нові точки на решітці, тому що коли ви додаєте та віднімаєте будь-які дві точки на решітці, ви отримуєте третю точку в тій же решітці. Отже, все, що вам потрібно зробити, це скласти бали, які вам дав ваш друг, або помножити їх на цілі числа, а потім додати, або поєднати обидва. Зробіть це вісьмома різними способами, і ви зможете відповісти на запитання свого друга.
Але ваш друг все одно не задоволений. Він дає вам ті самі дві вихідні точки, а потім запитує, чи точка [2, 1] знаходиться на тій самій решітці. Щоб правильно відповісти на це запитання, вам потрібно знайти комбінацію [101, 19] і [235, 44], яка дає [2, 1]. Це завдання набагато складніше, ніж перше, і, ймовірно, ви просто вгадаєте та перевіряєте, щоб отримати відповідь.* Ця асиметрія лежить в основі гратчастої криптографії.
Якщо ви справді хочете використовувати решітчасту криптографію для обміну інформацією, ви повинні зробити наступне. Уявіть, що друг (кращий!) хоче надіслати вам безпечне повідомлення. Ви починаєте з квадратної сітки чисел. Скажімо, він складається з двох рядків і двох стовпців і виглядає так:
Тепер ви придумали закритий «ключ», який знаєте лише ви. У цьому прикладі припустимо, що ваш закритий ключ складається лише з двох секретних чисел: 3 і −2. Ви множите числа в першому стовпчику на 3, а числа в другому стовпчику на −2. Додайте результати в кожному рядку, щоб отримати третій стовпець із двома записами.
Приклейте новий стовпчик до кінця сітки. Ця нова сітка з трьох стовпців є вашим відкритим ключем. Поділіться ним вільно!
(Сценарій у реальному світі буде дещо складнішим. Щоб утримати хакерів від декодування вашого закритого ключа, ви повинні додати трохи випадкового шуму в останній стовпець. Але тут ми проігноруємо цей крок заради простоти. )
Тепер ваш друг використовуватиме відкритий ключ, щоб надіслати вам повідомлення. Вона думає про два власних таємних числа: 2 і 0. Вона множить числа в першому рядку на 2, а числа в другому рядку на 0. Потім вона підсумовує результати в кожному стовпчику, щоб отримати третій рядок.
Тепер вона прикріплює новий рядок до нижньої частини сітки та надсилає його вам. (Знову ж таки, у реальній системі їй потрібно було б додати трохи шуму до свого рядка.)
Зараз ви прочитаєте повідомлення. Для цього ви перевіряєте, чи правильний останній рядок вашого друга. Застосуйте свій особистий ключ до перших двох записів її рядка. Результат повинен відповідати останньому запису.
Ваш друг також може надіслати вам рядок із неправильним числом в останньому стовпчику. Вона знає, що це число не збігається з вашими розрахунками.
Якщо ваш друг надішле рядок, де останнє число є правильним, ви сприймете це як 0. Якщо вона надішле рядок, де число буде неправильним, ви інтерпретуєте його як 1. Таким чином, рядок кодує один біт: 0 або 1.
Зауважте, що сторонній зловмисник не матиме доступу ні до вашого закритого ключа, ні до ключа вашого друга. Без них зловмисник не матиме жодного уявлення, чи остаточне число правильне чи ні.
На практиці ви хотіли б надсилати повідомлення довжиною більше одного біта. Тож люди, які хочуть отримати, скажімо, 100-бітне повідомлення, згенерують 100 нових стовпців замість одного. Потім відправник повідомлення створить один новий рядок, змінивши останні 100 записів, щоб закодувати 0 або 1 для кожного запису.
Якщо решітчаста криптографія дійсно буде реалізована, вона матиме незліченну кількість нюансів, не охоплених у цьому сценарії. Наприклад, якщо ви хочете, щоб повідомлення було справді захищеним від сторонніх очей, матриця повинна мати неймовірну кількість записів, що робить усе це настільки громіздким, що його не варто використовувати. Щоб обійти це, дослідники використовують матриці з корисною симетрією, які можуть скоротити кількість параметрів. Окрім цього, існує цілий набір налаштувань, які можна застосувати до самої проблеми, до способу включення помилок тощо.
Звичайно, завжди можливо, що хтось знайде фатальну помилку в ґратчастій криптографії, як Шор зробив для факторингу. Немає гарантії, що певна криптографічна схема працюватиме проти будь-якої можливої атаки. Криптографія працює, поки її не зламано. Дійсно, на початку літа була зламана одна багатообіцяюча схема постквантової криптографії використовуючи не квантовий комп’ютер, а звичайний ноутбук. За словами Штанге, весь проект створює незручний парадокс: «Я вважаю таким дивовижним у криптографії те, що ми побудували цю інфраструктуру для людської раси на твердому переконанні, що наші людські можливості обмежені», — сказала вона. «Це так відстало».
*: Відповідь, якщо вам цікаво, 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [повернутися до статті]
