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

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

Існують класичні криптосистеми, які спираються на обчислювально складні завдання та мають низку суттєвих відмінностей від зазначених вище систем, через що їх значно складніше вирішити. Ці системи незалежні від квантових обчислень, і, отже, їх вважають квантово-стійкими (quantum-resistant), або постквантовими криптосистемами.

Постквантова криптографія у свою чергу відрізняється від квантової криптографії, яка займається методами захисту комунікацій, заснованих на принципах квантової фізики.

Алгоритми

Постквантові криптографічні конструкції здатні врятувати криптографічний світ від квантових атак. Хоча квантовий комп'ютер і знищить більшість традиційних алгоритмів (RSA, DSA, ECDSA), але надшвидкі обчислення не скасують повністю криптографії, оскільки постквантова криптографія, переважно, зосереджена на п'яти різних підходах, які вирішують проблему квантових атак.

Криптографія, заснована на геш-функціях

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

Криптографія, заснована на кодах виправлення помилок

Один із найперспективніших кандидатів на постквантові криптосистеми. Класичним прикладом є схеми шифрування McEliece та Niederreiter.

Криптографія, заснована на ґратках

Класичним прикладом схем шифрування є Ring — Learning with Errors або старіші NTRU, GGH і криптосистема Міччанчо.

Криптографія, заснована на багатовимірних квадратичних системах

Однією з найцікавіших схем є підпис з відкритим ключем Жака Патаріна HFE, який він запропонував 1996 року, як узагальнення пропозицій Мацумото (Matsumoto) та Імаї (Imai).

Шифрування зі секретним ключем

Яскравим прикладом є шифр Rijndael, запропонований 1998 року, згодом перейменований на AES (Advanced Encryption Standard).

Шифрування з використанням суперсингулярної ізогенії

Аналог протоколу Діффі — Геллмана, заснований на блуканні в суперсингулярному ізогенному графі, що дозволяє двом і більше сторонам отримати спільний секретний ключ, використовуючи незахищений від прослуховування канал зв'язку.

Приклади криптографічних атак на RSA

У документі, який 1978 року опублікували розробники криптографічного алгоритму з відкритим ключем RSA (абревіатура від прізвищ Rivest, Shamir та Adleman), згадано новий алгоритм Річарда Шреппеля «лінійне сито» (англ. linear sieve), який факторизував будь-який модуль RSA $n$ довжини $[\log _{2}n]+1$ біт, використовуючи $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2}}$ найпростіших операцій. Таким чином, щоб цей алгоритм вимагав щонайменше $2^{b}$ простих операцій, необхідно вибирати $n$ довжини принаймні не менше ніж $(0,5+o(1))b^{2}/{\log _{2}b}$ біт. Оскільки $0{,}5+o(1)$ означає, що щось збігається до $0{,}5$ при $b\to \infty$, то для з'ясування правильного розміру $n$ за скінченного $b$ потрібен ретельніший аналіз швидкості «лінійного сита».

В 1988 Джон Поллард запропонував новий алгоритм факторизації, який називають «загальний метод решета числового поля». Цей алгоритм факторизував RSA-модуль $n$ розмірності $\log _{2}n$ біт, використовуючи $2^{(1,9\dotso +o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3}}$найпростіших операцій. Таким чином, щоб алгоритму знадобилося як мінімум $2^{b}$ найпростіших операцій, потрібно вибирати $n$ довжини не менше ніж $(0,016\dotso +o(1))b^{3}/(\log _{2}b)^{2}$ біт.

Від 2008 року найшвидші алгоритми факторизації для класичних комп'ютерних архітектур використовують щонайменше $2^{(const+o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3}}$ найпростіших операцій. Були деякі покращення в значеннях $const$ та в деталях $o(1)$, але зрозуміло, що $1/3$ оптимальне, і що вибір модуля $n$ довжиною приблизно рівною $b^{3}$ біт, дозволить чинити опір усім можливим атакам на класичних комп'ютерах.

1994 року Пітер Шор запропонував алгоритм, який факторизував будь-який RSA-модуль $n$ розмірності $b=\log _{2}n$ біт, використовуючи $b^{2+o(1)}$ (точніше $b^{2}\cdot \log(b)\cdot \log(\log(b))$) кубітових операцій на квантовому комп'ютері розміру порядку $2\cdot b^{1+o(1)}$ кубіт (і незначний обсяг допоміжних обчислень на класичному комп'ютері). Користуючись алгоритмом Шора, необхідно принаймні вибирати модуль $n$ бітовим розміром не менше ніж $2^{(0,5+o(1))b}$ біт, що є занадто великою кількістю для будь-якого цікавого для нас $b$.

Практичні застосування криптографічних конструкцій

Прикладів алгоритмів, стійких до квантових атак, дуже мало. Але, попри вищу криптографічну стійкість, постквантові алгоритми не здатні витіснити сучасних криптосистем (RSA, DSA, ECDSA тощо).

Розглянемо напади на криптосистему з відкритим ключем, а саме на алгоритм шифрування McEliece, який використовує двійкові коди Гоппи. Спочатку Роберт Мак-Еліс надав документи, в яких коди завдовжки $n$ зламуються за $2^{(0,5+o(1))n/{\log _{2}n}}$ найпростіших операцій. Таким чином, потрібно вибирати $n$ не меншим ніж $(2+o(1))b\log _{2}b$ біт, щоб алгоритму знадобилося як мінімум $2^{b}$ найпростіших операцій. Декілька наступних робіт скоротили кількість операцій атаки до $n^{\log _{2}n}=2^{(\log _{2}n)^{2}}$, але $(\log _{2}n)^{2}$ значно менше ніж $0{,}5n/{\log _{2}n}$, якщо $n$ велике. Тому покращені атаки досі використовують $2^{(0,5+o(1))n/{\log _{2}n}}$ найпростіших операцій. Що стосується квантових комп'ютерів, то їх використання призведе лише до зменшення константи $0,5$, що зовсім мало скоротить кількість операцій, необхідних для зламу цього алгоритму.

Якщо система шифрування McEliece так добре захищена, чому вона не приходить на зміну RSA? Причина в ефективності, зокрема в розмірі ключа. Відкритий ключ McEliece використовує приблизно ${n^{2}}/4$ ≈ ${b^{2}}(\log _{2}b)^{2}$ біт, тоді як для відкритого ключа RSA достатньо близько $(0{,}016\dots )b^{3}/(\log _{2}b)^{2}$ біт. Якщо $b\to \infty$, то $b^{2+o(1)}$ біт для McEliece, буде менше від $b^{3+o(1)}$ біт для RSA, але реальні рівні безпеки, такі як $b=128$, дозволяють RSA мати відкритий ключ довжиною кілька тисяч біт, тоді як для McEliece розмір ключа наближається до мільйона біт.

Конференція PQCrypto

Від 2006 року проводиться серія конференцій, присвячених постквантовій криптографії.

• PQCrypto 2006. Левенський католицький університет, Бельгія, від 23 до 26 травня
• PQCrypto 2008. Університет Цинциннаті, США, від 17 до 19 жовтня
• PQCrypto 2010. Дармштадт, Німеччина, від 25 до 28 травня
• PQCrypto 2011. Тайбей, Тайвань, від 29 листопада до 2 грудня
• PQCrypto 2013. Лімож, Франція, від 4 до 7 червня
• PQCrypto 2014. Університет Ватерлоо, Канада, від 1 до 3 жовтня
• PQCrypto 2016. Попередній план: Фукуока, Японія, лютий 2016^{[уточнити]}

Див. також

• Криптографія на ґратках
• Алгоритм Шора

Посилання

• PQCrypto, the post-quantum cryptography conference
• Post-Quantum Cryptography. — Springer, 2008. — С. 245. — ISBN 978-3-540-88701-0.
• ETSI Квантова безпека(англ.)
• NIST's Постквантовий криптопроєкт(англ.)
• PQCrypto Використання та розгортання(англ.)