Efficient OT Extension for Enhanced Secure Computation
Explore "Improved OT Extension for Transferring Short Secrets" by Vladimir Kolesnikov and Ranjit Kumaresan, delving into the state-of-the-art in secure computation, practical computational overhead hierarchy, and the impact of extending primitives like PKE and SKE. Discover the significance of Oblivious Transfer and its cost implications in cryptography.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Improved OT Extension for Transferring Short Secrets Vladimir Kolesnikov (Bell Labs) Ranjit Kumaresan (Technion)
Secure Computation x y f1(x,y) f2(x,y) Most general problem in cryptography Moving fast from theory to practice Major research effort Improving (asymptotic & concrete) efficiency Implementation & Systems issues
State of the Art (Semihonest Setting) THEORY PRACTICE [IKOS08] Constant overhead [G09,BV11]: FHE optimal communication [LO13,GKK+12,GGH+13] ORAM based SFE [HEKM11,BHKR13] Yao86+KS08,PSSW09 [KK12] [Yao86]+ [GMW87] [CHKM12,SZ13,ALSZ13] (Multiparty) [GMW87]
Practical Computational Overhead Hierarchy of efficiency FHE >> PKE >> SKE >> one-time pad LHS >> RHS cost of LHS is, and will probably always be, by orders of magnitude, bigger than cost of RHS. OT Extension motivated by PKE >> SKE
Talk Outline OT Extension Ishai et al. (IKNP) OT Extension A New Framework for IKNP
PKE >> SKE SKE PKE E.g: PRG, hash functions Easy to implement heuristically Cheaper E.g: KA, OT, SFE Hard to implement heuristically More expensive PKE cannot be black-box reduced to SKE [IR89] Factor ~ 3-4 orders of magnitude slower Intel AES-NI instruction set
The Next Best Thing: Extending Primitives [IR89] ? + Extending public key encryption is easy Encrypt payload with symmetric key Encrypt symmetric key with public key Huge practical impact What about extending Oblivious Transfer?
Oblivious Transfer (OT) r x0 , x1 ??? xr GMW Yao Used to select one of two garbled keys Evaluate each AND gate in the circuit
Cost of OT No blackbox redn from OT to one-way functions [IR89] OT length extension is easy: efficient, black-box G(s0) x0 x0 s0 + r r x1 s1 G(s1) x1 OT instance extension is possible [B96,IKNP03] Needs only k seed OTs to perform n >> k OTs Additional n symmetric key (cheap) operations Huge impact on SFE
OT Extension: Prior Work [Beaver 96]: First OT extension [Ishai-Kilian-Nissim-Petrank 03] (IKNP) Random Oracle (RO) model or Correlation robust hash functions (CRHF) Most practical OT extension [HIKN08,NNOB12]: Malicious OT extension [LZ13]: (In)feasibility results for OT extension This work: Improve semihonest IKNP
Talk Outline OT Extension Ishai et al. (IKNP) OT Extension A New Framework for IKNP
[IKNP03] Strategy s2 sk s1 x1,0 x1,1 r1 s2 sk s1 x2,0 x2,1 r2 ... ... n x3,0 x3,1 + O(n) H r3 .... xn,0 xn,1 Length Extension rn + O(n) H
[IKNP03] Main Reduction Receiver picks T R {0,1}n k Sender picks s R {0,1}k Sender obtains Q {0,1}n k qi= ti qi= ti s 1 1 0 0 1 1 ri=0 1 0 0 1 1 0 ri=1 t2 ...tk t1 r t1 r t2 r tk r ... t1 t2 tk r s1 s2 sk yi,0 = xi,0 H(qi) yi,1 = xi,1 H(qi s) zi= yi,r H(ti) For 1 i n, Sender sends For 1 i n, Receiver outputs i i
IKNP Cost Communication cost of resulting OT(n,L): Main reduction: 2nL bits Length extension: 2nk bits Communication cost of resulting SFE: [Yao86]: need to transfer keys of length L = k [GMW87]: L = 1, cost = 2nk +2n, optimal?
Talk Outline OT Extension Ishai et al (IKNP) OT Extension A New Framework for IKNP
Our Work: A Closer Look at IKNP 1 1 0 ri=0 1 0 1 0 0 0 1 0 1 ri=1 0 0 1 1 1 1 t2 r t1 r tk r ... ... ... ; = T t1 t2 tk r r r T U R
Alternate Point of View k R = T U ri=0 0 0 0 ri=1 1 1 1 Row-wise encoding 0 0k 1 1k ... n r r r IKNP uses repetition encoding R Can we use other encodings?
A Coding Theoretic Framework for IKNP k r1 C(r1) Suppose use code C Say ri comes from a larger domain {1, ,m} Row-wise encoding ri C(ri) {0,1}k r2 C(r2) ... n rn C(rn) C(R)
A Coding Theoretic Framework for IKNP C(R) = T U Sender obtains Q {0,1}n k q1= t1 (C(r1) s) q2= t2 (C(r2) s) r1 [m] r2 [m] ... ... u1t2 uk t1u1 t2u2 tkuk qn= tn (C(rn) s) rn [m] s1 s2 sk Bit-wise AND For 1 i n, 1 r m Sender sends For 1 i n, Receiver outputs yi,r= xi,r H(i, qi (C(r) s)) zi= yi,r H(i, ti) i i
Analysis Perfect security against malicious sender Statistical security against semihonest receiver: No loss unless query H on (i, ti (C(r) s))for some r Loss in security: m2-d, where d = min distance of C Cost of 1-out-of-m OT(n, L): Communication: (2nk+nmL)bits OT(n,L) 1-out-of-m OT(n/log m, L log m) Communication: (n/log m)(2k + mL log m) bits
Efficiency Concrete: Hadamard codes for encoding Factor 2 for 1-out-of-2 OT and GMW for k=256 Additional optimizations lead to factor 3.5 Asymptotic comm. cost per OT: O(k/log k) bits
Conclusions OT Extension motivated by PKE >> SKE Huge impact on practicality of SFE Coding theoretic framework for [IKNP03] RO or code correlation robust hash functions Improvements for GMW, OT, 1-out-of-m OT Rethink GMW vs. Yao? Also [KK12], [NNOB12], [SZ13], [ALSZ13]
The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 259426 ERC Cryptography and Complexity
