MarriageTheoremのこと

_ 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.