| 講演名 | 2017-05-12 ［招待講演］How to circumvent the two-ciphertext lower bound for linear gabling schemes 菊池 亮(NTT), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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 anAND gate with security parameter $k$. We show how to circumvent this lowerbound, and propose an efficient garbling scheme which requires less thantwo $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 |
| 資料番号 | ISEC2017-5 |
| 発行日 | 2017-05-05 (ISEC) |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2017/5/12(から1日開催) |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 満保 雅浩(金沢大) |
| 委員長氏名（英） | Masahiro Mambo(Kanazawa Univ.) |
| 副委員長氏名（和） | 小川 一人(NHK) / 藤岡 淳(神奈川大) |
| 副委員長氏名（英） | Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) |
| 幹事氏名（和） | 駒野 雄一(東芝) / 水木 敬明(東北大) |
| 幹事氏名（英） | Yuichi Komano(Toshiba) / Takaaki Mizuki(Tohoku Univ.) |
| 幹事補佐氏名（和） | 大東 俊博(東海大) / 須賀 祐治(インターネットイニシアティブ) / 猪俣 敦夫(東京電機大) |
| 幹事補佐氏名（英） | Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［招待講演］How to circumvent the two-ciphertext lower bound for linear gabling schemes |
| サブタイトル（和） | ASIACRYPT 2016より |
| タイトル（英） | [Invited Talk] How to circumvent the two-ciphertext lower bound for linear gabling schemes |
| サブタイトル（和） | from ASIACRYPT 2016 |
| キーワード(1)（和/英） | 歪曲回路 / garbled circuit |
| キーワード(2)（和/英） | 摂動回路 / garbling scheme |
| キーワード(3)（和/英） | スクランブル回路 / two-party computation |
| キーワード(4)（和/英） | / semi-private function evaluation |
| 第 1 著者 氏名（和/英） | 菊池 亮 / Ryo Kikuchi |
| 第 1 著者 所属（和/英） | NTT(略称：NTT) NTT Corporation(略称：NTT) |
| 発表年月日 | 2017-05-12 |
| 資料番号 | ISEC2017-5 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | ISEC-25 |
| ページ範囲 | pp.25-25(ISEC), |
| ページ数 | 1 |
| 発行日 | 2017-05-05 (ISEC) |