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

#前回の実装

• ScalaでRSA暗号を実装してみた-

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

#実装

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

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暗号を実装してみたを参照。

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

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)を与える。

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
• よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方
• 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜