_ arXiv:math 11月1日分まで、IACR ePrint 2012/678まで確認済み
_ 気になった論文１：A Necessary Solution Condition for Sudoku
, Thomas Fischer, http://jp.arxiv.org/abs/1210.6343
We develop a new discrete mathematical model which includes the classical Sudoku puzzle, Latin Squares and gerechte designs. This problem is described by integer equations and a special type of inequality constraint. We consider solutions of this generalized problem and derive a necessary condition on these solutions. The results are illustrated with examples.
_ 気になった論文２：An Inequality for the Sum of Independent Bounded Random Variables
, Christopher R. Dance, http://jp.arxiv.org/abs/1210.6484
We give a simple inequality for the sum of independent bounded random variables. This inequality improves on the celebrated result of Hoeffding in a special case. It is optimal in the limit where the sum tends to a Poisson random variable.
_ 気になった論文３：Coxeter Cochain Complexes
, Michael Larsen, Ayelet Lindenstrauss, http://jp.arxiv.org/abs/1210.7254
We define the Coxeter cochain complex of a Coxeter group (G,S) with coefficients in a Z[G]-module A. This is closely related to the complex of simplicial cochains on the abstract simplicial complex I(S) of the commuting subsets of S. We give some representative computations of Coxeter cohomology and explain the connection between the Coxeter cohomology for groups of type A, the (singular) homology of certain configuration spaces, and the (Tor) homology of certain local Artin rings.
_ 気になった論文４：Polynomial time cryptanalysis of noncommutative-algebraic key exchange protocols
, Boaz Tsaban, http://jp.arxiv.org/abs/1210.8114
We introduce the \emph{linear centralizer method} for a passive adversary to extract the shared key in group-theory based key exchange protocols (KEPs). We apply this method to obtain a polynomial time cryptanalysis of the \emph{Commutator KEP}, introduced by Anshel--Anshel--Goldfeld in 1999 and considered extensively ever since. We also apply this method to the \emph{Centralizer KEP}, introduced by Shpilrain--Ushakov in 2006.
Our method is proved to be of polynomial time using a technical lemma about sampling invertible matrices from a linear space of matrices.
_ 気になった論文５：Non-associative public-key cryptography
, Arkadius Kalka, http://jp.arxiv.org/abs/1210.8270
We introduce a generalized Anshel-Anshel-Goldfeld (AAG) key establishment protocol (KEP) for magmas. This leads to the foundation of non-associative public-key cryptography (PKC), generalizing the concept of non-commutative PKC. We show that left selfdistributive systems appear in a natural special case of a generalized AAG-KEP for magmas, and we propose, among others instances, concrete realizations using $f$-conjugacy in groups and shifted conjugacy in braid groups. We discuss the advantages of our schemes compared with the classical AAG-KEP based on conjugacy in braid groups.
_ arXiv:math 11月4日分まで、IACR ePrint 2012/678まで確認済み
_ 気になった論文１：The homeomorphism problem for closed 3-manifolds
, Peter Scott, Hamish Short, http://jp.arxiv.org/abs/1211.0264
We give a more geometric approach to an algorithm for deciding whether two hyperbolic 3-manifolds are homeomorphic. We also give a more algebraic approach to the homeomorphism problem for geometric, but non-hyperbolic, 3-manifolds.
_ 気になった論文２：On mutually unbiased bases: Passing from d to d**2
, Maurice Robert Kibler, http://jp.arxiv.org/abs/1210.8173
We show how to transform the problem of finding d+1 mutually unbiased bases in the d-dimensional Hilbert space into the one of finding d(d+1) vectors in the N-dimensional Hilbert space with N=d**2. The transformation formulas admit a solution when d is a prime number.
_ （12/10記：この日はミーティング中に大きな地震があって（ミーティング室のあたりは震度４ぐらいだったらしい）さすがにミーティングが少し中断したのだが、揺れのピークは過ぎたとはいえまだかなり揺れが残っている時点で平然と「で、さっきの話ですけど」みたいなノリで議論を再開しようとした某氏は素晴らしいと思った。）
_ 今日は筑波大学のリスク工学研究会という催しで、暗号と数学の関わりをテーマに１時間ほど話してきた。学生さんの反応はよくわからなかった（←追記：某氏によれば学生さんにも面白がってもらえたらしい。よかったよかった）のだけど、先生方や司会進行の某871氏にはそれなりに面白がってもらえた（色々な意味で）みたいなのでその点はよかったなぁと思っている。ただ、喉の具合を鑑みて途中で水分補給しながら喋るつもりが、熱が入りすぎてぶっ通しで喋り続けてしまったので、明日喉が無事であることを切に願う。
_ 何の話かは書かないが、書面で強い表現を使いつつ口頭で「あまり固く受け取らないように」と言うぐらいなら、書面の段階でもっと緩い表現に改めてほしいものである。検証可能な形で後に残るのは書面だけなのだから。
_ arXiv:math 11月6日分まで、IACR ePrint 2012/687まで確認済み
_ 気になった論文：The k-BDH Assumption Family: Bilinear Map Cryptography from Progressively Weaker Assumptions
, Karyn Benson and Hovav Shacham and Brent Waters, http://eprint.iacr.org/2012/687
Over the past decade bilinear maps have been used to build a large variety of cryptosystems. In addition to new functionality, we have concurrently seen the emergence of many strong assumptions. In this work, we explore how to build bilinear map cryptosystems under progressively weaker assumptions. We propose $k$-BDH, a new family of progressively weaker assumptions that generalizes the decisional bilinear Diffie-Hellman (DBDH) assumption. We give evidence in the generic group model that each assumption in our family is strictly weaker than the assumptions before it. DBDH has been used for proving many schemes secure, notably identity-based and functional encryption schemes; we expect that our $k$-BDH will lead to generalizations of many such schemes. To illustrate the usefulness of our $k$-BDH family, we construct a family of selectively secure Identity-Based Encryption (IBE) systems based on it. Our system can be viewed as a generalization of the Boneh-Boyen IBE, however, the construction and proof require new ideas to fit the family. We then extend our methods to produces hierarchical IBEs and CCA security; and give a fully secure variant. In addition, we discuss the opportunities and challenges of building new systems under our weaker assumption family.
_ arXiv:math 11月8日分まで、IACR ePrint 2012/692まで確認済み
_ 気になった論文１：Cryptography Using CAPTCHA Puzzles
, Abishek Kumarasubramanian and Rafail Ostrovsky and Omkant Pandey and Akshay Wadia, http://eprint.iacr.org/2012/689
A \captcha is a puzzle that is easy for humans but hard to solve for computers. A formal framework, modelling \captcha puzzles (as hard AI problems), was introduced by Ahn, Blum, Hopper, and Langford (\cite{AhnBHL03}, Eurocrypt 2003). Despite their attractive features and wide adoption in practice, the use of \captcha puzzles for general cryptographic applications has been limited.
In this work, we explore various ways to formally model \captcha puzzles and their human component and explore new applications for \captcha. We show that by defining \captcha with additional (strong but realistic) properties, it is possible to broaden \captcha applicability, including using it to learning a machine's ``secret internal state.'' To facilitate this, we introduce the notion of an human-extractable \captcha, which we believe may be of independent interest. We show that this type of \captcha yields a \emph{constant round} protocol for \emph{fully} concurrent non-malleable zero-knowledge. To enable this we also define and construct a \captcha -based commitment scheme which admits ``straight line'' extraction.
We also explore \captcha definitions in the setting of Universal Composability (UC). We show that there are two (incomparable) ways to model \captcha within the UC framework that lead to different results. In particular, we show that in the so called \emph{indirect access model}, for every polynomial time functionality $\calf$ there exists a protocol that UC-realizes $\calf$ using human-extractable \captcha, while for the so-called \emph{direct access model}, UC is impossible, even with the help of human-extractable \captcha.
The security of our constructions using human-extractable \captcha is proven against the (standard) class of all polynomial time adversaries. In contrast, most previous works guarantee security only against a very limited class of adversaries, called the \emph{conservative} adversaries.
_ 気になった論文２：Integrated PKE and PEKS - Stronger Security Notions and New Constructions
, Yu Chen and Jiang Zhang and Zhenfeng Zhang and Dongdai Lin, http://eprint.iacr.org/2012/692
In this paper we investigate the security for integrated public-key encryption (PKE) and public-key encryption with keyword search (PEKS) schemes. We observe that the security notions for integrated PKE and PEKS schemes considered in the existing literature are not strong enough to capture practical attacks, thus define a new notion named joint CCA-security which is shown to be stronger than the previous ones. We also propose two simple and efficient constructions of jointly CCA-secure integrated PKE and PEKS schemes from anonymous (hierarchical) identity- based encryption schemes. Besides, we review the consistency for PEKS schemes and improve previous results.
_ arXiv:math 11月18日分まで、IACR ePrint 2012/692まで確認済み
_ 気になった論文１：On the subgroups of the group $\Z_m \times \Z_n$
, Mario Hampejs, Nicki Holighaus, László Tóth, Christoph Wiesmeyr, http://jp.arxiv.org/abs/1211.1797
We discuss properties of the subgroups of the group $\Z_m \times \Z_n$, where $m$ and $n$ are arbitrary positive integers. Simple formulae for the total number of subgroups and the number of subgroups of a given order are deduced. The cyclic subgroups and subgroups of a given exponent are also considered.
_ 気になった論文２：Copies of classical logic in intuitionistic logic
, Jaime Gaspar, http://jp.arxiv.org/abs/1211.1850
Classical logic (the logic of non-constructive mathematics) is stronger than intuitionistic logic (the logic of constructive mathematics). Despite this, there are copies of classical logic in intuitionistic logic. All copies usually found in the literature are the same. This raises the question: is the copy unique? We answer negatively by presenting three different copies.
_ 気になった論文３：C(6) groups do not contain F_2 X F_2
, Hadi Bigdely, Daniel T. Wise, http://jp.arxiv.org/abs/1211.1998
We show that a group with a presentation satisfying the C(6) small cancellation condition cannot contain a subgroup isomorphic to F_2 X F_2.
_ （12/14記：今回の衆議院議員選挙のために投票先を検討していたところ、小選挙区でも比例代表でも私と妻の意見が一致するという極めて珍しい現象が発生した。今回はよほどまともな選択肢が少ないらしい。）
_ （12/17記：今回の選挙は本当にろくでもない結果になったものだと落胆しているが、嘆いているだけでは仕方がないので、自分に何ができるかを考えて少しずつでも実行に移していこうと気合を入れ直した。）
_ インド出張、発表の後半戦が無事終了（5分ほど時間超過したのを「無事」と言っていいかはともかく）。話の内容はさておき、扇子遣いがあまり受けなかったのが反省材料である。
_ arXiv:math 11月18日分まで、IACR ePrint 2012/711まで確認済み
_ 気になった論文：Non Observability in the Random Oracle Model
, Prabhanjan Ananth and Raghav Bhaskar, http://eprint.iacr.org/2012/710
The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to heuristically argue about the security of cryptographic primitives and protocols. The basis of this heuristic is that secure hash functions are close enough to random functions in their behavior, and so, a primitive that is secure using a random function should continue to remain secure even when the random function is replaced by a real hash function. In the security proof, this setting is realized by modeling the hash function as a random oracle. However, this approach in particular also enables any reduction, reducing a hard problem to the existence of an adversary, to \emph{observe} the queries the adversary makes to its random oracle and to \emph{program} the responses that the oracle provides to these queries. While, the issue of programmability of query responses has received a lot of attention in the literature, to the best of our knowledge, observability of the adversary's queries has not been identified as an artificial artefact of the Random Oracle Model. In this work, we study the security of several popular schemes when the security reduction cannot ``observe'' the adversary's queries to the random oracle, but can (possibly) continue to ``program'' the query responses. We first show that RSA-PFDH and Schnorr's signatures continue to remain secure when the security reduction is non observing (NO reductions), which is not surprising as their proofs in the random oracle model rely on programmability. We also provide two example schemes, namely, Fischlin's NIZK-PoK \cite{Fischlin05} and non interactive extractable commitment scheme, extractor algorithms of which seem to rely on observability in the random oracle model. While we prove that Fischlin's online extractors cannot exist when they are non observing, our extractable commitment scheme continues to be secure even when the extractors are non observing. We also introduce Non Observing Non Programming reductions which we believe are closest to standard model reductions.
_ （12/29記：この日は「第４回暗号及び情報セキュリティと数学の相関ワークショップ」（CRISMATH 2012）の日だった。講演３件とも非常に濃い内容で、それに伴い質疑応答の時間にも濃い議論ができて充実した会になったと思う。講演者と参加者の皆様に深く感謝。）
_ （2013年1月1日記：大晦日ということで、夕食に蕎麦を食べた。蕎麦を茹でるのは久々だったけれども無事にできたので、終わり良ければすべて良し、ということで。）
最近のツッコミ↓