Improving Algorithmic Efficiency using Cryptography

• Improving Algorithmic Efficiency using Cryptography
  • Info
  • Trapdoor matrix

Info

• authors: Vinod Vaikuntanathan and Or Zamir
• publication: arXiv

全体の要約

• LPNなどの困難性をもとにtrapdoor matrixを効率的にサンプリングできることを示した.
• trapdoor matrixとはランダム行列$M$とランダム回路$C$のペア$(M,C)$のことであり, 任意のベクトル$v$に対して$C$は$v\mapsto Mv$をほぼ$O(n)$時間で計算する. また, LPNなどの困難性を仮定することで$D$の分布は一様ランダムな行列と識別できない.
• 具体的な応用としてJohnson-Lindenstraussなどを述べている.

Trapdoor matrix

定義 (trapdoor matrix)

$\F_q$を有限体とする. $n\in\Nat$に対し, trapdoor matrixとは次の条件を満たすペア$(M,C)$のことである：

1. $M\in\F_q^{n\times n}$は何かしらの分布に従うランダム行列である.
2. $C\colon\F_q^n\to\F_q^n $は回路であり, 任意のベクトル$v\in\F_q^n$に対して$C(v)=Mv$を満たす.

また, trapdoor matrix $(M,C)$は写像$v\mapsto C(v)$が$T(n)$時間で計算できるとき, $T$-効率的であるという.

定理(informal)

Learning with Error判定問題が困難であるならば, ある$n^{1+o(1)}$-効率的なtrapdoor matrix$(M,C)$が存在して, 任意の多項式時間アルゴリズムは$M$と一様ランダム行列をアドバンテージ$1/\poly(n)$で識別できない.