_ （4/18記：今年度から職場が近い方の職場に統一されたのだが、居室の統合がまだできていない上に建物全体が年度替わりの影響で不具合に満ちていて大変であった。）
_ （4/18記：週末。「任意の素数pに対してp+1元集合に入る位相全体の集合の濃度はmod pで7」という血湧き肉躍る事実を教わった（あと、その一般化を含む論文も）。元論文は読んでないので自分の考えた証明が論文と同じ筋かどうかわからないのだが、面白かったし、いわゆる「集合と位相」の範囲外の知見を組み合わせる必要があるという点でとても院試向きの問いだなあと思った。）
_ （4/18記：TeXでスライド作りをしていて、マクロ定義がどうもうまく機能してくれず困ったので色々と調べ物をしていたら、 \let というコマンドの存在を知った（細かい原理は理解していないが、中身が \or のような制御用コマンドだとしても構わず「そのまま置き換える」働きをしているように見受けられる）。十数年使っているソフトでもまだまだ知らないことは多いものである。）
_ （4/18記：久々の某C大ミーティング。それはさておき、「任意のグラフに全域木が存在する」という命題がZF上で選択公理と同値であるという事実を教わった。証明を考えてみたらほどよい難度で面白かった。関連して考えたこととして、この命題から選択公理を導く過程はいかにも「選んでいる」感があって直感的に理解しやすいし、例えば比較的難しい部類であろう「「任意の線型空間に基底が存在する」から選択公理を導く」証明も、少なくとも基底の存在からAxiom of Multiple Choiceを導く過程は「選んでいる」ように見える（その「選び方」が巧妙とはいえ）。それと比べて、Tychonoffの定理から選択公理を導く証明は「選んでいる」感が希薄であるように私には感じられる。最初に証明を与えた人はよくこんなこと考えついたなぁ、と改めて感心する次第であった。）
_ （4/18記：週末。将棋の電王戦でプロ棋士が対戦相手のソフト固有のハメ手を使って勝った件で騒ぎになっていたが、個人的な感想としては、「（番外戦術などで）故意に相手に弱みを作る」ことが卑怯であったとしても「たまたま生じていた相手の弱みを（ルールの範囲内で）突く」ことが卑怯ということにはならないと思うし、それくらい勝負に徹する強さがないとプロ棋士になることはなかなかできないのではないかな、と思うので、まぁそんなもんだろうな、と思う。端的に言うとプロ棋士は「勝負師」、将棋ソフト開発者は「技術者」あるいは「研究者」の側に属する存在だと思うので、今回の件はその違いが改めて浮き彫りになったと言えるのかもしれない。）
_ （4/18記：「（有限）対称群のうち6次対称群にだけ、ある元による共役変換として表せない自己同型が存在する」という有名な事実についての備忘録を書いた。（その事実は憶えていても、そういう自己同型の具体的な形までは憶えられないので。））
_ （4/18記：先日の数セミ最新号は近所に新しくできた書店で購入したのだが、数学の本や漫画本は色々と置いてあるのに「数学女子」が置かれていなかったので涙を禁じ得ない。）
_ （4/18記：LaTeXのコマンドを二つ続けて実行する際、一つめのコマンドが無事終了したときだけ二つめを実行するための「&&」という接続詞があることを今更ながら初めて知った。これでbeamerでのスライド作りの際にコンパイルとdvi→pdf変換を立て続けに行う作業が非常に捗りそうである。）
_ 週末。
_ IACR ePrint 2015/328まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文：Size-Hiding in Private Set Intersection: what can be done and how to do it without random oracles
, Paolo D'Arco and Maria Isabel Gonzalez Vasco and Angel L. Perez del Pozo and Clauido Soriente, http://eprint.iacr.org/2015/321
In this paper we focus our attention on private set intersection protocols, through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage. Considering the (more restricted) size-hiding scenario, we are able to: - prove that it is impossible to realize an unconditionally secure set intersection protocol (size-hiding or not); - prove that unconditionally secure size-hiding set intersection is possible in a model where a set up authority provides certain information to the two parties and disappears; - provide several new computationally secure size-hiding set intersection protocols. Regarding the latter, in particular we provide a new generic construction without random oracles for the unbalanced setting, where only the client gets the intersection and hides the size of its set of secrets. The main tool behind this design are smooth projective hash functions for languages derived from perfectly-binding commitments. We stand on the seminal ideas of Cramer-Shoup and Gennaro-Lindell, which have already found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer.
_ （4/30記：海外出張2日目。ハンバーガーを食べたらこってりしすぎていて胸やけを起こすというお約束のパターンを辿ってしまった。あと、今回の国際会議は主催者が主催者だけに色々とサービスが充実していて、ホテルから会場までシャトルバスが運行していた。ホテル周辺の坂道が厳しいのでとてもありがたいサービスなのだが、ホテルとバス乗り場の間の坂道が実は一番厳しくて、その区間は自力で歩かなければならない、という微妙な状況でもあった。）
_ （4/30記：海外出張3日目。国際会議自体は面白いし快適に過ごせているのだが、ホテルの部屋が（というか、現地の気候自体が）寒い上に、お湯を沸かす設備が無い（コーヒーメーカーはあったのだが私はコーヒーを飲まないし、湯沸かしに使えないかと試してみたらなんか異音がし始めたのであきらめた）のには参った。）
_ （4/30記：海外出張4日目。時差ぼけで眠くて仕方がなかったのだが、自分の発表はどうにか乗り切った。発表に投入したネタにもわりと反応があったので満足である（←そこ？）。）
_ （4/30記：海外出張5日目。今回は二つの国際会議をハシゴする日程で、この日が前半の国際会議の最終日だった。ある人の発表に質問したら、後で発表者の人からメールが届いて、「名乗ってないのにどうして私だとわかったんだろう…」と不思議に思っていたのだが、よく考えると前日に私も発表していたのだからそのときに顔を憶えられていたのだろう…という可能性に全然気がつかなかったのだからあの日は相当時差ぼけがひどかったのだろうなぁ。で、この日の午後に次の会議の開催地へ出発。）
_ （4/30記：海外出張6日目。二つめの会議開催地に到着。途中に乗り継ぎをしたイスタンブール空港で、サマータイム期間中なのにフライト案内の画面の時刻がサマータイム仕様になっていない、というややこしい事態に遭遇した。）
_ （4/30記：海外出張7日目。前の滞在地は寒かったのだが今度の滞在地は、というかホテルの部屋が暑いので不思議な感覚を味わっていた。ところで、今回の出張から妻との連絡用にSkypeを導入してみたところ極めて快適なので、もっと早く使えばよかったなぁと感じている。そもそも、私は音声だけから情報を得るのが不得意（というか、音声情報を言語情報に復号するために集中力を多めに要するみたいで消耗しやすい）なこともあって電話で人と話すという行為が基本的に苦手なのだが、Skypeだと画面付きなので相手の話を聞き取りやすく長時間の通話でもラクチンなのである。便利な世の中になったものである。）
_ （4/30記：海外出張8日目。今度の滞在地でも相変わらず時差ぼけの影響を受けているのだが、時差の関係で、日本時間でいつもの調子に過ごすと現地時間では夜中に目が覚めて夕食後ぐらいの時間に眠くなるので、むしろ日本にいるときより健康的なライフサイクルになるというよくわからない状況になっている。目が覚めてから本格的な活動時間まで長い時間があるので、その間にたまっている仕事を鬼のように片付けたりしていた。）
_ （4/30記：海外出張9日目。現地の様子にも少し慣れてきたし、お土産を探しがてら少し町歩きをしてみよう、と思って外出した途端に大雨に降られるというアウェーの洗礼（←違）を受けた。）
_ （4/30記：海外出張10日目。この日は私の発表があった。織り交ぜたネタでもちゃんとウケを取ることができて満足である（←）。あと、どうもこのところ、発表中に「手元の時計で時間を確認する」という行為がうまくできなくて困っている（会場の壁に時計が掛かっていたり座長席のパソコンなどに時間が表示されている状況ではちゃんと時間の確認を怠らずできるのだが…）ところ、今回もやはり時計をほとんど見られなかったのだが、どうやら時間内に収まった（というか、むしろ少し早めだったらしい）のでほっとしている。）
_ 海外出張11日目。いよいよ帰国なのだが、ただでさえ長期間ゆえに着替えが多めなのに、二つの会議が両方ともカバンやらパンフレットやら何やら多めに物をくれたこともあって、過去に記憶にないほど荷詰めに苦労した。これ持って帰るのか…
_ IACR ePrint 2015/393まで確認済み、ECCC 2003年分まで確認済み
_ 気になった論文1：Arithmetic Cryptography
, Benny Applebaum and Jonathan Avron and Christina Brzuska, http://eprint.iacr.org/2015/336
We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field $\F$. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions.
We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under reasonable assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, multiplicative-homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.
_ 気になった論文2：Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
, Gilad Asharov and Gil Segev, http://eprint.iacr.org/2015/341
Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a ``central hub'' for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. In this paper we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows:
-- There is no fully black-box construction with a polynomial security loss of a collision-resistant function family from a general-purpose indistinguishability obfuscator.
-- There is no fully black-box construction with a polynomial security loss of a key-agreement protocol with perfect completeness from a general-purpose private-key functional encryption scheme.
-- There is no fully black-box construction with a polynomial security loss of an indistinguishability obfuscator for oracle-aided circuits from a private-key functional encryption scheme for oracle-aided circuits.
Specifically, we prove that any such potential construction must suffer from at least a sub-exponential security loss. Our results are obtained within a subtle framework capturing constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.
_ 気になった論文3：Matrix Computational Assumptions in Multilinear Groups
, Paz Morillo and Carla Ràfols and Jorge L. Villar, http://eprint.iacr.org/2015/353
We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. This family abstracts and includes as a special case several assumptions used in the literature under different names. Given some matrix $\matrA$ sampled from some distribution $\mathcal{D}_{\ell,k}$, the kernel assumption says that it is hard to find ``in the exponent'' a nonzero vector in the kernel of $\mathbf{A}^\top$. Our assumption is the natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala \textit{et al}.
We show that the $\mathcal{D}_{\ell,k}$ Kernel DH Assumption is a strictly increasing family of weaker computational assumptions when $k$ grows. This requires ruling out the existence of some black-box reductions between flexible problems (\textit{i.e.}, computational problems with a non unique solution), which is specially subtle. As opposed to the decisional MDDH Assumption, our kernel assumption might hold in the recent candidate multilinear groups.
Kernel assumptions have implicitly been used in recent works on QA-NIZK and structure-preserving signatures. We also provide a new construction of commitments to group elements in the multilinear setting, based on any kernel assumption.
_ 気になった論文4：On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation
, Nir Bitansky and Omer Paneth, http://eprint.iacr.org/2015/369
The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's technique has given rise to various powerful applications and it is a key component in all known protocols with non-black-box simulation.
We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity.
A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals as: simultaneously-resettable zero-knowledge, proofs of knowledge, and resettable-security from one-way functions. While previous works required tailored modifications to Barak's technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions.
The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality; thus, settling a question left open by Barak et al.. In the converse direction, we show a generic transformation from any resettably-sound zero-knowledge protocol to a family of functions that cannot be obfuscated.
_ 気になった論文5：Dual System Encryption Framework in Prime-Order Groups
, Nuttapong Attrapadung, http://eprint.iacr.org/2015/390
We propose a new generic framework for achieving fully secure attribute based encryption (ABE) in prime-order bilinear groups. It is generic in the sense that it can be applied to ABE for arbitrary predicate. All previously available frameworks that are generic in this sense are given only in composite-order bilinear groups. These consist of the frameworks proposed by Wee (TCC'14) and Attrapadung (Eurocrypt'14). Both frameworks provide abstractions of dual-system encryption techniques introduced by Waters (Crypto'09). Our framework can be considered as a prime-order version of Attrapadung's framework and works in a similar manner: it relies on a main component called pair encodings, and it generically compiles any secure pair encoding scheme for a predicate in consideration to a fully secure ABE scheme for that predicate. One feature of our new compiler is that although the resulting ABE schemes will be newly defined in prime-order groups, we require essentially the same security notions of pair encodings as before. Beside the security of pair encodings, our framework assumes only the Matrix Diffie-Hellman assumption, introduced by Escala et al. (Crypto'13), which is a weak assumption that includes the Decisional Linear assumption as a special case.（ステマ）
As for its applications, we can plug in available pair encoding schemes and automatically obtain the first fully secure ABE realizations in prime-order groups for predicates of which only fully secure schemes in composite-order groups were known. These include ABE for regular languages, ABE for monotone span programs (and hence Boolean formulae) with short ciphertexts or keys, and completely unbounded ABE for monotone span programs.
As a side result, we establish the first generic implication from ABE for monotone span programs to ABE for branching programs. Consequently, we obtain fully-secure ABE for branching programs in some new variants, namely, unbounded, short-ciphertext, and short-key variants. Previous ABE schemes for branching programs are bounded and require linear-size ciphertexts and keys.
最近のツッコミ↓