ライジームと効率の根 — Prioの改善

概要

Prioはプライバシー・バイ・デザインの原則に基づいて設計されており、非協力的なエンティティ間でクライアントが提供する測定値を集約するためのプロトコルです。測定値の有効性は、完全線形確率的検証可能証明（FLPCP）を用いて判定されます。プローバーは測定値と証明の秘密シェアを複数の検証者に配布します。これらの検証者は、実際の測定値にアクセスせずに、入力文書に対する線形クエリのみを使用して検証が可能です。実用的なPrioの適用において効率は重要な要素です。FLPCPは、単位根をノードとして使用するラグランジュ基底で表現された多項式で動作します。しかし、ラグランジュ基底をより広く活用することで、パフォーマンス向上の機会を確認しました。例えば、ラグランジュ基底における多項式評価の逆行列を用いないO(n)時間計算量のアルゴリズムを提示します（古典的な有理バーリセントリック公式の代替案）。我々の手法を、最先端のRust実装であるlibprio-rsに適用することで、シャーディングフェーズ（証明生成）は36％高速化され、プリップ・インイットフェーズ（証明検証）は2倍高速化され、Prioの最も時間がかかるフェーズの顕著な加速を実現しました。