通用组合密码框架A Unified Framework for UC from only OT

通用组合密码框架A Unified Framework for UC from only OT

A Unified Framework for UC from Only OTHuijia Lin, MIT and BU Rafael Pass, Cornell Muthuramakrishnan Venkitasubramaniam, University of Rochester

通用组合密码框架A Unified Framework for UC from only OT

Secure MPCGoal: Allow a set of distrustful parties to compute ANY function f on their own

CorrectnessWhat to get---the outputs

PrivacyWhat to hide---the private inputs

Even when no honest majority

通用组合密码框架A Unified Framework for UC from only OT

Simulation ParadigmREAL IDEALSimulator

x1 y 1 AR x2 y2 x1 y1

AI x2y2

“as correct& private as”Correctness: The output of every player in ideal is the same as in realPrivacy: The simulator can learn whatever the adv learnsIn this talk, we focus on static malicious corruption

通用组合密码框架A Unified Framework for UC from only OT

The Concurrent Model

MANY sets of players executing MANY different protocols all at once[DDN, DNS, GK, Fe, KPR, RK, CKPR, KP, PRS, C...and many others]

通用组合密码框架A Unified Framework for UC from only OT

Concurrent Security (informally)REAL IDEAL

Many executions of different protocols

Many executions with INDEPENDENT trusted parties

通用组合密码框架A Unified Framework for UC from only OT

Universal Composibility (UC)[Can00]

ZImpossible[CF01, CKF03]

Z

Strong Security ---Poly-Time Security Reduction Z: An online distinguisher UC-Compostion Thm: Supports modular analysis

通用组合密码框架A Unified Framework for UC from only OT

State-of-the-artEither, Assume additional TRUST --- UC with Set-Ups— Public Key Registration[BCNP04,LPV09,DNO10]— Tamper-Proof Hardware[Kat07,CGS08,LPV09,GISVW10]— CRS, URS, sun-spot[Can01,CLOS02,CPS07,CDPW07,LPV09,DNO10]— Timing Model[DNS98,KLP05,LPV09]

Or, Relax security requirement— Super-Poly Time Simulation (SPS)[Pas03, BS05, LPV09, GGJS12]— Angel-based Security Model[PS04, MMY06]— UC with super-poly helpers[CLP10]

通用组合密码框架A Unified Framework for UC from only OT

A Unified Framework for UC with Set-Ups[LPV09]:Assume the existence of t-round UC-Puzzle in Trusted Setup T& Enhanced Trapdoor Permutations. Then, every goal can be UC-securely realized in O(t)-rounds in T Minimal Trust: UC-Puzzles characterize when UC-sec is feasible in a setup Open: UC from semi-honest OT, generically? Optimal Round Complexity: If O(1)-rnd UC-puzzle O(1)-rnd UC protocols

with optimal round complexity?

Progress in Specific Models:Assume O(r)-round semi-honest OT: Key Registration (KA): Round Optimal (O(r)-rnd) UC protocols[DNO10] CRS, URS: O(m)-round (m is number of players) UC protocol[DNO10] Coin-Toss Hybrid Model: Round Optimal UC protocols[MPR10] Tamper-Proof Hardware: O(1)-round unconditional UC protocols[GJSVW10]

通用组合密码框架A Unified Framework for UC from only OT

Yes! (Our Result --- Part 1)Main Theorem: Unified Framework for UC from OTAssume the existence of t-round UC-Puzzle in Trusted Setup T& r-round semi-honest OT. Then, every goal can be UC-securely realized in O(t+r)-rounds in T

Optimal Solutions in various models:Trusted Set-Up Models, SPS Model, Bounded Concurrent Model

通用组合密码框架A Unified Framework for UC from only OT

Application to trusted set-up models:Corollary 1: O(r)-rnd UC from O(r)-rnd semi-honest OT in trusted set-up models: Public Key Registration Tamper-Proof Hardware CRS, URS Timing Model sun-spot (additionally assume CRHF)

Optimal Round Complexity: Assu

me O(1)-round semi-honest OT O(1)-round UC protocols Tight Assumption: In many models, like KR, CRS, URS ([DNO10]), timing O(r)-round UC protocols O(r)-round semi-honest OT

通用组合密码框架A Unified Framework for UC from only OT

Application to Strong SPS security:Corollary 2: O(r)-rnd Strong SPS from O(r)-rnd semi-honest OT secure for superpoly time. - Strong SPS means real and simulated executions are indistinguishable for super-poly time. Optimal Round Complexity: O(r)-round semi-honest OT for super-poly time O(1)-round SPS Tight Assumption: O(r)-round Strong SPS security O(r)-round semi-honest OT secure for superpoly time

通用组合密码框架A Unified Framework for UC from only OT

Application to m-Bounded Concurrent Model:(where there are at most m concurrent executions)

Corollary 3: O(m+ r)-round secure computation protocols in m-bounded concurrent model from O(r)-round semi-honest OT. Optimal Round Complexity: Assume O(1)-round semi-honest OT O(m)-rnd secure comp. in m-bounded concurrent model, optimal by[Lin08] Resolving the Complexity of Password-Authenticated Key Exchange (PAKE) Since, 2-bounded concurrent secure comp PAKE[BCLPR05] we have O(r)-round semi-honest OT O(r)-round PAKE By O(r)-round semi-honest OT O(r)-round PAKE[Ngu05] O(r)-round PAKE O(r)-round OT

通用组合密码框架A Unified Framework for UC from only OT

Our Result --- Part 2SPS from (Poly-Time Secure) Semi-Honest OTRecall: SPS with strong indistinguishability requires super-poly-time secure OT

Consider Plain SPS(SPS with only poly-time indistinguishability )

Theorem:Assume the existence of O(1)-round semi-honest OT. Then, every goal can be securely realized with plain SPS security in O(1)-round. The first constant-round concurrently secure protocol from standard poly-time hardness assumption(Independently achieved by[GGJS12])

通用组合密码框架A Unified Framework for UC from only OT

Towards Our Main Theorem

t-rnd UC-puzzle

r-rnd semi-honest OT

O(t+r)-rnd UC

通用组合密码框架A Unified Framework for UC from only OT

Approach of[LPV09]Trusted Set-Up OWF[LP12,Goy12]

UC-Puzz …… 此处隐藏：3897字，全部文档内容请下载后查看。喜欢就下载吧 ……