_ IACR ePrint 2013/429まで確認済み、ECCC 2000年分まで確認済み
_ 気になった論文：Private Database Queries Using Somewhat Homomorphic Encryption
, Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and David J. Wu, http://eprint.iacr.org/2013/422
In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier's additively homomorphic system as well as Brakerski's somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.
_ 気になった論文２：Instantiating Random Oracles via UCEs
, Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi, http://eprint.iacr.org/2013/424
This paper provides a (standard-model) notion of security for (keyed) hash functions, called UCE, that we show enables instantiation of random oracles (ROs) in a fairly broad and systematic way. Goals and schemes we consider include deterministic PKE; message-locked encryption; hardcore functions; point-function obfuscation; OAEP; encryption secure for key-dependent messages; encryption secure under related-key attack; proofs of storage; and adaptively-secure garbled circuits with short tokens. We can take existing, natural and efficient ROM schemes and show that the instantiated scheme resulting from replacing the RO with a UCE function is secure in the standard model. In several cases this results in the first standard-model schemes for these goals. The definition of UCE-security itself is quite simple, asking that outputs of the function look random given some 'leakage', even if the adversary knows the key, as long as the leakage does not permit the adversary to compute the inputs.
_ IACR ePrint 2013/431まで確認済み、ECCC 2002年分まで確認済み
_ 気になった論文：Inapproximability Results for Equations over Finite Groups
, Lars Engebretsen, Jonas Holmerin, Alexander Russell, http://eccc.hpi-web.de/report/2002/030/
An equation over a finite group G is an expression of form w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within |G| - epsilon for any epsilon > 0. This generalizes results of Håstad (2001, J.ACM, 48(4)), who established similar bounds under the added condition that the group G is Abelian.
_ （7/14記：今月号の『数学セミナー』に載っていたコンピュータ将棋の記事を読んだのだが、いくつか気になる点があったのでメモしておく。
まず、43ページの「最も長い詰将棋である1519手詰の「ミクロコスモス」が1997年にコンピュータによって解かれた」という記述について、橋本孝治作「ミクロコスモス」は確かに1986年の初発表時には1519手詰であったが、1995年に6手の逆算（手数が6手延びて1525手詰となる）が考案され、以降は（私の知る限り）1525手詰の作品として取り扱うのが普通となっている。念の為、「コンピュータソフト（脊尾詰）が当時解いたのは1519手詰版であった」という（あまりありそうにない）可能性を考慮して調べてみたが、以下のコンピュータ将棋関連のページと詰将棋関連のページの双方に「1525手詰」との記述があり、やはり1525手詰版が解かれたと考えるのが尤もらしいと考えられる（こちらの報告ページの「超長編作品リスト」も参照）。
他に、47ページに「動物将棋」とあるが、あのゲームの名称はひらがな書きで「どうぶつしょうぎ」のはずである。あと、46ページの「地平線」の話について、私はあの概念は「水平線効果」の呼称の方が一般的という印象を持っているのだが、「水平線」の呼称に触れなかったのは何か意図があるのだろうか。）
_ 週末。
_ IACR ePrint 2013/435まで確認済み、ECCC 2002年分まで確認済み
_ 気になった論文：Efficient Cryptosystems From $2^k$-th Power Residue Symbols
, Marc Joye and Benoit Libert, http://eprint.iacr.org/2013/435
Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular,they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.（EUROCRYPT 2013の論文らしい）
_ （7/16記：ここ数日、新調したWindows 8 PCのセットアップに追われていて、ほぼ使えるようになったものの、前のWindows 7マシンでは普通にできていたメール送信ができない問題（受信は平気）にみまわれて難儀していた。それがさっきようやく解決したのでメモ。
より詳しい状況としては、これまでWindows 7 PC上でメールソフトのSylpheedを使ってGoogle Gmailのメール*1を読み書きしていたのを、深く考えずに新しいPCに設定ファイルごと引越ししたところ、受信はできるのに送信がタイムアウトでエラーになってしまっていた。で、紆余曲折（後述）を経て、これまで smtp.gmail.com と設定していたSMTPサーバ名を gmail-smtp-msa.l.google.com に変更したら送信できるようになった。（そうなると、むしろ何故今までのPC上では前者の設定で送信できていたのか謎である。技術的な詳細には明るくないので憶測だが、実は今は後者のサーバ名が正式で前者はあくまでエイリアス的な扱いであり、Windows 8からは両者の区別が厳格になった、とかいう事情なのだろうか？）
以下余談。今回新調したPCではVirtualBox内部にインストールしたLinuxをメインに使おうとしているのだが、仮想マシンを導入するのは初体験なのでそれ自体の設定でも色々苦労していた。で、苦労の末にゲストOS側にSylpheedをインストールして動作確認したらメール送信ができなかったものだから、初めはホストOSとの間で何かネットワークの設定が上手くいっていないのかなぁとひとしきり悩んだものの解決しないので、根負けしてメールだけはホストOS側で使おうと思ってホストOS側にSylpheedをインストールしたところ、それでもやっぱり送信が上手くいかないので愕然とした。だってねぇ、いくらアップグレードしたからって同じWindowsなんだから、前の設定ごと引越せば普通に使えると思うじゃないですか。で、ファイアウォールとかセキュリティソフトに通信がブロックされているのかと思ってそのあたりの設定をいじってみたり、色々やった末、ふとping smtp.gmail.comとやったら「gmail-smtp-msa.l.google.com [アドレス略]にpingを送信しています」とか表示されたわけですよ。で、「ちょっとまて、今まではsmtp.（略）で普通に使えてたんだぞ、そんなばかな」と思いつつSMTPサーバ名を変更してみたら送信できてしまって脱力、という次第。まぁ、もっと早くpingを試さなかったために丸二日無駄にした自らを小一時間問い詰めつつも、これ、実は他にも嵌まる人少なくないんじゃないのかなぁと些か心配である。）
*1 そもそもGmailを使いたくないのだが、仕事の関係で
_ 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。上記の表現はあまりに簡潔過ぎて、現在の公開鍵暗号方式が既に危ういものであるかのような印象を与えてしまう懸念がある。（まぁ、上述の暗号解読と等価な計算問題の難易度が数学的に決定されていないことを「（安全性が）証明されていない」と表現するのは、紛らわしいとはいえ「完全に間違い」ではないといえばそうなのだが、その辺りの事情は格子暗号でも同じなのである。）とはいえ、こうした暗号の安全性評価周りの事情はそもそもが「簡単に説明し辛い」ものなので、記事を書いた人だけを責めるのは酷である。我々専門家の側でも、どうにかしてこの辺りをうまく説明できるように手段を考える必要があるだろう。
*1 他にも、格子暗号という新しい原理の導入によって初めて実現された高機能暗号もあるので、安全性の面だけが動機ではないのだが、それについては割愛
_ （7/23記：論文査読。長いレフェリーレポートを書いているとだんだん疲れてきて穏やかな表現を選ぶ余裕がなくなってくるので、短いレフェリーレポートで済むような論文を査読したいものである。）
_ IACR ePrint 2013/453まで確認済み、ECCC 2002年分まで確認済み
_ 気になった論文：A Note On the Storage Requirement for AKS Primality Testing Algorithm
, Zhengjun Cao, http://eprint.iacr.org/2013/449
We remark that AKS primality testing algorithm needs about 1,000,000,000 G (gigabyte) storage space for a number of 1024 bits. Such storage requirement is hard to meet in practice. To the best of our knowledge, it is impossible for current operating systems to write and read data in so huge storage space. Thus, the running time for AKS algorithm shuould not be simply estimated as usual in terms of the amount of arithmetic operations.
_ 今日出席したセミナーで「ロボットは東大に入れるか」プロジェクトの紹介を聴いてきた。人工知能に大学入試問題を解かせて、2021年度までに東京大学の入試を突破できるようにしようという無謀な研究プロジェクトとのこと。今日の講演者は数学担当の方だったのだが、数学は人工知能にとっては（少なくとも国語の論述問題などに比べれば）得意分野とはいえ、分野によってはまだ自動で答えを得るのが難しかったり、そもそも自然言語で書かれた問題文の意味を把握するところから始めなければならないなど色々と困難が多いらしい。人工知能に問題を解かせるための数学的な工夫などもあり、面白い講演だった。
ちなみに、その方によると、国語など現状では壊滅的な科目があるため、「得意科目」の数学では満点を取れるようにとハッパをかけられているらしい。自分の受験生時代の戦略を思い出して、人工知能にちょっと親近感が沸いた瞬間であった。（まぁ、人工知能は私と違って暗記科目は大得意なのだけど。）
_ IACR ePrint 2013/460まで確認済み、ECCC 2002年分まで確認済み
最近のツッコミ↓