MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 6月10日分まで、IACR ePrint 2012/531まで

_ 気になった論文１：A simplified and generalized treatment of DES related ciphers (Liljana Babinkostova, Alyssa M. Bowden, Andrew M. Kimball, Kameryn J. Williams, arXiv:1205.5613)

This work is a study of DES-like ciphers where the bitwise exclusive-or (XOR) operation in the underlying Feistel network is replaced by an arbitrary group operation. We construct a two round simplified version of DES that contains all the DES components and show that its set of encryption permutations is not a group under functional composition, it is not a pure cipher and its set of encryption permutations does not generate the alternating group. We present a non-computational proof that for n\leq6 the set of n-round Feistel permutations over an arbitrary group do not constitute a group under functional composition.

_ 気になった論文２：Optimal epsilon-biased sets with just a little randomness (Cristopher Moore, Alexander Russell, arXiv:1205.6218)

Subsets of F_2^n that are eps-biased, meaning that the parity of any set of bits is even or odd with probability eps close to 1/2, are useful tools in derandomization. A simple randomized construction shows that such sets exist of size O(n/eps^2), and known deterministic constructions achieve sets of size O(n/eps^3), O(n^2/eps^2), and O((n/eps^2)^{5/4}). Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size O(n/eps^2) with as few random bits as possible. The naive randomized construction requires O(n^2/eps^2) random bits. We show that this can be reduced to O(n log (n/eps)) random bits. Our construction uses the Legendre symbol and Weil sums, but in a different way than the construction of Alon, Goldreich, Haastad, and Peralta.

_ 気になった論文３：The Discrete Logarithm Problem in Bergman's non-representable ring (Matan Banin, Boaz Tsaban, arXiv:1206.1077)

Bergman's Ring $E_p$, parameterized by a prime number $p$, is a ring with $p^5$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_p$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems.

We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in $E_p$ to the classical Discrete Logarithm Problem in $\Zp$, the $p$-element field. In particular, the Discrete Logarithm Problem in $E_p$ can be solved, by conventional computers, in sub-exponential time.