To provide a public key encryption method that does not depend on the difficulty of prime factor factorization or the difficulty in obtaining the solution of a discrete logarithm problem.
A prime number P is determined, and a plaintext is defined as X=(x1, x2, ..., xm)T on a finite field Fp. Nonsingular matrixes A, B and a matrix Q are prepared, and the i-th column of Q is seen from the bottom. The row containing an element that is not 0 for the first time is designated as an ri row. X is multiplied by A from the left to obtain V'=AX. V' is multiplied by Q from the left to obtain V=QV'. Constant matrixes C, U, a polynomial, and a diagonal matrix T(V) are prepared, and T(V) is multiplied by U from the left to obtain S(V)=UT(V). A matrix N(V), in which two or more polynomials in v gk(V) are contained in each of the one or more columns and all the other elements are 0, is added to S(V) to obtain F(V). F(V) is multiplied by C from the left to obtain D(V)=CF(V). At this time, D(V) does not contain gk(V) and is an upper triangular matrix when only the ri-th row is concerned. Then, G(X)=BF(V)VmodP is prepared, and a ciphertext Y=(y1, y2, ..., yn)T is obtained by Y=G(X)modP.
KITAZAWA ATSUSHI
TSUJII SHIGEO
FUJITA AKIRA
TSUJII SHIGEO
Next Patent: IMAGE FORMING APPARATUS, EXCHANGE UNIT, AND DEVELOPING DEVICE