MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 2月22日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/189まで

_ 気になった論文：Zero Knowledge with Rubik's Cubes（Emmanuel VOLTE and Jacques PATARIN and Valérie NACHEF, IACR ePrint 2012/174）

Since the invention of the Rubik's cube by Ern\"o~Rubik in $1974$, similar puzzles have been produced, with various number of faces or stickers. We can use these toys to define several problems in computer science, such as go from one state of the puzzle to another one. In this paper, we will classify some of these problems based on the classic Rubik's cube or on generalized Rubik's Cube. And we will see how we can use them in Zero Knowledge Authentication with a public key in order to achieve a given complexity against the best known attacks (for example $2^{80}$ computations). The efficiency of these schemes, and their possible connection with NP-complete problems will also be discussed.

_ 気になった論文その２：Discrete logarithm computations over finite fields using Reed-Solomon codes（Daniel Augot (LIX, INRIA Saclay - Ile de France), François Morain (LIX), arXiv:1202.4361v1）

Cheng and Wan have related the decoding of Reed-Solomon codes to the computation of discrete logarithms over finite fields, with the aim of proving the hardness of their decoding. In this work, we experiment with solving the discrete logarithm over GF(q^h) using Reed-Solomon decoding. For fixed h and q going to infinity, we introduce an algorithm (RSDL) needing O (h! q^2) operations over GF(q), operating on a q x q matrix with (h+2) q non-zero coefficients. We give faster variants including an incremental version and another one that uses auxiliary finite fields that need not be subfields of GF(q^h); this variant is very practical for moderate values of q and h. We include some numerical results of our first implementations.