_ （5/4記：海外出張から帰国。帰りの便で預け荷物に入れておいた土産の品が消失したため涙を禁じ得ない。あと、空港から自宅近くへの高速バスの路線がいつの間にか廃止されていたことを知って悲しみに包まれている。）
_ （5/4記：この日もほぼ一日のんびりと過ごした。海外出張の出発時と帰国時で2週間弱しか経っていないはずなのだが、気候の変化だけみると1ヶ月以上経っているんじゃないかというぐらい暖かくなったなぁと思っている。）
_ IACR ePrint 2015/411まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文1：Factoring RSA moduli with weak prime factors
, Abderrahmane Nitaj and Tajjeeddine Rachidi, http://eprint.iacr.org/2015/398
In this paper, we study the problem of factoring an RSA modulus $N=pq$ in polynomial time, when $p$ is a weak prime, that is, $p$ can be expressed as $ap=u_0+M_1u_1+\ldots+M_ku_k$ for some $k$ integers $M_1,\ldots, M_k$ and $k+2$ suitably small parameters $a$, $u_0,\ldots u_k$. We further compute a lower bound for the set of weak moduli, that is, moduli made of at least one weak prime, in the interval $[2^{2n},2^{2(n+1)}]$ and show that this number is much larger than the set of RSA prime factors satisfying Coppersmith's conditions, effectively extending the likelihood for factoring RSA moduli. We also prolong our findings to moduli composed of two weak primes.
_ 気になった論文2：New attacks on RSA with Moduli $N=p^rq$
, Abderrahmane Nitaj and Tajjeeddine Rachidi, http://eprint.iacr.org/2015/399
We present three attacks on the Prime Power RSA with modulus $N=p^rq$. In the first attack, we consider a public exponent $e$ satisfying an equation $ex-\phi(N)y=z$ where $\phi(N)=p^{r-1}(p-1)(q-1)$. We show that one can factor $N$ if the parameters $|x|$ and $|z|$ satisfy $|xz|<N^\frac{r(r-1)}{(r+1)^2}$ thereby extending the recent results of Sakar~\cite{SARKAR}. In the second attack, we consider two public exponents $e_1$ and $e_2$ and their corresponding private exponents $d_1$ and $d_2$. We show that one can factor $N$ when $d_1$ and $d_2$ share a suitable amount of their most significant bits, that is $|d_1-d_2|<N^{\frac{r(r-1)}{(r+1)^2}}$. The third attack enables us to factor two Prime Power RSA moduli $N_1=p_1^rq_1$ and $N_2=p_2^rq_2$ when $p_1$ and $p_2$ share a suitable amount of their most significant bits, namely, $|p_1-p_2|<\frac{p_1}{2rq_1q_2}$.
_ 気になった論文3：Computation-Trace Indistinguishability Obfuscation and its Applications
, Yu-Chi Chen and Sherman S. M. Chow and Kai-Min Chung and Russell W. F. Lai and Wei-Kai Lin and Hong-Sheng Zhou, http://eprint.iacr.org/2015/406
We introduce a new, instance-based notion of indistinguishability obfuscation, called computation-trace indistinguishability obfuscation (CiO), for (parallel) RAM computation. CiO only obfuscates a fixed, single computation instance, as opposed to iO which obfuscates a function on all input instances. Specifically, for $\Pi$ defined by (P, x) consisting of a (parallel) RAM program P and an input x, the obfuscations of two instances $\Pi$ and $\Pi’$ are required to be indistinguishable only when the execution of $\Pi$ and $\Pi’$ generate an identical computation trace; namely, identical sequences of CPU states and memory content. On the other hand, we require the obfuscation to be (i) fully succinct: the runtime of the obfuscator (and thus the size of the obfuscated instance) depends only on the description and input/output size of $\Pi$, but is independent of the time and space complexities of $\Pi$, and (ii) efficiency preserving: the obfuscated instance is a (parallel) RAM program that preserves parallel/total time and space complexities of $\Pi$ up to polylogarithmic factors. As our main results, we construct CiO for parallel RAM (PRAM) computation based on iO for circuits and one-way functions, and demonstrate the power of CiO by the following applications. • With digital signatures, our CiO for PRAM immediately implies the first two-message (publicly- verifiable) delegation scheme for outsourcing PRAM computation, where the delegator’s runtime depends only on the program description and input/output size, and the server’s complexity matches the PRAM complexity of the computation up to polylogarithmic factors. • With public-key encryption, our CiO for PRAM, and a specific oblivious PRAM construction, we construct the first fully succinct randomized encoding (RE) for PRAM computation, where the encoder’s runtime (and thus the encoding size) depends only on the program description and input/output size, and the decoding complexity matches PRAM complexity of the computation up to polylogarithmic factors. • By plugging our fully succinct RE for PRAM into existing transformations, we obtain the first constructions of several cryptographic primitives for PRAM, such as functional encryptions with succinct (PRAM) function keys, succinct reusable garbling schemes, and succinct indistinguishability obfuscations (the later requires sub-exponential security). Notably, this implies that, while CiO is weaker than iO, sub-exponentially secure CiO for PRAM implies sub-exponentially secure iO for PRAM.
_ （5/11記：柏餅を買えることを期待して近所のコンビニに行ったが売られていなかった（品切れではなく売り場自体が無い）。恵方巻やらハロウィンに熱心になるのはいいけど、以前からある行事も大切にしてもらいたいものである。）
_ （5/11記：連休の最終日だったがそれはそれとして、とあるエラい数学者が「相手の誤りを率直に誤りだと指摘する行為」と「相手に対する罵倒」を混同している場面に遭遇して悲しい気持ちになった。後者のような行為をするぐらいなら数学をするべきである。）
_ （5/11記：某C大ミーティング。それはそれとして、「ベルヌーイ数」を「ベルヌーイ」「かず」で変換しようとしたら「ベルヌーイ和」と変換されて、微妙にそういう概念がありそうなだけに趣深かった。）
_ （5/11記：週末。このところ新井敏康「数学基礎論」を地味に読み進めている。まだ序盤とはいえ、噂には聞いていた色々な結果（コンパクト性定理、完全性定理、再帰的関数の話、等々）を実際に手元で再構成していくのは楽しいものである。あと、学部前半の頃にも少しこの辺りを勉強しようとしたことがあったもののわけがわからなくて挫折した、ということを思い出して懐かしんでもいる。まぁ確かに、読み進めていくにつれて、（少なくとも私の）学部前半の時点でこれは厳しいよなぁとも実感できるのだが。）
_ IACR ePrint 2015/447まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文1：Survey on Cryptographic Obfuscation
, Máté Horváth, http://eprint.iacr.org/2015/412
The recent result of Garg et al. (FOCS 2013) changed the previously pessimistic attitude towards general purpose cryptographic obfuscation. Since their first candidate construction, several authors proposed newer and newer schemes with more persuasive security arguments and better efficiency. At the same time, indistinguishability obfuscation proved its extreme usefulness by becoming the basis of many solutions for long-standing open problems in cryptography e.g. functional or witness encryption and others. In this survey, we give an overview of recent research, focusing on the theoretical results on general purpose obfuscation, particularly, indistinguishability obfuscation.
_ 気になった論文2：Conversions among Several Classes of Predicate Encryption and Their Applications
, Shota Yamada and Nuttapong Attrapadung and Goichiro Hanaoka, http://eprint.iacr.org/2015/431
Predicate encryption is an advanced form of public-key encryption that yield high flexibility in terms of access control. In the literature, many predicate encryption schemes have been proposed such as fuzzy-IBE, KP-ABE, CP-ABE, (doubly) spatial encryption (DSE), and ABE for arithmetic span programs. In this paper, we study relations among them and show that some of them are in fact equivalent by giving conversions among them. More specifically, our main contributions are as follows:（ステマ）
- We show that monotonic, small universe KP-ABE (CP-ABE) with bounds on the size of attribute sets and span programs (or linear secret sharing matrix) can be converted into DSE. Furthermore, we show that DSE implies non-monotonic CP-ABE (and KP-ABE) with the same bounds on parameters. This implies that monotonic/non-monotonic KP/CP-ABE (with the bounds) and DSE are all equivalent in the sense that one implies another.
- We also show that if we start from KP-ABE without bounds on the size of span programs (but bounds on the size of attribute sets), we can obtain ABE for arithmetic span programs. The other direction is also shown: ABE for arithmetic span programs can be converted into KP-ABE.These results imply, somewhat surprisingly, KP-ABE without bounds on span program sizes is in fact equivalent to ABE for arithmetic span programs, which was thought to be more expressive or at least incomparable.
By applying these conversions to existing schemes, we obtain many non-trivial consequences. We obtain the first non-monotonic, large universe CP-ABE (that supports span programs) with constant-size ciphertexts, the first ABE for arithmetic span programs with adaptive security, the first ciphertext-policy version of ABE for arithmetic span programs, the first KP-ABE with constant-size private keys, and even more.
We also obtain the first attribute-based signature scheme that supports non-monotone span programs and achieves constant-size signatures via our technique.
_ （5/15記：珍しく発売日に「数学セミナー」誌を入手したのだが、妻より「数学セミナーを読む前に数学セミナーの原稿を書くべき」という真っ当な指摘を受けたので原稿に向かっていた。）
_ （5/18記：週末。この日は大阪市を廃止するかどうかの住民投票が行われて、結果についてはここでは触れないのだが、どうやら投票率が66％程度にとどまったらしく、「このネタでも7割いかない投票率にしかならないのか」と嘆いている。）
_ IACR ePrint 2015/466まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：Efficient Fully Homomorphic Encryption with Circularly Secure Key Switching Process
, Zhou Tanping*, Yang Xiaoyuan, Zhang Wei and Wu Liqiang, http://eprint.iacr.org/2015/466
Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations inefficient. In this paper, the “special b” variant of the Learning With Errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearization process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski’s scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.
_ （5/29記：国際会議参加のためアメリカへ出発。現地について、チェックインまで時間があったので公園の噴水を眺めつつ数学をしていたら、最近考えていた問題の突破口を思いついた。自宅と職場にも噴水がほしい。）
_ （5/29記：会議が終わったので日本に向け出発。ところで、今回の現地到着時に空港で入国審査と税関を通過した後、ゲートを出たらいきなり屋外だったのには驚いた。到着が早めの便だから空港で少し休憩してから移動しようと思っていたのに意表を突かれた。）
_ IACR ePrint 2015/516まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文1：Practical Fully Homomorphic Encryption without Noise Reduction
, Dongxi Liu, http://eprint.iacr.org/2015/468
We present a new fully homomorphic encryption (FHE) scheme that is efficient for practical applications. The main feature of our scheme is that noise reduction considered essential in current FHE schemes, such as boot strapping and modulus switching, is not needed in our scheme, because it allows arbitrarily large noises in its ciphertexts. A ciphertext in our scheme is a vector with its dimension specified as a security parameter of the encryption key. The dimension of ciphertexts does not change with homomorphic operations and all ciphertext elements are in a finite domain, so our scheme is compact. In addition, our scheme can directly encrypt big integers, rather than only bit messages.
We proved the hardness of recovering encryption keys from any number of ciphertexts with chosen plaintexts and then the semantic security of our scheme. The hardness of recovering keys from ciphertexts is based on the approximate greatest common divisors problem. We implemented a prototype of our scheme and evaluated its concrete performance extensively from the aspects of encryption, decryption, homomorphic operations, and bitwise operators over ciphertexts. The efficiency of our scheme is confirmed by the evaluation result.
_ 気になった論文2：Fully Homomorphic Encryption without bootstrapping
, Masahiro Yagisawa, http://eprint.iacr.org/2015/474
Gentry’s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In this paper I propose a new fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. The security of the proposed fully homomorphic encryption scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on. The key size of this system and complexity for enciphering/deciphering become to be small enough to handle.
最近のツッコミ↓