🌟

ZKPのCircuit内で準同型暗号を扱うためのPaillier暗号について

2024/02/24に公開

Ethereum

circuit

circom

tech

はじめに

ETHGlobalハッカソンで準同型暗号とZKPを使用してスコアをオンチェーン上で送信し合うアプリケーションを開発しました。Circuit内でFHEの復号化をするのにどうしたかについて記事に書いていきます。

準同型暗号（HE）は、暗号化されたデータ上で直接計算を可能にする技術です。前回の記事では、Node.js と TypeScript を使用して FHE に関連する基本的な API を構築する方法を紹介しました。

今回はこの準同型暗号をCircuit内でどのように扱ったのか解説していきます。

参考github

Circuit内で準同型暗号を使用するために

前回の記事ではPaillier暗号のライブラリを使用して暗号化、復号化を解説しました。
今回のHacksonで提出したアプリケーションは、オンチェーン上にAのスコアをPaillier暗号で暗号したものを保存しながら、BやCがスコアをAに送るとそれを暗号化したまま加算していきます。そしてそのAのスコアが一定の評価を超えているか否かを確認するために、ZKPのCircuitの中でスコアを復号化し検証するという手法を取りました。
Circuit内ではライブラリの復号化メソッドは使用できません。なので数学的に実装していく必要があるのでそのことについて説明していきます。

ちなみに前回の記事(generateKeyPairs)で生成した鍵の中でPrivate keyのlambdaとmu、Public keyのnの値を使用していきます。

Paillier暗号とは

完全準同型暗号（FHE）技術の中でも、Paillier 暗号システムはその加法的準同型性質により、プライバシーを保護しつつデータの計算を可能にします。二つの大きな素数から生成される公開鍵と秘密鍵を用いて、データを暗号化および復号化します。このシステムの最大の特徴は、暗号化されたデータ同士を加算することで、それらの平文を暗号化したまま加算することができるという性質です。

復号化プロセスとL関数

復号化プロセスのコアとなるのが、L関数です。この関数は、復号化の際に特定の数学的操作を行うために用いられます。Paillier暗号の効率的な復号には、このL関数が必要になります。

L関数について

L関数は、Paillier 暗号システムの復号化アルゴリズムの一部で、次のように定義されます。

L(x) = \frac{x-1}{n}

ここでxは暗号化されたメッセージを特定の方法暗号化の値(c)を秘密鍵の一部(Labmda)で累乗した後の値をn^2でのモジュロ演算で変換した値、nは公開鍵の一部である大きな素数の積です。

x = c^{\lambda}\mod n^2

xは上記のようになるのでそれを踏まえてL関数を書き換えると下記のようになります。

L(x) = \frac{(c^{\lambda}\mod n^2) -1}{n}

復号化プロセス

それでは実際の復号化プロセスです。

累乗
暗号化されたメッセージを秘密鍵の一部であるlambdaで累乗し、さらにn^2でのモジュロを取ります。(lambdaとnについては上記鍵生成のスクショの部分。)この操作により、L関数の引数xを作成します。
(modPowメソッドについては後ほど実装します。)

modPow(chipher, dkLambda, ekNN)

L 関数の適用
上記の累乗結果から1を引いてnで割り、L関数の計算を行います。この操作で得られる結果をdenumとします。

denum = (bcu.modPow(encryptedSum, lambda, nn) - 1) / n;

復号化されたメッセージの計算
L関数の結果に別の秘密鍵の部分muを乗じてnでモジュロを取ります。(muについては上記鍵生成のスクショの部分。)これにより、元のメッセージmが得られます。

m = denum * mu % n;

実装

上記の復号プロセスを実装していきます。

まずは生成した鍵からCircuitに渡すinputを作成します。
セットアップなどについては前回の記事を参照ください。

createInput.

import { Request, Response } from 'express';
import { promises as fsPromises } from 'fs';
import path from 'path';

// BigInt オブジェクトを JSON 互換の文字列に変換する関数
function bigintToJson(key: any): string {
    return JSON.stringify(key, (key, value) =>
        typeof value === 'bigint' ? value.toString() : value
    );
}

export const createInput = async (req: Request, res: Response) => 
    if (req.method === 'POST') {
        // クライアントからのデータを取得
        const { encNum, name } = req.body;

        // private.json と public.json のパスを取得
        const priKeyPath = path.join(__dirname, 'data', `${name}-privateKey.json`);
        const pubKeyPath = path.join(__dirname, 'data', `${name}-publicKey.json`);

        // ファイルから非同期にデータを読み込む
        const privateKeyData = JSON.parse(await fsPromises.readFile(priKeyPath, 'utf8'));
        const publicKeyData = JSON.parse(await fsPromises.readFile(pubKeyPath, 'utf8'));

        // 必要なデータを抽出
        const { lambda, mu } = privateKeyData;
        const { n } = publicKeyData;

        // レスポンスとして返す JSON オブジェクトを作成
        const responseObject = {
            lambda.toString(),
            mu.toString(),
            n.toString(),
            encNum,
        };

        // ファイル書き込み。一旦コメントアウト
        // const inputPath = path.join(process.cwd(), 'data', `${name}-input.json`);
        // await fsPromises.writeFile(inputPath, bigintToJson(responseObject), 'utf8');

        res.status(200).json(responseObject);
    } else {
        // POST以外のメソッドを受け付けない場合
        res.setHeader('Allow', ['POST']);
        res.status(405).end(`Method ${req.method} Not Allowed`);
    }
};

上記で重要な部分は、作成した公開鍵と秘密鍵の中で必要な値(lambda, mu, n)を抽出し、それをcircuitに渡すためのinputとして埋め込んでいる部分です。(公開鍵や秘密鍵の全体の構成については上記Circuit内で準同型暗号を使用するためにで示したスクショをご覧ください。)

必要な値抽出部分

// 必要なデータを抽出
const { lambda, mu } = privateKeyData;
const { n } = publicKeyData;

// レスポンスとして返す JSON オブジェクトを作成
const responseObject = {
    lambda.toString(),
    mu.toString(),
    n.toString(),
    encNum,
};

circuit内の復号処理の実装
今回circomについての説明は特に省きますが、復号化処理の部分について説明していきます。

下記circomは今回サンプルのために書いたものなので参考程度にお願いいたします。

circuit.circom

pragma circom 2.0.0;

template Main() {
    signal input encNum;
    signal input lambda;
    signal input mu;
    signal input n;
    signal output plainNum;

    // 平均スコアの計算
    plainNum <-- decrypt(encNum, n, lambda, mu);
}

function decrypt(encNum, n, lambda, mu) {
    var nn = n * n;
    log("ekNN is", ekNN);
    var numL = (modPow(encNum, lambda, nn) - 1) \ n;
    log("numL is", numL);
    log("mu is", mu);
    var plain = numL * mu % n;
    log("n is", n);
    return plain;
}

function modPow(x, e, m) {
    var result = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            result = (result * x) % m;
        }
        x = (x * x) % m;
        e = e >> 1;
    }
    return result;
}

component main {public [totalScore, totalEvaluater, encryptionKeyN]} = Main();

復号化プロセス[1.累乗]

まず累乗処理です。decrypt関数の中の特にmodPow(encNum, lambda, nn)この部分です。

var nn = n * n;
var numL = (modPow(encNum, lambda, nn) - 1) \ n;

累乗
暗号化されたメッセージを秘密鍵の一部であるlambdaで累乗し、さらにn^2でのモジュロ> を取ります。(lambdaとnについては上記鍵生成のスクショの部分。)この操作により、L関数> の引数xを作成します。

そしてこのmodPow関数のアルゴリズムは、「二進法累乗法（Binary Exponentiation）」または「べき乗剰余アルゴリズム」として知られています。大きな数の累乗をモジュロmのもとで効率的に計算するために、累乗を計算してから m で割るのではなく、計算過程でモジュロを取ることで、数値が大きくなるのを防ぎ、計算効率を上げるというものです。

modPow

function modPow(x, e, m) {
    // 結果を格納する変数を1で初期化。1は乗算の単位元。
    var result = 1;

    // 指数 e が0より大きい間、計算を続ける。
    while (e > 0) {
        // e が奇数の場合、現在の result に x を乗じたものを m で割った余りを result に代入。
        // これは、累乗の途中結果を m でモジュロ取ることで、計算過程での数値の大きさを制御し、
        // オーバーフローを防ぐ。
        if (e % 2 == 1) {
            result = (result * x) % m;
        }

        // x を自身と乗じたものを m で割った余りに更新。
        x = (x * x) % m;

        // e を右に1ビットシフト。これは、e を2で割る操作に相当し、指数を半分にする。
        // 右シフトにより、奇数だった場合は自動的に切り捨てられ、偶数になる。
        e = e >> 1;
    }
    return result;
}

復号化プロセス[2.L関数の適用]

modPowによってL関数のxの値を算出することができました。次にL関数を適用していきます。

上記の累乗結果から1を引いてnで割り、L関数の計算を行います。

var numL = (modPow(encNum, lambda, nn) - 1) \ n;

復号化プロセス[3.復号化されたメッセージの計算]

最後にL関数で算出した値を mu で乗じて n でモジュロを取ることで復号化します。

L関数の結果に別の秘密鍵の部分muを乗じてnでモジュロを取ります。(muについては上記鍵生成のスクショの部分。)これにより、元のメッセージmが得られます。

var plain = numL * mu % n;

このようにPillier暗号システムでライブラリのメソッドを用いることなく復号化することで、circomのcircuit内でも復号化を実現することができました。

まとめ

今回Circomの中でのPillier暗号システムにおける準同型暗号について扱っていきました。ただ、circomで扱えるデータの大きさには限界があり、十分な準同型暗号としての鍵長での実装はできませんでした。これは今後の課題です。