1. A method 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 the target data; converting the target data using a private disturbance vector smaller than a first size to generate a converted vector; generating 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 the signature vector with public key vectors and the signature data, thus yielding a recovered signature vector, and verifying 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 information indicating that verification is successful when the distance is equal to or less than the second size.