部分字符串位置检测装置、部分字符串位置检测方法及程序

摘要

高效地检测模式中的部分字符串在文本中出现的位置。部分字符串位置检测装置(1)以文本t的秘文〔t〕、模式p的秘文〔p〕、向量c的秘文〔c〕及矩阵E的秘文〔E〕为输入，输出矩阵H的秘文〔H〕。第一矩阵生成单元20生成成为F[i][j]＝E[i][j+i mod n+1](其中，认为)的矩阵F的秘文〔F〕。第二矩阵生成单元(30)生成矩阵F'的秘文〔F'〕，该秘文〔F'〕在c[i]＝0的情况或c[i]＝1且关于以k＝i,…,n‑1连续为c[k]＝1的所有的k为F[k][j]＝1的情况下，设定F'[i][j]＝1，如果除此以外则设定F'[i][j]＝0。第三矩阵生成单元40计算〔H[i][j]〕＝〔F'[i][j‑i mod n+1]〕∧〔c[i]〕∧￢〔c[i‑1]〕，生成秘文〔H〕。

说明书

技术领域

本发明涉及密码应用技术，特别是涉及不显示输入数据而检测模式中所含的部分字符串在文本中的出现位置的技术。

背景技术

作为不复原被加密的数值而得到特定的运算结果的方法，有被称作秘密计算的方法(例如，参照非专利文献1)。在非专利文献1的方法中，进行使数值的片断分散在三个秘密计算装置中的加密，通过三个秘密计算装置进行协调计算，可以不复原数值而以将加减法、常数和、乘法、常数倍、逻辑运算(否定、逻辑积、逻辑和、异或)、数据形式变换(整数、二进制)的结果分散于三个秘密计算装置的状态、即维持加密的状态进行保持。

在进行字符串的模式匹配的情况下，求模式中所含的部分字符串在文本中的出现位置，基于该出现位置的信息，良好地进行文本是否与模式匹配的判定。

现有技术文献

非专利文献

非专利文献1：千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能3パーティ隐匿関数計算の再考”、CSS、2010年

发明内容

发明所要解决的课题

但是，要通过秘密计算求部分字符串的位置，需要在将文本和模式的内容隐匿的状态下进行处理。因此，在通过简单的方法进行模式匹配的情况下，如果将输入文本长设为n、将模式长设为m，则需要O(1)循环(rounds)、Ω(m³n)的通信量。

本发明的目的在于，在进行模式匹配的情况下，能够高效地检测模式中的部分字符串在文本中出现的位置。

用于解决课题的技术方案

为了解决所述的课题，本发明的部分字符串位置检测装置以长度n的文本t的秘文〔t〕、长度m的模式p的秘文〔p〕、长度m的向量c的秘文〔c〕及m行n列的矩阵E的秘文〔E〕为输入，输出m行n列的矩阵H的秘文〔H〕。p[i]为模式p的第i个要素，t[i]为文本t的第i个要素，c[i]为向量c的第i个要素，E[i][j]为矩阵E的第i行j列的要素，H[i][j]为矩阵H的第i行j列的要素。向量c为在p[i]不是表示任意长度的字符串的无限长度间隔的情况下，设定c[i]＝1，否则设定c[i]＝0的向量。矩阵E为，如果c[i]＝0或p[i]＝t[j]，则设定E[i][j]＝1，否则设定E[i][j]＝0的矩阵。矩阵H为，p[i]是以无限长度间隔分割了模式p的部分字符串的先头的要素，且如果部分字符串在文本t的第j个位置出现，则设定H[i][j]＝1，如果除此以外，则被设定H[i][j]＝0的矩阵。第一矩阵生成单元生成成为F[i][j]＝E[i][j+i mod n+1]的m行(n+1)列的矩阵F的秘文〔F〕，其中，认为第二矩阵生成单元生成m行(n+1)列的矩阵F'的秘文〔F'〕，该秘文〔F'〕在c[i]＝0的情况或c[i]＝1且关于将k从i逐次加上1时连续为c[k]＝1的所有的k为F[k][j]＝1的情况下，被设定F'[i][j]＝1，如果除此以外，则设定F'[i][j]＝0。第三矩阵生成单元计算生成秘文〔H〕。

发明效果

根据本发明的部分字符串位置检测技术，在提供了文本和模式的每一字符的匹配的结果时，以O(log m)循环、O(mn)的通信量可以检测模式中的部分字符串在文本中的出现位置。因此，在进行模式匹配的情况下，可以高效地检测模式中的部分字符串在文本中出现的位置。

附图说明

图1是示例部分字符串位置检测装置的功能结构的图；

图2是示例部分字符串位置检测方法的处理流程的图。

具体实施方式

在说明实施方式之前，说明本说明书中的记载方法及术语的定义。

＜记载方法＞

将通过加密或秘密分散等把某值a隐匿化后的值称作a的秘文，并记载为〔a〕。在隐匿化为秘密分散的情况下，通过〔a〕，参照各秘密计算装置具有的秘密分散的片断的集合。

将矩阵X的第i行记载为X[i]。将向量u的第i要素记载为u[i]。将把矩阵X的各要素隐匿化后的矩阵整体记载为〔X〕，并称作X的秘文。将把向量u的各要素隐匿化后的向量整体记载为〔u〕，并称作u的秘文。

·^T表示·的转置。

＜加法、减法、乘法＞

加法、减法、乘法的各运算以两个值a,b的秘文〔a〕,〔b〕为输入，分别计算a+b,a-b,ab的计算结果c₁,c₂,c₃的秘文〔c₁〕,〔c₂〕,〔c₃〕。将这些运算的执行分别如下式那样记载。

〔c₁〕←Add(〔a〕,〔b〕),

〔c₂〕←Sub(〔a〕,〔b〕),

〔c₃〕←Mul(〔a〕,〔b〕)

此外，在不可能导致误解的情况下，将Add(〔a〕,〔b〕),Sub(〔a〕,〔b〕),Mul(〔a〕,〔b〕)分别简记为〔a〕+〔b〕,〔a〕-〔b〕,〔a〕×〔b〕。

＜逻辑运算＞

逻辑和、逻辑积、否定的各运算以两个值a,b∈{0,1}的秘文〔a〕,〔b〕为输入，分别计算a和b的逻辑和,a和b的逻辑积,a的否定的计算结果c₁,c₂,c₃的秘文〔c₁〕,〔c₂〕,〔c₃〕。将这些运算的执行分别如下式那样记载。

〔c₁〕←〔a〕∨〔b〕,

〔c₂〕←〔a〕∧〔b〕,

这些逻辑运算通过下式的计算实现。

〔c₁〕←〔a〕+〔b〕-〔a〕×〔b〕,

〔c₂〕←〔a〕×〔b〕,

〔c₃〕←1-〔a〕

＜等号判定＞

等号判定的运算以两个值a,b的秘文〔a〕,〔b〕为输入，分别计算a＝b,a≠b的真伪值c₁,c₂的秘文〔c₁〕,〔c₂〕。真伪值为真时设为1，为伪时设为0。

将这些运算的执行分别如下式记载。

〔c₂〕←(〔a〕≠〔b〕)

隐匿化、复原、加法、减法、乘法例如只要使用非专利文献1所记载的方法即可。另外，等号判定例如只要使用“Ivan Damgard,Matthias Fitzi,Eike Kiltz,Jesper BuusNielsen,and Tomas Toft,“Unconditionally secure constant-rounds multi-partycomputation for equality,comparison,bits and exponentiation”,TCC,pp.285-304,2006.(参考文献1)”所记载的方法即可。

＜模式匹配＞

模式匹配是在被提供了文本t和模式p的两个字符串时，判定文本t是否满足模式p记载的条件的问题。文本t是将字母Σ＝{a,b,c,…,z}的要素排列0个以上的向量。模式p是由0个以上的字母或特殊记号构成的向量。作为特殊记号，可举出用于数据库操作的语言即SQL的LIKE命令或用于基本软件(OS)操作的语言即在大多数外壳(shells)中使用的特殊记号“？”或“*”。前者的特殊记号“？”是表示任意的一个字母的特殊记号，被称作通配符。后者的特殊记号“*”是表示0个以上的任意长度的字母的列的特殊记号，被称作无限长度间隔(gap)。文本t与模式p匹配是指在模式p可以表示的字符串的集合中含有文本t。

例如，将模式p设为p＝(a,b,？,a,b,*)。模式p可以表示t₀＝(a,b,c,a,b)或t₁＝(a,b,a,a,b,x,x)，但不能表示t₂＝(a,b,a,b,a)。因此前者两个文本t₀、t₁与模式p匹配，但后者的文本t₂与模式p不匹配。

进行这种模式匹配的情况下的有效的方法是将模式认为以无限长度间隔区分的部分字符串的排列，计算各部分字符串的文本中的出现位置，使用该出现位置的信息来判定文本是否与模式匹配的方法。

将由无限长度间隔“*”区分了模式p的部分字符串s₀,…,s_k-1(s_i[j]∈(Σ∪{？}))认为由无限长度间隔“*”连结的向量。在此，k是模式p中的部分字符串的个数。此时，如果满足下式，则部分字符串s_i在文本t的位置j出现。

(s_i[0]＝p[j]∨s_i[0]＝？)

∧(s_i[1]＝p[j+1]∨s_i[1]＝？)

∧…∧(s_i[λ_i-1]＝p[j+λ_i-1]∨s_i[λ_i-1]＝？)

其中，λ_i为部分字符串s_i的大小。

例如，在文本t＝(a,a,b,a,a,b,a)、模式p＝(*,a,？,*,b,*)时，模式p可以以无限长度间隔“*”分割成两个部分字符串(a,？),(b)。因此，k＝2、s₀＝(a,？)、s₁＝(b)。此时，s₀＝(a,？)在j＝0,1,3,4的位置出现，s₁＝(b)在j＝2,5的位置出现。

以下，对本发明的实施方式进行详细说明。此外，对图中具有相同功能的结构部标注相同编号，省略重复说明。

实施方式的部分字符串位置检测装置1如图1中所例示，包含输入单元10、第一矩阵生成单元20、第二矩阵生成单元30、第三矩阵生成单元40及输出单元50。

部分字符串位置检测装置1例如是使具有中央运算处理装置(CentralProcessing Unit、CPU)、主存储装置(Random Access Memory、RAM)等的公知或专用的计算机读入特别的程序而构成的特别的装置。部分字符串位置检测装置1例如基于中央运算处理装置的控制执行各处理。被输入部分字符串位置检测装置1的数据或在各处理中得到的数据例如存储于主存储装置，存储于主存储装置的数据根据需要读出，用于其它处理。

部分字符串位置检测装置1以长度n的文本t的秘文〔t〕、长度m的模式p的秘文〔p〕、长度m的向量c的秘文〔c〕及m行n列的矩阵E的秘文〔E〕为输入，输出m行n列的矩阵H的秘文〔H〕。

向量c在p[i]不是表示任意长度的字符串的无限长度间隔的情况下，被设定c[i]＝1，否则被设定c[i]＝0。在此，p[i]是模式p的第i个要素。c[i]是向量c的第i个要素。

就矩阵E而言，如果c[i]＝0或p[i]＝t[j]，则被设定E[i][j]＝1，否则被设定E[i][j]＝0。在此，t[i]是文本t的第i个要素。E[i][j]是矩阵E的第i行j列的要素。

矩阵H是p[i]以无限长度间隔分割了模式p的部分字符串s_λ的先头的要素，且如果部分字符串s_λ在文本t的第j位置出现，则设定H[i][j]＝1，如果除此以外，则设定H[i][j]＝0。在此，H[i][j]是矩阵H的第i行j列的要素。在此，λ是部分字符串的指数，设定以无限长度间隔分割了模式p的部分字符串有L个，为λ＝0,…,L-1。

以下，参照图2说明实施方式的部分字符串位置检测方法。

在步骤S10，向输入单元10输入文本t的秘文〔t〕、模式p的秘文〔p〕、向量c的秘文〔c〕及矩阵E的秘文〔E〕。

在步骤S20，第一矩阵生成单元20生成成为F[i][j]＝E[i][j+i mod n+1](其中，认为)的m行(n+1)列的矩阵F的秘文〔F〕。矩阵F将在矩阵E的最终列连结有的矩阵作为关于i＝0,…,m-1在第i行仅向左位移i的矩阵。

在步骤S30，第二矩阵生成单元30生成m行(n+1)列的矩阵F'的秘文〔F'〕，该秘文〔F'〕在c[i]＝0的情况或c[i]＝1且关于将k从i逐次加上1时，连续地对c[k]＝1的所有的k在为F[k][j]＝1的情况下，设定F'[i][j]＝1，除此以外，设定F'[i][j]＝0。

矩阵F'只要如下生成即可。将矩阵F的第j列向量设为e_j。使用向量c和向量e_j，如下生成向量e’_j。向量e’_j在c[i]＝0∨(关于满足c[i]＝1∧(c[i]以后的连续的所有的c[k]＝1的k为e_j[k]＝1))的情况下，设定e’_j[i]＝1，如果除此以外的情况，则设定e’_j[i]＝0。矩阵F'使用向量e’_j，作为F'[i][j]＝e'_j[i]生成。

计算向量e’_j的具体的方法只要如下即可。首先，考虑通过下式定义的二项运算：

定义为p_i:＝(c[i],e_j[i])，将通过下式计算的S_i的第1个要素S_i[0]设为e’_j[i]。由此，可以生成满足上述条件的向量e’_j。

此时，利用二项运算

具有结合性，可以应用“Richard E.Ladner and Michael J.Fischer,“Parallelprefix computation”,J.ACM,vol.27,no.4,pp.831-838,1980.(参考文献2)”中记载的方法。参考文献2是改变二项运算的顺序而高效地计算的方法。由此，可以通过O(m)次、O(logm)段的二项运算计算S₁,…,S_m-1，可以更高效地计算向量e’_j。

在步骤S40，第三矩阵生成单元40计算并生成矩阵H的秘文〔H〕。

在步骤S50，输出单元50输出m行n列的矩阵H的秘文〔H〕。矩阵H表示的是，在将p[i]设为模式p的部分字符串s_λ的先头的要素时，如果在矩阵H的第i行存在H[i][j]＝1的j，则在文本t的第j个位置检测部分字符串s_λ。

以下，使用具体例示出可以通过上述的方法检测部分字符串的位置。

例如，在步骤S10，输入下式所示的文本t、模式p、向量c及矩阵E。

t＝(a,a,b,a,b,a,b,b,a,b),

在该例中，n＝10、m＝7。

在步骤S20中，生成下式所示的矩阵F。

在步骤S30中，生成下式所示的矩阵F'。

在步骤S40中，生成下式所示的矩阵H。

例如，模式p＝(*,a,b,*,？,b,*)的部分字符串(p[4],p[5])＝(？,b)以文本t＝(a,a,b,a,b,a,b,b,a,b)出现的是t[1]＝(a,b),t[3]＝(a,b),t[5]＝(a,b),t[6]＝(b,b),t[8]＝(a,b)。可知，在矩阵H中，在向量H[4]＝(0 1 0 1 0 1 1 0 1 0)中，要素H[4][1],H[4][3],H[4][5],H[4][6],H[4][8]为1，其它要素为0。这样，可以使用矩阵H检测模式p的部分字符串的出现位置。

＜发明效果＞

根据本发明的部分字符串位置检测技术，在被提供了文本和模式的每一字符的匹配的结果时，以O(log m)循环、O(mn)的通信量可以实现模式中的部分字符串在文本中的出现位置。

＜发明要点＞

本发明中，不对模式中的每一部分字符串计算模式中的各部分字符串在文本中的出现位置，而使用每一字符的匹配的结果一并进行计算，由此，在对每一部分字符串进行计算时，以O(mn)的通信量实现需要Ω(m³n)的通信量的处理。

本发明不限于上述的实施方式，不用说，在不脱离本发明的宗旨的范围内可以适宜变更。上述实施方式中说明的各种处理不仅按记载的顺序以时间序列执行，还可以根据执行处理的装置的处理能力或需要并行或个别地执行。

[程序、记录介质]

在由计算机实现上述实施方式中说明的各装置的各种处理功能的情况下，各装置应具有的功能的处理内容通过程序进行记载。而且，通过由计算机执行该程序，在计算机上实现上述各装置中的各种处理功能。

记载有该处理内容的程序可以预先记录在由计算机可读取的记录介质中。作为由计算机可读取的记录介质，例如也可以是磁记录装置、光盘、光磁记录介质、半导体存储器等的任一种。

另外，该程序的流通例如通过销售、转让、出租记录有该程序的DVD、CD－ROM等可移动型记录介质而进行。进而，也可以为将该程序预先存储于服务器计算机的存储装置，经由网络从服务器计算机向其它计算机转发该程序，由此使该程序流通的结构。

执行这种程序的计算机，例如，首先将记录于可移动型记录介质的程序或从服务器计算机转发的程序暂时地存储于自己的存储装置。而且，在处理执行时，该计算机读取在自己的记录装置中存储的程序，执行遵照读取的程序的处理。另外，作为该程序的另一执行方式，计算机也可以从可移动型记录介质直接读取程序，执行遵照该程序的处理，再者，也可以每次从服务器计算机对该计算机转发程序时，逐次执行遵照所获取的程序的处理。另外，也可以是通过不进行从服务器计算机向该计算机转发程序而仅通过其执行指示和结果取得而实现处理功能的、所谓ASP(Application Service Provider，应用服务提供者)型的服务，执行上述的处理的结构。此外，本方式的程序中，包含以供电子计算机进行的处理用的信息、即以程序为基准的信息(虽然不是针对计算机的直接的指令，但具有规定计算机的处理的性质的数据等)。

另外，在该方式中，在计算机上执行规定的程序，由此构成了本装置，但这些处理内容的至少一部分也可以由计算机硬件实现。