暗号化したまま距離計算！JavaScriptと準同型暗号「paillier-bigint」で学ぶプライバシー保護技術

位置情報のような機密性の高いデータを、サーバーに渡すことなく安全に処理したいと考えたことはありませんか？例えば、「2つのGPS座標間の距離を、それぞれの座標を秘密にしたまま計算する」といった処理です。

これを実現するのが準同型暗号という技術です。この技術を使えば、暗号化されたデータを復号することなく、データに対する加算や乗算などの計算ができます。

この記事では、JavaScriptの準同型暗号ライブラリpaillier-bigintを使い、暗号化された緯度・経度データからユークリッド距離を計算するデモプログラムを通して、その仕組みと可能性を探ります。

シナリオ：暗号化された位置情報から距離を求める

このプログラムの目的は、2つの地点（lat1, lon1）と（lat2, lon2）の間の距離を、元の座標値を一切復号することなく計算することです。

具体的には、以下の計算を暗号文の上で行います。

緯度の差 dLat = lat2 - lat1 を計算
経度の差 dLon = lon2 - lon1 を計算
差からユークリッド距離 √(dLat² + dLon²) を求める

このデモでは、計算の単純化のため球面を考慮しないユークリッド距離を用いていますが、プライバシーを保護しながらデータ活用する準同型暗号の強力なコンセプトを示しています。

デモプログラムの完全なコード

まず、今回解説するプログラムの全体像を以下に示します。

import * as paillierBigint from 'paillier-bigint'

// BigIntの平方根を計算するヘルパー関数（Newton法）
function bigintSqrt(n) {
  if (n < 0n) throw new Error("負の平方根は定義されません")
  if (n < 2n) return n
  let x = n / 2n
  while (true) {
    const y = (x + n / x) / 2n
    if (y >= x) return x
    x = y
  }
}

// 復号後の値が負数である可能性を考慮して補正する関数
function correctSigned(val, n) {
  return val > n / 2n ? val - n : val
}

async function main() {
  // 3072ビット長の公開鍵と秘密鍵を生成
  const { publicKey, privateKey } = await paillierBigint.generateRandomKeys(3072)

  // 緯度・経度（×1,000,000で整数化）
  const lat1 = 35681236n, lon1 = 139767125n
  const lat2 = 35689487n, lon2 = 139700464n

  console.log('元の緯度経度:')
  console.log('lat1:', lat1.toString())
  console.log('lon1:', lon1.toString())
  console.log('lat2:', lat2.toString())
  console.log('lon2:', lon2.toString())

  // 各座標値を公開鍵で暗号化
  const lat1Enc = publicKey.encrypt(lat1)
  const lon1Enc = publicKey.encrypt(lon1)
  const lat2Enc = publicKey.encrypt(lat2)
  const lon2Enc = publicKey.encrypt(lon2)

  // --- ここから準同型計算 ---
  const n = publicKey.n
  const neg = n - 1n // モジュロ演算における「-1」

  // 暗号文のまま差を計算 E(lat2 - lat1)
  const dLatEnc = publicKey.addition(lat2Enc, publicKey.multiply(lat1Enc, neg))
  // 暗号文のまま差を計算 E(lon2 - lon1)
  const dLonEnc = publicKey.addition(lon2Enc, publicKey.multiply(lon1Enc, neg))
  // --- ここまで準同型計算 ---

  // 差分のみを秘密鍵で復号
  let dLatRaw = privateKey.decrypt(dLatEnc)
  let dLonRaw = privateKey.decrypt(dLonEnc)
  
  // 負数補正
  let dLat = correctSigned(dLatRaw, n)
  let dLon = correctSigned(dLonRaw, n)

  console.log('\n補正後の差分:')
  console.log('dLat:', dLat.toString())
  console.log('dLon:', dLon.toString())

  // 最終的なユークリッド距離を計算
  const dist = bigintSqrt(dLat ** 2n + dLon ** 2n)
  const distanceInDegrees = Number(dist) / 1_000_000

  console.log('\nユークリッド距離（度）:', distanceInDegrees)
}

main()

コード解説と実行結果

上記のコードが何をしているのか、ステップごとに見ていきましょう。

1. 準備と暗号化

まず、Paillier暗号で計算するための鍵ペアを生成し、少数の緯度・経度を1,000,000倍してBigInt型の整数に変換します。

// 元の緯度経度:
lat1: 35681236
lon1: 139767125
lat2: 35689487
lon2: 139700464

これらの4つの座標値を、publicKeyを使ってそれぞれ暗号化します。この時点で、暗号化されたデータの中身を見ても、元の座標値を知ることはできません。

2. 暗号化されたまま差を計算（準同型計算）

ここがこのプログラムの核心です。lat2 - lat1という引き算を、Paillier暗号の性質を利用して lat2 + (-1 * lat1) のように考え、暗号文のまま計算します。

publicKey.multiply(lat1Enc, neg): 暗号化されたlat1Encに-1を掛け合わせ、E(-lat1) を得ます。
publicKey.addition(...): E(lat2) と、上で計算した E(-lat1) を足し合わせることで、最終的に差の結果を暗号化した E(lat2 - lat1) を計算します。

この計算は、経度の差 dLonEnc についても同様に行われます。

3. 復号と最終計算

準同型計算によって得られた差分の暗号文 (dLatEnc, dLonEnc) のみを、秘密鍵で復号します。重要なのは、復号したのはあくまで「差分」だけであり、元の座標ではないという点です。

復号された差分と、そこから計算された最終的なユークリッド距離は以下の通りです。

補正後の差分:
dLat: 8251
dLon: -66661

ユークリッド距離（度）: 0.067169

dLat = 35689487 - 35681236 = 8251
dLon = 139700464 - 139767125 = -66661

差分の値は正しく計算できており、そこから求められたユークリッド距離も期待通りの結果となっています。

実行結果の確認

まず、プログラムの入力となる2地点の座標を見てみましょう。これらは他者に知られたくない、秘密の元データです。

次に、これらの暗号化された座標値から、準同型計算と復号を経て得られた最終的な出力結果がこちらです。

出力された差分の値が正しいか検証してみます。

緯度の差 (dLat): 35689487 - 35681236 = 8251
経度の差 (dLon): 139700464 - 139767125 = -66661

計算結果は、スクリーンショットの「補正後の差分」と完全に一致します。

まとめ

このデモは、準同型暗号を利用することで、データを暗号化したまま足し算や定数倍の乗算といった演算が可能であることを示しました。これにより、プライバシーを完全に保護した上で、データの分析や活用ができるようになります。

今回のような位置情報サービスのほか、医療データ分析、金融取引の監査など、機密情報を扱いながらも計算が必要となる多くの分野での応用が期待される、非常にパワフルな技術です。

参考資料:

paillier-bigint GitHubリポジトリ: https://github.com/juanelas/paillier-bigint