概要

準同型暗号を用いて、暗号文上で和や積の演算を行なったりできますが、準同型暗号が苦手としている演算の１つが比較演算です。
もちろん、暗号文が簡単に比較できてしまえば、挟み込みなどによって値の特定ができてしまうのでこれは当たり前といえば当たり前です。
しかしながら、実際のアプリケーションでは、決定木であったりNNのRelu関数であったりと比較演算をしなければならない状況が往々にして存在します。
この時に準同型暗号を用いて比較演算をする方法が存在します。今回はそれについて少しまとめたいと思います。

論文を読みたい方はこちらから。

通信が必要

準同型暗号を用いた比較演算を行う時に、制約となってくるのが通信です。具体的には、暗号文を取り扱う計算サーバが直接比較演算を行うことはできないものの、計算サーバが比較演算に必要な計算を行い、その結果を一度ユーザに返して、ユーザが最終的に比較の判断を（暗に）行います。

とあんまり上手な説明ではないですが、まとめると、
準同型暗号を用いると、比較はめんどくさいけどまあできなくもない。
ということです。

2017のIEEEにも出ている Performance Analysis of Sorting of FHE Data: Integer-wise Comparison vs Bit-wise Comparison（Harika Narumanchi1, Dishant Goyal2, Nitesh Emmadi3, and Praveen Gauravaram4）

などにもまとめられていますが、２つのやり方が（今の所）存在するようで、

入力をビット表記に直して、ビット演算をすることで比較を行う
ビットには直さずに頑張る

この２つが紹介されています。
今回は、格子暗号ではないですが、加法性を持つ準同型暗号のPaillier暗号を用いて、上のビット演算を用いた暗号文の比較演算を行ったコードを紹介します。

このコードは、我々がKPMG Ignition Tokyo様と協同で行なった、秘密計算ハッカソン2019 で技術提供した際の　gitレポジトリに格納されているので、興味がある人がいましたらご覧ください。
また、このハッカソンのレポートは第1回　KPMGジャパン　秘密計算ハッカソン　レポートにまとめられていますので、ぜひご覧ください。

compare_two_value_paillier.py

from phe import paillier as pl

def binarize_int(a:int, binary_length=5):
    '''
    Make Integer Into Binaryzed Representaion, 
    For Example, 3 => 00011,  8 => 01000
    Note that Input Cannot Exceed 2^(binary_length)

    Args:
        a: integer
        binary_length: length of output binary string

    Returns:
        binary string of a which its length is equal to binary_length
    '''
   
    bit_a = bin(a)
    b_ind = bit_a.rfind("b")
    bit_a = bit_a[b_ind+1:]
    diff = binary_length - len(bit_a)
    for i in range(diff):
        bit_a = "0" + bit_a

    return bit_a

def encrypt_binarized_int(bit_a:str, pk):
    '''
    Encrypt Each Binary with Paillier
    For Example, 3 => 00011 => ['89729857','2398739572','3724983270','223848920','09873522']

    Args:
        bit_a: input binary string
        pk: PaillierPublicKey object. It is used for encryption

    Returns:
        A python list of all encrypted binary from bit_a.
    '''
    enc_bit_a = []
    for i in range(len(bit_a)):
        enc_bit_a.append(pk.encrypt(int(bit_a[i])))
    return enc_bit_a

def compare_encrypted_binarized_input_with_plaintext(a:list, b:str, pk):
    '''
    Compare One Encrypted Int with Plaintext Int

    Args: 
        a: list of encrypted binary string (list of EncryptedNumber objects).
        b: binary string for comparison


    Returns:
        A python list, which Includes Encrypted Judging Number, If Any Of Them is 0, It Indicates a < b.
    '''
    
    result = []
    for i in range(len(a)):
        second_half = pk.encrypt(0)
        for j in range(0,i):
            tmp = int(b[j])
            # print(tmp)
            if tmp == 0:
                xor_result = a[j]
                second_half = second_half + xor_result
            elif tmp == 1:
                xor_result = pk.encrypt(1) - a[j]
                second_half = second_half + xor_result
            else:
                raise Exception("b should be binary representation")
        second_half = second_half * 3
        tmp_result = a[i] - pk.encrypt(int(b[i])) + pk.encrypt(1) + second_half
        result.append(tmp_result)
    
    return result


if __name__ == "__main__":
    # This Program is Sample Code for Compare Encrypted Number with Plaintext.
    # Usually This is Not Allowed for CipherText, Because If It is, By Compare Numerous Encrypted Number,
    # One can Find at Least Sort CipherText in Order, which Reveal Information of Secret Data.

    # Compare int a and int b.
    # This Program can Compare One Encrypted Number, in This Case, a, 
    # With Plaintext, in This Case, b.
    a = 4
    b = 9

    pk, sk = pl.generate_paillier_keypair(n_length=256)

    # Make Two Number Into Binary Representation
    bit_a = binarize_int(a)
    bit_b = binarize_int(b)

    # Encrypt Binary Representation of a
    enc_bit_a = encrypt_binarized_int(bit_a, pk)

    # Compare Encrypted int a and Plaintext b
    result = compare_encrypted_binarized_input_with_plaintext(enc_bit_a, bit_b, pk)

    # If Decrypted Result Includes 0, a < b
    # Otherwise, a >= b
    decrypt_result = [sk.decrypt(result[i]) for i in range(len(result))]

    # decrypt_result = [1, 0, 5, 7, 6], which Includes 0, So, a < b.
    print('decrypt result is ', decrypt_result)
    print('a > b or not: ', not any([x == 0 for x in decrypt_result]))

２つ目の「ビットには直さずに頑張る」の方法は上でも紹介した「Performance Analysis of Sorting of FHE Data: Integer-wise Comparison vs Bit-wise Comparison（Harika Narumanchi1, Dishant Goyal2, Nitesh Emmadi3, and Praveen Gauravaram4）」
の4.Bのinteger-wise comparisonで紹介されているようですが、まだよく追えていません。また、実用上速度がかなり遅いので問題があるようです。

まとめ

比較演算を準同型暗号を用いて行うことは現状色々制約があり、お世辞にも準同型暗号が比較演算を得意にしている、とは言えません。比較演算においては、MPCでのガーブレッド回路などを使っているアプリケーションが多いです（つまり、比較などが挟まる時はMPCでの秘密計算に切り替える、ハイブリッド方式）。しかしながら、準同型暗号でも比較を工夫して行うやり方が存在するため、これらがより研究され、高速化が実現することで、準同型暗号をもちいて比較演算も含んだ計算をやりきることができれば、より準同型暗号ライブラリの実世界へのアプリケーションが現実的なものになるでしょう。
今回はこの辺で。

おわり。