Patent Document ID: 8452975
Application ID: 12921507
Patent Status: 1

Claim One:
1. A method, used in a signature generation device and a signature verification device, for generating and verifying a signature for target data having one of a shortest vector problem and an approximate shortest vector problem as a basis for security, in which a vector is a multi-dimensional representation of data divided into a plurality of pieces, the method comprising the steps of: acquiring, using the signature generation device, the target data; converting, using the signature generation device, the target data using a private disturbance vector smaller than a first size to generate a converted vector; generating, using the signature generation device, a signature vector for the converted vector by seeking, in a lattice whose basis vectors are determined by private key vectors, a lattice point closest to the converted vector and selecting a part of the signature vector as signature data; recovering, using the signature verification device, the signature vector with public key vectors and the signature data, thus yielding a recovered signature vector, and verifying, using the signature verification device, whether a distance between a vector representing the target data and the recovered signature vector is equal to or less than a second size that is larger than the first size; and outputting, using the signature verification device, information indicating that verification is successful when the distance is equal to or less than the second size, wherein the first size is a size of a vector, and the second size is a size of a different vector, wherein each vector is represented as a polynomial, wherein the signature generation device stores a disturbance vector distribution table that includes, in correspondence, an upper limit on a coefficient, a lower limit on the coefficient, and a model polynomial serving as a basis for generating of the disturbance vector, and wherein the converting step randomly selects the coefficient between the upper limit and the lower limit, inclusive, multiplies the model polynomial by the selected coefficient, and treats the result as a polynomial representing the disturbance vector.