講演抄録/キーワード |
講演名 |
2017-05-12 12:00
[招待講演]How to circumvent the two-ciphertext lower bound for linear gabling schemes ~ ASIACRYPT 2016より ~ ○菊池 亮(NTT) ISEC2017-5 |
抄録 |
(和) |
Garbling scheme とは,入力を秘匿しつつ回路計算を行うために,通常の回路を暗号文で構成された garbled circuit に変換する手法である. Zahur らは linear garbling scheme と呼ばれる効率的な手法において, AND ゲートを 1 つ garbling するために最低 k ビットの暗号文 2 つが必要になることを示し,さらにこの下限を満たす手法を提案した.本論文では,この下限が回避できることを示し,実際に k ビットの暗号文が 2 つ未満となる garbling scheme を提案する.提案手法は Zahur らの文脈において linear garbling scheme に含まれるため, Zahur らの下限を回避し更なる暗号文サイズの削減が可能であることを示している.また,提案手法はゲートの種類を秘匿する semi-private function evaluation にも応用可能である. |
(英) |
At EUROCRYPT 2015, Zahur et al. argued that all linear, and thus, efficient, garbling schemes need at least two $k$-bit elements to garble an
AND gate with security parameter $k$. We show how to circumvent this lower
bound, and propose an efficient garbling scheme which requires less than
two $k$-bit elements per AND gate for most circuit layouts. Our construction slightly deviates from the linear garbling model, and constitutes no contradiction to any claims in the lower-bound proof. With our proof of concept construction, we hope to spur new ideas for more practical garbling schemes.
Our construction can directly be applied to semi-private function evaluation by garbling XOR, XNOR, NAND, OR, NOR and AND gates in the same way, and keeping the evaluator oblivious of the gate function. |
キーワード |
(和) |
歪曲回路 / 摂動回路 / スクランブル回路 / / / / / |
(英) |
garbled circuit / garbling scheme / two-party computation / semi-private function evaluation / / / / |
文献情報 |
信学技報, vol. 117, no. 25, ISEC2017-5, pp. 25-25, 2017年5月. |
資料番号 |
ISEC2017-5 |
発行日 |
2017-05-05 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2017-5 |