2012-08-21
（8/27記：夏休みその２。妻の猫レーダーが偶然にも猫カフェを捉えたので初めての猫カフェ体験をしてきた。個人的にツボだったのは本棚のラインナップ。ドラゴンボールやドクタースランプを置かずにこれを置くあたりに猫カフェとしての矜恃が感じられて心が躍った。）
[ツッコミを入れる]
_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/419まで
_ 集中講義四日目。今日の午前中はHamiltonグラフに関するゼロ知識証明プロトコル、午後はFiat-Naorの放送暗号とDiffie-Hellman鍵交換とElGamal暗号を題材に話をした。さすがに集中講義も四日目となると疲労が否めない（主に私の喉が）。
_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/421まで
_ 集中講義最終日。量子力学の知識を仮定しない状態から２時間でBB84プロトコルその他の量子情報理論のトピックを話す、という突貫作業を行った。振り返ってみると、今回の集中講義は全体的に無茶ぶりの多いテーマ選定だった気がするが、最後まで出席の学生さんがそれなりに残っていたのはありがたい話である。
_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/451まで
_ 気になった論文：Factorization of a 1061-bit number by the Special Number Field Sieve
（Greg Childers, IACR ePrint Archive 2012/444）
I provide the details of the factorization of the Mersenne number $2^{1061}-1$ by the Special Number Field Sieve. Although this factorization is easier than the completed factorization of RSA-768, it represents a new milestone for factorization using publicly available software.
千手越えか！（←単位が違います）
_ プレプリント確認状況：arXiv:math 2月27日分まで、IACR ePrint 2012/451まで
_ 気になった論文１：How to write a permutation as a product of involutions (and why you might care)
(T. Kyle Petersen, Bridget Eileen Tenner, arXiv:1202.5319)
It is well-known that any permutation can be written as a product of two involutions. We provide an explicit formula for the number of ways to do so, depending only on the cycle type of the permutation.In many cases, these numbers are sums of absolute values of irreducible characters of the symmetric group evaluated at the same permutation, although apart from the case where all cycles are the same size, we have no good explanation for why this should be so.
_ 気になった論文２：Nondeterministic graph property testing
(László Lovász, Katalin Vesztergombi, arXiv:1202.5337)
A property of finite graphs is called nondeterministically testable if it has a "certificate" such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or more unary and/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that nondeterministically testable properties are also deterministically testable.
_ プレプリント確認状況：arXiv:math 3月4日分まで、IACR ePrint 2012/451まで
_ 気になった論文１：Some Characterizations of a Normal Subgroup of a Group
(Vipul Kakkar, R. P. Shukla, arXiv:1202.5626)
Let G be a group and H be a subgroup of G which is either finite or of finite index in G. In this note, we give some characterizations for normality of H in G. As a consequence we get a very short and elementary proof of the Main Theorem of [5], which avoids the use of the classification of finite simple groups
_ 気になった論文２：Chordal Graphs are Fully Orientable
(Hsin-Hao Lai, Ko-Wei Lih, arXiv:1202.5718)
Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.
_ 気になった論文３：Automorphisms of geometric structures associated to Coxeter groups
(Graham White, arXiv:1202.6441)
In this paper, we consider the automorphism groups of the Cayley graph with respect to the Coxeter generators and the Davis complex of an arbitrary Coxeter group. We determine for which Coxeter groups these automorphism groups are discrete. In the case where they are discrete, we express them as semidirect products of two obvious families of automorphisms. This extends a result of Haglund and Paulin.
_ プレプリント確認状況：arXiv:math 3月6日分まで、IACR ePrint 2012/463まで
_ 気になった論文１：An Undecidable Nested Recurrence Relation
(Marcel Celaya, Frank Ruskey, arXiv:1203.0586)
Roughly speaking, a recurrence relation is nested if it contains a subexpression of the form ... A(...A(...)...). Many nested recurrence relations occur in the literature, and determining their behavior seems to be quite difficult and highly dependent on their initial conditions. A nested recurrence relation A(n) is said to be undecidable if the following problem is undecidable: given a finite set of initial conditions for A(n), is the recurrence relation calculable? Here calculable means that for every n >= 0, either A(n) is an initial condition or the calculation of A(n) involves only invocations of A on arguments in {0,1,...,n-1}. We show that the recurrence relation A(n) = A(n-4-A(A(n-4)))+4A(A(n-4)) +A(2A(n-4-A(n-2))+A(n-2)). is undecidable by showing how it can be used, together with carefully chosen initial conditions, to simulate Post 2-tag systems, a known Turing complete problem.
_ 気になった論文２：Computing small discrete logarithms faster
(Daniel J. Bernstein and Tanja Lange, IACR ePrint Archive 2012/458)
Computations of small discrete logarithms are feasible even in "secure" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh--Goh--Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.21*l^{2/3} multiplications, and computing a discrete logarithm in a group of order l takes only 1.77*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.24*l^{2/3} multiplications.
_ プレプリント確認状況：arXiv:math 3月12日分まで、IACR ePrint 2012/463まで
_ 気になった論文：Stirling's approximation for central polynomial coefficients
(Steffen Eger, arXiv:1203.2122)
We derive asymptotic formulae for central polynomial coefficients, a generalization of binomial coefficients, using the distribution of the sum of independent uniform random variables and the CLT.
_ プレプリント確認状況：arXiv:math 3月12日分まで、IACR ePrint 2012/475まで
_ 気になった論文１：T-MATCH: Privacy-Preserving Item Matching for Storage-Only RFID Tags
(Kaoutar Elkhiyaoui and Erik-Oliver Blass and Refik Molva, IACR ePrint 2012/465)
RFID-based tag matching allows a reader Rk to determine whether two tags Ti and Tj store some attributes that jointly fulfill a boolean constraint. The challenge in designing a matching mechanism is tag privacy. While cheap tags are unable to perform any computation, matching has to be achieved without revealing the tags’ attributes. In this paper, we present T-MATCH, a protocol for secure and privacy preserving RFID tag matching. T-MATCH involves a pair of tags Ti and Tj , a reader Rk, and a backend server S. To ensure tag privacy against Rk and S, T-MATCH employs a new technique based on secure two-party computation that prevents Rk and S from disclosing tag attributes. For tag privacy against eavesdroppers, each tag Ti in T-MATCH stores an IND-CPA encryption of its attribute. Such an encryption allows Rk to update the state of Ti by merely re-encrypting Ti’s ciphertext. T-MATCH targets cheap tags that cannot perform any computation, but are only required to store 150 bytes.
Computational Entropy and Information Leakage(Benjamin Fuller and Leonid Reyzin, IACR ePrint 2012/466)
We investigate how information leakage reduces computational entropy of a random variable X. Recall that HILL and metric computational entropy are parameterized by quality (how distinguishable is X from a variable Z that has true entropy) and quantity (how much true entropy is there in Z).
We prove an intuitively natural result: conditioning on an event of probability p reduces the quality of metric entropy by a factor of p and the quantity of metric entropy by log 1/p note that this means that the reduction in quantity and quality is the same, because the quantity of entropy is measured on logarithmic scale). Our result improves previous bounds of Dziembowski and Pietrzak (FOCS 2008), where the loss in the \emph{quantity} of entropy was related to its original quality. The use of metric entropy simplifies the analogous the result of Reingold et. al. (FOCS 2008) for HILL entropy.
Further, we simplify dealing with information leakage by investigating conditional metric entropy. We show that, conditioned on leakage of \lambda bits, metric entropy gets reduced by a factor 2^\lambda in quality and \lambda in quantity.
_ 気になった論文３：A Quasigroup Based Random Number Generator for Resource Constrained Environments
(Matthew Battey and Abhishek Parakh, IACR ePrint 2012/471)
This paper proposes a pseudo random number generator (PRNG) based on quasigroups. The proposed PRNG has low memory requirements, is autonomous and the quality of the output stream of random numbers is better than other available standard PRNG implementations (commercial and open source) in majority of the tests. Comparisons are done using the benchmark NIST Statistical Test Suite and compression tools. Results are presented for quality of raw stream of random numbers and for encryption results using these random numbers.
_ 「数学女子」のスピンオフ作品として、作中に登場する女性教授の渡教授を主役とした「数学女史」という作品を妄想した。自分に絵心があったら本当に描いてしまいかねないので絵心がなくてよかったなぁと思った次第である。
_ （8/27記：私は夏休み中なので欠席したのだが、この日は共同研究相手の某氏がその研究の関係で某所に打ち合わせに行って下さっていた。そしたらなんと、打ち合わせ相手の方が将棋好き、もっと言えば詰キストだったらしく、私のことを専門誌（十中八九詰パラのことだろう）でよく見掛けたと仰っていたらしい。その方のお名前を伺ってみると、確かに私も見覚えのあるお名前であった。なんとまぁ世間の狭いことよ。というわけで、今のところ次の打ち合わせの予定がないにもかかわらず次は私も同席するという約束にいつの間にかなってしまったので、何とかしてその方と打ち合わせする用事をひねり出さなければならないかもしれない（笑）。）
_ （8/27記：夏休みなので自宅で論文書きに勤しんでいた。泊りがけの出張の翌日に投稿〆切という困ったスケジュールなので、早めに目途をつけておかなければならない。）
_ プレプリント確認状況：arXiv:math 3月12日分まで、IACR ePrint 2012/489まで
_ 気になった論文：Short communication: An interpretation of the Linux entropy estimator
(Benjamin Pousse, IACR ePrint 2012/487)
The Linux random number generator (LRNG) aims to produce random numbers with all the limitations due to a deterministic machine. Two recent analysis exist for this generator. These analysis provide strong cryptographic details about LRNG. However both fail to give a mathematical explanation of the entropy estimator embedded. In this paper we propose an interpretation using Newton polynomial interpolation.
_ とある用事に使う書類を受け取るのを忘れていたところ、今日からその用事当日まで職場へ行く間がないことにさっき気が付いて焦った。メールで送ってもらえる書類だったから事なきを得たものの…
_ 会場の方々によれば、私は今「組合世論サマースクール」に参加していることになっているらしい。それはそれで何となく意味が通ってしまうのがまた困りものである。
最近のツッコミ↓