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

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

準同型暗号（Homomorphic Encryption）とは

準同型暗号の概要

準同型暗号（homomorphic encryption）とは、暗号化したまま計算や検索ができる暗号化方式です。演算するときに複数の事象の類似性を利用する”準同型”という数学的な性質を応用しています。この特徴から、主に機密性の高い情報を扱う場合や、他社とデータを連携する際に用いられ、秘密計算の手法にも採用されています。

基礎理論は1978年に確立されていましたが、2009年に公開鍵暗号の一つである格子暗号を用いた準同型暗号が提案され、実用化にむけて急速に研究が進みました。

準同型暗号方式の種類

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

方式と機能の種類

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

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

完全準同型暗号

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

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

FHEは、2009年にGentryらが提案した格子暗号を用いた準同型暗号をベースに構成されています。暗号化したまま演算することによって安全性が担保される反面、演算（特に掛け算）を繰り返すほど暗号文が長くなります。そのため、演算処理に要する時間や負荷が課題となり、現実的な社会実装にはハードウェアの性能向上だけではなく、暗号処理やアルゴリズムの構成等に工夫が必要です。

この演算の負荷を解消すべく開発されたのが、演算回数に制限を設けることで暗号文の長大化を防ぎ演算処理を向上することが可能な ”somewhat準同型暗号” です。FHEとほぼ遜色ない形で暗号化したまま演算できることから、現実的な演算方法として研究が進んでいます。詳しくは次の章で説明します。

somewhat準同型暗号

somewhat準同型暗号（Somewhat Homomorphic Encryption、以下“SHE”）は、FHEと同様に足し算・掛け算のどちらも暗号化したままで演算でき、演算（特に掛け算）の実施回数に制限をかけることで、FHEに比べ処理にかかる時間や負荷の軽減を可能としました。演算処理が重たいFHEよりも実用的なため、社会実装に向けて様々な構成が発表されている方式です。

SHEの中でも、2010年にDijkらが考案したbootstrap処理とあわせておこなうSHE方式が代表的です。この方式をうまく活用することで、演算回数の制限をFHEに近づけることが可能としています。

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方式は、HElibやMicerosoft SEALに用いられています。

第3世代：GSW方式、FHEW、TFHE

2013年提案のGSW（Gentry-Sahai-Waters）方式と、これを改良したFHEW（2014年）・TFHE（2016年）が第3世代に分類されます。第2世代までの掛け算によって肥大化していた非効率な計算処理を解決し、bootstrap処理を高速で行える点を特徴とする方式です。

FHEWとTFHEは、PalisadeやConcrete ML等に用いられています。

第4世代：CKKS方式

CKKS（Cheon、Kim、Kim、Song）方式は、整数だけではなく実数や複素数も計算することが可能です。スケールというパラメータによって実数を整数に見立てて計算することから、計算結果に若干のノイズが生じ、計算を繰り返すとノイズが大きくなるためにリスケール処理が必要になります。この課題解決に向けた研究も進んでおり、近年では機械学習に応用可能であることから利用の増えている方式です。

CKKSは、Micerosoft SEAL、Palisade、HEAAN等に用いられています。

*3　LFHE（Leveled Fully Homomorphic Encryption）は計算回数の制限を定数値の他にパラメータによる制限しており、bootstrap処理がなくても演算速度の向上が可能とした方式。

*4　SV（Smart-Vercauteren）パッキングは、同じ系統の整数をまとめて処理することで計算回数をへらすことで演算速度の向上を可能とした方式。

*5　SIMD（Single Instruction,Multiple Data）は複数のデータに対して同時に同じ処理をおこなう方式で、コンピュータやGPU等のメディア処理用チップに用いられる演算処理方法。

準同型暗号のライブラリ

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

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

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

準同型暗号方式の導入例

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

まとめ

準同型暗号（Homomorphic Encryption）は、暗号化したまま計算や検索ができる暗号化方式です。秘密計算の手法として利用され、データセキュリティ・プライバシー保護を支えるプライバシーテックの要素技術としても取り上げられています。

長く研究が続けられたことで計算処理にかかる負荷が改善され、近年では海外のテックジャイアントも注目する等、今後さらに市場の拡大が見込まれています。

EAGLYSでは創業より、準同型暗号の研究をしており、専門知識がなくとも準同型暗号を扱えることを目指し、DataArmotシリーズとして提供を行っております。

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

参考文献のご紹介

• 準同型暗号を用いた秘密計算とその応用　p64-69
• クラウドを支えるこれからの暗号技術　p145
• 量子コンピュータの脅威を考慮した高機能暗号：格子問題に基づく準同型暗号とその応用　p81-83
• 整数上完全準同型暗号の研究　p73
• 準同型暗号を用いた複数企業間の顧客情報分析　p3
• SVパッキングによる完全準同型暗号を用いた安全な委託　Apriori高速化　p3
• CKKS方式準同型暗号におけるRescale 演算のGPU実装と演算性能評価　p1-2
• 演算ビット数削減による準同型暗号ライブラリSEALの高速化　p1-3