A cryptographic system comprising: a key generation apparatus to generate a signature key including a subset of respective bases B 0 *,..., B N * of dual pairing spaces (N being an integer not less than two), using the bases B 0 *,..., B N * where the bases after the B 2 * are generated by using N - 1 transformation matrices W 1,..., W N - 1; a signature generation apparatus to generate a first signature for a message including N characters, using the signature key, the signature generation apparatus generating a set of elements σ 1,..., σ N being elements of the dual pairing vector spaces and including each character contained in the message, using the subset of the respective bases B 0 *,..., B N * included in the signature key and the message, and generating the first signature including the set of the elements σ 1,..., σ N generated; and a homomorphic operation apparatus to generate a second signature for an altered message where two characters at different positions in the message are interchanged, using the first signature and a homomorphic key different from the signature key, the homomorphic operation apparatus obtaining a parameter and generating the second signature for the altered message where a jth (j being an integer not less than one and not more than N - 1) character and a j + 1 character in the message are interchanged, using the parameter, the first signature, and the homomorphic key, the jth being a value of the parameter, wherein the key generation apparatus generates the homomorphic key including the transformation matrices W 1,..., W N - 1 and the subset of the respective bases B 0 *,..., B N *, and wherein using, among the transformation matrices W 1,..., W N - 1 included in the homomorphic key, the jth transformation matrix W j where the jth is the value of the parameter, the homomorphic operation apparatus interchanges the jth σ j and the j + 1th σ j + 1 in the set of the elements σ 1,..., σ N included in the first signature wherein the jth is the value of the parameter, thereby generating an interchanged signature where the σ j and the σ j + 1 are interchanged, and generates the second signature, using the interchanged signature. a key generation apparatus to generate a signature key including a subset of respective bases B 0 *,..., B N * of dual pairing spaces (N being an integer not less than two), using the bases B 0 *,..., B N * where the bases after the B 2 * are generated by using N - 1 transformation matrices W 1,..., W N - 1; a signature generation apparatus to generate a first signature for a message including N characters, using the signature key, the signature generation apparatus generating a set of elements σ 1,..., σ N being elements of the dual pairing vector spaces and including each character contained in the message, using the subset of the respective bases B 0 *,..., B N * included in the signature key and the message, and generating the first signature including the set of the elements σ 1,..., σ N generated; and a homomorphic operation apparatus to generate a second signature for an altered message where two characters at different positions in the message are interchanged, using the first signature and a homomorphic key different from the signature key, the homomorphic operation apparatus obtaining a parameter and generating the second signature for the altered message where a jth (j being an integer not less than one and not more than N - 1) character and a j + 1 character in the message are interchanged, using the parameter, the first signature, and the homomorphic key, the jth being a value of the parameter, wherein the key generation apparatus generates the homomorphic key including the transformation matrices W 1,..., W N - 1 and the subset of the respective bases B 0 *,..., B N *, and wherein using, among the transformation matrices W 1,..., W N - 1 included in the homomorphic key, the jth transformation matrix W j where the jth is the value of the parameter, the homomorphic operation apparatus interchanges the jth σ j and the j + 1th σ j + 1 in the set of the elements σ 1,..., σ N included in the first signature wherein the jth is the value of the parameter, thereby generating an interchanged signature where the σ j and the σ j + 1 are interchanged, and generates the second signature, using the interchanged signature.