| Presentation | 2017-05-12 [Invited Talk] How to circumvent the two-ciphertext lower bound for linear gabling schemes Ryo Kikuchi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | garbled circuit / garbling scheme / two-party computation / semi-private function evaluation |
| Paper # | ISEC2017-5 |
| Date of Issue | 2017-05-05 (ISEC) |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2017/5/12(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kikai-Shinko-Kaikan Bldg. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Masahiro Mambo(Kanazawa Univ.) |
| Vice Chair | Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) |
| Secretary | Kazuto Ogawa(Toshiba) / Atsushi Fujioka(Tohoku Univ.) |
| Assistant | Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Invited Talk] How to circumvent the two-ciphertext lower bound for linear gabling schemes |
| Sub Title (in English) | from ASIACRYPT 2016 |
| Keyword(1) | garbled circuit |
| Keyword(2) | garbling scheme |
| Keyword(3) | two-party computation |
| Keyword(4) | semi-private function evaluation |
| 1st Author's Name | Ryo Kikuchi |
| 1st Author's Affiliation | NTT Corporation(NTT) |
| Date | 2017-05-12 |
| Paper # | ISEC2017-5 |
| Volume (vol) | vol.117 |
| Number (no) | ISEC-25 |
| Page | pp.pp.25-25(ISEC), |
| #Pages | 1 |
| Date of Issue | 2017-05-05 (ISEC) |