(n,n)しきい値法の情報漏れ耐性

はじめに

秘密分散法はセキュリティ技術の一つで，情報の秘匿化においてかなり基礎的な理論で構成されています．この分野の研究で情報漏れに対する耐性は，注目されている研究の一つで，暗号系の中で有名な国際会議「CRYPTO」でも毎年この研究に関する論文が発表されています．
私も所属している研究室でこの分野の研究を行っています．これまでの研究成果をなるべく専門用語を用いないように書いていこうと思います．

秘密分散法

秘密分散法は秘密情報を分散管理する手法です．このとき分散した後の情報を一般にシェアと呼びます．例えばメッセージを秘密裏に送受信するとき，実際には分散したシェアを送受信することで，送信された情報を見られても，もとのメッセージはわからないということができるようになります．ただし，もちろん受信側ではもとのメッセージが復元できるようにシェアを設定する必要があります．
この過程を簡単に説明します．まず秘密情報を有限体$\mathbb{F}_{p}$上の整数に符号化します．ただし$p$は素数です．有限体についての詳しい説明は省きますが，体についての詳しい説明は

ガロア理論12講 概念と直観でとらえる現代数学入門(加藤 文元,2022)

に載っているので興味があれば，調べてみてください．ここでは$\mathbb{F}_{p}=\lbrace0,1,\ldots,p-1\rbrace$となっていて，四則演算が$p$の剰余演算(モジュロ演算)で定義することで，演算が集合上で閉じているという理解で十分です．ここで符号化された整数値を$s$として，また$s$を分割する数，つまりシェアの数を$n$とします．$n=3$のときのシェアの生成過程のイメージはこんな感じです．

(n,n)しきい値法

秘密分散法の一例に$(t,n)$しきい値法というものがあります．この方法ではしきい値$t$個以上のシェアが集まったときに秘密情報が復元できるようにシェアを生成します．このうち最も簡単な例が$(n,n)$しきい値法，つまり全てのシェアが集まったときにのみ秘密情報が復元されます．
このときのシェアの生成方法は，シェア$X_1\text{～}X_{n-1}$は$\mathbb{F}_{p}$上の一様乱数によって生成します．そして最後のシェアは$$X_n=s-\sum_i^{n-1}X_i$$に従って生成します．こうすることで受信側では$\sum_i^nX_i$を計算することで復元することができる．
この手法に対して全てのシェアから1ビットの情報漏れが起こったときに秘密情報に関する情報がどの程度漏れるのかを考えます．
これを計算するコードをPythonで実装するとこのようになります．
このコードの出力は異なる二つの秘密情報間の統計的距離の差です．

#-------01/2-------#
def mapping(share):
    leakage = []
    for c in share:
        x = []
        for j in range(len(c)):
            if(c[j] > p/2):
                x.append(1)
            else:
                x.append(0)
        leakage.append(x)
    return leakage

#-------0/1/2-------#
# def mapping(share):
    # leakage = []
    # for c in share:
    #     x = []
    #     for j in range(len(c)):
    #         if(c[j] < p/3):
    #             x.append(0)
    #         elif(c[j] < 2*p/3):
    #             x.append(1)
    #         else:
    #             x.append(2)
    #     leakage.append(x)
    # return leakage

import itertools
import pandas as pd
import numpy as np

#参加者数
n = 5
#有限体のサイズ
p = 3

#leakageの集合
leakages = []

#leakageの全列挙
pat = []
nums = [0,1]
for c in itertools.product(nums, repeat = n):
    pat.append(list(c))

nums = range(p)
#print(pat)

for i in range(p):
    #secret
    s = i
    
    #shareの集合
    share = []
    for c in itertools.product(nums, repeat = n - 1):
        x = []
        sum_x = 0
        for j in range(n - 1):
            x.append(c[j])
            sum_x = sum_x + c[j]
        x.append((s - sum_x) % p)
        share.append(x)
        
    #leakageの生成
    leakage = mapping(share)
    
    #share１つごとの確率
    pr = p ** (1 - n)
    
    #leakageの全パターンの個数カウント
    counter = []
    for j in range(len(pat)):
        counter.append(leakage.count(pat[j]))  
    
    #print(counter)
    
    #leakageの全パターンの確率計算
    leakage = []
    for j in range(len(counter)):
        leakage.append(pr * counter[j])
    leakages.append(leakage)

#secretを固定したときの統計距離
def SD(x,y):
    ans = 0
    for i in range(len(x)):
        ans = ans + abs(x[i] - y[i])
    return ans

#全てのsecretの統計距離
def SD_array(x):
    ans = []
    for i in range(len(x)):
        ans0 = []
        for j in range(len(x)):
            ans0.append(SD(x[i], x[j]))
        ans.append(ans0)
    return ans

index = []
for i in range(p):
    index.append("s = "+str(i))
df = pd.DataFrame(SD_array(leakages), index=index, columns=index)
print(df)

#np.amax(SD_array(leakages))

コードのファイルは以下のGithubのページにも載せてあります
(追記：Pythonでは計算速度が出なかったためC++で書き直しました．同様にGithubにおいておきます．)
https://github.com/h28a3/n-n_threshold_scheme

情報漏れが起こるとは

ここでいう情報漏れとは全てのシェアから1ビットの情報漏れのことを指しています． 例えばシェアが偶数のときに0，奇数のときに1が漏れる状況は，シェアの最終ビットが漏れることを意味している． ただしここでシェアの実際の値と漏れる値には本質的な関係はなく，ただ漏れる値とその値が漏れるシェアの種類の数だけが本質的に関係している． またそれぞれの漏れる値を与えるシェアの種類の数は半数に最も近いときが最も情報漏れが大きいことを前提としている． 私の研究ではこのことをテーマに行っている． 興味があればご連絡ください．