コンクリートセキュリティ

暗号学において、具体的なセキュリティまたは正確なセキュリティは、多項式同値よりも正確に敵対的タスクの計算の複雑さを推定することを目的とした実践指向のアプローチです。^[^要出典^]これは、敵対者が一定時間実行した場合の成功確率を制限することで、暗号システムのセキュリティを定量化します。 ^[1]^[^{より良いソースが必要}^{]正確な分析による}セキュリティ証明は、具体的なセキュリティと呼ばれます。^[2]^[^{より良いソースが必要}^]

従来、証明可能なセキュリティは漸近的である。つまり、多項式時間の縮約可能性を使用して計算問題の難しさを分類する。安全なスキームは、計算上制限された敵の利点が無視できるものと定義される。このような理論的な保証は重要であるが、実際には、セキュリティパラメータをインスタンス化する必要があるため、縮約がどの程度効率的であるかを正確に知る必要がある。つまり、「十分に大きい」セキュリティパラメータで十分であると知るだけでは十分ではない。非効率的な縮約は、敵の成功確率またはスキームのリソース要件が望ましい値よりも大きくなるかのいずれかになる。^{[引用が必要]}

具体的なセキュリティは、実行時間やメモリなど、敵対者が利用できるすべてのリソースと、取得できる平文の数や利用可能なオラクルに実行できるクエリの数など、問題のシステムに固有のその他のリソースをパラメータ化します。次に、敵対者の利点は、これらのリソースと問題のサイズの関数として上限が設定されます。上限に一致する下限（つまり、敵対的戦略）を与えることがしばしば可能であるため、厳密なセキュリティと呼ばれます。^[要出典]

例

具体的なセキュリティ推定が暗号化アルゴリズムに適用されています。

1996年にRSA暗号とラビン暗号に基づいたデジタル署名の方式が提案され、元の暗号とほぼ同じくらい解読が困難であることが示されました。^[3]
1997年、対称暗号化アルゴリズムの具体的なセキュリティの概念（左右の区別不能性、実数かランダムかの区別不能性、発見して推測するセキュリティ、意味的セキュリティ）が、 CBC、CTR、XOR（CBCの状態のない変種）などのさまざまなブロック暗号モードでほぼ同等であることが証明されました。^[4]^[^{説明が必要}^]
2017年に発表された論文では、格子点列挙アルゴリズムと格子ブロック削減アルゴリズムが格子ベースの暗号への攻撃に使用できることが示されました。^[5]
2021年には、 NC0で提案された疑似乱数生成器に対して「推測して決定」および「推測して解読」タイプの攻撃^{[説明が必要]}が実証され、以前は128ビットのセキュリティがあると主張されていたパラメータ値を持つインスタンスが約操作で解決されました。^[6]^[^{より良い情報源が必要}^] $2^{78}$

さらに、Coqに組み込まれた「Foundational Cryptography Framework」というソフトウェアツールは、具体的な安全性の証明を形式的に検証することができます。 ^{[7]たとえば、}ElGamal暗号化の具体的な安全性を検証することができます。^[7]

参考文献

^ 「Modern symmetric-key Encryption」メリーランド大学。2017年9月10日時点のオリジナルよりアーカイブ。2021年5月6日閲覧。
^ Kamara, Seny. 「講義 2+3: 証明可能セキュリティ」(PDF)。2017 年 2 月 15 日時点のオリジナルよりアーカイブ(PDF) 。2021 年5 月 6 日閲覧。
^ Bellare, Mihir; Rogaway, Philip (1996). 「デジタル署名の厳密なセキュリティ - RSA と Rabin による署名方法」(PDF) .暗号学の進歩 - EUROCRYPT '96 .コンピュータサイエンスの講義ノート。第 1070 巻。Springer -Verlag。pp . 399–416。doi : 10.1007 /3-540-68339-9_34。ISBN 978-3-540-68339-1。
^ Bellare, Mihir; Desai, A.; Jokipii, E.; Rogaway, Philip (1997 年 10 月)。「対称暗号化の具体的なセキュリティ処理」(PDF)。第 38 回コンピュータサイエンスの基礎に関する年次シンポジウムの議事録。pp. 394–403。doi : 10.1109 / SFCS.1997.646128。ISBN 0-8186-8197-7. S2CID 42604387。
^ Walter, Michael (2017). 「格子ベース暗号の具体的なセキュリティについて」.カリフォルニア大学サンディエゴ校. 2021年5月6日閲覧。
^ Yang, Jian; Guo, Qian; Johansson, Thomas; Lentmaier, Michael (2021年3月3日). 「Goldreichの疑似乱数ジェネレータの具体的なセキュリティの再検討」. arXiv : 2103.02668 [cs.CR].
^ ab Petcher, Adam (2014年10月14日). 「基礎暗号化フレームワーク」. arXiv : 1410.3735 [cs.PL].

外部リンク

https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf
https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf
https://eprint.iacr.org/2006/278.pdf
https://www.baigneres.net/downloads/2007_provable_security.pdf
https://eprint.iacr.org/2020/1213.pdf

[1] 「Modern symmetric-key Encryption」メリーランド大学。2017年9月10日時点のオリジナルよりアーカイブ。2021年5月6日閲覧。

[2] Kamara, Seny. 「講義 2+3: 証明可能セキュリティ」(PDF)。2017 年 2 月 15 日時点のオリジナルよりアーカイブ(PDF) 。2021 年5 月 6 日閲覧。

[3] Bellare, Mihir; Rogaway, Philip (1996). 「デジタル署名の厳密なセキュリティ - RSA と Rabin による署名方法」(PDF) .暗号学の進歩 - EUROCRYPT '96 .コンピュータサイエンスの講義ノート。第 1070 巻。Springer -Verlag。pp . 399–416。doi : 10.1007 /3-540-68339-9_34。ISBN 978-3-540-68339-1。

[4] Bellare, Mihir; Desai, A.; Jokipii, E.; Rogaway, Philip (1997 年 10 月)。「対称暗号化の具体的なセキュリティ処理」(PDF)。第 38 回コンピュータサイエンスの基礎に関する年次シンポジウムの議事録。pp. 394–403。doi : 10.1109 / SFCS.1997.646128。ISBN 0-8186-8197-7. S2CID 42604387。

[5] Walter, Michael (2017). 「格子ベース暗号の具体的なセキュリティについて」.カリフォルニア大学サンディエゴ校. 2021年5月6日閲覧。

[6] Yang, Jian; Guo, Qian; Johansson, Thomas; Lentmaier, Michael (2021年3月3日). 「Goldreichの疑似乱数ジェネレータの具体的なセキュリティの再検討」. arXiv : 2103.02668 [cs.CR].

[:0-7] Petcher, Adam (2014年10月14日). 「基礎暗号化フレームワーク」. arXiv : 1410.3735 [cs.PL].