MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 1月31日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/168まで

_ 気になった論文：A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes（Val\'erie Gauthier and Ayoub Otmani and Jean-Pierre Tillich, IACR ePrint 2012/168）

Bogdanov and Lee suggested a homomorphic public-key encryption scheme based on error correcting codes. The underlying public code is a modified Reed-Solomon code obtained from inserting a zero submatrix in the Vandermonde generating matrix defining it. The columns that define this submatrix are kept secret and form a set $L$. We give here a distinguisher that detects if one or several columns belong to $L$ or not. This distinguisher is obtained by considering the code generated by component-wise products of codewords of the public code (the so called ``square code''). This operation is applied to punctured versions of this square code obtained by picking a subset $I$ of the whole set of columns. It turns out that the dimension of the punctured square code is directly related to the cardinality of the intersection of $I$ with $L$. This allows an attack which recovers the full set $L$ and which can then decrypt any ciphertext.

まだ中身をちゃんと読んでいないのだが、以前の日記で紹介した、STOC 2012に採録された符号ベース準同型暗号方式に対する攻撃のようである。STOC 2012自体はまだ開催されていないのだが、開催に先駆けて論文がプレプリントサーバで公表され、それに対する攻撃がやはりSTOC 2012本番前に公表され、それを受けてかSTOC 2012の採録論文リストから当該論文が削除される*1という中々趣深い事態になっている*2。昔の暗号系の学会では、新しい暗号方式の提案に関する発表の最中に聴講者が提案方式を破ってしまうという光景も見られたらしい*3が、それに比べると発表前に気付けるだけ進歩した状況なのだろうか。