_ プレプリント確認状況：arXiv:math 9月16日分まで、IACR ePrint 2012/560まで
_ 気になった論文１：Nonassociative Ramsey Theory and the amenability of Thompson's group
(Justin Tatch Moore, arXiv:1209.2063)
The purpose of this article is prove that Thompson's group F is amenable. The methods developed will then be used to prove a generalization of Hindman's theorem for the free nonassociative binary system on one generator.
_ 気になった論文２：An entropic partial order on a parabolic quotient of S6
(Gary McConnell, arXiv:1209.2674)
Let m and n be any integers with n>m>=2. Using just the entropy function it is possible to define a partial order on S_mn (the symmetric group on mn letters) modulo a subgroup isomorphic to S_m x S_n. We explore this partial order in the case m=2, n=3, where thanks to the outer automorphism the quotient space is actually isomorphic to a parabolic quotient of S_6. Furthermore we show that in this case it has a fairly simple algebraic description in terms of elements of the group ring.
_ ↓苦節１年、ついにarXivチェックが最新データまで追い付いた。感慨深い。
_ プレプリント確認状況：arXiv:math 10月2日分まで、IACR ePrint 2012/560まで
_ 気になった論文：Random subgroups of linear groups are free
(Richard Aoun, arXiv:1005.3445)
We show that on an arbitrary finitely generated non virtually solvable linear group, any two independent random walks will eventually generate a free subgroup. In fact, this will hold for an exponential number of independent random walks.
_ プレプリント確認状況：arXiv:math 10月3日分まで、IACR ePrint 2012/562まで
_ どうやらNISTのSHA-3 competitionが決着したらしい。
_ プレプリント確認状況：arXiv:math 10月4日分まで、IACR ePrint 2012/562まで
_ 気になった論文：Invariance groups of finite functions and orbit equivalence of permutation groups
(Eszter K. Horváth, Géza Makay, Reinhard Pöschel, Tamás Waldhauser, arXiv:1210.1015)
Which subgroups of the symmetric group Sn arise as invariance groups of n-variable functions defined on a k-element domain? It appears that the higher the difference n-k, the more difficult to answer this question. For k>=n, the answer is easy: all subgroups of Sn are invariance groups. We give a complete answer in the cases k=n-1 and k=n-2, and we also give a partial answer in the general case: we describe invariance groups when n is much larger than n-k. The proof utilizes Galois connections and the corresponding closure operators on Sn, which turn out to provide a generalization of orbit equivalence of permutation groups. We also present some computational results, which show that all primitive groups except for the alternating groups arise as invariance groups of functions defined on a three-element domain.
_ （10/25記：「森」で有名な某大学に潜入。論文書きを手伝いに行ったと思ったらいつのまにか科研費の書類書きを手伝っていたという俗に言うポルナレフ状態を味わった。）
_ （10/25記：職場のミーティングで科研費の応募書類についてみんなで相談した、ような…。今回は「うそっ、私の科研費応募、多すぎ…！？」というレベルで分担者になりまくっているので、自分が代表者な書類に記載する項目が増えて困りものである。）
_ （10/25記：今日は放送大学での講義（といっても、テレビに出るわけではなく、面接授業という普通の講義形式での講義。放送大学にも普通の形式の講義があるのです）。全８コマを二日間に分けて行うので、この日と翌週で一日４コマずつ喋るというかなりハード（特に私の喉に）な日程である。内容的にも「高校程度の数学しか使いません(ｷﾘｯ」と言いつつ角の三等分問題やらゲーデルのＬやら色々詰め込んでしまったのだが、想像以上にタフな受講者が多くてよい意味で驚きであった。）
_ （10/25記：いよいよ論文の締切がピンチな状況になってきたので、セミナー会場へ向かうときに歩きながら論文を書いていたら、初めて行く場所だったため危うく迷子になりかけてしまった。）
_ （10/25記：某ミーティングで学部4年の皆さんの卒業研究ネタを聴いていたのだが、結構難しそうなネタもあって、楽しみと心配が混ざり合った心境になっていた。いやまぁ、「大体の状況では」（つまり、相応しいレベルに強めた仮定を適切な形で導入してやれば、最終的には）成り立つはずの主張の証明が目標なので研究そのものがダメになることはなかろうが、プロの研究者にとっては珍しくもない「欲しい命題の証明のために仮定の側を調整する」という方法論は、初見のしかも学部生の人にとってはだいぶ発想の転換を要するのではないかと想像する次第である。）
_ （10/25記：この日は元々は妻の親戚方面の冠婚葬祭関係のアレコレがあったのだが、妻の体調不良と私の論文書きの状況を鑑みて予定はキャンセルさせてもらい、家でひたすら論文書きを進めていた。）
_ （10/25記：この日元々入っていた打ち合わせが急遽キャンセルになったので存分に論文書きに勤しんだ。指定のページ数制限に合わせるため論文を無理やり切り詰めていると、ボクサーが試合前に減量する様子（本物は見たことが無いので主に漫画経由の情報だが）が想い起こされてならない。）
_ （10/25記：この日はこのところ書き続けてきた論文の投稿〆切、かつ放送大学の講義二日目である。何故わざわざこの日を講義日に指定したのかと過去の自分を小一時間問い詰めたくなる心境になったが、その頃は論文〆切日が決まっていなかったのだから仕方がない。
講義に関しては、数学っぽいネタで話をした初日から雰囲気がガラッと変わり、二日目は暗号分野を中心とする情報系のネタに終始した。暗号についての予備知識を全く仮定しない状態から出発して最終的にメタ帰着やオラクル分離についての紹介まで辿り着くという見事な暴走ぶりだったにも関わらず、最後までまともに聴いてくれた受講者が少なくなかったのは驚きであった。事前に放送大学の事務の方から「本学には「数学マニア」な学生がそこそこいるので遠慮しないでよい」（←大意）と聞いていたあれは本当だったのだなぁと言葉ではなく心で理解した。
一方の論文については、共著者の皆さんからの鋭いコメントなどを頂きつつ、〆切数十秒前まで修正投稿を繰り返す状況だったが、何とか無事投稿することができた。ぜひとも良い結果を聞きたいものである。）
_ 今日は科研費応募書類の内部提出〆切日、かつ職場の一般公開イベント初日である。「片方だけならスゲーよくわかる、だが両方同じ日に設定するってのはどういうことだこのド（中略）が」と私の頭の中のギアッチョ氏の怒りをなだめつつ職場へ向かう。
_ 折角arXivの新着チェックが最新版に追い付いていたのに、ここ最近の忙しさでまた引き離されてしまった。再度追い付かなければ。（メモ：arXiv:math 10月5日分まで、IACR ePrint 2012/562まで確認済み）
_ 今日は私の頭の中のギアッチョ氏が大活躍する一日だった。明日からはもっと静かに暮らしたいものである。
_ arXiv:math 10月5日分まで、IACR ePrint 2012/587まで確認済み
_ 気になった論文１：On the Power of Random Oracles
, Iftach Haitner and Eran Omri and Hila Zarosim, http://eprint.iacr.org/2012/573
Abstract: In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open:
What is the exact power of the random oracle model, and more specifically, of the random function model?
We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property.
To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.
_ 気になった論文２：Quantum algorithm for the discrete logarithm problem for matrices over finite group rings
, A. D. Myasnikov and A. Ushakov, http://eprint.iacr.org/2012/574
We propose a polynomial time quantum algorithm for solving the discrete logarithm problem in matrices over finite group rings. The hardness of this problem was recently employed in the design of a key-exchange protocol proposed by D. Kahrobaei, C. Koupparis, and V. Shpilrain. Our result implies that the Kahrobaei et al. protocol does not belong to the realm of post-quantum cryptography.
_ arXiv:math 10月18日分まで、IACR ePrint 2012/605まで確認済み
_ 気になった論文１：On trivial words in finitely presented groups
, M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, http://jp.arxiv.org/abs/1210.3425
We propose a numerical method for studying the cogrowth of finitely presented groups. To validate our numerical results we compare them against the corresponding data from groups whose cogrowth series are known exactly. Further, we add to the set of such groups by finding the cogrowth series for Baumslag-Solitar groups $BS(N,N) = \langle a,b | a^N b = b a^N \rangle$ and prove that their cogrowths are algebraic numbers. We have been unable to find the cogrowth series for other Baumslag-Solitar groups, but we have found recurrences that yield the first few terms of the cogrowth series exponentially faster than is possible by naive methods. Finally we apply our numerical method to several presentations of Thompson's group $F$ and our results give strong indication that the group is not amenable.
_ 気になった論文２：Group structures of elliptic curves over finite fields
, Vorrapan Chandee, Chantal David, Dimitris Koukoulopoulos, Ethan Smith, http://jp.arxiv.org/abs/1210.3880
It is well-known that if $E$ is an elliptic curve over the finite field $\F_p$, then $E(\F_p)\simeq\Z/m\Z\times\Z/mk\Z$ for some positive integers $m, k$. Let $S(M,K)$ denote the set of pairs $(m,k)$ with $m\le M$ and $k\le K$ such that there exists an elliptic curve over some prime finite field whose group of points is isomorphic to $\Z/m\Z\times\Z/mk\Z$. Banks, Pappalardi and Shparlinski recently conjectured that if $K\le (\log M)^{2-\epsilon}$, then a density zero proportion of the groups in question actually arise as the group of points on some elliptic curve over some prime finite field. On the other hand, if $K\ge (\log M)^{2+\epsilon}$, they conjectured that a density one proportion of the groups in question arise as the group of points on some elliptic curve over some prime finite field. We prove that the first part of their conjecture holds in the full range $K\le (\log M)^{2-\epsilon}$, and we prove that the second part of their conjecture holds in the limited range $K\ge M^{4+\epsilon}$. In the wider range $K\ge M^2$, we show that a positive density of the groups in question actually occur.
_ 気になった論文３：On conjugacy separability of some Coxeter groups and parabolic-preserving automorphisms
, Pierre-Emmanuel Caprace, Ashot Minasyan, http://jp.arxiv.org/abs/1210.4328
We prove that even Coxeter groups, whose Coxeter diagrams contain no (4,4,2) triangles, are conjugacy separable. In particular, this applies to all right-angled Coxeter groups or word hyperbolic even Coxeter groups. For an arbitrary Coxeter group W, we also study the relationship between Coxeter generating sets that give rise to the same collection of parabolic subgroups. As an application we show that if an automorphism of W preserves the conjugacy class of every sufficiently short element then it is inner. We then derive consequences for the outer automorphism groups of Coxeter groups.
_ 気になった論文４：Randomness, pseudorandomness and models of arithmetic
, Pavel Pudlak, http://jp.arxiv.org/abs/1210.4692
Pseudorandmness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To this end we construct a set of models $\cal M$, a common element $\iota$ of these models and a probability distribution on $\cal M$, such that for every pseudorandom sequence $s$, the probability that $s(\iota)=1$ holds true in a random model from $\cal M$ is equal to 1/2.
_ arXiv:math 10月18日分まで、IACR ePrint 2012/610まで確認済み
_ 気になった論文１：Graph-Theoretic Algorithms for the ``Isomorphism of Polynomials'' Problem
, Charles Bouillaguet and Pierre-Alain Fouque and Amandine Véber, http://eprint.iacr.org/2012/607
We give three new algorithms to solve the ``isomorphism of polynomial'' problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$ (heuristically), where $q^n$ is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis.
_ 気になった論文２：A New Approach to Discrete Logarithm Problem with Auxiliary Inputs
, Taechan Kim and Jung Hee Cheon, http://eprint.iacr.org/2012/609
Embedding an element of a finite field into auxiliary groups such as elliptic curve groups or extension fields of finite fields has been useful tool for analysis of cryptographic problems such as establishing the equivalence between the discrete logarithm problem and Diffie-Hellman problem or solving the discrete logarithm problem with auxiliary inputs (DLPwAI). Actually, Cheon's algorithm solving the DLPwAI can be regarded as a quantitative version of den Boer and Maurer. Recently, Kim showed in his dissertation that the generalization of Cheon's algorithm using embedding technique including Satoh's \cite{Sat09} is no faster than Pollard's rho algorithm when $d\nmid (p\pm 1)$.
In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials.
More precisely, with a polynomial $f(x)$ of degree $d$ over $\mathbf{F}_p$, the proposed algorithm shows the complexity $O\left(\sqrt{p^2/R}\log^2d\log p\right)$ group operations to recover $\alpha$ with $g, g^{\alpha}, \dots, g^{\alpha^{d}}$, where $R$ denotes the number of pairs $(x, y)\in\mathbf{F}_p\times \mathbf{F}_p$ such that $f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal $\alpha$ in $O(p^{1/3}\log^2{d}\log{p})$ group operations when $d|(p+1)$. Note that Cheon's algorithm requires $g, g^{\alpha}, \dots, g^{\alpha^{d}}, \dots, g^{\alpha^{2d}}$ as an instance for the same problem.
_ 気になった論文３：Candidate Multilinear Maps from Ideal Lattices and Applications
, Sanjam Garg and Craig Gentry and Shai Halevi, http://eprint.iacr.org/2012/610
We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show that some applications of such multi-linear maps can be realized using our approximations. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.
_ 昨日の某ナイトセッション、延べ４回も登壇したせいで喉が枯れ気味である。質より量。
_ ↑シンポジウム５回目の登壇（というかこれが本番）も無事終了。２分だの５分だので喋った翌日だと20分が長く感じるという亀仙人の甲羅メソッド。
最近のツッコミ↓