Patent ID: 9621533
Date: 2017-04-11
CPC Classifications: G06F,H04L

Claim:
1. A bit string collation system comprising: a memory: at least one processor configured to implement: a first bit string position permutation unit that receives a first bit string as an input and performs position permutation of the first bit string; a template generation unit that is communicatively connected with the first bit string position permutation unit to receive, from the first bit string permutation unit, a bit string resulting from the position permutation of the first bit string, the template generation unit configured to: perform an exclusive OR operation of the received bit string resulting from the position permutation of the first bit string by the first bit string position permutation unit and a code word of a binary linear code, generate auxiliary data for use in verifying that a Hamming distance between bit strings resulting from position permutation operations is not more than a predetermined value, and store a result of the exclusive OR operation and the auxiliary data as a template in the memory; a second bit string position permutation unit that receives a second bit string as an input and performs same position permutation of the second bit string as the position permutation by the first bit string position permutation unit; a bit string inquiry unit that is communicatively connected with the second bit string position permutation unit to receive, from the second bit string permutation unit, a bit string resulting from the position permutation of the second bit string; and a bit string collation unit that is communicatively connected with the bit string inquiry unit and the memory, wherein the bit string collation unit is configured to: receive the bit string resulting from the position permutation of the second bit string by the second bit string position permutation unit from the bit string inquiry unit; receive the template stored in the memory; verify that a Hamming distance between the bit string resulting from the position permutation of the second bit string by the second bit string position permutation unit and the bit string used for generation of the template and resulting from the position permutation of the first bit string by the first bit string position permutation unit is not more than the predetermined value, based on the bit string resulting from the position permutation of the second bit string by the second bit string position permutation unit and the result of the exclusive OR operation and the auxiliary data stored in the memory as the template; determine that the first bit string and the second bit string match when the Hamming distance is verified to be not more than the predetermined value; and output a collation result that indicates whether the first bit string matches the second bit string.