Authenticating acceptance of a string using an automaton

摘要

Provided is a server connectable to a client for input of a string and that has an automaton defining a subsequent state for transition for each state and each character. This server has a key chain generating unit for generating a key chain for each combination of index, character and state expressing the position of each character in a string, the key chain having encrypted keys for the next index corresponding to the subsequent state of transition from the current state in accordance with the character on the basis of the key corresponding to the current state, and a providing unit for communicating with a client and providing to the client a key chain corresponding to each inputted key among a set of key chains for each index in a state concealing the inputted characters from the client.

主权项

1. A server connectable to a client, the server comprising:
an automaton defining a subsequent state of transition from a current state for each character in a string, wherein each character in the string is associated with an index representing a position of that character in the string; a key generating unit that performs operations comprising generating, for each index, a key corresponding to each of a plurality of states included in the automaton; a key chain generating unit that performs operations 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 a providing unit that performs operations comprising communicating with the client 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.