Microsoft SEAL と準同型暗号の夜明け

完全な準同型暗号 (FHE) は 2009 年に最初に達成されましたが、計算能力がその計算要求に追いついた今、より注目を集め始めています。ただし、準同型暗号の目標は 10 年前にさかのぼります。

大雑把に検索すると、複数の定義が見つかります。これは最も直接的で簡潔です。

暗号化された結果を生成する暗号文の計算を可能にする暗号化の形式。復号化すると、平文で実行されたかのように操作の結果と一致します。

— Massimo Bertaccini ( 暗号化アルゴリズム)

その言葉を少し考えてみてください。準同型暗号化では、元の暗号化されていない値に対して実行されたかのように、復号化された結果が操作の結果を生成するように、暗号化された値に対して操作を実行できます。私が見つけた最初の言及は、 On Data Banks and Privacy Homomorphisms (1978) で、著者は、リモート タイムシェアリング サービスを使用して、システム プログラマーがオンプレミス システムに格納された機密の金融データにアクセスできないようにしようと試みています。

機密の財務データはデータ バンクに保存されます。データを計算するタイムシェアリング サービスは、適切なセキュリティを実装していません。システム プログラマーは財務データにアクセスできます。この論文は次のように述べています。

特別なプライバシー準同型を使用してデータを暗号化し、タイムシェア コンピュータが最初にデータを復号化する必要なくデータを操作できるようにします。

別の言い方をすれば、データへのアクセスを与えることなく、データの処理を削除したいと考えています。

さらに別の言い方をすれば、 function(A, B) = function (A , B ) ここで、 A  and Bは、それぞれ A と B の暗号化された値です。これにより、第三者は暗号化されたデータを計算し、元の値を知らなくても結果を提供できます。 RSA を使用すると、同じキーで暗号化された 2 つの値を乗算し、積を復号化して、暗号化された値の積を得ることができます。

RSA(5)_RSA(6) を使用して 5_6 を取得します。

1. RSA(5) = (5^17) mod 3233 = 3096

2. RSA(6) = (6^17) mod 3233 = 824

3. 3096*824 = 254864

4. RSA^-1(254864) = 254864^2753 (mod 3233) = 30

5. 5*6 = 30

   
   

ただし、これは追加には機能しません。 RSA は、乗算のみをサポートするという点で、部分準同型暗号化 (PHE) 方式です。以下のタイムラインは、(PHE) スキームから、加算と乗算の限られた組み合わせを許可する多少の準同型暗号化 (SHWE) までの進行を示しています。これらの操作は、無効な結果に到達するまでに最大 5 回繰り返される可能性があります。その後、 Craig Gentryによる最初の FHE スキームが登場し、忠実度を損なうことなく加算と乗算を繰り返すことが可能になりました。

準同型暗号ライブラリ

2009 年以降、FHE スキームとライブラリが急増しました。

Microsoft SEAL (Simple Encrypted Arithmetic Library) は、C# ラッパーと共に C++ 17 で開発されています。 2015 年に最初にリリースされ、現在も開発が活発に行われています。 github リポジトリには詳細な C# の例が含まれており、さらに深く掘り下げたい場合に検討する必要があります。

これらのスキームは SEAL によってサポートされており、加算、除算、減算、累乗の準同型演算が含まれていますが、除算は含まれていません。

• ブラケスキー・ジェントリー・ヴァイクンタナサン (BGV)/ファン・ヴェルカウテレン (BFV)

  
  

  • 整数 (ロング)

  • 精度が必要な場合に使用

  • 計算はCKKSより遅い

  • BGV で暗号化された値は、BFV で暗号化された値で使用できます

  • BGV/BVF で暗号化された値は、CKKS で暗号化された値では使用できません

  • 有限体の準同型暗号方式の再検討

    
    

• チョン・キム・キム・ソン (CKKS)

  
  

  • 浮動小数点 (double)
  • 精度が必要ない場合に使用
  • CKKS で暗号化された値は、BGV/BFV で暗号化された値では使用できません
  • 計算はBFV/BGFより速い

Microsoft SEAL による暗号化と計算

これらの例では、 Microsoft.Research.SEALNet Nuget パッケージと CKKS スキームを使用しています。 FitBit や AppleHeath などのヘルス トラッカーでは、ある程度のプライバシーを放棄する必要があります。歩数や着用者の動きの地理座標、心拍数、その他の重要な統計情報などの個人情報を収集します。準同型暗号化を使用すると、これらのヘルス メトリック アグリゲーターは、生データにアクセスしなくてもデータを操作できます。

この単純な例では、クライアントは距離と時間を含む実行メトリックを送信します。サーバーは暗号化されたデータを集約し、平均速度を計算します。

開始するには、公開鍵がクライアントによって作成され、サーバーと共有されます。データを暗号化したり、暗号化されたデータに対して算術演算を実行したりするために使用されます。クライアントとサーバーの両方がEncryptor を使用します。クライアントは、適切な名前のDecryptorによって使用される復号化に使用される秘密鍵を生成して保持します。

データを傍受する悪意のある人物が、暗号化されたデータの公開鍵を使用し、サーバーになりすまして呼び出し元に返す可能性があります。サーバーは結果に署名する必要があり、クライアントは署名を検証して、信頼できるパーティから返されたことを確認する必要があります。

 using Microsoft.Research.SEAL; protected SEALContext _context; private KeyGenerator _keyGenerator; private Encryptor _encryptor; private Decryptor _decryptor; protected IFitnessTrackerApiClient _apiClient; . . . _context = SEALUtils.GetContext(_config.Value.PolyModulusDegree, this.SchemeType); _keyGenerator = new KeyGenerator(_context); _keyGenerator.CreatePublicKey(out PublicKey publicKey); _keyGenerator.CreateRelinKeys(out RelinKeys relinKeys); _encryptor = new Encryptor(_context, _publicKey); _decryptor = new Decryptor(_context, _keyGenerator.SecretKey); . . . PublicKeyModelCKKS keyModelCKKS = new( SEALUtils.KeyToBase64String(_publicKey), SEALUtils.KeyToBase64String(relinKeys)); await _apiClient.SendPublicKeyCKKSAsync(keyModelCKKS);

再線形化キーは、クライアントからサーバーに渡されます。 Microsoft SEAL によると、これらには、乗算操作に続く暗号文のサイズを縮小する以外に意味的な意味はありません。

コマンド ラインで、ユーザーは時間と距離を入力します。

各値は PlainText にエンコードされ、次に Ciphertext に暗号化され、最後に base64 にエンコードされてからサーバーに送信されます。

 using Microsoft.Research.SEAL; var plaintext = new Plaintext(); _encoder.Encode(value, _scale, plaintext); var ciphertext = new Ciphertext(); _encryptor.Encrypt(value, ciphertext); using (var ms = new MemoryStream()) { ciphertext.Save(ms); return Convert.ToBase64String(ms.ToArray()); }

準同型暗号方式は除算をサポートしていないため (CKKS も例外ではありません)、クライアントはサーバーを支援する必要があります。速度の式は次のとおりです。

• 距離・時間

  
  

別の書き方としては、

• 距離 * (1/回)

  
  

したがって、クライアントは次を送信します。

 RunItemCKKS metricsRequest = new( EncryptBase64(runItem.Distance), EncryptBase64(runItem.Time), EncryptBase64(1 / runItem.Time)); await _apiClient.AddNewRunningDistanceCKKSAsync(metricsRequest);

サーバーは、公開鍵と再線形化鍵のみを使用してSEALContextを作成する同様のブートストラップ機能を実行し、要求を処理します。

 var distance = SEALUtils.BuildCiphertextFromBase64String(request.Distance, _sealContext); var time = SEALUtils.BuildCiphertextFromBase64String(request.Time, _sealContext); var timeReciprocal = SEALUtils.BuildCiphertextFromBase64String(request.TimeReciprocal, _sealContext); Ciphertext speed = new(); _evaluator.Multiply(distance, timeReciprocal, speed); _evaluator.RelinearizeInplace(speed, _relinKeys); _runListCKKS.Add(new EncryptedRunInfoCKKS(distance, time, speed));

送信された実行の速度を計算するために時間の逆数が使用され、 RelinearizeInplaceメソッドが結果の暗号文のサイズを縮小します。距離、時間、速度はメモリ内のリストに保存されます。

GetMetricsメソッドは、リストを集計して次を返します。

• 実行の合計数

• 総距離

• 合計時間

• 平均速度

  
  

  public SummaryItemCKKS GetMetrics() { int count = _runListCKKS.Count; var totalDistanceCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Distance)); var totalTimeCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Time)); var totalSpeed = SumEncryptedValues(_runListCKKS.Select(m => m.Speed)); . . . protected Ciphertext SumEncryptedValues(IEnumerable<Ciphertext> encryptedData) { . . . Ciphertext encTotal = new(); _evaluator.AddMany(encryptedData, encTotal); return encTotal; . . . }

  
  

平均速度を取得するには、カウントの逆数が使用されるため、以下を使用するのではなく:

(速度の合計)/使用する実行数:

(速度の合計) * (1/実行回数)

サーバーは実行の送信数を追跡しているため、実行の合計数は暗号化された値ではありません。その暗号化されていない値を平文に変換し、暗号文で実行される操作で使用できます。これは単純な例ですが、その影響は注目に値します。サーバーは、暗号化されたデータで使用される追加の値を提供できるため、サードパーティのプロバイダーは、顧客が提供した暗号化されたデータに対する計算に独自のデータを適用できます。

以下の例では、合計カウントが逆数に変換され、 List<double> に追加されます。 CKKS 操作は、リストに単一の値しか含まれていない場合でも、暗号化されたリスト値を想定しています。したがって、 List<double>はPlainTextにエンコードされます。 MultiplyPlainInplaceは、totalSpeed に (1/実行回数) を掛けて、平均速度を求めます。スペースを節約するために、結果はtotalSpeed 暗号文に適用され、再線形化キーによって出力のサイズが縮小されます。

 Plaintext encodedCountReciprocal = new(); List<double> averagePaceList = new(); double runCountReciprocal = 1 / (double)count; averagePaceList.Add(runCountReciprocal); _encoder.Encode(averagePaceList, _scale, encodedCountReciprocal); _evaluator.MultiplyPlainInplace(totalSpeed, encodedCountReciprocal); _evaluator.RelinearizeInplace(totalSpeed, _relinKeys);

値は base64 でエンコードされて返され、クライアントで復号化されます。クライアントは、復号化されたプレーンテキストをList<double>に変換する追加の手順を実行します。

 var payload = Convert.FromBase64String(encryptedDistanceText); using var ms = new MemoryStream(payload); var ciphertext = new Ciphertext(); ciphertext.Load(_context, ms); var decryptedText = new Plaintext(); _decryptor.Decrypt(cypherText, decryptedText); List<double> distanceList = new(); _encoder.Decode(decryptedText, distanceList);

次の値を送信すると、クライアントから送信されたデータを復号化せずに、合計と平均を表にしたサービスによって計算された合計と平均ペースが得られます。

サーバーはデータを計算し、送信されたデータを復号化せずに合計走行数、距離、時間、およびペースを返します。

概要

Microsoft SEAL は Microsoft Research プロジェクトであり、実稼働アプリケーションの準備ができていません。すべてのクラスはIDisposableを実装し、アンマネージ リソースを使用します。プロダクション コードは、メモリ リークから保護する必要があります。 SEALContextクラスは、単一責任の原則に従っていません。 BGV/BVF と CKKS の両方のメソッドが含まれています。さらに、CKKS はベクトル操作をサポートしますが、ベクトル加算はサポートしません。単一のList<double>を単一のCipherText に暗号化できますが、単一の CipherTextの値を合計する手段はありません。 ベクトル回転で行うことができますが、それは次善の解決策です。

このフィットネス トラッカーのコード サンプルは、複雑なトピックへの簡単な紹介です。より複雑なロジックを使用した説得力のある使用例がいくつかあります。

• 遺伝子マーカーの検出

• 生体認証テンプレートの保護

• 老朽化のための人間による安全な監視

• クレジットカード詐欺の検出

  
  

準同型暗号は、主に学界やプロトタイプで使用されてきました。実際のアプリケーションは、準同型暗号化スキームに必要な計算能力によって制限されてきました。 GPU アクセラレーションと ASIC プロセッサは、この障壁を侵食し続けます。 Intel は、Microsoft および DARPA と協力して、準同型暗号化スキーム専用のFHE ハードウェア アクセラレータを開発しています。 NASDAQ はまた、機械学習による不正検出のための準同型暗号を使用する R&D プロジェクトに資金を提供しています。 FHE.org コミュニティは、この分野の最新の開発に関する優れたリソースです。アクティブなDiscord サーバーがあります。

この記事のすべてのコード サンプルは、 johniwasz/microsoft-seal-samplesで入手できます。詳細な Microsoft SEAL の例については、これらの.NET の例を参照してください。

こちらにも掲載。