Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула
A modular approach is usually used to build modern key encapsulation mechanisms. Some asymmetric scheme is taken as a basis, and with the help of a certain CPA-to-CCA transformation, a key encapsulation mechanism is built on its basis. Many modern key encapsulation mechanisms use provably secure tra...
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/285 |
| 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_ | 1867479654585073664 |
|---|---|
| author | Kandii, Serhii |
| author_facet | Kandii, Serhii |
| author_institution_txt_mv | [
{
"author": "Serhii Kandii",
"institution": "співробітник АТ «Інститут Інформаційних технологій» вул. Коломенська, 15, 61166, Харків"
}
] |
| author_sort | Kandii, Serhii |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | A modular approach is usually used to build modern key encapsulation mechanisms. Some asymmetric scheme is taken as a basis, and with the help of a certain CPA-to-CCA transformation, a key encapsulation mechanism is built on its basis. Many modern key encapsulation mechanisms use provably secure transformations, but for DSTU 8961:2019 there is currently a significant lack of such an analysis. The analysis of such transformations usually takes place not in the standard model, but in the random oracle model, since it is quite difficult to take into account the influence of hash functions. The paper presents the first results of the analysis in the model of the random oracle CPA-to-CCA conversion, which is used in the DSTU 8961:2019 standard to build the key encapsulation mechanism. It is shown that the construction is safe provided that a number of model assumptions are fulfilled. |
| first_indexed | 2026-06-09T01:09:42Z |
| format | Article |
| fulltext |
101
doi.org/10.15407/fmmit2023.36.101
Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі
випадкового оракула
Сергій Кандій1
1 співробітник АТ «Інститут Інформаційних технологій» вул. Коломенська, 15, 61166, Харків, e-mail:
sergeykandy@gmail.com
Для побудови сучасних механізмів інкапсуляції ключів використовується модульний підхід.
За основу береться деяка асиметрична схема і за допомогою певного CPA-to-CCA
перетворення на її основі будується механізм інкапсуляції ключів. У багатьох сучасних
механізмах інкапсуляції ключів використовуються доказово безпечні перетворення, проте
для ДСТУ 8961:2019 наразі спостерігається суттєвий брак такого аналізу. Аналіз
подібних перетворень зазвичай відбувається не у стандартній моделі, а у моделі
випадкового оракула, оскільки доволі важко врахувати вплив геш функцій. У роботі
наведено перші результати аналізу у моделі випадкового оракула CPA-to-CCA
перетворення, що використовується в стандарті ДСТУ 8961:2019 для побудови механізма
інкапсуляції ключів. Показано, що конструкція є безпечною за умови, якщо виконується ряд
модельних припущень.
Ключові слова: ДСТУ 8961:2019; модель випадкового оракула;
криптографія на решітках; доказова безпека; механізми інкапсуляції
ключів
Вступ. Зазвичай, для практичних застосувань механізми інкапсуляції ключів
(КЕМ) вважаються безпечними [1,2], якщо складність будь-якої атаки з
адаптивно підібраними шифротекстами є занадто великою для практичної
реалізації. Якщо КЕМ містить доказ того, що він є безпечним у зазначеному
више сенсі за умови складності певного невеликого набору теоретико-числових
проблем при конкретних значеннях загальносистемних параметрів, то кажуть,
що він є безпечним у стандартній моделі [3]. Нажаль, докази у стандартній
моделі часто не можливо отримати для реальних КЕМ. Причиною цього є
використання криптографічних геш функцій [3]. Часто відсутні інструменти для
того, щоб врахувати вплив алгебраїчної структури та властивостей геш функції
на безпеку перетворень. Тому, на практиці, поширеною модифікацією є модель
випадкового оракула [4], у якій усі геш функції замінюються на випадкові
оракули - ідеалізовані геш функції, що не мають внутрішньої структури.
1. Формальний опис ДСТУ 8961:2019
Введемо позначення. Нехай [ ] / ( 1)
n
q qR Z X X X – кільце поліномів над qZ з
твірним поліномом 1
n
X X , а 3R – множина поліномів кільця qR , усі
УДК 004.056.55
mailto:sergeykandy@gmail.com
Кандій Сергій
Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула
102
коефіцієнти яких належать до множини { 1,0,1} . Позначимо як ,
3
a b
R множину
усіх поліномів у
3R , що мають кількість ненульових елементів у діапазоні [ , ]a b .
Якщо a b , то використовується скорочене позначення ,
3 3
t t t
R R . ДСТУ
8961:2019 використовує наступні геш функції:
8*max
3
:{0,1}
: {0,1}
: {0,1}
: {0,1} bytes
MsgLenBytes db
q q
q
q
K
q
BPGM R R
MGF R
H R
KDF R
(1)
де – параметр безпеки, t – загальносистемний параметр, а
maxMsgLenBytes , db , bytesK є константами, що визначаються на основі
загальносистемних параметрів. Також використовується бієктивне
відображення:
8*max
3
8*max1
3
:{0,1} {0,1}
: {0,1} {0,1}
MsgLenBytes
MsgLenBytes
db
db
Pad R
Pad R
(2)
,яке кодує повідомлення (у вигляді строки бітів), довжину повідомлення
та випадкову строку бітів у поліном з
3R .
Схема асиметричного шифрування, що лежить в основі протоколу
інкапсуляції ключів, наведена на рисунку 1. CPA-to-CCA перетворення
ДСТУ 8961:2019 наведено на рисунку 2.
Рис 1. Асиметрична схема шифрування у ДСТУ 8961:2019
Рис 2. Механізм інкапсуляції ключів ДСТУ 8961:2019
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 101-105
103
Від асиметричної схеми додатково вимагається, щоб існувало
достатньо мала константа , для якої виконується нерівність
| : ( , , ) | ( ) ( )r Enc pk r m C negl (3)
2. Безпека CPA-to-CCA перетворення
IND-CCA2 безпеки SkelyaPKE у моделі випадкового оракула грунтується на
стандартних техніках. Використовується наступна технічна лема [5]:
Лема 1. Позначимо як , ,A B E деякі події в ймовірністному просторі. Якщо
Pr[ | ] Pr[ | ]A E B E , то має місце нерівність | Pr[ ] Pr[ ] | Pr[ ]A B E .
Теорема 1. Нехай ( , , )PPKE Gen Enc Dec - деяка ймовірнісна схема
асиметричного шифрування, а SkelyaKEM - механізм інкапсуляції ключей, що
побудований за допомогою застосування перетворення на Рис 2 до PPKE. Якщо
існує алгоритм A , що може перемогти у IND-CCA2 грі SkelyaKEM за
поліноміальний час з ймовірністю та робить , , ,BPGM H KDF Decapsq q q q запитів до
випадкових оракулів BPGM ,H,KDF та оракула дешифрування, то існує алгоритм
B , що може інвертувати PPKE з ймовірністю ' .
2 , 2
3
'
| | 2
Decaps Decaps
t N t
q q
R
(4)
Доказ.
Алгоритм B приймає у якості аргумента шифротекст PPKE- *
1C , відкритий
ключ pk та повертає x . Сутність алгоритму B полягає у симуляції IND-CCA2
гри для алгоритму A та працює наступним чином:
Крок 1: Алгоритм B генерує випадкові бітові строки * *
2 ,C K .
Крок 2: Алгоритм B передає pk до A .
Крок 3: Алгоритм B чекає доки A запросить завдання, на запит B
посилає пару * *
1 2
* *
( , ),C C C K .
Крок 4: Алгоритм B чекає доки A поверне біт ' .
Крок 5: Алгоритм B перевіряє чи існує ( , ) LISTx r BPGM , для якого
виконується *
1( , , )Enc x r pk C . Якщо так, то обчислює та повертає x .
Крок 6: Алгоритм B перевіряє чи існує ( , ) LISTr K KDF або ( , ) LISTr hash H ,
для якого виконується 1 * *
1 1( ( )); ( , , )x Pad C rh MGF rh Enc x r pk C
. Якщо так,
то повертає x .
Крок 7: Алгоритм B повертає випадкове x .
Оракул для ( )BPGM x працює наступним чином:
Крок 1: Якщо ( , ) LISTx r BPGM , то повернути r .
Крок 2: Якщо *
1( ),Decaps C sk x , то повернути ( )BPGM x .
Кандій Сергій
Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула
104
Крок 3: Інакше обрати випадковие r , додати до
LISTBPGM ( , )x r та
повернути r .
Оракул для ( )H r працює наступним чином:
Крок 1: Якщо ( , ) LISTr hash H , то повернути hash .
Крок 2: Якщо *
1( ( , ), )BPGM Decaps C sk pk r , то повернути ( )H r .
Крок 3: Інакше обрати випадковие hash , додати до
LISTH ( , )r hash та
повернути hash .
Оракул для ( )KDF r працює наступним чином:
Крок 1: Якщо ( , ) LISTr K KDF , то повернути K .
Крок 2: Якщо *
1( ( , ), )BPGM Decaps C sk pk r , то повернути ( )KDF r .
Крок 3: Інакше обрати випадковие K , додати до LISTKDF ( , )r K та
повернути K .
Оракул декапсуляції 1 2(( , ))Decaps C C працює наступним чином:
Крок 1: Якщо *
1 1C C , то повернути .
Крок 2: Для кожного значення ( , ) LISTx r BPGM перевірити, чи виконується
( , , )Enc x r pk та 2( )H r C . Якщо такої пари не знайдено, то повернути .
Крок 3: Обчислити ( )K KDF r з використанням оракула для KDF.
Крок 4: Повернути K .
Позначимо як win
realW та win
oracleW події, що відповідають перемозі A у IND-
CCA2 грі з реальними геш функціями та з оракулами відповідно. Розглянемо як
зміниться ймовірність перемоги, якщо замінити справжні геш функції на
випадкові оракули. Для алгоритму A різниця не буде помітна, якщо: A
робив запит на розшифрування завдання до того, як отримав завдання або
A робив запит на декапсуляцію валідного шифротексту 1 2,C C ,але A не
робив відповідних запитів до H або BPGM.
Позначимо як indW подію, що зазначені вище випадки не стануться, отже,
використовуючи Лемму 1, маємо:
Pr[ | ] Pr[ |
| Pr
]
Pr[ ][ | Pr[] ]
win win
real ind oracle ind
win
ereal n
win
oracl i dW
W W W W
W W
(5)
Так як шифротекст був обраний випадково, то ймовірність першої події
обмежена
2 , 2
3/ | |t N t
Decapsq R
. Ймовірність того, що ( ( ( , ), ))H BPGM Decaps C sk pk
обмежена / 2Decapsq . Отже, повна ймовірність буде
2 , 2
3| | 2
Decaps Decaps
t N t
q q
R
(6)
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 101-105
105
Оскільки перевага у грі з оракулом є нижньою оцінкою ймовірності того,
що серед запитів до геш функцій буде інформація, якої достатньо для
дешифрування шифротексту *
1C , то маємо:
2 , 2
3
'
| | 2
Decaps Decaps
t N t
q q
R
(7)
Що і треба було довести.
Висновки. У роботі було доведена в моделі випадкового оракула IND-CCA2
безпека CPA-to-CCA перетворення ДСТУ 8961:2019. Важливо розуміти, що
доказ у моделі випадкового оракула не означає, що взагалі атак не має, а лише
доводить захист від широкого класу атак, що підпадають під модельні
припущення. Наведений в цій роботі доказ може в подальшому бути
вдосконалений з використанням більш сильних технік та з меншою кількістю
модельних припущень. Досліджуючи властивості загальних параметрів та
доповнюючи існуючі докази можливо створити більш комплексні моделі
безпеки, що враховують большу кількість загроз і мають менше ризиків.
Література
[1] CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM / Leo Ducas., and other. // URL:
https://eprint.iacr.org/2017/634.pdf
[2] FrodoKEM. Learning With Errors Key Encapsulation Algorithm Specifications. And Supporting
Documentation. / Leo Ducas., and other. // URL: https://frodokem.org/files/FrodoKEM-
specification-20210604.pdf
[3] Introduction to Modern Cryptography: Principles and Protocols / Katz, Jonathan; Lindell, Yehuda
// Chapman & Hall/CRC Cryptography and Network Security Series, CRC Press, 2014.
[4] Canetti R., Goldreich O., Halevi S. The random oracle methodology, revisited. In: 30th
symposium on theory of computing. STOC, 1998. P. 209–218.
[5] А. Dent. A Designer’s Guide to KEMs. // URL:
http://www.cogentcryptography.com/papers/designer.pdf
Analysis of DSTU 8961:2019 CPA-to-CCA transformation in
random oracle model
Kandii Serhii
A modular approach is usually used to build modern key encapsulation mechanisms. Some
asymmetric scheme is taken as a basis, and with the help of a certain CPA-to-CCA transformation,
a key encapsulation mechanism is built on its basis. Many modern key encapsulation mechanisms
use provably secure transformations, but for DSTU 8961:2019 there is currently a significant lack
of such an analysis. The analysis of such transformations usually takes place not in the standard
model, but in the random oracle model, since it is quite difficult to take into account the influence
of hash functions. The paper presents the first results of the analysis in the model of the random
oracle CPA-to-CCA conversion, which is used in the DSTU 8961:2019 standard to build the key
encapsulation mechanism. It is shown that the construction is safe provided that a number of
model assumptions are fulfilled.
Отримано 05.04.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-285 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:42Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/ad/5aaf075b66b2f9f0e6a5b2874f1e6aad.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2852025-02-21T17:32:19Z Analysis of DSTU 8961:2019 CPA-to-CCA transformation in random oracle model Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула Kandii, Serhii ДСТУ 8961:2019; модель випадкового оракула; криптографія на решітках; доказова безпека; механізми інкапсуляції ключів A modular approach is usually used to build modern key encapsulation mechanisms. Some asymmetric scheme is taken as a basis, and with the help of a certain CPA-to-CCA transformation, a key encapsulation mechanism is built on its basis. Many modern key encapsulation mechanisms use provably secure transformations, but for DSTU 8961:2019 there is currently a significant lack of such an analysis. The analysis of such transformations usually takes place not in the standard model, but in the random oracle model, since it is quite difficult to take into account the influence of hash functions. The paper presents the first results of the analysis in the model of the random oracle CPA-to-CCA conversion, which is used in the DSTU 8961:2019 standard to build the key encapsulation mechanism. It is shown that the construction is safe provided that a number of model assumptions are fulfilled. Для побудови сучасних механізмів інкапсуляції ключів використовується модульний підхід. За основу береться деяка асиметрична схема і за допомогою певного CPA-to-CCA перетворення на її основі будується механізм інкапсуляції ключів. У багатьох сучасних механізмах інкапсуляції ключів використовуються доказово безпечні перетворення, проте для ДСТУ 8961:2019 наразі спостерігається суттєвий брак такого аналізу. Аналіз подібних перетворень зазвичай відбувається не у стандартній моделі, а у моделі випадкового оракула, оскільки доволі важко врахувати вплив геш функцій. У роботі наведено перші результати аналізу у моделі випадкового оракула CPA-to-CCA перетворення, що використовується в стандарті ДСТУ 8961:2019 для побудови механізма інкапсуляції ключів. Показано, що конструкція є безпечною за умови, якщо виконується ряд модельних припущень. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/285 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 101-105 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 101-105 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/285/245 Авторське право (c) 2023 Сергій Кандій (Автор) |
| spellingShingle | ДСТУ 8961:2019 модель випадкового оракула криптографія на решітках доказова безпека механізми інкапсуляції ключів Kandii, Serhii Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title | Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title_alt | Analysis of DSTU 8961:2019 CPA-to-CCA transformation in random oracle model |
| title_full | Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title_fullStr | Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title_full_unstemmed | Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title_short | Аналіз CPA-to-CCA перетворення ДСТУ 8961:2019 у моделі випадкового оракула |
| title_sort | аналіз cpa-to-cca перетворення дсту 8961:2019 у моделі випадкового оракула |
| topic | ДСТУ 8961:2019 модель випадкового оракула криптографія на решітках доказова безпека механізми інкапсуляції ключів |
| topic_facet | ДСТУ 8961:2019 модель випадкового оракула криптографія на решітках доказова безпека механізми інкапсуляції ключів |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/285 |
| work_keys_str_mv | AT kandiiserhii analysisofdstu89612019cpatoccatransformationinrandomoraclemodel AT kandiiserhii analízcpatoccaperetvorennâdstu89612019umodelívipadkovogoorakula |