秘密数据匹配装置以及秘密数据匹配方法

摘要

本公开涉及秘密数据匹配装置和秘密数据匹配方法。根据本发明的秘密数据匹配装置登记通过如下方式获得的第一秘密向量，基于第一随机数和对于包括秘密数据匹配装置的每个系统不同的近似确定矩阵的行向量的第一线性组合来隐藏生物数据和密钥。秘密数据匹配装置获取通过如下方式获得的第二秘密向量，基于第二随机数和近似确定矩阵的行向量的第二线性组合来隐藏匹配数据。秘密数据匹配装置根据第一秘密向量与第二秘密向量之间的差使用近似确定矩阵作为模数来计算残差向量，并且基于残差向量来确定生物数据和匹配数据是否彼此近似。

说明书

技术领域

本文所讨论的实施方式涉及秘密数据匹配装置等。

背景技术

生物认证是一种使用人类物理特征和行为特征的个人认证技术。人类 物理特征的示例包括指纹、静脉、虹膜和DNA。行为特征的示例包括笔 迹等。在生物认证中，通过预先收集称作模板的生物信息并且当进行匹配 时将生物信息与由传感器获取的信息进行比较来进行认证。

近年来，关注一种其中将某种程度转换的模板存储在数据库中并且当 进行匹配时在不恢复原始模板的情况下进行比较的生物认证技术。生物认 证技术被称为“生物模板保护”。在使用生物模板保护的系统中，即使泄 露经转换的模板，但是通过改变转换方法，使泄露的模板是不可用的，使 得可以阻止泄露的模板被访问。

在生物模板保护中，要求多个安全要求。安全要求之一是多样性。多 样性是不能在多个数据库之间交叉匹配经转换的模板的特性。换句话说， 多样性意味着分别存储在多个数据库中的、相同生物信息的经转换的模板 不具有共性。

所谓的密钥绑定方法的模板保护方法已知为一种生物模板保护技术。 密钥绑定方法是其中将表示根据用户特有密钥生成的辅助信息和生物信 息的模板存储在数据库中并且当进行匹配时，在匹配的生物信息足够接近 模板的情况下提取用户特有密钥的方法。在密钥绑定方法中，可以在不将 表示生物信息的模板本身登记在数据库中的情况下进行匹配。

实现密钥绑定方法的方案的典型示例包括使用误差校正码的技术的 模糊承诺和模糊保险箱。已知的是，模糊承诺是使用量化的生物信息和随 机信息的异或(exclusive-OR)的方法。已知的是，模糊保险箱通过使用 预先作为密钥准备的一对信息来隐藏可选的秘密信息。已知的是，在利用 模糊承诺或模糊保险箱的密钥绑定方法中，根据相同生物信息的模板和用 户特有密钥生成的辅助信息包括公用部分(例如，参见非专利文献1至3)。

非专利文献1：A.K.Jain,K.Nandakumar和A.Nagar，“Biometric  template security(review article)”，EURASIP Journal on Advances in  Signal Processing,pp.1-17,2008

非专利文献2：A.Juels和M.Wattenberg，“A fuzzy commitment  scheme”，in Proceedings of 6th ACM Conference on Computer and  Communications Security(ACMCCS’99),pp.28-36,1999

非专利文献3：A.Juels和M.Sudan，“A fuzzy vault scheme”，in  Proceedings of the IEEE International Symposium on Information Theory, p.408,2002。

然而，实现相关密钥绑定方法的方案具有如下问题：这些方案不能满 足作为生物模板保护的安全要求之一的多样性。换句话说，在利用模糊承 诺或模糊保险箱的密钥绑定方法中，根据相同生物信息的模板和用户特有 密钥生成的辅助信息包括公用部分，使得可以在多个数据库之间进行交叉 匹配。也就是说，这样的密钥绑定方案不满足多样性。

不仅在生物信息的匹配中出现上述问题，而且在数值信息如位置信息 和机密信息的校对中也出现上述问题。

因此，本发明的实施方式的一个方面的目标是提供一种改进生物模板 保护的密钥绑定方法的多样性的秘密数据匹配装置。

发明内容

秘密数据匹配装置包括：存储单元，存储通过基于第一随机数和确定 矩阵的行向量的第一线性组合来隐藏第一数据和密钥数据所获得的第一 秘密向量，所述确定矩阵对于包括所述秘密数据匹配装置的每个系统不 同，并且通过将随机数向量作为最后一列添加到包括对角分量的矩阵来生 成，所述对角分量包括确定所述第一数据与第二数据是否彼此近似的阈值 和与所述秘密数据相关的阈值；获取单元，获取通过基于第二随机数和所 述确定矩阵的行向量的第二线性组合来隐藏所述第二数据所获得的第二 秘密向量；计算单元，根据所述存储单元中存储的所述第一秘密向量与由 所述获取单元获取的所述第二秘密向量之间的差来计算当所述确定矩阵 用作模数时为残差的残差向量；确定单元，基于由所述计算单元计算的所 述残差向量来确定所述第一数据与所述第二数据是否彼此近似；以及提取 单元，当确定所述第一数据与所述第二数据彼此近似，作为所述确定单元 的确定结果时，从所述残差向量提取密钥数据。

附图说明

图1是示出了根据实施方式的秘密数据匹配系统的功能配置的示例 的图；

图2是示出了根据实施方式的近似确定矩阵的图；

图3是描绘了根据实施方式的秘密数据登记处理的序列的图；

图4是描绘了根据实施方式的秘密数据匹配处理的序列的图；以及

图5是描绘了执行秘密数据匹配程序的计算机的示例的图。

具体实施方式

将参照附图来说明优选实施方式。秘密数据匹配装置采用生物模板保 护的密钥绑定方案。实施方式并不限制本发明。

秘密数据匹配系统的配置

图1是示出了根据实施方式的秘密数据匹配系统的功能配置的示例 的图。如图1所描绘的，秘密数据匹配系统9包括客户端1和客户端2 以及秘密数据匹配装置3。秘密数据匹配装置3包括数据库330。秘密数 据匹配装置3与客户端1和客户端2通过网络连接。

在此，秘密数据匹配系统9基于称作点阵掩蔽的特殊随机数(点阵元 素)来隐藏客户特有密钥数据和客户端的生物数据，并且将通过隐藏上述 数据所获得的第一秘密数据登记在数据库330中。当秘密数据匹配系统9 接收对生物数据进行匹配的请求时，秘密数据匹配系统9基于点阵的不同 元素隐藏要被匹配的生物数据，并且获取通过隐藏生物数据所获得的第二 秘密数据。然后，秘密数据匹配系统9通过使用点阵理论特定的映射，根 据第一秘密数据与第二秘密数据之间的差异来确定与第一秘密数据对应 的生物数据和与第二秘密数据对应的生物数据是否彼此近似。如果秘密数 据匹配系统9确定与第一秘密数据对应的生物数据和与第二秘密数据对 应的生物数据彼此近似，则秘密数据匹配系统9从第一秘密数据提取密钥 数据，并且将所提取的密钥数据输出至请求源。在该实施方式中，为了方 便描述，假定客户端1是登记生物数据的客户端，并且假定客户端2是请 求对生物数据进行匹配的终端。可以存在多个客户端1。可以存在多个客 户端2。

下面将对秘密数据匹配系统9中的生物数据和客户特有密钥数据的 隐藏以及每个隐藏的秘密数据之间的近似确定的内容进行描述。

客户端1包括登记请求单元11和秘密数据生成单元12。在该实施方 式中，由例如数值表示密钥112。

登记请求单元11请求秘密数据匹配装置3来登记生物数据111和密 钥112。例如，登记请求单元11从外部终端接收生物数据111和密钥112。 然后，登记请求单元11请求秘密数据匹配装置3来登记接收到的生物数 据111和密钥112。外部终端可以是通过网络连接的终端。

在此，生物数据111是客户端的物理特征或行为特征的数据。物理特 征的示例包括指纹、静脉、虹膜和DNA。行为特征的示例是笔迹。在该 实施方式中，由包括n维分量的向量表示生物数据111。密钥112是客户 端想要连同生物数据一起登记的密钥数据。在该实施方式中，由例如数值 表示密钥112。

登记请求单元11作为对登记请求的响应，从秘密数据匹配装置3接 收的、与下文将描述的近似确定矩阵331对应的线性组合(点阵元素)， 并且将所接收的点阵元素输出至秘密数据生成单元12。当登记请求单元 11从秘密数据生成单元12接收其中隐藏生物数据111和密钥112的秘密 向量时，登记请求单元11请求秘密数据匹配装置3来登记秘密向量。

秘密数据生成单元12生成其中隐藏生物数据111和密钥112的秘密 向量。

例如，秘密数据生成单元12对于生物数据111和密钥112生成其中 将“0”附加到生物数据111和密钥112的组合数据的最后一个分量的(n+2) 维向量。具体地，秘密数据生成单元12生成其中将密钥112中包括的一 维分量以及作为第(n+2)个分量的“0”附加到生物数据111中包括的n 维分量的(n+2)维向量。作为示例，假定生物数据111是表示n维分量 的T，而密钥112是表示一维分量的K。那么，秘密数据生成单元12生 成(T，K，0)作为(n+2)维向量。

当秘密数据生成单元12从登记请求单元11获取线性组合(点阵元素) 时，秘密数据生成单元12生成随机数。然后，秘密数据生成单元12生成 秘密向量，其中所生成的(n+2)维向量与线性组合(点阵元素)和随机 数的乘积相加。作为示例，如果随机数为r₁，并且点阵元素为b₁，则由 (T，K，0)+r₁×b₁表示秘密向量。然后，秘密数据生成单元12将所生 成的秘密向量输出至登记请求单元11。

客户端2包括匹配请求单元21和秘密数据生成单元22。

匹配请求单元21请求秘密数据匹配装置3来匹配生物数据。请求要 被匹配的生物数据是匹配数据211。在该实施方式中，由包括n维分量的 向量表示匹配数据211。匹配请求单元21作为对匹配请求的响应，从秘 密数据匹配装置3接收与下文将描述的近似确定矩阵331对应的线性组合 (点阵元素)，并且将所接收的点阵元素输出至秘密数据产生单元22。当 匹配请求单元21从秘密数据生成单元22接收到其中隐藏匹配数据211的 秘密向量时，匹配请求单元21请求秘密数据匹配装置3来匹配秘密向量。 从秘密数据匹配装置3接收到的点阵元素不同于当进行登记时由客户端1 的登记请求单元11接收到的点阵元素。

秘密数据生成单元22生成其中隐藏匹配数据211的秘密向量。

例如，秘密数据生成单元22生成其中将“0”附加到匹配数据211的 最后一个分量和倒数第二个分量的(n+2)维向量。具体地，秘密数据生 成单元22生成其中将两个“0”作为第(n+1)分量和第(n+2)分量附 加到匹配数据211中包括的n维分量的(n+2)维向量。作为示例，假定 匹配数据211是表示n维分量的Q。那么，秘密数据生成单元22生成(Q， 0，0)作为(n+2)维向量。

当秘密数据生成单元22从匹配请求单元21获取线性组合(点阵元素) 时，秘密数据生成单元22生成随机数。然后，秘密数据生成单元22生成 秘密向量，其中所生成的(n+2)维向量与线性组合(点阵元素)和随机 数的乘积相加。作为示例，如果随机数为r₂，并且点阵元素为b₂，则由 (Q，0，0)+r₂×b₂表示秘密向量。然后，秘密数据生成单元22将所生 成的秘密向量输出至匹配请求单元21。尽管可以使用任意方法作为生成 随机数的方法，但是期望参数在客户端1与客户端2之间不同，使得在客 户端1和客户端2中生成的随机数彼此不重叠。

秘密数据匹配装置3包括登记单元31、认证单元32和存储单元33。 登记单元31生成下文将描述的近似确定矩阵，并且将所生成的近似确定 矩阵登记在存储单元33的数据库330中。此外，登记单元31将被请求登 记在数据库330中的秘密数据登记在存储单元33中。认证单元32将被请 求匹配的、其中隐藏匹配数据的秘密数据与所登记的秘密数据进行匹配， 并且确定这两个秘密数据是否彼此近似。

存储单元33是存储装置如硬盘或光盘。存储单元33可以是数据可重 写半导体存储器如RAM(随机存取存储器)、ROM(只读存储器)、闪存 和NVSRAM(非易失静态随机存取存储器)。

存储单元33存储数据库330。数据库330存储近似确定矩阵331和 秘密数据332。近似确定矩阵331和秘密数据332由下面描述的登记单元 31登记。下文将描述近似确定矩阵331的细节。

登记单元31包括随机数生成单元311、近似确定矩阵生成单元312、 近似确定矩阵登记单元313和秘密数据登记单元314。

随机数生成单元311生成近似确定矩阵331中所使用的随机数，并且 将所生成的随机数输出至近似确定矩阵生成单元312。在此，当生成近似 确定矩阵331时，近似确定矩阵331中所使用的随机数是被添加作为表示 近似范围的阈值的方阵的倒数第二行和最后一行的随机数。近似范围的阈 值是由客户端设定为近似范围的数值并且是将每维方向中的长度表示为 近似范围中的向量的信息。例如，当近似范围的阈值是“e、f、g”时， 随机数生成单元311生成满足e/2≥h，f/2≥i以及g/2≥j的随机数 “h、i、j”以及任意随机数“k、l”。

近似确定矩阵生成单元312生成近似确定矩阵331以进行近似确定。 所生成的近似确定矩阵331被生成为，对于安装有秘密数据匹配装置3 的每个系统来说不同。

例如，近似确定矩阵生成单元312生成其中表示近似范围的阈值是对 角分量并且其他分量是“0”的对角矩阵。作为示例，当要被确定的生物 数据是表示n个分量的信息时，也就是说，当生物数据111是n维信息时， 近似确定矩阵生成单元312生成n×n对角矩阵。此外，近似确定矩阵生 成单元312在第(n+1)行和第(n+1)列设定密钥112的阈值。密钥112 的阈值是表示由客户设定的密钥的最大值的信息。

然后，近似确定矩阵生成单元312生成其中将所有分量为“0”的倒 数第二行和最后一行附加到所生成的n×n对角矩阵的(n+2)×n矩阵。 近似确定矩阵生成单元312生成具有n个分量的随机数向量。近似确定矩 阵生成单元312生成具有分量的随机数向量，分量的数量通过使2与对角 矩阵的列的数量n相加来获得(其数量是最后一列的序数)。由随机数生 成单元311生成的随机数被设定成随机数向量的分量。然后，秘密数据匹 配装置3生成被附加随机数向量的(n+2)×(n+2)方阵，作为近似确 定矩阵331。

近似确定矩阵登记单元313将由近似确定矩阵生成单元312生成的近 似确定矩阵331登记在数据库330中。

在此，将参照图2来描述近似确定矩阵331。图2是示出了根据实施 方式的近似确定矩阵的图。在图2所描绘的示例中，将描述由三维数字表 示生物数据和近似范围的示例。如图2所描绘的，与近似确定矩阵331 对应的近似确定矩阵V是其中将随机数向量和密钥的阈值附加到由虚线 表示的范围中的近似确定矩阵的矩阵。

近似确定矩阵包括阈值，其将长度指定为近似范围中的每维方向上的 向量，作为对角元素。例如，图2中所描绘的示例表示近似范围中的x 轴方向上的向量的长度是“20”，近似范围中的y轴方向上的向量的长度 是“10”，并且近似范围中的z轴方向上的向量的长度是“14”。换句话说， 图2中所描绘的近似确定的矩阵是确定两个生物数据是否在x轴方向上包 括在“±10”的范围内，在y轴方向上包括在“±5”的范围内，并且在 z轴方向上包括在“±7”的范围内。

此外，将“0、0、0”附加到用于嵌入密钥的第四行中。此外，将通 过组合随机数向量“7、4、5”与密钥的阈值“20000”所获得的“7、4、 5、20000”添加到第四列中。然后，将“0、0、0、0”添加到作为最后一 行的第五行中。此外，将随机数向量“5、3、﹣2、﹣42、123”添加到作 为最后一列的第五列中。在图2中所描绘的示例，尽管由三维数字指定近 似范围，但该实施方式不限于此，并且可以使用任何维数字。

秘密数据登记单元314将秘密数据登记在数据库330中。所登记的秘 密数据对应于密钥绑定方案中被保护的模板。

例如，当秘密数据登记单元314从客户端1接收生物数据111和密钥 112的登记请求时，秘密数据登记单元314生成与近似确定矩阵331对应 的线性组合的随机数。作为示例，秘密数据登记单元314获取包括与近似 确定矩阵331对应的(n+2)个分量的行向量v₁、v₂、...、和v_n+2。然后， 秘密数据登记单元314分别选择与行向量v₁、v₂、...、和v_n+2对应的适当 整数d₁、d₂、...、和d_n+2。然后，秘密数据登记单元314计算每个行向量 与每个整数的乘积之和，也就是说，由d₁×v₁+d₂×v₂+...+d_n+2×v_n+2表示的(n+2)维向量，作为线性组合。该线性组合是“点阵元素”。秘 密数据登记单元314为每个生物数据选择不同的整数集合d₁、d₂、...、和 d_n+2，并且计算作为所选择的整数集合与近似确定矩阵331的每个行向量 的乘积之和的线性组合。

秘密数据登记单元314作为对登记请求的响应，将所计算的线性组合 即点阵元素，分发给客户端1。当秘密数据登记单元314从客户端1接收 秘密数据332的登记请求时，秘密数据登记单元314将被请求登记的秘密 数据332登记在数据库330中。

认证单元32包括匹配请求接收单元321、计算单元322、近似确定单 元323和密钥输出单元324。

当匹配请求接收单元321从客户端2接收匹配请求时，匹配请求接收 单元321生成与近似确定矩阵331对应的线性组合(点阵元素)的随机数。 线性组合的随机数生成与通过秘密数据登记单元314的随机数生成相同， 使得将省略其描述。由匹配请求接收单元321生成的点阵元素被生成为， 与当进行登记时由秘密数据登记单元314生成的点阵元素不同。

匹配请求接收单元321作为对匹配请求的响应，将所计算的线性组 合，即点阵元素，分发给客户端2。当匹配请求接收单元321从客户端2 接收其中隐藏匹配数据211的秘密向量的匹配请求时，匹配请求接收单元 321将被请求匹配的秘密向量输出至计算单元322。

计算单元322计算被登记在数据库330中的秘密数据332(秘密向量) 与其中隐藏匹配数据211且从客户端2接收的秘密向量之间的差向量。然 后，计算单元322根据所计算的差向量来计算当近似确定矩阵331用作模 数时作为残差的残差向量。作为一个示例，当差向量为z并且近似确定矩 阵331为V时，由“z mod V”表示残差向量。然后，计算单元322将所 生成的残差向量输出至近似确定单元323。

近似确定单元323确定从计算单元322接收的残差向量的最后一个分 量是否是“0”，如果残差向量的最后一个分量是“0”，则近似确定单元 323确定匹配数据211和登记源的生物数据111彼此近似。另一方面，如 果残差向量的最后一个分量不是“0”，则近似确定单元323确定匹配数据 211和登记源的生物数据111彼此不近似。

当确定生物数据111和匹配数据211彼此近似时，密钥输出单元324 从残差向量提取第(n+1)个分量的密钥112。然后，秘密数据匹配装置3 将所提取的密钥112输出至作为匹配源的客户端2。

在此，将描述由认证单元32执行的近似确定的原理。假定近似确定 矩阵331是近似确定矩阵V来描述该原理。近似确定矩阵V的每个行向 量v₁、v₂、...、和v_n+2的线性组合可以由其元素是近似确定矩阵V的每个 行向量的线性组合d₁×v₁+d₂×v₂+...+d_n+2×v_n+2的集合L(点阵L)来 表示。换句话说，近似确定矩阵V的每个行向量的线性组合对应于由集 合L的元素形成的点阵上的交叉中的任意一个。

使用随机数r₁和集合L的点阵元素b₁由下面的表达式(1)表示其 中隐藏n维生物数据T和密钥K的秘密向量H。在此，[T,K,0]是其中将 密钥K和作为第(n+2)分量的“0”附加到生物数据T的(n+2)维向 量。

H＝[T,K,0]+r₁×b₁              (1)

使用随机数r₂和集合L的点阵的元素b₂由下面的表达式(2)表示 其中隐藏n维匹配数据Q的秘密向量H’。在此，[Q,0,0]是其中将两个 “0”作为第(n+1)分量和第(n+2)分量附加到匹配数据Q的(n+2) 维向量。

H’＝[Q,0,0]+r₂×b₂            (2)

在这种情况下，由下面的表达式(3)表示秘密向量H与H’之间的 差向量z。

z＝H–H’＝[T-Q,K,0]+r₁×b₁-r₂×b₂     (3)

在此，包括在差向量z中的r₁×b₁-r₂×b₂是集合L的元素与随机数 的乘积之间的差，使得r₁×b₁-r₂×b₂包括在集合L的元素中。换句话说， r₁×b₁-r₂×b₂对应于由集合L的元素形成的点阵上的交叉中的任意一 个。当根据差向量z计算近似确定矩阵V的残差向量时，(z mod V)对 应于将差向量z映射到由集合L确定的基本域P(L)。因此，当根据差 向量z计算近似确定矩阵V的残差向量时，忽略r₁×b₁-r₂×b₂。因此， 当计算z mod V时，忽略差向量z中的包括除了差向量z的前端部分之外 的部分的点阵部分，并且将包括差向量z的前端部分的仅一个点阵映射到 基本域P(L)。具体地，由下面的表达式(4)表示z mod V。

z mod V＝[T-Q,K,0]mod V             (4)

当将向量[T-Q,K,0]包括在基本域P(L)中时，也就是说，当生物数据 T和匹配数据Q彼此近似时，建立z mod V＝[T-Q,K,0]。因此，当生物 数据T和匹配数据Q彼此近似时，存在z mod V的最后一个分量是“0” 的高可能性。

另一方面，当向量[T-Q,K,0]不包括在基本域P(L)中时，也就是说， 当生物数据T和匹配数据Q彼此不近似时，当b是属于集合L的点阵的 某个元素时，建立z mod V＝[T-Q,K,0]+b。因此，当生物数据T和匹配 数据Q彼此不近似时，存在z mod V的最后一个分量是除了“0”之外的 值的高可能性。

根据该原理，认证单元32可以根据秘密向量之间的差z来计算近似 确定矩阵V的残差向量，并且基于所计算的残差向量的最后一个分量来 执行隐藏的生物数据的近似确定。当认证单元32确定隐藏的生物数据近 似作为近似确定的结果时，认证单元32从秘密向量H提取密钥K，并且 将所提取的密钥K输出至匹配源。

秘密数据登记处理的序列

接下来，将参照图3来描述秘密数据登记处理的序列。图3是描绘了 根据实施方式的秘密数据登记处理的序列的图。在图3中，由T表示客 户的生物数据111，由K表示客户特有密钥112，由V表示近似确定矩阵 331，并且由H表示秘密向量。

在秘密数据匹配装置3中，近似确定矩阵生成单元312生成近似确定 矩阵V(步骤S11)。然后，近似确定矩阵登记单元313将所生成的近似 确定矩阵V登记在数据库330中(步骤S12)。

在客户端1中，登记请求单元11获取登记信息(步骤S13)。在此， 登记请求单元11获取生物数据T和密钥K作为登记信息。然后，登记请 求单元11请求秘密数据匹配装置3来登记生物数据T和密钥K(步骤 S14)。

在秘密数据匹配装置3中，从客户端1接收登记请求的秘密数据登记 单元314生成随机数点阵向量(步骤S15)。在此，秘密数据登记单元314 计算由近似确定矩阵V的每个行向量与每个适当整数的乘积之和表示的 线性组合。所计算的线性组合是作为点阵元素的随机数点阵向量b₁。然 后，秘密数据登记单元314将所计算的随机数点阵向量(点阵元素)b₁ 发送至客户端1(步骤S16)。

在客户端1中，秘密数据生成单元12生成登记信息(步骤S17)。在 此，秘密数据生成单元12生成其中将“0”附加到生物数据T和密钥K 的组合数据的最后一个分量的向量(T,K,0)。

然后，秘密数据生成单元12隐藏登记信息(步骤S18)。在此，秘密 数据生成单元12生成秘密向量H，其中所生成的向量(T,K,0)与随机 数点阵向量(点阵元素)b₁和随机数的乘积相加。当随机数是r₁时，由 (T,K,0)+r₁×b₁表示秘密向量H。

然后，登记请求单元11将秘密向量H发送至秘密数据匹配装置3来 请求秘密数据匹配装置3登记为由秘密数据生成单元12隐藏的登记信息 的秘密向量H(步骤S19)。因此，秘密向量H被登记在秘密数据匹配装 置3的数据库330中。

秘密数据匹配处理的序列

接下来，将参照图4来描述秘密数据匹配处理的序列。图4是描绘了 根据实施方式的秘密数据匹配处理的序列的图。在图4中，由Q表示客 户的匹配数据211，由K表示客户特有密钥112，由V表示近似确定矩阵 331，并且由H’和H表示秘密向量。

在客户端2中，匹配请求单元21获取匹配信息(步骤S21)。在此， 匹配请求单元21获取匹配数据Q作为匹配信息。然后，匹配请求单元21 请求秘密数据匹配装置3对匹配数据Q进行匹配(步骤S22)。

在秘密数据匹配装置3中，从客户端2接收匹配请求的匹配请求接收 单元321从数据库330获取近似确定矩阵V(步骤S23)。然后，匹配请 求接收单元321生成随机数点阵向量(步骤S24)。在此，匹配请求接收 单元321计算由所获取的近似确定矩阵V的每个行向量与每个适当整数 的乘积之和表示的线性组合。所计算的线性组合是作为点阵元素的随机数 点阵向量b₂。然后，匹配请求接收单元321将所计算的随机数点阵向量 (点阵元素)b₂发送至客户端2(步骤S25)。在此，b₂和b₁彼此不同。

在客户端2中，秘密数据生成单元22生成秘密匹配信息(步骤S26)。 在此，秘密数据生成单元22生成其中将两个“0”附加到匹配数据Q的 向量(Q,0,0)。然后，秘密数据生成单元22生成秘密向量H’，其中所 生成的向量(Q,0,0)与随机数点阵向量(点阵元素)b₂和随机数的乘积 相加。当随机数是r₂时，由(Q,0,0)+r₂×b₂表示秘密向量H’。然后， 匹配请求单元21将秘密向量H’发送至秘密数据匹配装置3来请求秘密数 据匹配装置3匹配秘密向量H’(步骤S27)。

在秘密数据匹配装置3中，计算单元322从数据库300获取秘密向量 H(步骤S28)。然后，近似确定单元323在不改变秘密向量的秘密状态的 情况下通过使用根据被请求匹配的秘密向量H’与所获取的秘密向量H之 间的差向量所计算的残差向量来进行匹配处理。(步骤S29)。在此，近似 确定单元323确定残差向量的最后一个分量是否是“0”。如果残差向量的 最后一个分量是“0”，则近似确定单元323确定匹配数据Q和登记源的 生物数据T彼此近似。另一方面，如果残差向量的最后一个分量不是“0”， 则近似确定单元323确定匹配数据Q和登记源的生物数据T彼此不近似。

当确定生物数据T和匹配数据Q彼此近似时，密钥输出单元324从 残差向量提取用户特有密钥K(步骤S30)。然后，密钥输出单元324将 所提取的密钥K发送至请求匹配的客户端2(步骤S31)。

由此，之后，客户端2可以通过使用所提取的客户特有密钥K来进 行认证检查。作为示例，在客户端2中，如果所提取的客户特有密钥K 用作秘密密钥，则可以通过使用秘密密钥和预先存储的公共密钥来进行基 于公共密钥认证方法的认证检查。

秘密数据匹配装置3可以满足生物模板保护中的密钥绑定方法中的 多样性。具体地，秘密数据匹配装置3根据生物数据T和客户特有密钥K 的近似确定矩阵V来生成要登记在数据库330中的秘密向量H。假定根 据两个不同的近似确定矩阵V₁和V₂分别生成生物数据T和客户特有密钥 K的秘密向量H₁和H₂。当b₁是根据近似确定矩阵V₁所生成的点阵元素 时，由(T,K,0)+r₁×b₁表示根据近似确定矩阵V₁所生成的秘密向量 H₁。当b₂是根据近似确定矩阵V₂所生成的点阵元素时，由(T,K,0)+r₂×b₂表示根据近似确定矩阵V₂所生成的秘密向量H₂。然后，近似确定矩 阵V₁和V₂彼此不同，使得b₁和b₂彼此不同。从而，难以从两个秘密向 量H₁和H₂获得公用信息。因此，如果近似确定矩阵V₁和V₂对于每个系 统来说彼此不同，则对于生物数据T和客户特有密钥K来说不交叉匹配 秘密向量H₁和H₂。也就是说，满足多样性。

秘密数据的登记处理和匹配处理的具体示例

接下来，将使用具体示例来描述根据实施方式的秘密数据的登记处理 和匹配处理。假定秘密数据匹配系统9使用三维数据作为生物数据。例如， 假定当它们被登记时客户端1中输入的第一用户的生物数据T为[123,512, 120]，并且密钥K为“6497”。假定图2中所描绘的近似确定矩阵V由秘 密数据匹配装置3生成。

秘密数据的登记处理的具体示例

从客户端1接收到生物数据T和密钥K的登记请求的秘密数据匹配 装置3在近似确定矩阵V中设定每个行向量V₁至V₅。然后，秘密数据匹 配装置3计算由每个行向量V₁至V₅与每个适当整数的乘积之和表示的线 性组合b₁。在此，由下面的表达式(5)表示线性组合b₁。

b₁＝2×v₁+3×v₂-5×v₃-v₄+5×v₅＝[40,30,-70,-199999,686]  (5)

然后，秘密数据匹配装置3将所计算的线性组合b₁发送至客户端1。

接收线性组合b₁的客户端1生成秘密向量H，其中“0”被附加到生 物数据T和密钥K的组合数据的最后一个分量的向量(T,K,0)与线性 组合b₁和随机数的乘积相加。在此，当由客户端选择的随机数r₁是“7” 时，由下面的表达式(6)表示秘密向量H。

H＝[T,K,0]+r₁×b₁＝[403,722,-370,133496,4802]      (6)

然后，客户端1将所计算的秘密向量H发送至秘密数据匹配装置3。 秘密数据匹配装置3将秘密向量H登记在数据库330中。

秘密数据的匹配处理的具体示例1

作为一个示例，假定当进行匹配时在客户端2中输入的第一用户的匹 配数据Q1是[122,514,124]。

从客户端2接收匹配数据Q1的匹配请求的秘密数据匹配装置3在近 似确定矩阵V中设定每个行向量V₁至V₅。然后，秘密数据匹配装置3计 算由每个行向量V₁至V₅与每个适当整数的乘积之和表示的线性组合b₂。 在此，由下面的表达式(7)表示线性组合b₂。

b₂＝5×v₁-2×v₂+7×v₃+v₅＝[100,20,98,62,128]      (7)

然后，秘密数据匹配装置3将所计算的线性组合b₂发送至客户端2。

接收线性组合b₂的客户端2生成秘密向量H1，其中两个“0”被附 加到匹配数据Q1的向量(Q1,0,0)与线性组合b₂和随机数的乘积相加。 在此，当由客户端选择的随机数r₂是“123”时，由下面的表达式(8) 来表示秘密向量H1。

H1＝[Q1,0,0]+r₂×b₂＝[12422,-1946,12178,7626,15744]      (8)

然后，客户端2将秘密向量H1发送至秘密数据匹配装置3来请求秘 密数据匹配装置3匹配所计算的秘密向量H1。

随后，秘密数据匹配装置3根据被请求匹配的秘密向量H1与所登记 的秘密向量H之间的差向量z₁使用近似确定矩阵V作为模数来计算残差 向量。在此，计算差向量z₁＝(H–H1)，并且如下面的表达式(9)来计 算使用近似确定矩阵V作为模数的残差向量。

z₁mod V＝z₁-[z₁×V^-1]×V＝[1,-2,-4,6497,0]       (9)

然后，因为根据秘密向量H1所计算的残差向量的最后一个分量是 “0”，所以秘密数据匹配装置3确定匹配数据Q1和登记源的生物数据T 彼此近似。然后，秘密数据匹配装置3提取残差向量的倒数第二个分量的 密钥K。在此，将“6497”提取为密钥K。

然后，秘密数据匹配装置3将“6497”发送至请求匹配的客户端2。

秘密数据的匹配处理的具体示例2

作为另一示例，假定当进行匹配时作为在客户端2中输入的第二用户 的生物数据的秘密数据Q2是[121,555,123]。

从客户端2接收匹配数据Q2的匹配请求的秘密数据匹配装置3在近 似确定矩阵V中设定每个行向量V₁至V₅。然后，秘密数据匹配装置3计 算由每个向量V₁至V₅与每个适当整数的乘积之和表示的线性组合b₂。在 此，由上述表达式(7)来表示线性组合b₂。

然后，秘密数据匹配装置3将所计算的线性组合b₂发送至客户端2。

接收线性组合b₂的客户端2生成秘密向量H2，其中两个“0”被附 加到匹配数据Q2的向量(Q2,0,0)与线性组合b₂和随机数的乘积相加。 在此，当由客户端选择的随机数r₃是“-17”时，由下面的表达式(10) 来表示秘密向量H2。

H₂＝[Q2,0,0]+r₃×b₂＝[-1579,895,-1543,-1054,-2176]     (10)

然后，客户端2将秘密向量H2发送至秘密数据匹配装置3来请求秘 密数据匹配装置3匹配所计算的秘密向量H2。

随后，秘密数据匹配装置3根据被请求匹配的秘密向量H2与所登记 的秘密向量H之间的差向量z₂使用近似确定矩阵V作为模数来计算残差 向量。在此，计算差向量z₂＝(H–H2)，并且如下面的表达式(11)来 计算使用近似确定矩阵V作为模数的残差向量。

z₂mod V＝z₂-[z₂×V^-1]×V＝[2,-3,-3,6513,12]         (11)

然后，因为根据秘密向量H2所计算的残差向量的最后一个分量不为 “0”，所以秘密数据匹配装置3确定匹配数据Q2和登记源的生物数据T 彼此不近似。然后，秘密数据匹配装置3将表示匹配失败的信息发送至客 户端2。秘密数据匹配装置3可以发送残差向量的倒数第二个分量“6513” 而非表示匹配失败的信息。

实施方式的效果

根据上述实施方式，秘密数据匹配装置3将通过基于第一随机数和对 于包括秘密数据匹配装置3的每个系统不同的近似确定矩阵331的行向量 的第一线性组合隐藏生物数据和密钥所获得的第一秘密向量登记在数据 库330中。然后，秘密数据匹配装置3获取通过基于第二随机数和近似确 定矩阵331的行向量的第二线性组合隐藏匹配数据所获得的第二秘密向 量。然后，秘密数据匹配装置3根据第一秘密向量与第二秘密向量之间的 差来计算当近似确定矩阵331用作模数时作为残差的残差向量。然后，秘 密数据匹配装置3基于所计算的残差向量来确定生物数据和匹配数据是 否彼此近似，并且当生物数据和匹配数据彼此近似时，秘密数据匹配装置 3从残差向量提取密钥。根据该配置，秘密数据匹配装置3通过使用秘密 向量进行近似确定，该秘密向量由对于包括秘密数据匹配装置3的每个系 统不同的近似确定矩阵331所对应的线性组合隐藏，并且当确定近似时， 秘密数据匹配装置3提取密钥。因此，即使另一系统通过使用另一近似确 定矩阵331来隐藏相同的数据，但是根据每个近似确定矩阵331分别生成 的秘密向量不具有相同的部分，使得秘密向量彼此不交叉匹配。因此，秘 密数据匹配装置3可以改进密钥绑定方法的多样性。

根据上述实施方式，秘密数据匹配装置3基于第二随机数和与生成第 一秘密向量时所使用的第一线性组合不同的第二线性组合来获取第二秘 密向量。根据该配置，秘密数据匹配装置3获取使用与生成第一秘密向量 时所使用的线性组合不同的线性组合的第二秘密向量，使得难以区分秘密 向量之间的相关性。因此，可以防止信息泄露。

根据上述实施方式，秘密数据匹配装置3将所提取的密钥输出至匹配 数据的确定请求源。根据该配置，确定请求源可以通过使用所接收的密钥 来进行认证检查。

其他

在该实施方式中，描述了其中秘密数据匹配装置3将其中隐藏与一个 客户相关的生物数据111和密钥112的秘密数据332登记在数据库330中 并且将所登记的秘密数据332与其中隐藏匹配数据211的秘密数据进行匹 配的情况。然而，秘密数据匹配装置3可以将其中隐藏与多个客户有关的 生物数据111和密钥112的多个秘密数据332分别登记在数据库330中。 在该情况下，当秘密匹配数据装置3接收匹配请求时，秘密数据匹配装置 3可以依次选择所登记的秘密数据332，并且将所选择的秘密数据332与 其中隐藏被请求匹配的匹配数据211的秘密数据进行匹配。如果秘密数据 匹配装置3确定所选择的秘密数据332和秘密数据彼此近似，作为匹配的 结果，则秘密数据匹配装置3可以从进行匹配时所生成的残差向量提取密 钥112，并且将密钥112发送至匹配请求源。

在该实施方式中，描述了秘密数据匹配装置3通过确定进行匹配时所 生成的残差向量的最后一个分量是否是“0”来确定匹配数据211与登记 源的生物数据111是否彼此近似。然而，这不限于此，并且秘密数据匹配 装置3可以通过确定残差向量的多个分量是否为“0”来确定匹配数据211 和登记源的生物数据111是否彼此近似。

例如，当要被确定的生物数据是表示包括n个分量的信息时，也就是 说，当生物数据111是n维信息时，近似确定矩阵生成单元312生成n× n对角矩阵。此外，近似确定矩阵生成单元312将其中第(n+1)行的分 量为“0”的行向量附加到n×n对角矩阵。然后，近似确定矩阵生成单元 312将其中组合n维随机数向量与密钥112的阈值的列向量附加到第 (n+1)列。然后，近似确定矩阵生成单元312附加其中第(n+2)行的 分量为“0”的行向量。然后，近似确定矩阵生成单元312通过将(n+2) 维随机数向量附加到第(n+2)列来生成(n+2)×(n+2)矩阵。

此外，近似确定矩阵生成单元312附加其中第(n+3)行的分量为“0” 的行向量。近似确定矩阵生成单元312可以通过将(n+3)维随机数向量 附加到第(n+3)列来生成(n+3)×(n+3)近似确定矩阵331。

然后，秘密数据匹配装置3通过执行与该实施方式中的处理相同的处 理使用近似确定矩阵331作为模数来计算(n+3)维残差向量。然后，秘 密数据匹配装置3可以通过确定残差向量的第(n+2)维至第(n+3)维 的所有分量是否为“0”来进行近似确定。由此，秘密数据匹配装置3可 以改进近似确定的精确度。以相同的方式，如果近似确定矩阵生成单元 312生成(n+m)×(n+m)近似确定矩阵331(m是大于3的自然数)， 则可以进一步改进近似确定的精确度。

在该实施方式中，描述其中秘密数据匹配装置3用于生物数据111的 近似确定的情况。然而，秘密数据匹配装置3不限于此，并且秘密数据匹 配装置3可以用于机密文本之间的秘密相似度确定。例如，客户端1从机 密文本提取特征字符或文本部分，并且生成表示所提取的部分的特征量的 特征量向量。然后，客户端1通过执行与该实施方式中的处理相同处理来 生成其中隐藏所生成的特征量向量和密钥的秘密向量，并且将秘密向量登 记在秘密数据匹配装置3的数据库330中。然后，秘密数据匹配装置3 可以通过执行与该实施方式中的处理相同处理，将由客户端2生成的并且 其中隐藏期望被匹配的特征量向量的秘密向量与所登记的秘密向量进行 匹配。

秘密数据匹配装置3可以通过将登记单元31、认证单元32等的每个 功能安装在信息处理装置如已知的个人计算机和工作站中来实现。

图中所描绘的装置的部件不一定物理上被配置为图中所描绘的那样。 换句话说，装置的分布和集成的具体形式不限于图中所示出的这些形式， 并且装置的全部或部分可以根据各种负载和使用状态在功能上或物理上 被分布或集成在任意单元中。例如，随机数生成单元311和近似确定矩阵 生成单元312可以被集成到一个单元中。另一方面，近似确定矩阵生成单 元312可以被划分成在矩阵中设定表示近似范围的阈值和密钥的阈值的 第一设定单元，以及设定随机数的第二设定单元。此外，数据库330可以 是连接至秘密数据匹配装置3的外部装置或可以是通过网络连接的外部 装置。

可以通过在计算机如个人计算机或工作站上执行预先准备的程序来 实现上述实施方式中所描述的各种处理。因此，下面将对执行实现与图1 中所描绘的数据匹配装置3的功能相同的功能的秘密数据匹配程序的计 算机的示例进行描述。图5是描绘了执行秘密数据匹配程序的计算机的示 例的图。

如图5所描绘的，计算机200包括：进行各种算术处理的CPU 203、 从用户接收数据输入的输入装置215、以及控制显示装置209的显示控制 单元207。计算机200还包括：从存储介质读取程序等的驱动装置213、 以及通过网络将数据发送至另一计算机或从另一计算机接收数据的通信 控制单元217。计算机200还包括HDD 205和临时存储各种信息的存储 器201。存储器201、CPU 203、HDD 205、显示控制单元207、驱动装置 213、输入装置215和通信控制单元217通过总线219连接。

例如，驱动装置213是可移动盘211的装置。HDD205存储秘密数据 匹配程序205a和秘密数据匹配相关信息205b。

作为处理，CPU203读取秘密数据匹配程序205a，将秘密数据匹配程 序205a扩展到存储器201中，并且执行秘密数据匹配程序205a。该处理 对应于秘密数据匹配装置3中的每个功能单元。秘密数据匹配相关信息 205b对应于近似确定矩阵331和秘密数据332。例如，可移动盘211存储 每条信息如秘密数据匹配程序205a。

秘密数据匹配程序205a不一定从开始就被存储在HDD 205中。例如， 程序存储在插入计算机200中的“便携式物理介质”如柔性盘(FD)、 CD-ROM、DVD盘、磁光盘和IC卡中。然后，计算机200可以从这样 的介质中读取秘密数据匹配程序205a，并且执行秘密数据匹配程序205a。

根据本申请中所公开的系统的一种模式，可以改进生物模板保护中的 密钥绑定方法的多样性。