シャミアの秘密分散法を実装してみた

これは何?

秘密分散法の(k,n)しきい値法の一つである，シャミアの秘密分散法を実装してみました。
前記事でTODOにしていたやつの一つです。

---

秘密分散法の中のシャミアの秘密分散法の位置づけ

プライバシー保護データマイニング」特集号 秘密分散法を用いた秘密計算
大原 一真*によると，秘密分散法は以下の3種類があります。

1. (k,n)しきい値法: ざっくり書くとn個のシェアのうち，k個集まれば復元できるようになるもの。
2. (n,n)下方型秘密分散法: n個のシェアすべてが復元に必要。
3. 複製型秘密分散法: (n,n)秘密分散法のシェアを一人に複数個割り当てることで，(k,n)しきい値法として扱えるようにするもの。

シャミアの秘密分散法は1の(k,n)しきい値法にあたります。

---

シャミアの秘密分散法のしくみ(イメージ)

• 論文A. Shamir, “How to share a secret,” Commun. ACM,vol. 22, no. 11, pp. 612–613, 1979.
• Wikipedia(わかりやすかった)
  を貼っておきます。

自分の理解では肝となるのはラグランジュ補完です。
シャミアの秘密分散法では，

1. 秘密データ +「シェアの数(k)-1」個の乱数を使った多項式f(x)として表現する。e.g. f(x) = 1234 + 166x + 94x^2
2. 多項式を通る点(x,y)をn個用意する。これがシェアが持つ情報になる。
3. ラグランジュ補完により，k個の点があれば元の多項式が復元できるのでf(0)が秘密データになる。

という流れで秘密データの分散と複合を行っています。
通常のラグランジュ補完では，複数の(x,y)を通る関数を探すのだと思いますが，シャミアの秘密分散法では先に関数を作り，それを通る点をシェアとし，シェアから関数を再度生成することで秘密情報が複合できるのです。

---

実際にやってみた

# coding: utf-8
"""_summary_
https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing
"""
import random


def create_random_coefficients(k: int) -> list[int]:
    """_summary_
    create random coefficients for the polynomial
    a1, a2, ..., ak-1

    Args:
        k int: number of shares

    Returns:
        list[int]: random coefficients
    """
    return [random.randint(1, 100) for _ in range(k - 1)]


def print_polynomial(an_list: list[int]) -> None:
    """_summary_
    for debugging, print polynomial

    Args:
        an_list (_type_): _description_
    """
    for i in range(len(an_list)):
        if i == 0:
          print(f"f(x) = {an_list[0]}", end="")
        else:
          print(f" + {an_list[i]}x^{i}", end="")
    print()
    return


def print_D_n_list(D_n_list: list[int]) -> None:
    """_summary_
    for debugging, print D_n_list

    Args:
        D_n_list (_type_): _description_
    """
    for i in range(len(D_n_list)):
        print(f"D_{i} = {D_n_list[i]}")
    return


def create_points(x: int, an_list) -> list[int]:
    """_summary_

    Args:
        x (_type_): _description_
        an_list (_type_): _description_

    Returns:
        (x, fx) = (x, sum(a0 + a1x + a2x^2 + ... + ak-1x^(k-1)))
    """
    return [x, sum([an_list[i] * x**i for i in range(len(an_list))])]


def cal_lagrange_basis_for_polynomial(D_k_list: list[list[int]]) -> int:
    """_summary_
    Lagrange basis polynomial(ラグランジュ補完)

    Args:
        D_n_list list[int]: list of points D_n

    Returns: f(0) = a0 int: secret data.
    NOTE: f(x)でラグランジュ補完を求めても必要なのはf(0)だけなので最初からf(0)だけ求める
    """
    # l_0(0), l_1(0), ... l_k-1(0)
    l_k_list = []
    for j in range(len(D_k_list)):
        for m in range(len(D_k_list)):
            if m == j:
                continue
            if "tmp" not in locals():
                tmp = (0 - D_k_list[m][0]) / (D_k_list[j][0] - D_k_list[m][0])
            else:
                tmp = tmp * (0 - D_k_list[m][0]) / (D_k_list[j][0] - D_k_list[m][0])
        l_k_list.append(tmp)
        del tmp

    # calculate f(0) = a0
    f0 = 0.0
    for k in range(len(D_k_list)):
        f0 += D_k_list[k][1] * l_k_list[k]

    return f0


def main():
    n = 6  # number of shares
    k = 3  # number of shares required to reconstruct the secret
    test_score_list = [10, 20, 30, 40]  # example secret data

    for a0 in test_score_list:
        # -----Preparation-----

        # create random coefficients a1, a2, ..., ak-1
        coefficients = create_random_coefficients(k)
        an_list = [a0] + coefficients
        print_polynomial(an_list)

        # create points D(x-1) = (x, f(x))
        D_x_list = []
        # NOTE: D(0) = (1, a0)，D(1) = (2, a0 + a1 * 2)
        for x in range(n):
            D_x_list.append(create_points(x + 1, an_list))
        print_D_n_list(D_x_list)

        # -----Reconstruction-----
        # select k random points(D_x)
        random_points = random.sample(D_x_list, k)
        print(f"random_points D: {random_points}")

        # calcurate f(0) = a0 with Lagrange basis polynomial
        f0 = cal_lagrange_basis_for_polynomial(random_points)
        print(f"f(0) = {f0} = a0 = {a0}")
        print("----------DONE----------")


if __name__ == "__main__":
    main()

割り算をする関係上，答えが整数でなく少数になってしまいますが，秘密情報の復元ができることが確認できました。
(int型にキャストしても良いのだけど)

python3 shamir_secret_sharing.py
f(x) = 10 + 44x^1 + 51x^2
D_0 = [1, 105]
D_1 = [2, 302]
D_2 = [3, 601]
D_3 = [4, 1002]
D_4 = [5, 1505]
D_5 = [6, 2110]
random_points D: [[2, 302], [3, 601], [5, 1505]]
f(0) = 10.0 = a0 = 10
----------DONE----------
f(x) = 20 + 63x^1 + 76x^2
D_0 = [1, 159]
D_1 = [2, 450]
D_2 = [3, 893]
D_3 = [4, 1488]
D_4 = [5, 2235]
D_5 = [6, 3134]
random_points D: [[1, 159], [6, 3134], [3, 893]]
f(0) = 20.0 = a0 = 20
----------DONE----------
f(x) = 30 + 44x^1 + 53x^2
D_0 = [1, 127]
D_1 = [2, 330]
D_2 = [3, 639]
D_3 = [4, 1054]
D_4 = [5, 1575]
D_5 = [6, 2202]
random_points D: [[3, 639], [1, 127], [5, 1575]]
f(0) = 30.0 = a0 = 30
----------DONE----------
f(x) = 40 + 86x^1 + 88x^2
D_0 = [1, 214]
D_1 = [2, 564]
D_2 = [3, 1090]
D_3 = [4, 1792]
D_4 = [5, 2670]
D_5 = [6, 3724]
random_points D: [[5, 2670], [3, 1090], [4, 1792]]
f(0) = 40.0 = a0 = 40

---

感想

最初は全然意味がわからなかったのですが，ラグランジュ補完の意味に気づいた時に闇に電流が走りました。