_ 謹賀新年。年内分の日記が書き終わらなかったので急いで書き終えるなど。
_ IACR ePrint 2014/1021まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：Controlled Homomorphic Encryption: Definition and Construction
, Yvo Desmedt and Vincenzo Iovino and Giuseppe Persiano and Ivan Visconti, http://eprint.iacr.org/2014/989
Fully Homomorphic Encryption schemes (FHEs) and Functional Encryption schemes (FunctEs) have a tremendous impact in Cryptography both for the natural questions that they address and for the wide range of applications in which they have been (sometimes critically) used. In this work we put forth the notion of a Controllable Homomorphic Encryption scheme (CHES), a new primitive that includes features of both FHEs and FunctEs. In a CHES it is possible (similarly to a FHE) to homomorphically evaluate a ciphertext Ct = Enc(m) and a circuit C therefore obtaining Enc(C(m)) but only if (similarly to a FunctE) a token for C has been received from the owner of the secret key. We discuss difficulties in constructing a CHES and then show a construction based on any FunctE.
_ IACR ePrint 2014/1022まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：Topology-Hiding Computation
, Tal Moran and Ilan Orlov and Silas Richelson, http://eprint.iacr.org/2014/1022
Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography, allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the output of the function. Following the seminal works of Yao and Goldreich, Micali and Wigderson and Ben-Or, Goldwasser and Wigderson, the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model, underlying assumptions, complexity and composability of the resulting protocols.
One question that appears to have received very little attention, however, is that of MPC over an underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being of pure theoretical interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations, vehicle-to-vehicle networks and the ``internet of things'' are some of the examples.
In this paper, we initiate the study of ``topology-hiding computation'' in the computational setting. We give formal definitions in both simulation-based and indistinguishability-based flavors. We show that, even for fail-stop adversaries, there are some strong impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.
_ IACR ePrint 2014/1029まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：Cryptanalysis of a New Additive Homomorphic Encryption based on the co-ACD Problem
, Moon Sung Lee, http://eprint.iacr.org/2014/1024
In CCS'14, Cheon et al. proposed a new additive homomorphic encryption scheme which is claimed to be the most efficient among the additive homomorphic encryption schemes. The security is proved based on the hardness of a new problem, the (decisional) co-approximate common divisor problem. In this paper, we cryptanalyze the scheme and investigate the hardness of an aforementioned problem. Our first result shows that Cheon et al.'s scheme is insecure for the range of parameters considered in the original paper~\cite{CLSCCS14}. Experiments show that the message can be recovered in seconds for the proposed parameters. We also analyze the condition of the parameters to thwart the proposed attack. As a second result, we show that the co-approximate common divisor problem is easy for the similar range of parameters, in condition that the modulus is known and is a product of two primes. In our estimate, to thwart the proposed attack, the parameters should be enlarged many times. Apart from the scheme, the co-approximate common divisor problem itself is interestingly related to the well-known hard problem, an approximate common divisor problem. And further investigation on this relationship would be desirable.
_ 気になった論文2：On the Cryptographic Hardness of Finding a Nash Equilibrium
, Nir Bitansky and Omer Paneth and Alon Rosen, http://eprint.iacr.org/2014/1029
We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete.
Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps.
Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.
_ （2/6記：正月休み明け、かつ翌日から海外出張ということで、慌ただしく過ごしていた。喉の調子が悪かったので職場近くの病院に行きたかったのだが間に合わず。）
_ （2/6記：フィンランド出張中。到着が夜中だったので本質的にはこの日が初日である。「夜中に空港へ到着して、寝坊せず翌朝早くに街中までバスで移動して待ち合わせ場所まで時間通りに辿り着く」という超絶難解ミッション（←本人比）を無事遂行した。）
_ （2/6記：フィンランド出張中。前日に、日本からの参加者側と現地の参加者側で簡単な研究自己紹介をしていたので、この日はそれを踏まえて共同研究の相談をするなどした。研究の話は英語でもどうにかなっていた（と信じている）のだが、「午後は○○号室に移動して△時から再開ね」のような研究以外の会話が難関という罠。）
_ （2/6記：フィンランド出張中。ホテルの朝食会場に日本風のみかんが置いてあった。海外のホテルだとオレンジが置いてあることが多い印象なので、みかんは珍しいなあと思った。個人的にはみかんの方が好みなので、フィンランドの好感度が上昇した（←）。）
_ （2/6記：フィンランド出張中。この日は日本への出発日だった。出張前は寒さや気候面をかなり心配していたのだが、寒いことは寒かったものの想像していたほどではなかったので助かった。ただ、今回がたまたま暖かめだっただけという可能性もあり、今回のことで油断して次回のときに無茶苦茶寒い思いをするフラグかもしれない。）
_ （2/6記：フィンランド出張から無事帰国。「北欧の食器と言ったらこの会社」とも言われる（らしい）iittalaのムーミンマグカップを（そうとは知らず）お土産に買って帰ったところ、妻と二人して絵柄が気に入りすぎてしまいマグカップを飾りっぱなしで使用できない事案が発生した。）
_ （2/6記：「空中に手書きで文字入力する指輪型デバイス、富士通研が開発」という記事を読んだ。この手の技術が進化したら、例えばこのデバイスと発破の起動装置を連動させることでナッパの「クンッ」を再現できたりするのかなぁ、などと妄想を逞しくしたのは私だけではないと信じている。）
_ （2/6記：週末。この日は阪神淡路大震災からちょうど20年の日。私自身はあちらに住んでいたことはないので、当時の知人で被災した人はいなかったと記憶しているが、詰将棋パラダイス誌に著名な詰将棋作家の方の訃報が掲載されたのを見て衝撃を受けたことが今でも印象に残っている。）
_ （2/6記：この日から福岡出張。今回は前後半で宿が違うのだが、前半の宿が何故か各部屋に調理場や洗濯機が設置されている不思議仕様だった。長く泊まるときは便利そうである。）
_ （2/6記：福岡出張中。この日はSCIS、ではなくSCAIS（Small-workshop on Communications between Academia and Industry for Security）というワークショップで実行委員のお仕事をしていた。英語の略称から逆算して名称を決めたせいで日本語名称が無い（直前になって気が付いた）怪しげなワークショップにもかかわらず多くの方に参加していただいて、濃密な議論ができたので、開催して本当に良かったなぁと感じている。講演者と参加者の皆様に改めてお礼申し上げます。）
_ （2/6記：福岡出張中。この日からSCIS本編が始まった。自分の共著論文2件の発表があったのだが、そのうちの一つで発表者のSNGWさんがぶっ込んできたネタで爆笑していたら、会場で笑っていたのが私だけだったので大いなる悲しみに包まれていた。何故だ。ところで、この日から会場のホテルに宿を切り替えていたのであるが、やはり楽でいいなぁと思った。難点は職場から支給される宿泊費では足が出ることなのだが、今回は体調が思わしくなかったこともあり宿の選択は正解だったと思う。）
_ （2/6記：福岡出張中。SCIS二日目。この日は自分の発表があったのだが、発表の予稿を提出した後で提案暗号方式の具体例に問題が発覚していたこともあってグダグダな中身になってしまった。良かった点は時間内に収まったことぐらいだろうか。次回は捲土重来を期したい。）
_ （2/6記：福岡出張中。SCIS三日目。この日は自分の共著論文の発表、を華麗にスルーして特別講演「数学と暗号の接点 ～ 代数曲線、有限体、そしてモチビックゼータ ～」を聴講。無茶苦茶面白かったので聴きにいって正解だったのだが、やはり共著論文の発表も聴きたかったなぁと思うのである（発表件数が多すぎてプログラムの尺が足りなくなったのだろう、本来ならシングルセッションで行われるはずの招待講演がパラレルセッションの一部に組み込まれていた）。プログラム編成の苦労は容易に想像できるので止むを得ないことではあるのだが。）
最近のツッコミ↓