矩阵/密钥生成装置、矩阵/密钥生成系统、矩阵结合装置、矩阵/密钥生成方法、程序

摘要

将要素中有重复的向量和结合对象的矩阵转换为不重复的向量和与该向量对应的矩阵。矩阵/密钥生成装置具备向量生成单元、集合生成单元、矩阵生成单元、密钥生成单元。向量生成单元以在i≠j时，如果是k

说明书

技术领域

本发明涉及用于处理表等由行和列构成的数据的矩阵/密钥生成装置、矩阵/密钥生成系统、矩阵结合装置、矩阵/密钥生成方法、程序。

背景技术

非专利文献1中公开有下述技术：对于要素被隐匿化的矩阵、具有与该矩阵的行的每一行对应的被隐匿化的要素的向量，在通过隐匿计算依旧将要素隐匿化的情况下，将矩阵的行的顺序和向量的要素的顺序按照向量的要素进行排序(sort)。非专利文献2中公开有下述技术：在依旧将要素隐匿化的情况下，进行对相同的要素出现的次数(重复的个数)进行计数的计算(以下，称为“阶段计算”)，输出隐匿化的结果。图1是用于说明阶段计算的概要的图。此外，∥∥是表示被隐匿化的情况的记号。输入的第1要素∥1∥第1次出现，所以输出的第1要素是∥1∥。输入的第2要素∥2∥第1次出现，所以输出的第2要素是∥1∥。输入的第3要素∥2∥是第2次出现，所以输出的第3要素是∥2∥。输入的第6要素∥3∥是第3次出现，所以输出的第6要素是∥3∥。这样，进行阶段计算时，对相同的要素出现的次数(重复的个数)进行计数，输出其结果。非专利文献3中公开有下述技术：以较少的通信量，基于与各矩阵对应的向量的被隐匿化的要素将要素被隐匿化的多个矩阵进行结合。非专利文献4中公开有将数据隐匿化的技术(分散处理)、恢复被隐匿化的数据的技术(恢复处理)、在将被隐匿化的数据隐匿化的状态下进行相加、相乘、验证(2个被隐匿化的数据是否相等的验证)而得到被隐匿化的结果的技术等。

非专利文献1:Koki Hamada,Dai Ikarashi,Koji Chida,and KatsumiTakahashi,“Oblivious radix sort:An efficient sorting algorithm for practicalsecure multi-party computation”,IACR Cryptology ePrint Archive,Vol.2014,p.121,2014.

非专利文献2:濱田浩気,五十嵐大,千田浩司，“秘匿計算上の集約関数中央値計算アルゴリズム”,In CSS,2012.

非专利文献3:濱田浩気,菊池亮,五十嵐大,千田浩司，“秘匿計算上の結合アルゴリズム”,人工知能学会全国大会(第26回)論文集,June 2012.

非专利文献4:千田浩司,濱田浩気,五十嵐大,高橋克巳，“軽量検証可能3パーティ秘匿関数計算の再考”,In CSS,2010.

发明所要解决的课题

非专利文献3所示的结合矩阵的技术以成为结合的密钥的向量的要素上没有重复的情况为前提，以少的通信量，通过隐匿计算实现矩阵的结合。但是，存在在向量的要素中有重复的情况下不能利用这种课题。为了能够利用非专利文献3的结合矩阵的技术，需要将要素上有重复的向量和结合对象的矩阵转换为在要素上无重复的向量和与该向量对应的矩阵。

发明内容

因此，本发明的目的在于，提供将要素中有重复的向量和结合对象的矩阵转换为要素中无重复的向量和与该向量对应的矩阵的技术。

用于解决课题的手段

首先，将N设为1以上的整数，n设为0以上N－1以下的整数，K_n设为1以上的整数，i和j设为整数，T_n设为K_n行的矩阵，k_n设为要素的数量为K_n个的向量，T_n[j]设为矩阵T_n的第j行，k_n[j]设为向量k_n的第j个要素，m_n设为向量k_n的要素重复的上限数。向量k_n的第j个要素为与矩阵T_n的第j行对应的要素。

本发明的第1发明是限定于隐匿计算，可以和非专利文献3所示的矩阵结合组合的技术。第1发明中，将∥∥设为表示是被隐匿化的数据的记号，M_n设为将∥1∥，…，∥m_n∥作为基元的集合。第1发明的矩阵/密钥生成装置通过由网络连接的3个以上的矩阵/密钥生成装置构成矩阵/密钥生成系统。矩阵/密钥生成系统在矩阵/密钥生成装置间一边进行数据通信一边进行隐匿计算。另外，矩阵T_n的行和列的数量、向量k_n的要素的数量、值m_n是未被隐匿化的信息，矩阵T_n的要素的每一个、向量k_n的要素的每一个是在矩阵/密钥生成装置之间被隐匿化的信息。矩阵/密钥生成装置具备排序单元、向量生成单元、集合生成单元、矩阵生成单元、密钥生成单元。

排序单元通过和其它矩阵/密钥生成装置的排序单元的隐匿计算，对于n＝0，…，N－1的每一个，在按照向量k_n的要素依旧维持了对应的情况下，将矩阵T_n的行的顺序和向量kn的要素的顺序进行排序，以排序后的矩阵和向量，更新矩阵T₀，…，T_N－1和向量k₀，…，k_N－1。向量生成单元、集合生成单元、矩阵生成单元、密钥生成单元对排序单元更新了的矩阵T₀，…，T_N－1和向量k₀，…，k_N－1进行处理。向量生成单元通过与其它矩阵/密钥生成装置的向量生成单元的隐匿计算，对于n＝0，…，N－1的每一个，以设定x_n[1]＝∥1∥，对于2≤i≤K_n，如果是k_n[i－1]＝k_n[i]，则x_n[i]＝∥x_n[i－1]+1∥，如果是k_n[i－1]≠k_n[i]，则x_n[i]＝∥1∥的方式，生成要素的数量为K_n个，且将要素的每一个隐匿化的向量x_n。集合生成单元通过与其它的矩阵/密钥生成装置的集合生成单元的隐匿计算，对于n＝0，…，N－1的每一个，且对于j＝1，…，K_n每一个，以各基元与一个一个选自集合M_n以外的集合M₀，…，M_N－1的N－1个基元和x_n[j]的组合对应，包含全部的组合量的基元的方式，生成将基元的每一个隐匿化的集合B_n，j。矩阵生成单元通过和其它的矩阵/密钥生成装置的矩阵生成单元的隐匿计算，对于n＝0，…，N－1的每一个，以对于j＝1，…，K_n的全部，只具有集合B_n，j的基元的数量的与T_n[j]相同的行的方式，生成将要素的每一个隐匿化的矩阵Tn'。密钥生成单元通过和其它的矩阵/密钥生成装置的密钥生成单元的隐匿计算，对于n＝0，…，N－1的每一个，以在与矩阵T_n'的和T_n[j]相同的行对应的要素与k_n[j]和集合B_n，j的基元的组合对应，且具有多个与T_n[j]相同的行的情况下，集合B_n，j的基元相互不同的方式，生成将要素的每一个隐匿化的向量k_n'。

本发明的第2发明是不进行隐匿计算，将要素中有重复的向量和结合对象的矩阵转换为要素中无重复的向量和与该向量对应的矩阵的技术。第2发明中，将Mn设为由相互不同的m_n个基元构成的集合，M_n[i]设为集合M_n的第i个基元。另外，将矩阵T₀，…，T_N－1和向量k₀，…，k_N－1作为输入。第2发明的矩阵/密钥生成装置具备向量生成单元、集合生成单元、矩阵生成单元、密钥生成单元。向量生成单元对于n＝0，…，N－1的每一个，以i≠j时，如果是k_n[i]＝kn[j]，则x_n[i]≠x_n[j]的方式，生成将要素的数量为K_n个，且各要素是集合M_n的基元的向量x_n。集合生成单元对于n＝0，…，N－1的每一个，且对于j＝1，…，K_n的每一个，以各基元与一个一个选自集合M_n以外的集合M₀，…，M_N－1的N－1个基元和x_n[j]的组合对应，包含全部的组合量的基元的方式，生成集合B_n，j。矩阵生成单元对于n＝0，…，N－1的每一个，以对于j＝1，…，K_n的全部，只具有集合B_n，j的基元的数量的与T_n[j]相同的行的方式，生成矩阵T_n'。密钥生成单元对于n＝0，…，N－1的每一个，以在与矩阵T_n’的和T_n[j]相同的行对应的要素与k_n[j]和集合B_n，j的基元的组合对应，且具有多个与T_n[j]相同的行的情况下，集合B_n，j的基元相互不同的方式，生成向量k_n’。

发明效果

根据本发明的矩阵/密钥生成系统、矩阵/密钥生成装置，可以将要素上有重复的向量和结合对象的矩阵转换为要素无重复的向量和与该向量对应的矩阵。

附图说明

图1是用于说明阶段计算的概要的图。

图2是表示矩阵的结合的具体例的图。

图3是表示实施例1的矩阵/密钥生成系统的构成例的图。

图4是表示实施例1的矩阵/密钥生成系统及实施例2的矩阵/密钥生成装置的处理流程的图。

图5是表示在按照向量k₀的要素依旧维持了对应的情况下，对隐匿计算中图2所示的矩阵T₀的行的顺序和向量k₀的要素的顺序进行排序的情况的图。

图6是表示对要素被隐匿化的状态的图2所示的向量k₀，k₁，k₂进行了阶段计算的结果的向量x₀，x₁，x₂的图。

图7是表示结合要素被隐匿化的状态的图2所示的矩阵T₀和矩阵T₁的情况的矩阵T₀'、向量k₀'和矩阵T₁'、向量k₁'的例子的图。

图8是表示实施例1变形例的矩阵结合系统的构成例的图。

图9是表示实施例1变形例的矩阵结合系统的处理流程的图。

图10是表示结合图7所示的矩阵T₀'和矩阵T₁'而得的矩阵的图。

图11是表示实施例2、实施例2变形例的矩阵/密钥生成装置的构成例的图。

具体实施方式

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

实施例1

实施例1的说明中，N设为1以上的整数，n设为0以上N－1以下的整数，K_n设为1以上的整数，i和j设为整数，T_n设为K_n行的矩阵，k_n设为要素的数量为K_n个的向量，T_n[j]设为矩阵T_n的第j行，k_n[j]设为向量k_n的第j个要素，m_n设为向量k_n的要素重复的上限数，M_n设为以1，…，m_n为基元的集合，∥∥作为表示是被隐匿化的数据的记号。向量k_n的第j个要素是与矩阵T_n的第j行对应的要素。此外，上限数m_n也可以不是向量k_n的要素实际上重复的数，只要设定为有重复的可能性的最大值即可。

＜矩阵的结合＞

首先，对于表现表的矩阵和表现该矩阵的各行的密钥的列向量及矩阵的结合进行说明。矩阵的结合中，在全部向量k₀，…，k_N－1中具有共同的要素的情况下，结合与共同的要素对应的矩阵T₀，…，T_N－1的行作为1个行。图2表示矩阵的结合的具体例。矩阵T₀，T₁，T₂是成为结合的对象的矩阵。向量k₀，k₁，k₂是表示密钥的列向量。此外，在本说明书中，“矩阵”指表现表的形式，“向量”指表现密钥的形式，因此，矩阵T_n和向量k_n的各要素不需要限制在1个数值，也可以是数值的组合、字符串等。

在此，考虑矩阵T₀和矩阵T₁的结合。表示矩阵T₀的密钥的向量k₀的第1个和第4个要素、表示矩阵T₁的密钥的向量k₁第1个和第2个要素为“1”，是共同的。即，矩阵T₀的第1行和第4行的密钥、矩阵T₁的第1行和第2行的密钥为“1”，是共同的。另外，矩阵T₀的第3行的密钥(向量k₀的第3个要素)、矩阵T1的第3行和第4行的密钥(向量k₁的第3个和第4个要素)为“3”，是共同的。因此，在结合矩阵T₀和矩阵T₁的矩阵中，将结合了矩阵T₀的第1行和矩阵T₁的第1行的结果作为第1行、将结合了矩阵T₀的第1行和矩阵T₁的第2行的结果作为第2行、将结合了矩阵T₀的第4行和矩阵T₁的第1行的结果作为第3行、将结合了矩阵T₀的第4行和矩阵T₁的第2行的结果作为第4行，将结合了矩阵T₀的第3行和矩阵T₁的第3行的结果作为第5行，结合了矩阵T₀的第3行和矩阵T₁的第4行的结果作为第6行。

接着，考虑矩阵T₀和矩阵T₁和矩阵T₂的结合。表示密钥的向量k₀的要素、向量k₁的要素、向量k₂的要素共同的是要素为“1”的向量k₀的第1个和第4个要素、向量k₁的第1和第2的要素、向量k₂的第1的要素。即，密钥共同的是密钥为“1”的矩阵T₀的第1行和第4行、矩阵T₁的第1行和第2行、矩阵T₂的第1行。因此，在结合了矩阵T₀和矩阵T₁和矩阵T₂的矩阵中，将结合了矩阵T₀的第1行和矩阵T₁的第1行和矩阵T₂的第1行的结果设为第1行，将结合矩了阵T₀的第1行和矩阵T₁的第2行和矩阵T₂的第1行的结果设为第2行，将结合了矩阵T₀的第4行和矩阵T₁的第1行和矩阵T₂的第1行的结果作为第3行，将结合了矩阵T₀的第4行和矩阵T₁的第2行和矩阵T₂的第1行的结果设为第4行。

＜结构和算法＞

图3表示矩阵/密钥生成系统的构成例，图4表示矩阵/密钥生成系统的处理流程。矩阵/密钥生成系统具有由网络800连接的3个以上的矩阵/密钥生成装置160，在矩阵/密钥生成装置160间可以进行隐匿计算。各矩阵/密钥生成装置160具备排序单元110、向量生成单元120、集合生成单元130、矩阵生成单元140、密钥生成单元150、记录单元190。本实施例中，矩阵T_n的行和列的数量、向量k_n的要素的数量、以及值m_n是未被隐匿化的信息，矩阵T_n的要素每一个、向量k_n的要素的每一个是在矩阵/密钥生成装置160之间被隐匿化的信息。即，矩阵T_n的要素的每一个、向量k_n的要素的每一个的断片分散记录于多个矩阵/密钥生成装置的记录单元190。此外，“断片”即为只要了解规定的数量的断片，则可以恢复基元的值的数据，非专利文献4中称为“分散数据”。

排序单元110通过和其它矩阵/密钥生成装置160的排序单元110的隐匿计算，对于n＝0，…，N－1每一个整数，在按照向量k_n的要素依旧维持对应的情况下，将矩阵T_n的行的顺序和向量k_n的要素的顺序进行排序，以排序后的矩阵和向量，更新矩阵T₀，…，T_N－1和向量k₀，…，k_N－1(S110)。此外，对于通过隐匿计算进行排序处理的方法，具体在非专利文献1所示。另外，排序即可以是升序也可以是降序。图5表示通过隐匿计算，在按照向量k₀的要素依旧维持对应的情况下，将图2所示的矩阵T₀的行的顺序和向量k₀的要素的顺序进行了排序的情况。在该例中，值越小的密钥(向量k₀的要素)，顺序越提前(上)。向量生成单元120、集合生成单元130、矩阵生成单元140、密钥生成单元150对排序单元110更新了的矩阵T₀，…，T_N－1和向量k₀，…，k_N－1进行处理。

向量生成单元120通过和其它的矩阵/密钥生成装置160的向量生成单元120的隐匿计算，对于n＝0，…，N－1的每一个整数，以设定x_n[1]＝∥1∥，对于2≤i≤K_n，如果是k_n[i－1]＝k_n[i]，则x_n[i]＝∥x_n[i－1]+1∥，如果是k_n[i－1]≠k_n[i]，则x_n[i]＝∥1∥的方式，生成要素的数量为Kn个、且将要素的每一个隐匿化的向量x_n(S120)。该处理与非专利文献2所示的阶段计算相同。另外，将值隐匿化的技术在非专利文献4等中示出。图6表示排序单元110对要素被隐匿化的状态的图2所示的向量k₀，k₁，k₂排序后的向量k₀，k₁，k₂、和向量生成单元120对排序后的向量k₀，k₁，k₂进行了阶段计算的结果即向量x₀，x₁，x₂。

集合生成单元130通过和其它的矩阵/密钥生成装置160的集合生成单元130的隐匿计算，对于n＝0，…，N－1的每一个整数，且对于j＝1，…，K_n的每一个，以各基元与一个一个选自集合M_n以外的集合M₀，…，M_N－1的N－1个基元和x_n[j]的组合对应、包含全部的组合量的基元的方式，生成将基元的每一个隐匿化的集合B_n，j(S130)。例如，如(M₀的基元，…，M_n－1的基元，x_n[j]，M_n+1的基元，…，M_N－1的基元)那样作出组合，只要为1个基元即可。另外，也可以将由组合决定性地计算的值(以与组合1对1对应的值，换句话说，以在不同组合时一定成为不同的计算值的方式求出的值)作为基元。上述的“与组合对应”即为用于表示不仅包含组合自身，而且包含由组合决定性地计算的值的表现。

例如，使用图6所示的向量k₀、向量k₁、向量k₂说明集合生成单元130的处理。向量k₀中，要素中具有2个∥1∥，其它的要素分别是一个一个，所以向量k₀中要素重复的上限数m₀为2。同样研究要素重复的上限数，向量k₁中要素重复的上限数m₁为2，向量k₂中要素重复上限数m₂是3。因此，是集合M₀＝{∥1∥，∥2∥}、集合M₁＝{∥1∥，∥2∥}、集合M₂＝{∥1∥，∥2∥，∥3∥}。首先，表示结合矩阵T₀和矩阵T₁的处理的例子。因x₀[1]＝∥1∥、集合M₁＝{∥1∥，∥2∥}，所以x₀[1]和集合M₁的基元的组合为(∥1∥，∥1∥)和(∥1∥，∥2∥)。因此，集合B_0，1＝{(∥1∥，∥1∥)，(∥1∥，∥2∥)}。另外，例如，x₀[2]＝∥2∥、集合M₁＝{∥1∥，∥2∥}，所以x₀[2]和集合M₁的基元的组合为(∥2∥，∥1∥)和(∥2∥，∥2∥)，集合M₀的基元和x₁[4]的组合是(∥1∥，∥2∥)和(∥2∥，∥2∥)。对于其它的组合也同样进行即可。结合矩阵T₀和矩阵T₁和矩阵T₂的处理的情况下，为3个组合。x₀[1]＝∥1∥、集合M₁＝{∥1∥，∥2∥}、集合M₂＝{∥1∥，∥2∥，∥3∥}，所以x₀[1]和集合M₁的基元和集合M₂的基元的组合为(∥1∥，∥1∥，∥1∥)，(∥1∥，∥1∥，∥2∥)，(∥1∥，∥1∥，∥3∥)，(∥1∥，∥2∥，∥1∥)，(∥1∥，∥2∥，∥2∥)，(∥1∥，∥2∥，∥3∥)。因此，集合B_0，1＝{{(∥1∥，∥1∥，∥1∥)，(∥1∥，∥1∥，∥2∥)，(∥1∥，∥1∥，∥3∥)，(∥1∥，∥2∥，∥1∥)，(∥1∥，∥2∥，∥2∥)，(∥1∥，∥2∥，∥3∥)}}。

矩阵生成单元140通过和其它的矩阵/密钥生成装置160的矩阵生成单元140的隐匿计算，对于n＝0，…，N－1的每一个整数，以对于j＝1，…，K_n的全部，只具有集合B_n，j的基元的数量的与T_n[j]相同的行的方式，生成将要素的每一个隐匿化的矩阵T_n'(S140)。图7中表示结合要素被隐匿化的状态的图2所示的矩阵T₀和矩阵T₁的情况的矩阵T₀'，向量k0'和矩阵T₁'，向量k₁'的例子。结合矩阵T₀和矩阵T₁的处理的情况下，集合B_0，1的基元的数量为2，所以将与T₀[1]相同的行作出2行。同样，集合B_0，2，B_0，3，B_0，4，B_0，5的基元的数量也为2，所以分别将相同的行每个作出2行。因此，矩阵T₀'为相同的行每个存在2行的10行的矩阵。另外，矩阵T₁'也为相同的行每个存在2行的8行的矩阵。

密钥生成单元150通过和其它的矩阵/密钥生成装置160的密钥生成单元150的隐匿计算，对于n＝0，…，N－1的每一个整数，以与矩阵T_n’的和T_n[j]相同的行对应的要素与k_n[j]和集合B_n，j的基元的组合对应、且具有多个与T_n[j]相同的行的情况下，集合B_n，j的基元相互不同的方式，生成将要素的每一个隐匿化的向量k_n'(S150)。矩阵T₀'为10行，矩阵T₁'为8行，所以向量k₀'的要素是10个，向量k₁'的要素是8个。T₀'[1]和T₀'[2]均为T₀[1]，所以k₀'[1]为(k₀[1]，B_0，1的1个基元)，k₀'[2]为(k₀[1]，B_0，1的另外的基元)。图7中，k₀'[1]＝(∥1∥，(∥1∥，∥1∥))、k₀'[2]＝(∥1∥，(∥1∥，∥2∥))。即，与矩阵T₀'的和T₀[1]相同的行对应的要素(k₀'[1]和k₀'[2])与k₀[1]和集合B_0，1的基元的组合对应。而且，因为具有多个与T₀[1]相同的行，所以集合B_0，1的基元以相互不同的方式选择。

此外，密钥生成单元150的说明中的“与组合对应”也是用于表示不仅包含组合自身，还包含由组合决定性地计算的值(与组合1对1对应的值)的表现。例如，将f作为由组合决定地计算值的函数，也可以设为k₀'[1]＝∥f(∥1∥，(∥1∥，∥1∥))∥。但是，f是可隐匿计算的函数。

如从图7可知，无论向量k₀'还是向量k₁'在向量内均无要素的重复。因此，根据实施例1的矩阵/密钥生成装置，可以将要素中有重复的向量和结合对象的矩阵转换为要素中无重复的向量和与该向量对应的矩阵。

[变形例]

图8表示矩阵结合系统的构成例，图9表示矩阵结合系统的处理流程。矩阵结合系统具有由网络800连接的3个以上的矩阵结合装置100，在矩阵结合装置100彼此之间进行隐匿计算。矩阵结合装置100具备矩阵/密钥生成装置160和结合部170。矩阵/密钥生成装置160及矩阵/密钥生成步骤S160与实施例1中说明的内容相同。

结合部170通过和其它的矩阵结合装置100的结合部170的隐匿计算，在全部向量k₀'，…，k_N－1'中具有共同的要素的情况下，结合与共同的要素每一个对应的矩阵T₀'，…，T_N－1'的行作为一行，生成将要素的每一个隐匿化的矩阵(S170)。该处理只要使用非专利文献3记载的矩阵结合的技术即可。图10表示结合图7所示的矩阵T₀'和矩阵T₁'而得的矩阵。可知图10所示的矩阵为将结合了图2所示的矩阵T₀和矩阵T₁的矩阵的各要素隐匿化的矩阵。此外，至求出矩阵T₀'，…，T_N－1'和向量k₀'，…，k_N－1'的处理中，有可能知道行间的对应关系，但隐匿计算中的矩阵的结合时，只要随机置换行，则可以不知道行间的对应关系。

非专利文献3的矩阵结合的技术在将输入的表的记录数的总和(以矩阵形式表现的情况为行数的总和)设为Q时，通信量为O(Q·logQ)。在本发明的矩阵/矩阵结合系统的情况下，在将行数的总和设为Q、重复数的上限设为P时，通信量可以为O(PQ·logQ)。在密钥上有重复的情况下，一般处理以P的乘方的等级增加，本发明的情况因为是P的1次方的等级，所以能够实现可以减少非专利文献3的通信量的优点。

实施例2

实施例1中研究了隐匿计算的情况，但本发明的考虑方式不限定于隐匿计算也可以利用。如果不是隐匿计算，则不需要使用多个矩阵/密钥生成装置。利用1台的矩阵/密钥生成装置，可以将表示要素中有重复的密钥的向量和结合对象的矩阵转换为表示要素中无重复的密钥的向量和与该向量对应的矩阵。在此，实施例2说明无隐匿化的情况。

实施例2中，设N为1以上的整数，n为0以上N－1以下的整数，K_n为1以上的整数，i和j为整数，T_n为K_n行的矩阵，k_n为要素的数量为K_n个的向量，T_n[j]为矩阵T_n的第j行，k_n[j]为向量k_n的第j的要素，m_n为向量k_n的要素重复的上限数，矩阵T₀，…，T_N－1和向量k₀，…，k_N－1作为输入。另外，M_n设为由M_n[i]＝i的m_n个基元构成的集合。

图11表示实施例2的矩阵/密钥生成装置的构成例，图4表示实施例2的矩阵/密钥生成装置的处理流程的例子。矩阵/密钥生成装置260具备排序单元210、向量生成单元220、集合生成单元230、矩阵生成单元240、密钥生成单元250。排序单元210对于n＝0，…，N－1的每一个整数，在按照向量k_n的要素依旧维持对应的情况下，对矩阵T_n的行的顺序和向量k_n的要素的顺序进行排序，以排序后的矩阵和向量，更新矩阵T₀，…，T_N－1和向量k₀，…，k_N－1(S210)。向量生成单元220、集合生成单元230、矩阵生成单元240、密钥生成单元250对排序单元210更新了的矩阵T₀，…，T_N－1和向量k₀，…，k_N－1进行处理。

向量生成单元220对于n＝0，…，N－1的每一个整数，以设定x_n[i]＝1，对于2≤i≤K_n，如果是k_n[i－1]＝k_n[i]，则x_n[i]＝x_n[i－1]+1，如果是k_n[i－1]≠k_n[i]，则x_n[i]＝1的方式，生成向量x_n(S220)。集合生成单元230对于n＝0，…，N－1的每一个，且对于j＝1，…，K_n的每一个，以各基元与一个一个选自集合M_n以外的集合M₀，…，M_N－1的N－1个基元和x_n[j]的组合对应、且包含全部的组合量的基元的方式，生成集合B_n，j(S230)。矩阵生成单元240对于n＝0，…，N－1的每一个整数，以对于j＝1，…，K_n的全部，仅具有集合B_n，j的基元的数量的与T_n[j]相同的行的方式，生成矩阵T_n'(S240)。密钥生成单元250对于n＝0，…，N－1的每一个整数，在与矩阵T_n’的和T_n[j]相同的行对应的要素与k_n[j]和集合B_n，j的基元的组合对应，且具有多个与T_n[j]相同的行的情况下，以集合B_n，j的基元相互不同的方式，生成向量k_n'(S250)。

各处理因仅不是隐匿计算这点与实施例1不同，所以在输入图2所示的矩阵T₀，T₁和向量k₀，k₁的情况下，所输出的矩阵T₀'，T₁'和向量k₀'，k₁'为图7的各要素未被隐匿化的矩阵和向量。因此，根据实施例2的矩阵/密钥生成装置，可以将要素中有重复的向量和结合对象的矩阵转换为要素中无重复的向量和与该向量对应的矩阵。

[变形例]

本变形例中，导出实施例2的上位概念。本变形例中，省略排序单元210，将向量生成单元220变更为向量生成单元220'。另外，本变形例中，不是将M_n限定为M_n[i]＝i的集合，而将M_n设为由相互不同的m_n个的基元构成的集合，将M_n[i]作为集合M_n的第i的基元。本变形例的矩阵/密钥生成装置的功能构成在图11中表示，处理流程在图4中表示。本变形例中，向量生成单元220'、集合生成单元230、矩阵生成单元240、密钥生成单元250对所输入的矩阵T₀，…，T_N－1和向量k₀，…，k_N－1进行处理(不进行排序步骤S210)。

向量生成单元220'对于n＝0，…，N－1每一个整数，以在i≠j时，如果是k_n[i]＝k_n[j]，则为x_n[i]≠x_n[j]的方式，生成要素的数量为K_n个，各要素为集合M_n的基元的向量x_n。变形例2的向量生成单元220的处理是满足事先将向量k_n排序的情况下可以利用的向量生成单元220'的处理的条件的一个处理。因此，本变形例的发明是实施例2的发明的上位概念。

如果这样生成向量x_n，则不存在集合生成单元230、矩阵生成单元240、密钥生成单元250的处理是否被排序造成的不同，所以本变形例的矩阵/密钥生成装置也可以将要素中有重复的向量和结合对象的矩阵转换为要素中无重复的向量和与该向量对应的矩阵。

[程序、记录介质]

上述的各种处理不仅按照记载在时间序列上执行，而且也可以根据执行处理的装置的处理能力或需要并列或分别执行。另外，不言而喻在不脱离本发明的宗旨的范围内可适当变更。

另外，通过计算机实现上述的构成的情况下，各装置应该有的功能的处理内容通过程序记述。而且，通过在计算机中执行该程序，在计算机上实现上述处理功能。

记述该处理内容的程序可以记录在利用计算机可读取的记录介质上。作为在计算机可读取的记录介质，例如也可以是磁记录装置、光盘、光磁记录介质、半导体存储器等。

另外，该程序的流通例如通过出售、转让、借贷记录了该程序的DVD、CD－ROM等便携型记录介质而进行。另外，也可以作为通过将该程序存储在服务器计算机的存储装置，经由网络，从服务器计算机向其它的计算机转发该程序，使该程序流通的构成。

执行这种程序的计算机例如首先暂时在本身的存储装置中存储记录于便携型记录介质的程序或从服务器计算机转发的程序。而且，在处理执行时，该计算机读取存储于自身的记录介质的程序，执行遵循读取的程序的处理。另外，作为该程序的另外的执行方式，计算机也可以从便携型记录介质直接读取程序，执行遵循该程序的处理，进而也可以每次从服务器计算机对该计算机转发程序时，逐次执行遵循获取的程序的处理。另外，也可以作为下述构成，即不进行从服务器计算机到本计算机的程序的转发，而仅根据其执行指示和结果取得实现处理功能的所谓ASP(Application Service Provider)型的服务，执行上述的处理。此外，本方式的程序中包含供计算机进行的处理之用的信息即根据程序的信息(不是对计算机的直接指令，但具有规定计算机的处理的性质的数据等)。

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

产业上的可利用性

本发明可以用于使用计算机的统计数据的处理或分析。

标记说明

100矩阵结合装置 110，210排序单元

120，220向量生成单元 130，230集合生成单元

140，240矩阵生成单元 150，250密钥生成单元

160，260矩阵/密钥生成装置170结合部

190记录单元 800网络