MarriageTheoremのこと

_ IACR ePrint 2013/443まで確認済み、ECCC 2002年分まで確認済み

_ 気になった論文：Information Theoretic Security for Encryption Based on Conditional Renyi Entropies, Mitsugu Iwamoto and Junji Shikata, http://eprint.iacr.org/2013/440

In this paper, information theoretic cryptography is discussed based on conditional Renyi entropies. Our discussion focuses not only on cryptography but also on the denitions of conditional Renyi entropies and the related information theoretic inequalities. First, we revisit conditional Renyi entropies, and clarify what kind of properties are required and actually satised. Then, we propose security criteria based on Renyi entropies, which suggests us deep relations between (conditional) Renyi entropies and error probabilities by using several guessing strategies. Based on these results, unied proof of impossibility, namely, the lower bounds of key sizes is derived based on conditional Renyi entropies. Our model and lower bounds include the Shannon's perfect secrecy, and the min-entropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini. Finally, new optimal symmetric key cryptography and almost optimal secret sharing schemes are proposed which achieve our lower bounds.

_ 今朝、朝日新聞デジタル版に「ＫＤＤＩ研と九大、１２８次元の暗号解読－次世代公開鍵実用化に寄与」（http://www.asahi.com/tech_science/nikkanko/NKK201307190017.htmlという記事が出ていたのをtwitter経由で知ったので読んでみた。以下感想。

記事の中で特に良かったと思った点は、

新たな暗号の安全性を高めるために、暗号がどの程度の時間で解読できるかを調べる作業が重要で、今回の解読も次世代公開鍵暗号の実用化に寄与する。

という記述で、「なぜ暗号解読が真っ当な研究として価値を持つのか」を端的に説明できていると思う。そもそもこの動機の部分をうまく説明するのが大変なことが少なくないので。

一方、これはちょっとなぁと思ったのは、

【用語】公開鍵暗号＝（引用時略）安全だと信じられているが証明はされていない。そのため格子暗号などの次世代公開鍵暗号の研究が進んでいる。

という記述。現代の公開鍵暗号分野では、「新しい暗号の解読」という難易度の測り辛い行為と、例えば「巨大な整数の素因数分解」のような難易度の測り易い行為との等価性を数学的に証明することがほぼ必須条件となっている。確かに後者の問題の絶対的な難易度が理論的に決定されているわけではないとはいえ、暗号の解読の相対的な難易度は詳しく見積もられている。格子暗号のような新種の暗号を研究する理由も、現在の暗号技術が「既に危険だから」ではなく、万が一「将来的に危険になったときの保険」のようなものである*1。上記の表現はあまりに簡潔過ぎて、現在の公開鍵暗号方式が既に危ういものであるかのような印象を与えてしまう懸念がある。（まぁ、上述の暗号解読と等価な計算問題の難易度が数学的に決定されていないことを「（安全性が）証明されていない」と表現するのは、紛らわしいとはいえ「完全に間違い」ではないといえばそうなのだが、その辺りの事情は格子暗号でも同じなのである。）とはいえ、こうした暗号の安全性評価周りの事情はそもそもが「簡単に説明し辛い」ものなので、記事を書いた人だけを責めるのは酷である。我々専門家の側でも、どうにかしてこの辺りをうまく説明できるように手段を考える必要があるだろう。