MarriageTheoremのこと

_ arXiv:math 10月18日分まで、IACR ePrint 2012/610まで確認済み

_ 気になった論文１：Graph-Theoretic Algorithms for the ``Isomorphism of Polynomials'' Problem, Charles Bouillaguet and Pierre-Alain Fouque and Amandine Véber, http://eprint.iacr.org/2012/607

We give three new algorithms to solve the ``isomorphism of polynomial'' problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$ (heuristically), where $q^n$ is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis.

_ 気になった論文２：A New Approach to Discrete Logarithm Problem with Auxiliary Inputs, Taechan Kim and Jung Hee Cheon, http://eprint.iacr.org/2012/609

Embedding an element of a finite field into auxiliary groups such as elliptic curve groups or extension fields of finite fields has been useful tool for analysis of cryptographic problems such as establishing the equivalence between the discrete logarithm problem and Diffie-Hellman problem or solving the discrete logarithm problem with auxiliary inputs (DLPwAI). Actually, Cheon's algorithm solving the DLPwAI can be regarded as a quantitative version of den Boer and Maurer. Recently, Kim showed in his dissertation that the generalization of Cheon's algorithm using embedding technique including Satoh's \cite{Sat09} is no faster than Pollard's rho algorithm when $d\nmid (p\pm 1)$.

In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials.

More precisely, with a polynomial $f(x)$ of degree $d$ over $\mathbf{F}_p$, the proposed algorithm shows the complexity $O\left(\sqrt{p^2/R}\log^2d\log p\right)$ group operations to recover $\alpha$ with $g, g^{\alpha}, \dots, g^{\alpha^{d}}$, where $R$ denotes the number of pairs $(x, y)\in\mathbf{F}_p\times \mathbf{F}_p$ such that $f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal $\alpha$ in $O(p^{1/3}\log^2{d}\log{p})$ group operations when $d|(p+1)$. Note that Cheon's algorithm requires $g, g^{\alpha}, \dots, g^{\alpha^{d}}, \dots, g^{\alpha^{2d}}$ as an instance for the same problem.

_ 気になった論文３：Candidate Multilinear Maps from Ideal Lattices and Applications, Sanjam Garg and Craig Gentry and Shai Halevi, http://eprint.iacr.org/2012/610

We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show that some applications of such multi-linear maps can be realized using our approximations. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.