[Claim 1] A cryptographic system comprising:
a signature generation apparatus to generate a first signature for a message including N (N being an integer not less than two) characters, using a signature key; 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. [Claim 2] The cryptographic system according to claim 1,
wherein the cryptographic system further comprises:
a key generation apparatus to generate the signature key including a subset of respective bases Bo*, ..., BN* of dual pairing vector spaces, using the bases Bo*, ..., BN* where the bases after the B2* are generated by using N - 1 transformation matrices Wi, ...,WN_i, and
wherein the signature generation apparatus generates a set of elements o"i, ..., ON being elements of the dual pairing vector spaces and including each character contained in the message, using the subset of the respective bases Bo*, ..., BN* included in the signature key and the message, and generates the first signature including the set of the elements c\, ..., ON generated. [Claim 3] The cryptographic system according to claim 2,
wherein the homomorphic operation apparatus obtains a parameter and generates 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.

[Claim 4] The cryptographic system according to claim 3,
wherein the key generation apparatus generates the homomorphic key including the transformation matrices Wi, ..., WN- I and the subset of the respective bases B0*, ..., BN*, and
wherein using, among the transformation matrices Wi, ..., WN- 1 included in the homomorphic key, the jth transformation matrix Wj where the jth is the value of the parameter, the homomorphic operation apparatus interchanges the jth Oj and the j + 1th Oj +1 in the set of the elements oi, ..., GN included in the first signature wherein the jth is the value of the parameter, thereby generating an interchanged signature where the Oj and the GJ +1 are interchanged, and generates the second signature, using the interchanged signature. [Claim 5] The cryptographic system according to claim 4,
wherein the homomorphic operation apparatus generates elements To, ..., IN from the dual pairing vector spaces, using the subset of the respective bases Bo*, ..., BN* included in the homomorphic key, and generates the second signature, using products between the interchanged signature and the elements To, ..., TN. [Claim 6] The cryptographic system according to any one of claims 2 to 5,
wherein the key generation apparatus further generates a verification key including the subset of the respective bases B0*, ..., BN* of the dual pairing vector spaces, and
wherein the cryptographic system further comprises a signature verification apparatus to obtain the second signature as a verification signature and verify the verification signature, using the verification key. [Claim 7] The cryptographic system according to claim 6,
wherein the signature verification apparatus obtains the first signature as the

verification signature, and verifies the verification signature, using the verification key. [Claim 8] The cryptographic system according to claim 6 or 7,
wherein the signature verification apparatus generates elements Co, ..., CN of the dual pairing vector spaces, using the bases Bo, ..., BN included in the verification key, executes a pairing operation with respect to the elements Co, ..., CN and the verification signature, and verifies the verification signature, based on an operation result of the pairing operation. [Claim 9] A homomorphic signature method comprising:
by a signature generation apparatus, generating a first signature for a message including N (N being an integer not less than two) characters, using a signature key; and
by a homomorphic operation apparatus, generating 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 [Claim 10] A homomorphic signature program to cause a computer to execute:
a signature generation process of generating a first signature for a message including N (N being an integer not less than two) characters, using a signature key; and
a homomorphic operation process of generating 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.