_ arXiv:math 2012年11月20日分まで、IACR ePrint 2012/733まで確認済み
_ 気になった論文：Reflection subgroups of odd-angled Coxeter groups
, Anna Felikson, Jessica Fintzen, Pavel Tumarkin, http://jp.arxiv.org/abs/1211.4194
We give a criterion for a finitely generated odd-angled Coxeter group to have a proper finite index subgroup generated by reflections. The answer is given in terms of the least prime divisors of the exponents of the Coxeter relations.
_ 累次積分の順序交換不可能性に関するシェルピンスキーの結果を紹介した@kadamasaruさんのノートを（だいぶ前にダウンロードしていたのに、今頃になってようやく）読んだ。曰く、ZFC上で連続体仮説を仮定すると、正方形状の閉領域上の（つまり、実2変数の）関数を二つの変数について順次（ルベーグ）積分したとき、積分する変数の順番を入れ替えると（どちらの順番でも積分の値自体は定まるのに）最終的な値が一致しなくなる例が存在するとのこと。私の勝手な直感だと、連続体仮説が成り立たない場合の方が実数集合の構造が豊かになるような想像をしていたのだけど、連続体仮説の否定ではなく連続体仮説の成立を仮定した場合にこういう奇妙な例が現れるというのがなんとも趣深いなぁと思った。
_ 某所で@math26さんに教えていただいた「駒.zone」という将棋文芸誌のvol.6を拝読。といっても私の某作品を取り上げて下さったという詰将棋論考の文章しか読んでない（そこに辿りつくまでに画面をスクロールさせていたらなぜか「魔法少女」とか「10万3000冊」とかいう語が目に入ってきたのは置いといて）のだけれども、想像の３周ぐらい上をいく充実の文章でとても驚いた。少しでも詰将棋に関心があって、かつ「こんな作品全部知ってるよ」という超マニアでない方にはぜひ読んでみていただきたい。
なお、筆者の方は文章中で「そろそろ修論がやばいので」云々と書かれていたのだけれども、某選択公理の人といい、最近は修論の時期に専門以外でよい書き物をするのが流行りなのだろうか。（だがそれがいい）
_ （1/12記：某国際会議に参加中なのだけれど、開催地の大学自体には前にも来たことがあるから大丈夫だろうと油断していたら、大学の内部で道に迷ってしまった。）
_ arXiv:math 2012年11月20日分まで、IACR ePrint 2013/013まで確認済み
_ 気になった論文１：Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security
, Kai-Min Chung and Rafael Pass and Karn Seth, http://eprint.iacr.org/2013/008
The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques.
The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol.
In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.
_ 気になった論文２：Tropical cryptography
, Dima Grigoriev and Vladimir Shpilrain, http://eprint.iacr.org/2013/012
We employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to linear algebra attacks were they based on ``usual" algebras as platforms.
_ 今日は前日の雪の影響で外を歩くのが大変そうなのだけど、偶然にも予め有給休暇を取得していたので通勤しないですんでいる。
_ 先日Twitterでの会話の流れから生じたちょっとした問題。数学で「aがbともcとも異なる」ことを「b≠a≠c」と表す書き方は、紛らわしい場合がある*1し決して行儀のよい書き方とはいえないのだけれど、自分用のメモなどではそういう書き方を使ってしまうこともあるかもしれない。さて、上のような横着した書き方で「aとbとcが全て異なる」ことを1行で表そうとすると、例えばa≠b≠c≠aと書けば不等号3個で用が足りる。では、一般にn個の元が全て異なることをこのような書き方で表そうとすると、不等号を最小で何個使うことになるだろうか？
なお、3個の元のときを例にとると、上のa≠b≠c≠aのような無駄のない書き方だけでなく、a≠b≠c≠b≠a≠cみたいな冗長性のある（同じペアについての不等号関係が2回以上現れる）書き方でも構わないことを注意しておく。（そういう書き方を許さないとすると、n=4の場合で既に条件を満たす書き方が存在しなくなってしまう。）
*1 一つの問題として、等号の場合にはb = aとa = cがb = cを導くのでb = a = cと書いたら「aとbとcが全て等しい」の意味で誤解はないのだけど、不等号の場合にはそういう導出関係は一般には成り立たないので、どこまでの範囲で等しくない関係が言えているのか混乱する場合がある。
_ arXiv:math 2012年11月28日分まで、IACR ePrint 2013/017まで確認済み
_ 気になった論文１：Groups with a base property analogous to that of vector spaces
, Paul Apisa, Benjamin Klopsch, http://jp.arxiv.org/abs/1211.6137
A B-group is a group such that all its minimal generating sets (with respect to inclusion) have the same size. We prove that the class of finite B-groups is closed under taking quotients and that every finite B-group is solvable. Via a complete classification of Frattini-free finite B-groups we obtain a general structure theorem for finite B-groups. Applications include new proofs for the characterization of finite matroid groups and the classification of finite groups with the basis property.
_ 気になった論文２：Complete and Unified Group Laws are not Enough for Elliptic Curve Cryptography
, Graham Enos, http://eprint.iacr.org/2013/015
We analyze four recently proposed normal forms for elliptic curves. Though these forms are mathematically appealing and exhibit some cryptographically desirable properties, they nonetheless fall short of cryptographic viability, especially when compared to various types of Edwards Curves. In this paper, we present these forms and demonstrate why they fail to measure up to the standards set by Edwards Curves.
_ arXiv:math 2012年11月28日分まで、IACR ePrint 2013/023まで確認済み
_ 気になった論文：Nonlinear cryptanalysis of reduced-round Serpent and metaheuristic search for S-box approximations
, James McLaughlin and John A. Clark, http://eprint.iacr.org/2013/022
We utilise a simulated annealing algorithm to find several nonlinear approximations to various S-boxes which can be used to replace the linear approximations in the outer rounds of existing attacks. We propose three variants of a new nonlinear cryptanalytic algorithm which overcomes the main issues that prevented the use of nonlinear approximations in previous research, and we present the statistical frameworks for calculating the complexity of each version. We present new attacks on 11-round Serpent with better data complexity than any other known-plaintext or chosen-plaintext attack, and with the best overall time complexity for a 256-bit key.
_ arXiv:math 2012年12月2日分まで、IACR ePrint 2013/023まで確認済み
_ 昨日と今日は大学入試センター試験だったらしい。受験者と関係者の皆様お疲れさまでした。
さて、そのセンター試験、そりゃまぁ現状のセンター試験に利点が全くないとは言わないけれども、ずっと今の制度でセンター試験を続けていくのは問題があるので、どうにか改善してもらいたいものだと思っている。50万人規模を対象として二日間に亘って一斉に試験を行い、しかも英語リスニング問題用の機器まで登場するとあってはトラブルを完全に防ぐなんて無理ゲーすぎる、という運営側の阿鼻叫喚はさておき、受験生にとっての問題としては、年１回（しかも真冬）しか受験の機会がない点はぜひとも見直されるべきだと考えている。
極論を言えば、現状のセンター試験で良い成績を収める受験者というのは、それまでの学習内容を良く身につけている人ではなく、年にたった１回の試験に向けて、それこそ「落ちる」「すべる」といった単語にまで神経質になるような極限の精神状態の中、真冬の寒さで風邪をひくこともなく、試験の当日のみに調子の良かった人である。つまり、その人本来の学習の出来不出来ではなく、スポーツ選手さながらの「プレッシャーの中で本番当日にピークを合わせる調整能力」が試験結果に大きく影響を及ぼしてしまう。でも、そんな能力は大学での学びに必要な能力なのか？例えば、本人がしっかり勉学に励んでいたとしても、体質的に寒さに弱ければそれだけで試験において大きく不利であるし、また緊張しやすい性格かどうかも大きく関わってくる。そのような要素は、本当に大学入試で試されるべき要素なのだろうか？
もし仮に、現在のような年１回の一発勝負ではなく、自動車運転免許試験のように頻繁に試験を実施…はさすがに労力的に大変かもしれないが、せめて年数回実施される試験の中で一番良い結果の成績を用いるといった制度にできたとしたら。上で例示した寒さへの耐性といった本質的でない要素の影響や、受験者の本領発揮を阻害する強烈なプレッシャーをだいぶ排除できるのではないだろうか、と思うのである。まぁ、かく言う私自身はどちらかというと試験当日だけやたら調子が良かったことで得をした側の受験生だったのでこんなこと言うのもアレなのだけど、折角試験される側もする側も苦労して試験を行うわけだから、どうせなら本当に試されるべき能力が試される試験制度に近付けてほしいなぁと思う次第である。
_ 某論文誌に載った論文の別刷りが職場に送られてきた。大きめの小包二つ分くらい。60ページの論文50編分なので、両面印刷とすると紙が1500枚ほど増えたことになるのか。
_ （1/25記：某なんちゃらCIS三日目。前日よりはましな体調とはいえやはり風邪であることは否めない。仕事がある間にだけエネルギーを集中させている感がある。）
_ 某SCなんちゃら最終日。体調は少し良くなった。色々と面白そうな発表があったようなので（←会場係の割り当ての関係上、あまり直に発表を聴けなかった）体調と相談して予稿集を読み込みたいものである。
_ arXiv:math 2012年12月2日分まで、IACR ePrint 2013/030まで確認済み
_ （1/28記：妻が借りてきていた映画版「るろうに剣心」のDVDを観た。初めに実写化の話を耳にしたときには、ジャンプ漫画の実写化ということで（自主規制）や（察して下さい）のときのようなアレな出来だったらどうしようと心配していたのだが、実際見てみると完全な取り越し苦労だったようでとても面白く観ることができた。個人的には、特に剣心が戦う殺陣の場面が非常にスピード感溢れる作りで、よくこれだけ雰囲気のある殺陣を実現したなぁと驚きだった。ストーリーも役者さんの演技も良かったと思うので、原作好きで映画版をまだ観ていない方には視聴をお勧めしておきたい。）
_ （1/29記：朝起きたら雪が積もっていたのでびっくりした。思わず有給休暇を申請しそうになしばらく前の大雪のときとは違って電車が止まったりは特になかったので助かった。）
_ arXiv:math 2012年12月2日分まで、IACR ePrint 2013/043まで確認済み
_ 気になった論文：Batch Fully Homomorphic Encryption over the Integers
, Jean-Sébastien Coron and Tancrède Lepoint and Mehdi Tibouchi, http://eprint.iacr.org/2013/036
We extend the fully homomorphic encryption scheme over the integers of van Dijk et al. (DGHV) to batch fully homomorphic encryption, i.e. to a scheme that supports encrypting and homomorphically processing a vector of plaintext bits as a single ciphertext. Our variant remains semantically secure under the (error-free) approximate GCD problem. We also show how to perform arbitrary permutations on the underlying plaintext vector given the ciphertext and the public key. Our scheme offers competitive performance: we describe an implementation of the fully homomorphic evaluation of AES encryption, with an amortized cost of about 12 minutes per AES ciphertext on a standard desktop computer; this is comparable to the timings presented by Gentry et al. at Crypto 2012 for their implementation of a Ring-LWE based fully homomorphic encryption scheme.
最近のツッコミ↓
_ ikutana [(a-b)(b-c)(c-a)≠0 って表記はどうだろう、と思ったけど、実数ならいいけど、複素数とかだとまずいかな。]
_ MarriageTheorem [コメントありがとうございます。その表記は実数や複素数など体の要素なら成り立ちますが、例えば環Z/nZでnが合成数の場..]