System for determining whether character string has been accepted by automaton

A client for inputting a string, the client being able to communicate with a server having an automaton defining a subsequent state of transition from a current state for each character in the string, wherein each character in the string is associated with an index representing a position of that character in the string, the client comprising:

• a receiving unit that performs operations comprising communicating with the server and receiving from the server, for each index, a plurality of key chains corresponding to a character in the string;
• and
• a decrypting unit that performs operations comprising decrypting a key corresponding to an index by performing decryption processing on a plurality of received key chains for that index using a key obtained by decryption processing of key chains corresponding to a previous index in a sequential order of the indices.

An information processing method performed by a server connectable to a client, the server having an automaton defining a subsequent state of transition from a current state for each character in the string, wherein each character in the string is associated with an index representing a position of that character in the string, the method comprising:

• generating a key chain for each combination of index, character and state, each key chain having an encrypted key comprising a key corresponding to a subsequent state of transition for a character in the string in a subsequent index, which is encrypted using a key corresponding to a current state for the character in the string and a current index;
• and
• providing to the client a key chain corresponding to each character in the string among a set of key chains for each index, wherein key chains corresponding to characters that are not in the string are concealed from the client.

An information processing method performed by a client connectable to a server, the server having an automaton defining a subsequent state of transition from a current state for each character in the string, wherein each character in the string is associated with an index representing a position of that character in the string, the method comprising:

• receiving, from the server, for each index, a plurality of key chains corresponding to an character in the string;
• and
• decrypting a key corresponding to an index by performing decryption processing on a plurality of received key chains for that index using a key obtained by decryption processing of key chains corresponding to a previous index in a sequential order of the indices.