多値化法による秘匿四則演算及びその秘匿部分一致検索への応用

摘要

栗原らは秘密分散を計算量の少ないXOR演算のみで実現する手法（XOR法）を提案したが，それは四則演算に対する準同型性を持たないため，秘匿演算に対応できない．そこで，XOR．法をもとに，多値のデータを扱う手法（多値化法）に拡張する．さらに，その多値化法によって秘匿四則演算を実現できる手法を提案する．秘密分散法を用いた秘匿四則演算は，加算準同型性と定数倍準同型性があれば神宮らが提案した次数を変化させずに四則演算を行える手法（TUS法）によって実現できる．ただし，この手法には秘密情報にOを含む場合，秘密情報が漏洩するため，秘密情報にOを含まないという条件がある．多値化法はXOR法と同様に秘密情報を分割して秘密分散を行うが，それにTUS法をそのまま適用すると，分割された部分秘密情報にOを含むとその部分秘密情報が漏洩する．そこで，本論文では多値化法にコンパクト法を適用しても部分秘密情報が漏洩しない手法を提案し，その応用として秘匿部分一致検索を実現する．