Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля»
In the paper the influence of quantum computers on the security of key encapsulation mechanisms is presented and analyzed. The current state of post-quantum cryptography and post-quantum cryptanalysis algorithms is considered. The current state of the process of standardization of post-quantum crypt...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/286 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479655063224320 |
|---|---|
| author | Kaptol, Yevhenii |
| author_facet | Kaptol, Yevhenii |
| author_institution_txt_mv | [
{
"author": "Yevhenii Kaptol",
"institution": "аспірант, Харківський національний університет ім. В.Н.Каразіна, Площа Свободи, 6, 61000, Харків"
}
] |
| author_sort | Kaptol, Yevhenii |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | In the paper the influence of quantum computers on the security of key encapsulation mechanisms is presented and analyzed. The current state of post-quantum cryptography and post-quantum cryptanalysis algorithms is considered. The current state of the process of standardization of post-quantum cryptography for use in the transition period is considered and analyzed, and a conclusion is made that there are no alternatives among candidates for standardization among key encapsulation mechanisms. The development of post-quantum cryptanalysis methods and the reduction of quantum resources required for their implementation are considered. It is concluded that it is necessary to choose and use key encapsulation mechanisms from the list of available options that meet the requirements of post-quantum cryptography. In the paper the security of the DSTU 8961:2019 key encapsulation mechanism in the random oracle model is described and analyzed. |
| first_indexed | 2026-06-09T01:09:43Z |
| format | Article |
| fulltext |
106
doi.org/10.15407/fmmit2023.36.106
Аналіз впливу квантових комп’ютерів на безпеку
механізмів інкапсуляції ключів на прикладі ДСТУ
8961:2019 «Скеля»
Євгеній Каптьол1
1 аспірант, Харківський національний університет ім. В.Н.Каразіна, Площа Свободи, 6, 61000, Харків, e-mail:
kaptevg@gmail.com
У роботі наведено та проаналізовано вплив квантових комп’ютерів на безпеку механізмів
інкапсуляції ключів. Розглянуто сучасний стан постквантової криптографії та
постквантових алгоритмів криптоаналізу. Розглянуто та проаналізовано сучасний стан
процесу стандартизації постквантової криптографії для використання в перехідний
період та зроблено висновок про відсутність альтернатив серед кандидатів для
стандартизації серед механізмів інкапсуляції ключів. Розглянуто розвиток методів
постквантового криптоаналізу та зменшення необхідної для їх реалізації квантових
ресурсів. Зроблено висновок про необхідність обрання та використання механізмів
інкапсуляції ключів з доступних варіантів, що задовольняють вимоги постквантової
криптографії. У роботі наведено опис та досліджено безпеку механізму інкапсуляції
ключів ДСТУ 8961:2019 у моделі випадкового оракула.
Ключові слова: квантовий комп’ютер; постквантова криптографія;
механізм інкапсуляції ключів; «Скеля»
Вступ. Розвиток потужностей квантових комп’ютерів, розмірів квантових
регістрів та квантових алгоритмів ставить під загрозу сучасну криптографію з
відкритим ключем. Особливо актуальною ця загроза стає з урахуванням факту
початку комерціалізації квантових обчислень, про що свідчать широке
поширення Quantum as a Service (QaaS) (таких як IBM Quantum[1]) та продаж
окремих зразків квантових комп’ютерів (як наприклад продукція компанії D-
wave[2]) Згідно з BSI[3], для практичного використання сучасних
криптографічно релевантних алгоритмів необхідна успішна реалізація квантової
корекції помилок (QEC). Таким чином, на час перехідного періоду одним з
основних способів боротьби з цією загрозою є постквантова криптографія.
1. Аналіз стану постквантової криптографії
Постквантові алгоритми базуються на математичних задачах, які не мають ні
класичних ні квантових ефективних алгоритмів розв’язку. Основною особливістю
постквантової криптографії є можливість її реалізації на звичайних апаратних
засобах. Постквантова криптографія може бути реалізована за допомогою різних
підходів, серед яких можна виділити: криптографію на основі кодів, криптографію
на основі решітки, криптографію на основі гешування, криптографію на основі
УДК 004.056.55
mailto:kaptevg@gmail.com
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 106-110
107
ізогенії та багатовимірну криптографію.
У зв’язку з потребою в постквантовій криптографії для застосування в
перехідний та квантовий періоди та з метою стандартизації постквантових
алгоритмів, з боку NIST було розпочато конкурс NIST PQC, в результаті котрого в
липні 2022 було обрано для стандартизації 4 кандидати (механізм інкапсуляції
ключа CRYSTALS-Kyber та цифрові підписи CRYSTALS-Dilithium, Falcon та
SPHINCS
+
) та було визначено кандидатів для четвертого раунду (механізми
інкапсуляції ключів BIKE, Classic McEliece, HQC та SIKE)[4].
Розвиток алгоритмів криптоаналізу також не стоїть на місці. Так
нещодавно в [5] було запропоновано універсальний квантовий алгоритм для
факторизації цілих чисел, котрий базується на алгоритмі Шора та застосовує
алгоритм квантової наближеної оптимізації (QAOA) для пришвидшення. Таким
чином цей алгоритм потребує сублінійних квантових ресурсів для своєї роботи.
Квантові алгоритми криптоаналізу проходять вдосконалення щодо
зменшення кількості квантових ресурсів, необхідних для їх застосування. Це
призводить до наближенням практичного застосування квантових комп’ютерів
для практичного криптоаналізу та зростання потреби в постквантових
алгоритмах ще до їх стандартизації. Особливо варто зазначити потребу в
механізмах інкапсуляції ключів, котрі не отримали багато альтернатив під час
оцінки постквантових алгоритмів в ході визначення кандидатів на
стандартизацію в ході третього раунду NIST PQC. У зв’язку з цим варто
звернути увагу на існуючі варіанти механізмів інкапсуляції ключів для їх оцінки
на придатність до застосування в якості постквантового алгоритму. Так,
наприклад, розглянемо механізм інкапсуляції ключів ДСТУ 8961:2019 «Скеля».
2. Механізм інкапсуляції ключів та його безпека
Механізм інкапсуляції ключів «Скеля» використовує гібридний варіант
перетворень Дента власної розробки для отримання IND-CCA2 безпечного
механізму інкапсуляції ключів з ймовірнісної схеми асиметричного шифрування.
Через це спочатку потрібно визначити загальні ймовірнісну схему
асиметричного шифрування, механізм інкапсуляції ключів та безпеку механізму
інкапсуляції ключів. Ймовірнісна схема асиметричного шифрування представляє
собою трійку алгоритмів ( , , )Gen Enc Dec , де: Gen – поліноміальний за часом
алгоритм генерації ключової пари, що приймає параметр безпеки 1 та
повертає ключову пару ( , )pk sk ; Enc – поліноміальний за часом алгоритм
шифрування, що приймає повідомлення mM , випадкове значення rR
та відкритий ключ pk і повертає шифротекст cC ; Dec – поліноміальний
за часом алгоритм розшифрування, що приймає шифртекст cC ,
секретний ключ sk та повертає повідомлення mM або помилку
розшифрування .
Механізм інкапсуляції ключів представляє собою трійку алгоритмів
( , , )Gen Encaps Decaps , де: Gen – поліноміальний за часом алгоритм
генерації ключової пари, що приймає параметр безпеки 1 та повертає
Євгеній Каптьол
Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів …
108
ключову пару ( , )pk sk ; Encaps – поліноміальний за часом алгоритм, що
приймає відкритий ключ pk та повертає ключ K та його інкапсуляцію С;
Decaps – поліноміальний за часом алгоритм, що приймає інкапсуляцію
ключа С, секретний ключ sk та повертає ключ K .
Нарешті визначимо безпеку механізму інкапсуляції ключів. Нехай
( , , )П Gen Encaps Decaps позначає механізм інкапсуляції ключів, а A
позначає супротивника. Для атаки { , 1, 2}atk cpa cca cca і параметра безпеки
ймовірність успіху супротивника визначається як
1 0
, , ,
( ) | Pr[ ( ) 1] Pr[ ( ) 1] |
ind atk ind atk ind atk
A П A П A П
Adv Exp Exp
, (1)
для {0,1}b , експеримент
,
( ) '
ind atk b
A П
Exp b
визначається як
1
2
0
1
(1 )( , )
( )( )
{0,1}
( )( , )
{0,1}
' ( , )
'
O
R
KeyLen
R
O
b
Genpk sk
A pkpk
b
Encaps pkK C
K
b A pk K
bПовернути
, (2)
де для
1 2
( ) , ( )atk cpa O O ,
1 2
1 ( ) ( ), ( )
Decaps
atk cca O O O
та
1 2
2 ( ) ( ), ( ) ( )
Decaps Decaps
atk cca O O O O .
Механізм інкапсуляції ключів є безпечним в сенсі IND-ATK, де
{ , 1, 2},atk cpa cca cca якщо
,
( )
ind atk
A П
Adv
є незначною величиною, як
функція від .
3. Формальний опис механізму інкапсуляції ключів ДСТУ 8961:2019
"Скеля"
Тепер час навести опис механізму інкапсуляції ключів ДСТУ 8961:2019 "Скеля".
Для цього потрібно ввести деякі позначення.
Нехай [ ] / ( 1)n
q qR X X X Z – кільце поліномів над qZ з твірним
поліномом 1nX X , а
3R – множина поліномів кільця
qR , усі коефіцієнти
яких належать до множини { 1,0,1} . Позначимо як ,
3
a bR множину усіх поліномів
у
3R , що мають кількість ненульових елементів у діапазоні [ , ]a b .
Задля уникнення технічних деталей, які не впливають на аналіз у моделі
випадкового оракула та для полегшення аналізу потрібно ввести наступні геш-
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 106-110
109
функції, які є еквівалентними до перетворень, що використовуються у ДСТУ
8961:2019:
*
_
8
3
3
:{0,1}
:
: {0,1}
{0: ,1}K b s
maxMsgLenBytes db t
q
q
q
y
q
te
BPGM R R
MGF R R
H R
KDF R
(3)
де – параметр безпеки, t – загальносистемний параметр, а
max , , _MsgLenBytes db K bytes є константами, що визначаються на основі
загальносистемних параметрів. ДСТУ 8961:2019 має ймовірність помилок
дешифрування (криптоаналізу). Загальносистемні параметри забезпечують, щоб
вона була достатньо мала, і на практиці не виникало помилок дешифрування.
Позначимо ймовірність виникнення помилки дешифрування як
Dec .
4. Аналіз механізму інкапсуляції ключів ДСТУ 8961:2019 "Скеля" у моделі
випадкового оракула
Доказ IND-CCA2 безпеки SkelyaPKE у моделі випадкового оракула ґрунтується
на стандартних техніках. Використовується наступна технічна лема.
Лема 1. Позначимо як , ,A B E деякі події в ймовірністному просторі.
Якщо Pr[ | ]=Pr[ | ]A E B E , то має місце нерівність
Pr[ ] Pr[ ] Pr[ ]A B E .
Теорема 1. Нехай , ,PPKE Gen Enc Dec – деяка ймовірнісна схема
асиметричного шифрування, а SkelyaKEM – механізм інкапсуляції ключів, що
побудований за допомогою застосування перетворення до PPKE . Якщо існує
алгоритм A , що може перемогти у IND-CCA2 грі SkelyaKEM за поліноміальний
час з ймовірністю та робить , , ,BPGM H KDF Decq q q q запитів до випадкових
оракулів BPGM, H, KDF та оракула дешифрування, то існує алгоритм B , що
може інвертувати PPKE з ймовірністю .
2 , 2
3 3
2
D D D
t n t t
q q q
R R
. (4)
де
2 , 2
3
D
t n t
q
R
,
2
Dq
та
3
D
t
q
R
- обмеження ймовірностей, пов’язаних з випадковим
обранням шифротексту та помилками дешифрування.
Висновки. Розвиток потужностей квантових комп’ютерів, розмірів квантових
регістрів та квантових алгоритмів ставить під загрозу сучасну криптографію з
Євгеній Каптьол
Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів …
110
відкритим ключем. Квантові алгоритми криптоаналізу проходять вдосконалення
щодо зменшення кількості необхідних квантових ресурсів.
Механізми інкапсуляції ключів, котрі не отримали багато альтернатив під
час оцінки постквантових алгоритмів в ході визначення кандидатів на
стандартизацію в ході третього раунду NIST PQC.
Механізм інкапсуляції ключів «Скеля» використовує гібридний варіант
перетворень Дента власної розробки для отримання IND-CCA2 безпечного
механізму інкапсуляції ключів з ймовірнісної схеми асиметричного шифрування.
Доказ IND-CCA2 безпеки SkelyaPKE у моделі випадкового оракула ґрунтується
на стандартних техніках та показує, що механізм інкапсуляції ключів ДСТУ
8961:2019 "Скеля" задовольняє вимоги.
Література
[1] Docs directory - IBM Quantum; [accessed 2023 Mar 10]. https://quantum-computing.ibm.com/.
[2] D-Wave systems | The Practical Quantum Computing Company; [accessed 2023 Mar 12].
https://www.dwavesys.com/.
[3] Federal Office for Information Security (BSI). Quantum-safe cryptography – fundamentals,
current developments and recommendations. 2021 Oct [accessed 2023 Mar 9].
https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Brochure/quantum-safe-
cryptography.pdf?__blob=publicationFile&v=4.
[4] NISTIR 8413. Status Report on the Third Round of the NIST Post-Quantum Cryptography
Standardization Process. 2022 Jul [accessed 2023 Mar 13].
https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf.
[5] Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang. Factoring integers with sublinear
resources on a superconducting quantum processor. arXiv. 2022 Dec 23 [accessed 2023 Mar 13].
State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou.
https://arxiv.org/abs/2212.12372. doi: https://doi.org/10.48550/arXiv.2212.12372.
Analysis of the impact of quantum computers on the security of
key encapsulation mechanisms using an example of ДСТУ
8961:2019 «Скеля»
Yevhenii Kaptol
In the paper the influence of quantum computers on the security of key encapsulation mechanisms
is presented and analyzed. The current state of post-quantum cryptography and post-quantum
cryptanalysis algorithms is considered. The current state of the process of standardization of post-
quantum cryptography for use in the transition period is considered and analyzed, and a
conclusion is made that there are no alternatives among candidates for standardization among key
encapsulation mechanisms. The development of post-quantum cryptanalysis methods and the
reduction of quantum resources required for their implementation are considered. It is concluded
that it is necessary to choose and use key encapsulation mechanisms from the list of available
options that meet the requirements of post-quantum cryptography. In the paper the security of the
DSTU 8961:2019 key encapsulation mechanism in the random oracle model is described and
analyzed.
Отримано 15.03.23
https://quantum-computing.ibm.com/
https://www.dwavesys.com/
https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Brochure/quantum-safe-cryptography.pdf?__blob=publicationFile&v=4
https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Brochure/quantum-safe-cryptography.pdf?__blob=publicationFile&v=4
https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf
https://arxiv.org/abs/2212.12372
https://doi.org/10.48550/arXiv.2212.12372
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-286 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:43Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/61/5d7f2fdb1c61da4924f7830a25274161.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2862025-02-21T17:32:19Z Analysis of the impact of quantum computers on the security of key encapsulation mechanisms using an example of ДСТУ 8961:2019 «Скеля» Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» Kaptol, Yevhenii квантовий комп’ютер; постквантова криптографія; механізм інкапсуляції ключів; «Скеля» In the paper the influence of quantum computers on the security of key encapsulation mechanisms is presented and analyzed. The current state of post-quantum cryptography and post-quantum cryptanalysis algorithms is considered. The current state of the process of standardization of post-quantum cryptography for use in the transition period is considered and analyzed, and a conclusion is made that there are no alternatives among candidates for standardization among key encapsulation mechanisms. The development of post-quantum cryptanalysis methods and the reduction of quantum resources required for their implementation are considered. It is concluded that it is necessary to choose and use key encapsulation mechanisms from the list of available options that meet the requirements of post-quantum cryptography. In the paper the security of the DSTU 8961:2019 key encapsulation mechanism in the random oracle model is described and analyzed. У роботі наведено та проаналізовано вплив квантових комп’ютерів на безпеку механізмів інкапсуляції ключів. Розглянуто сучасний стан постквантової криптографії та постквантових алгоритмів криптоаналізу. Розглянуто та проаналізовано сучасний стан процесу стандартизації постквантової криптографії для використання в перехідний період та зроблено висновок про відсутність альтернатив серед кандидатів для стандартизації серед механізмів інкапсуляції ключів. Розглянуто розвиток методів постквантового криптоаналізу та зменшення необхідної для їх реалізації квантових ресурсів. Зроблено висновок про необхідність обрання та використання механізмів інкапсуляції ключів з доступних варіантів, що задовольняють вимоги постквантової криптографії. У роботі наведено опис та досліджено безпеку механізму інкапсуляції ключів ДСТУ 8961:2019 у моделі випадкового оракула. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/286 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 106-110 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 106-110 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/286/244 |
| spellingShingle | квантовий комп’ютер постквантова криптографія механізм інкапсуляції ключів «Скеля» Kaptol, Yevhenii Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title | Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title_alt | Analysis of the impact of quantum computers on the security of key encapsulation mechanisms using an example of ДСТУ 8961:2019 «Скеля» |
| title_full | Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title_fullStr | Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title_full_unstemmed | Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title_short | Аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі ДСТУ 8961:2019 «Скеля» |
| title_sort | аналіз впливу квантових комп’ютерів на безпеку механізмів інкапсуляції ключів на прикладі дсту 8961:2019 «скеля» |
| topic | квантовий комп’ютер постквантова криптографія механізм інкапсуляції ключів «Скеля» |
| topic_facet | квантовий комп’ютер постквантова криптографія механізм інкапсуляції ключів «Скеля» |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/286 |
| work_keys_str_mv | AT kaptolyevhenii analysisoftheimpactofquantumcomputersonthesecurityofkeyencapsulationmechanismsusinganexampleofdstu89612019skelâ AT kaptolyevhenii analízvplivukvantovihkompûterívnabezpekumehanízmívínkapsulâcííklûčívnaprikladídstu89612019skelâ |