MarriageTheoremのこと

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

_ IACR ePrintで気になった論文２編。まずはPublic Key Cryptosystems Constructed Based on Reed-Solomon Codes, K(XV)SE(2)PKC, Realizing Coding Rate of Exactly 1.0（Masao KASAHARA, 2012/079）

In this paper, we present a new class of public-key cryptosystems, K(XV)SE(2)PKC realizing the coding rate of exactly 1.0, based on Reed-Solomon codes(RS codes). We show that K(XV)SE(2)PKC is secure against the various attacks including the attacks based on the Gröbner basis calculaｔion (Gröbner basis attack, GB attack) and a linear transformation attack.

もう一つは、Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms（Joppe W. Bos and Alina Dudeanu and Dimitar Jetchev, 2012/087）

We prove collision bounds for the Pollard rho algorithm to solve the discrete logarithm problem in a general cyclic group $G$. Unlike the setting studied by Kim et al. we consider additive walks: the setting used in practice to solve the elliptic curve discrete logarithm problem. Our bounds differ from the birthday bound $O(\sqrt{|G|})$ by a factor of $\sqrt{\log{|G|}}$ and are based on mixing time estimates for random walks on finite abelian groups due to Hildebrand.