Scalaで(k,n)しきい値法の秘密分散を実装してみた

#前回の実装
- [ScalaでRSA暗号を実装してみた](https://qiita.com/Tenn/items/bd90d0399c039481a672)-

#(k,n)しきい値法による秘密分散
秘密情報**s**を**n**個のシェアという単位に分割して、秘密を分散することで隠す方法。
解読者は**k**（しきい値）個以上のシェアを集めることで秘密**s**を復元できるが、**k**個未満のシェアからは秘密が一切漏れない。例えば**k=3**,**n=5**なら秘密**s**を5個のシェアとして分割し、そのシェアを3個以上集めると、秘密**s**が復元できる。
分散したシェアで演算した結果が秘密同士の演算結果になるので、秘密計算に活用できる。

#実装

まずは(k,n)しきい値法に用いる剰余演算とべき乗計算を実装する。

```scala
package secretSharing                                                                                                                                         
object utils {
    def power(x:Int,p:Int):Int = if(p==0) 1 else x * power(x,p-1)
    def mod(x:Int,power:Int,modulo:Int):Int = (1 to power).foldLeft(1)((a ,i) => a * ( x % modulo + modulo ) % modulo )
    def modInv(a:Int,modulo:Int) = {
        def extEuclid(a:Int,b:Int):(Int,Int) = if (b==0) (1,0) else ((t:(Int,Int)) => (t._2,t._1 - a/b * t._2))(extEuclid(b,a%b))
        mod(extEuclid(a,modulo)._1,1,modulo)
    }
}
```

`power`(べき乗)メソッドは標準ライブラリの`scala.math.pow`だと返り値が`Double`で、整数に収まらなくなるので返り値が`Int`のものを用意している。`mod`は剰余演算、`modInv`は逆元を求めている。この二つについて詳しくは参考文献や[ScalaでRSA暗号を実装してみた](https://qiita.com/Tenn/items/bd90d0399c039481a672)を参照。


次にメインとなる秘密分散のプログラムを実装する。
秘密分散はランダムな係数を選んで**k-1**次多項式**f**を作って**x**にn個の値を入れ、その値をシェアとし秘密分散する。計算後に係数は破棄する。
シェアをk個以上集めたらラグランジュ補間を用いて、破棄された係数を復元する。係数が復元されたら、**f**が分かるので**x=0**を代入することで1次以上が消えるので、0次の項である秘密**s**を復元するという流れだ。

```scala
package secretSharing                                                                                                                                         
object scheme {
    import secretSharing.utils._
    def secretShare (secret:Int,k:Int,n:Int,prime:Int,coeffs:Seq[Int]) = {
        def distFun(x:Int):Int = secret + mod((1 to k-1).foldLeft(0)((sum,l) => sum + coeffs(l)* power(x,l)),1,prime)
        for (i <- 1 to n) yield (i,distFun(i))
    }

    def restore (shares:Seq[(Int,Int)],sharesId:Seq[Int],prime:Int) = {
        def restFun(x:Int,sharesId:Seq[Int]):Int = mod( sharesId.foldLeft(0)((sum,j)=> sum + interpolation(x,j,sharesId) * shares(j)._2 ),1,prime )
        def interpolation(x:Int,j:Int,sharesId:Seq[Int]) = ( for(l <- sharesId if l != j) yield l ).foldLeft(1){
            (a,l) =>  a * ((x-shares(l)._1) * modInv( shares(j)._1-shares(l)._1,prime))
        }
        restFun(0,sharesId)
    }
    def addShares(s1:Seq[(Int,Int)],s2:Seq[(Int,Int)]) = (0 to s1.size-1).map(x => (s1(x)._1,s1(x)._2 + s2(x)._2))
}
```

それぞれのメソッドの役割について説明する。

`secretShare`
秘密分散する多項式**f**を構成するメソッド。コレクションに格納されたタプル表現のシェアを返す。タプルはシェアidとシェアのペアを格納する。係数のコレクション`coeffs`は実装の都合で0次式の係数として0番目に0が入っている。総和、総乗は`foldLeft`を使ったコレクションの畳み込みで実装している。

`restore`
係数が破棄されたことで分からなくなった多項式**f**を復元するメソッド。多項式の計算結果を返す。`sharesId`は入手できたシェアが`shares`の何番目にあるかをコレクションで与える。`interpolation`はラグランジュ補間で、係数を復元するのに利用する。

`addShares`
秘密**s1**と秘密**s2**のシェア同士を足し算する際に使うメソッド。


#テスト
実装したプログラムをテストする。秘密分散して復元するのに成功したか、秘密同士の加算結果とシェア同士の加算結果が同じかで実装できたかを確認する。(`prime`は定数を与えているが本来は**max(secret,n) < prime**である必要がある。)
係数`coeffs`には乱数で値を与える。今回分散したシェアのうち手に入ったのは１、３、５番目なので`restore`の引数`sharesId`には`Seq(0,2,4)`を与える。

```scala
object Main extends App{                                                                                                                                          import scala.util.Random
    import secretSharing.utils._
    import secretSharing.scheme._

    val secret1:Int = 11
    val secret2:Int = 13
    val k:Int = 3
    val n:Int = 5
    val prime:Int = 17
    val coeffs1:Seq[Int] = Seq(1,Random.nextInt(100000),Random.nextInt(100000))
    val coeffs2:Seq[Int] = Seq(1,Random.nextInt(100000),Random.nextInt(100000))

    val shares1 = secretShare(secret1,k,n,prime,coeffs1)
    val result1:Int = restore(shares1,Seq(0,2,4),prime)

    val shares2 = secretShare(secret2,k,n,prime,coeffs2)
    val result2:Int = restore(shares2,Seq(0,2,4),prime)

    val secret3:Int = mod(secret1 + secret2,1,prime)
    val result3:Int = restore(addShares(shares1,shares2),Seq(0,2,4),prime)

    println("----------result1---------")
    println(s"secret1 = $secret1")
    println(s"result1 = $result1")

    println("----------result2---------")
    println(s"secret2 = $secret2")
    println(s"result2 = $result2")

    println("------result1+result2------")
    println(s"secret1 + secret2 = $secret3")
    println(s"result1 + result2 = $result3")

}
```
実行結果は以下のようになる

```
----------result1---------
secret1 = 11
result1 = 11
----------result2---------
secret2 = 13
result2 = 13
------result1+result2------
secret1 + secret2 = 7
result1 + result2 = 7
```

確かに秘密と分散した秘密を復元した結果が同じになっている。またシェア同士の加算は秘密同士を加算したのと同じ結果であることが分かる。
加算結果の7というのは`prime`を法としているので`result1+result2 = result3 = 24 `を17で割った余り7である。

#まとめ
- 秘密分散が秘密計算に利用できることを確認した。
- Scalaだと関数の単純処理をまとめやすいので、定式の構造を保ったまま実装できたのではないかと思う。

#参考文献
- IPUSIRON 「暗号技術のすべて」2017
- 瀬良 和弘、水島 宏太、河内 崇、麻植 泰輔、青山 直紀　「実践Scala入門」2018
- [The Scala Programming Language](https://www.scala-lang.org/)
- [よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方](http://drken1215.hatenablog.com/entry/2018/06/08/210000)
- [拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)