Breaking the Akiyama-Goto cryptosystem
Petar Ivanov, José Felipe Voloch · Contemporary mathematics - American Mathematical Society · 2009
Abstract. Akiyama and Goto have proposed a cryptosystem based on rational points on curves over function elds (stated in the equivalent form of sections of brations on surfaces). It is easy to construct a curve passing through a few given points, but nding the points, given only the curve, is hard. We show how to break their original cryptosystem by using algebraic points instead of rational points and discuss possibilities for changing their original system to create a secure one. 1. The cryptosystem of Akiyama and Goto In this section we present the cryptosystem described by Akiyama and Goto in [1]. Let p be a prime number, R = Fp[t] be the polynomial ring over the prime eld Fp and K = Fp(t) be the eld of rational functions over Fp. K is the eld of fractions of R. Pick a polynomial in two variables X(x, y) ∈ R[x, y], together with two points U = (ux, uy) ∈ R 2 and V = (vx, vy) ∈ R 2, such that X(U) = X(V) = 0. In other words, we take an algebraic curve over K together with 2 rational points on the curve. It is easy to nd two points and a curve passing through them and we will show how below. On the other hand, if the curve is given (in terms of the polynomial X(x, y)), it is a hard mathematical problem to nd rational points on it. This fact can be used to build the cryptosystem described in this section.