A signature apparatus for generating a signature text by using a commitment, wherein the commitment is a hash value of a set including a to-be-committed value, data including a pair of elements of a cyclic group associated with a discrete logarithm problem is used as a public key, and a discrete logarithm of an order of the pair is used as a secret key; the signature apparatus comprising: a) committed vector selecting means adapted to select a committed vector associated with a first commitment; b) first commitment calculating means adapted to calculate a first commitment; c) basis vector calculating means adapted to calculate a basis vector; d) second commitment calculating means adapted to calculate the power residue and generate a second commitment; e) vector challenge calculating means adapted to calculate a vector challenge; f) vector response calculating means adapted to calculate a vector response by using the first commitment, a set used for calculating the power residue, the vector challenge, and the basis vector; and g) a storage unit adapted to store the committed vector, the first commitment, the basis vector, the second commitment, the vector challenge, and the vector response, wherein the basis vector and the vector challenge are hash values; wherein the committed vector selecting means is adapted to select a plurality of the committed vectors, each having the same configuration as the committed vector, each component of the plurality of committed vectors and a secret key satisfy a relation equation with a group order as a modulus, and the set is data calculated by using a portion of data selected by the committed vector selecting means, the basis vector, and the vector challenge; wherein each component of the committed vectors and the secret key satisfy a linear equation with the group order as a modulus, an input of the first commitment is data including a random number, a portion of the data is determined by the vector challenge, and the set is represented by a linear equation of the portion of the data and the basis vector; wherein the committed vector includes two components, the one component being a value obtained by adding a secret key to the other component and obtaining a residue with a group order as a modulus, an input to the first commitment includes data for specifying each component of the committed vector, and the set is an inner product of the portion of the data and the basis vector; wherein assuming that security parameters are κ, N, and v, and an order of the cyclic group is q, the committed vector selecting means is adapted to select a residue group X_,..., X_ e (Z/qZ) at random and set values obtained by adding x to the residue group X_ for j = 1,...N and obtaining a residue with the order q as a modulus to X_, the committed vector for i = 0, 1 is Y_i = (X_,..., X_{iN}), the first commitment calculating means is adapted to select at random a bit column r of v bits. a hash value of data including the public key, X_{ij}, i, j, r for i = 0, 1 is set to a first commitment C_{ij}, the basis vector calculating means is adapted to set a hash value of data including the public key and the first commitment C_{ij} to the basis vector V = (u_1,..., u_N), the second commitment calculating means is adapted to calculate an inner product of the basis vector V and the Y_0 and calculate a second commitment G = g^, the vector challenge calculating means is adapted to calculate a hash value K = (c_1,..., c_N) of data including the public key, {C_{ij}}, G, r, and a message received by signature apparatus, the vector response calculating means is adapted to calculate the vector response ξ_{j} = X_{c_jj} for all j = 1,..., N and Ξ = (ξ_1,..., ξ_κ), and a signature text (r, {C_{ij}}, G, Ξ) is output. a) committed vector selecting means adapted to select a committed vector associated with a first commitment; b) first commitment calculating means adapted to calculate a first commitment; c) basis vector calculating means adapted to calculate a basis vector; d) second commitment calculating means adapted to calculate the power residue and generate a second commitment; e) vector challenge calculating means adapted to calculate a vector challenge; f) vector response calculating means adapted to calculate a vector response by using the first commitment, a set used for calculating the power residue, the vector challenge, and the basis vector; and g) a storage unit adapted to store the committed vector, the first commitment, the basis vector, the second commitment, the vector challenge, and the vector response,