_ （2/6記：週末。結局、月末締切の原稿はextended 月末（この日の営業時間前）の提出となってしまった。この日は妻の髪飾りを近所のお店へ探しに行ったのだが、品揃えが悪くなった、というか品物の傾向が相性悪い感じに変化してしまったらしく不調に終わった。また品揃えが復活してくれるといいのだが。）
_ （2/6記：打ち合わせのために信州大へ出張。エヌ氏が考えている問題の応用先について議論していたら何故か将棋の話になったりして混沌とした時間であった。だがそれがいい。）
_ IACR ePrint 2015/069まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文1：Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR
, Tancrède Lepoint and Mehdi Tibouchi, http://eprint.iacr.org/2015/012
Private Information Retrieval (PIR) protects users' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a “real world” level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).
In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the users' access pattern in a matter of seconds.
_ 気になった論文2：A LINEAR ATTACK ON A KEY EXCHANGE PROTOCOL USING EXTENSIONS OF MATRIX SEMIGROUPS
, JINTAI DING, ALEXEI MIASNIKOV, AND ALEXANDER USHAKOV, http://eprint.iacr.org/2015/018
In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.
_ 気になった論文3：Group Signature with Deniability: How to Disavow a Signature
, Ai Ishida, Keita Emura, Goichiro Hanaoka, Yusuke Sakai, and Keisuke Tanaka, http://eprint.iacr.org/2015/043
Group signature is a class of digital signatures with enhanced privacy. By using this type of signature, a user can prove membership of a specific group without revealing his identity, but in the case of a dispute, for a given signature, an authority can expose the identity of its signer. However, in some situations wherein it is necessary to only know whether a specified user is the signer of the given signature, the naive use of a group signature may be problematic since if the specified user is NOT the actual signer, then the identity of the actual signer will be exposed. In this paper, inspired by this problem, we propose the notion of a deniable group signature, where with respect to a signature and a user, the opener can issue a proof that the opening result of the signature is NOT the specified user without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.（ステマ）
_ 気になった論文4：Linearly Homomorphic Encryption from DDH
, Guilhem Castagnos and Fabien Laguillaumie, http://eprint.iacr.org/2015/047
We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.CT-RSAの（なぜかウェブページからリンクされていない）accepted papers listで見かけて気になっていた論文、プレプリント版がアップされたのか。後で読もう。
_ （2/25記：前日に疲れたこともあってこの日に休日出張の代休を投入。ところで、少なくともTwitter上では「（主に学生による）学会発表のスライドの最後に「ご清聴ありがとうございました」とだけ書いたページ（通称「ご清聴スライド」）を置くのはけしからん」という議論が定期的に再燃する。個人的には、「ご清聴」がよくないというよりは、ご清聴（略）とだけ書かれたスライドはあまりにも情報量が少なすぎてほとんど役に立っていないのが問題の根本のような気がしているので、「ご清聴スライドを置きたければ余白を有効活用すべし」と指導する案を提示したい。なお、たとえばご清聴スライドの余白には必ずネタを突っ込んで聴衆のウケを狙う、というのも一つの方針であるが、実体験として茨の道であるので万人向けではないことを注意しておきたい。）
_ （2/25記：九州大のマス・フォア・某ンダストリ研究所へ出張してセミナーで発表してきた。風邪は相変わらずひどくて喉の調子が最悪で、こんな声で喋ってもまともに聞き取れないのではないかと心配したものの、どうにか発表を終えることができてよかった。）
_ （2/26記：遠い方の職場へ。夜にあまりよく眠れなかったせいか、一日中ひどく疲れていて、帰りのバスで乗り物酔いした上に帰宅後すぐに寝落ちしてしまった。）
_ IACR ePrint 2015/118まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文１：Factoring N=p^r q^s for Large r and s
, Jean-Sebastien Coron and Jean-Charles Faugere and Guenael Renault and Rina Zeitoun, http://eprint.iacr.org/2015/071
Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.
_ 気になった論文２：Re-encryption Verifiability: How to Detect Malicious Activities of a Proxy in Proxy Re-encryption
, Satsuya Ohata and Yutaka Kawai and Takahiro Matsuda and Goichiro Hanaoka and Kanta Matsuura, http://eprint.iacr.org/2015/112
In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.（ステマ）
_ 気になった論文３：Constructing and Understanding Chosen Ciphertext Security via Puncturable Key Encapsulation Mechanisms
, Takahiro Matsuda and Goichiro Hanaoka, http://eprint.iacr.org/2015/118
In this paper, we introduce and study a new cryptographic primitive that we call "puncturable key encapsulation mechanism" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC'91), and "break down" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security.（ステマ）
To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: "sender non-committing encryption" (SNCE) and non-interactive witness indistinguishable proofs.
Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: "SNCE" and "symmetric key encryption secure for key-dependent messages" (KDM secure SKE). Our construction realizes the "decrypt-then-re-encrypt"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.
_ IACR ePrint 2015/135まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文１：Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications
, Takashi Yamakawa and Shota Yamada and Goichiro Hanaoka and Noboru Kunihiro, http://eprint.iacr.org/2015/128
A self-bilinear map is a bilinear map where the domain and target groups are identical. In this paper, we introduce a self-bilinear map with auxiliary information which is a weaker variant of a self-bilinear map, construct it based on indistinguishability obfuscation and prove that a useful hardness assumption holds with respect to our construction under the factoring assumption. From our construction, we obtain a multilinear map with interesting properties: the level of multilinearity is not bounded in the setup phase, and representations of group elements are compact, i.e., their size is independent of the level of multilinearity. This is the first construction of a multilinear map with these properties. Note, however, that to evaluate the multilinear map, auxiliary information is required. As applications of our multilinear map, we construct multiparty non-interactive key-exchange and distributed broadcast encryption schemes where the maximum number of users is not fixed in the setup phase. Besides direct applications of our self-bilinear map, we show that our technique can also be used for constructing somewhat homomorphic encryption based on indistinguishability obfuscation and the Phi-hiding assumption.（ステマ）
_ 気になった論文２：Homomorphic Computation of Edit Distance
, Jung Hee Cheon and Miran Kim and Kristin Lauter, http://eprint.iacr.org/2015/132
These days genomic sequence analysis provides a key way of understanding the biology of an organism. However, since these sequences contain much private information, it can be very dangerous to reveal any part of them. It is desirable to protect this sensitive information when performing sequence analysis in public. As a first step in this direction, we present a method to perform the edit distance algorithm on encrypted data to obtain an encrypted result. In our approach, the genomic data owner provides only the encrypted sequence, and the public commercial cloud can perform the sequence analysis without decryption. The result can be decrypted only by the data owner or designated representative holding the decryption key.
In this paper, we describe how to calculate edit distance on encrypted data with a somewhat homomorphic encryption scheme and analyze its performance. More precisely, given two encrypted sequences of lengths $n$ and $m$, we show that a somewhat homomorphic scheme of depth $\bigo((n+m) \log\log (n+m))$ can evaluate the edit distance algorithm in $\bigo(nm \log (n+m))$ homomorphic computations. In the case of $n=m$, the depth can be brought down to $\bigo(n)$ using our optimization technique. Finally, we present the estimated performance of the edit distance algorithm and verify it by implementing it for short DNA sequences.
_ 気になった論文３：Private Computation on Encrypted Genomic Data
, Kristin Lauter and Adriana Lopez-Alt and Michael Naehrig, http://eprint.iacr.org/2015/133
A number of databases around the world currently host a wealth of genomic data that is invaluable to researchers conducting a variety of genomic studies. However, patients who volunteer their genomic data run the risk of privacy invasion. In this work, we give a cryptographic solution to this problem: to maintain patient privacy, we propose encrypting all genomic data in the database. To allow meaningful computation on the encrypted data, we propose using a homomorphic encryption scheme.
Specifically, we take basic genomic algorithms which are commonly used in genetic association studies and show how they can be made to work on encrypted genotype and phenotype data. In particular, we consider the Pearson Goodness-of-Fit test, the D' and r^2-measures of linkage disequilibrium, the Estimation Maximization (EM) algorithm for haplotyping, and the Cochran-Armitage Test for Trend. We also provide performance numbers for running these algorithms on encrypted data.
_ 週末だというのにePrintが（また）大量に更新されている件。
_ IACR ePrint 2015/175まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：New Multilinear Maps over the Integers
, Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi, http://eprint.iacr.org/2015/162
In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map.
In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.
最近のツッコミ↓