System for checking acceptance of string by automaton

A client connectable to a server having an automaton whose state transitions in accordance with received characters, receiving input of a string, and determining whether the automaton has transitioned to a final state on based on the string, the client comprising:

• a processing device for executing components;
• a sending component for sending to a server, in characters included in a string, a coding sequence whose elements corresponding to characters are values encrypting a non-unity using a first encryption scheme having homomorphism, and whose elements not corresponding to the characters are values encrypting a unity using a first encrypting scheme;
• and
• a receiving component for receiving from the server ciphertext encrypting exchange data using a corresponding previous state key, the exchange data generated, in response to receiving the coding sequence, to encrypt a subsequent state key corresponding to each of a plurality of previous states of the automaton based on the coding sequence using the first encryption scheme.

An information processing method for a server connectable to a client for input of a string, having an automaton whose state transitions in accordance with received characters, the server determining whether the automaton has transitioned to a final state based on string, the method comprising:

• receiving from the client, in characters included in the string, a coding sequence whose elements corresponding to the characters are values encrypting a non-unity using a first encryption scheme having homomorphism, and whose elements not corresponding to the characters are values encrypting a unity using the first encrypting scheme;
• generating, in response to receiving the coding sequence, exchange data encrypting a subsequent state key corresponding to each of a plurality of previous states of the automaton on the basis of the coding sequence using the first encryption scheme;
• encrypting the exchange data with the corresponding previous state key;
• and
• sending the encrypted exchange data to the client.

A program storage medium storing a program of instructions for causing the computer to execute the instructions to perform a method of:

• receiving from the client in characters included in the string a coding sequence whose elements corresponding to the characters are values encrypting a non-unity using a first encryption scheme having homomorphism, and whose elements not corresponding to the characters are values encrypting a unity using the first encrypting scheme;
• generating, in response to receiving the coding sequence, exchange data encrypting a subsequent state key corresponding to each of a plurality of previous states of the automaton based on the coding sequence using a first encryption scheme;
• encrypting exchange data with the corresponding previous state key;
• and
• sending the encrypted exchange data to the client.