はじめに

準同型暗号とは暗号化方式の一つで、英語ではHomomorphic Encryptionと表記されます。秘密計算技術にも利用されている暗号化方式で、データの保護と活用の両立を実現する「プライバシー強化技術（プライバシーテック）」として近年世界的に注目されています。

この記事では準同型暗号の特徴や研究開発の歴史、実装方式等について紹介します。

準同型暗号（Homomorphic Encryption）とは

準同型暗号の概要

準同型暗号（Homomorphic Encryption）とは、暗号化したまま計算や検索ができる暗号化方式です。
暗号文どうしに対する演算結果を復号すると、平文どうしに同じ演算をした結果と一致する、という数学的な性質である”準同型性”を応用しています。この特徴から、主に機密性の高い情報を扱う場合や、他社とデータを連携する際に用いられ、秘密計算の手法にも採用されています。

 

準同型暗号の概念自体は1978年に確立されていましたが、2009年に、数学的な構造である格子を用いた格子暗号による準同型暗号方式が提案され、そこから実用化にむけて急速に研究が進みました。

準同型暗号方式の種類

準同型暗号は、“加法” “乗法” の大きく2種類の演算を暗号化したままで処理できます。加法とは足し算（および引き算）で、乗法とは掛け算（および割り算）を指し、それぞれの構成には暗号研究者の名称からなる暗号名が付与されています。下に記す4種類が主な演算方式です。

 方式と機能の種類 

*1,2    合わせて部分準同型暗号（Partial Homomorphic Encryption;PHEもしくはGroup Homomorphic Encryption;GHE）と呼ぶ場合もあります。

次に主要な方式である「完全準同型暗号」 について詳細に解説します。

完全準同型暗号

完全準同型暗号（Fully Homomorphic Encryption以下“FHE”）は、加法・乗法のどちらも暗号化したままで演算できる暗号化方式です。

”完全”は数学上の性質からきている言葉です。2で割った余りの世界において加法は排他的論理和（xor）、乗法は論理積（and）に相当し、加法と乗法ができれば、非線型演算を含むあらゆる計算を網羅できることから“完全”準同型と呼ばれています。

FHEは、2009年にGentryが提案した格子暗号を用いた準同型暗号をベースに構成されています。しかし、FHEには大きな欠点が2つあり、それらを克服するために、近年では、研究開発が盛んに行われております。

まず、1つ目に、一般に、暗号文上での演算は平文に比べて計算コストが高く、中でも乗算や非線型演算は特に重い処理になりやすいです。そのため、演算処理に要する時間や負荷が課題となり、現実的な社会実装にはハードウェアの性能向上だけではなく、暗号処理やアルゴリズムの構成等に工夫が必要です。

そして、2つ目に、Gentryによる方式では、暗号文の安全性を担保するために、ノイズと呼ばれる小さい数値が暗号文へ加えられます。しかし、暗号文演算を重ねると、ノイズの値が増大し、ある時点（下図でいう赤線を超えるタイミング）で正しい復号値を得られなくなります。

  

この課題を解決する手段の一つがBootstrap処理です。Bootstrap処理によって、暗号文に含まれるノイズを低減することができます。暗号文演算の適切なタイミングでBootstrap処理を挟み、ノイズの値を調節することで、何度も暗号文演算を行えます。しかしながら、Bootstrap処理自体も重たい処理であることは変わりなく、処理時間やメモリ消費の課題を完全に解決できているわけではないため、さらなる研究開発が進んでいます。

  

準同型暗号の歴史

 研究の歴史 

準同型暗号の研究は1978年にRivest、Adleman、Dertouzosによって構想され、2009年にCraig Gentryによって格子暗号を用いた実用的な構成が提案されました。このGentryの論文以降、盛んに研究がおこなわれ、その進化によって4つの世代に分類されます。

準同型暗号の世代区分

• 第1世代：イデアル格子による方式
  2009年にCraig Gentryらが提案したイデアル格子暗号を用いた方式や、翌2010年に提案されたSHEとBootstrap処理をかけ合わせた手法が、第1世代に分類されます。いずれの方式も構造自体は実用的と言われていますが、実際は1テラバイト以上のメモリを必要とする等、処理効率の課題から実装は難しい方式でした。

• 第2世代：BGV/BFV方式
  第2世代には、2011〜12年に構成されたBGV（Brakerski-Gentry-Vaikuntanathan）方式やBFV（Brakerski/Fan-Vercauteren）方式が分類されます。これらの方式は、LFHE（Leveled Fully Homomorphic Encryption）という暗号^*3や、同じ計算をまとめるSVパッキング処理^*4を用いたSIMD演算^*5等を用いることで、第1世代の暗号処理が肥大化する課題を解決している方式です。
  BGVやBFV方式は、LattigoやOpenFHEに用いられています。

• 第3世代：GSW、FHEW、TFHE方式
  2013年提案のGSW（Gentry-Sahai-Waters）と、これを改良したFHEW（2014年）・TFHE（2016年）方式が第3世代に分類されます。第2世代までの掛け算によって肥大化していた非効率な計算処理を解決し、Bootstrap処理を高速で行える点を特徴とする方式です。
  FHEWとTFHEは、OpenFHEやTFHE-rs等に用いられています。
  
  
• 第4世代：CKKS方式
  CKKS（Cheon、Kim、Kim、Song）方式は、整数だけではなく実数や複素数も計算することが可能です。スケールというパラメータによって実数を整数に見立てて計算することから、計算結果に若干のノイズが生じ、計算を繰り返すとノイズが大きくなるためにリスケール処理が必要になります。この課題解決に向けた研究も進んでおり、近年では機械学習に応用可能であることから利用の増えている方式です。
  CKKSは、Lattigo、OpenFHE、HEAAN等に用いられています。
  

*3　LFHE（Leveled Fully Homomorphic Encryption）は計算回数の制限を定数値の他にパラメータによる制限しており、Bootstrap処理がなくても演算速度の向上が可能とした方式。
*4　SV（Smart-Vercauteren）パッキングは、同じ系統の整数をまとめて処理することで計算回数をへらすことで演算速度の向上を可能とした方式。
*5　SIMD（Single Instruction,Multiple Data）は複数のデータに対して同時に同じ処理をおこなう方式で、コンピュータやGPU等のメディア処理用チップに用いられる演算処理方法。

準同型暗号のライブラリ

現在、いくつかのオープンソースライブラリが公開されています。ここでは代表的なものをそれぞれの特徴とあわせて紹介します。

 主なオープンソースライブラリ 

上記以外にも多くのライブラリがあり、それぞれの使い勝手や最新の情報については弊社テックブログ（DevelopersShare）でも公開していますので、ぜひご覧ください。

 準同型暗号方式の導入例 

  
準同型暗号を利用した実用化事例は近年徐々に増えています。以下に代表的な事例をご紹介します。

まとめ

準同型暗号（Homomorphic Encryption）は、暗号化したまま計算や検索ができる暗号化方式です。秘密計算の手法として利用され、データセキュリティ・プライバシー保護を支えるプライバシーテックの要素技術としても取り上げられています。
長く研究が続けられたことで計算処理にかかる負荷が改善され、近年では海外のテックジャイアントも注目する等、今後さらに市場の拡大が見込まれています。
 
EAGLYSでは創業より、準同型暗号の研究をしており、専門知識がなくとも準同型暗号を扱えることを目指し、DataArmorシリーズとして提供を行っております。

プライバシー強化技術（プライバシーテック）にご興味をお持ちの方や、準同型暗号（完全準同型暗号）ならびに秘密計算技術を使った課題解決をお考えの方は、お気軽にお問い合わせください。

 
参考文献

• 準同型暗号を用いた秘密計算とその応用　p64-69
  

• クラウドを支えるこれからの暗号技術　p145
  

• 量子コンピュータの脅威を考慮した高機能暗号：格子問題に基づく準同型暗号とその応用　p81-83
  

• 整数上完全準同型暗号の研究　p73
  

• 準同型暗号を用いた複数企業間の顧客情報分析　p3
  

• SVパッキングによる完全準同型暗号を用いた安全な委託　Apriori高速化　p3
  

• CKKS方式準同型暗号におけるRescale 演算のGPU実装と演算性能評価　p1-2
  

• 演算ビット数削減による準同型暗号ライブラリSEALの高速化　p1-3
  

※本記事に記載されている会社名・製品名・サービス名は、 各社の商標または登録商標です。