Відомий алгоритм криптографії отримує оновлення | Журнал Quanta

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

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

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

"Це було справді захоплююче", - сказав Кріс Пайкерт, криптограф з Мічиганського університету, який не брав участі в роботі. Інструмент був предметом вивчення протягом десятиліть, сказав він. «Завжди приємно, коли ціль, над якою працювали так довго... показує, що ще можна знайти сюрпризи».

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

Решітку можна описати за допомогою її «основи». Це набір векторів (по суті, списків чисел), які можна комбінувати різними способами, щоб отримати кожну точку в решітці. Уявімо решітку з базисом, що складається з двох векторів: [3, 2] і [1, 4]. Решітка — це лише всі точки, до яких можна дійти шляхом додавання та віднімання копій цих векторів.

Ця пара векторів не є єдиним базисом решітки. Кожна решітка принаймні з двома вимірами має нескінченну кількість можливих основ. Але не всі основи однакові. Базис, вектори якого коротші та ближчі до прямих кутів один до одного, зазвичай легше працювати та корисніший для вирішення деяких обчислювальних задач, тому дослідники називають ці бази «хорошими». Прикладом цього є пара синіх векторів на малюнку нижче. Бази, що складаються з довших і менш ортогональних векторів, як червоні вектори, можна вважати «поганими».

Це робота для LLL: дайте йому (або його братам) основу багатовимірної решітки, і він виплюне кращу. Цей процес відомий як скорочення базису решітки.

Яке це все має відношення до криптографії? Виявляється, завдання зламу криптографічної системи в деяких випадках може бути перероблено як інша проблема: пошук відносно короткого вектора в решітці. І іноді цей вектор можна взяти зі скороченого базису, згенерованого алгоритмом у стилі LLL. Ця стратегія допомогла дослідникам повалити системи, які на перший погляд мало пов’язані з решітками.

У теоретичному розумінні вихідний алгоритм LLL працює швидко: час, необхідний для виконання, не залежить від розміру вхідних даних, тобто розміру решітки та розміру (у бітах) чисел у базисні вектори. Але він збільшується як поліноміальна функція, і «якщо ви справді хочете це зробити, поліноміальний час не завжди настільки здійсненний», сказав Лео Дюкас, криптограф Національного дослідницького інституту CWI в Нідерландах.

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

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

Попередня робота дотримувалася подібного підходу: A Папір 2021 також поєднує рекурсію та керування точністю для швидкої роботи з великими ґратками, але це працювало лише для певних типів ґраток, а не для всіх тих, які важливі в криптографії. Новий алгоритм добре працює в значно ширшому діапазоні. "Я дуже радий, що хтось це зробив", - сказав Томас Еспітау, дослідник криптографії в компанії PQShield і автор версії 2021 року. Робота його команди запропонувала «доказ концепції», сказав він; новий результат показує, що «ви можете зробити дуже швидке скорочення решітки надійним способом».

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

Алгоритми в стилі LLL також можуть відігравати важливу роль у дослідженнях, пов’язаних із криптографічними системами на основі решітки, призначеними для залишатися в безпеці навіть у майбутньому з потужними квантовими комп’ютерами. Вони не становлять загрози для таких систем, оскільки для їх ліквідації потрібно знайти коротші вектори, ніж можуть досягти ці алгоритми. Але найкращі відомі дослідникам атак використовують алгоритм у стилі LLL як «базовий будівельний блок». Вессель ван Вурден, криптограф в університеті Бордо. У практичних експериментах з вивчення цих атак цей будівельний блок може сповільнити все. Використовуючи новий інструмент, дослідники зможуть розширити спектр експериментів, які вони можуть проводити з алгоритмами атаки, пропонуючи більш чітку картину того, як вони працюють.

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів інформатики і ви будете введені, щоб виграти безкоштовно Quanta товар