Efficient Pseudorandom Correlation Generators: MPC With .
Efficient Pseudorandom Correlation Generators:MPC with Silent PreprocessingPeter Scholl21 January 2020, IISc BangaloreJoint work with:Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal
Outline Pseudorandom correlation generators (PCGs) Motivation: MPC in the preprocessing model Why LPN is a perfect match for HSS/PCGs PCG for OT from LPN: Two-round “silent” OT extension Practical PCG for OLE from LPN Concretely efficient under variant of ring-LPNPeter Scholl2
Secure Computation with PreprocessingDominates overall cost[Beaver ’91]Correlated Online phase𝑓𝑓(𝑥𝑥, 𝑦𝑦)Peter Scholl𝑦𝑦 Information-theoretic Constant comp. and comm.overhead3
Secure Computation with Silent Preprocessing[BCGI 18, BCGIKS lated, short seeds Less communication Lower storage costsSilentexpansionCorrelated pseudorandomness𝑥𝑥Online phase𝑓𝑓(𝑥𝑥, 𝑦𝑦)Peter Scholl𝑦𝑦4
Pseudorandom Correlation Generators[BCGI 18, BCGIKS 19] Target correlation: (𝑅𝑅0 , 𝑅𝑅1 ) E.g. random OT ( 𝑏𝑏, 𝑚𝑚𝑏𝑏 , 𝑚𝑚0 , 𝑚𝑚1 ) Algorithms Gen, Expand:𝑅𝑅 0 Expand 𝑘𝑘0𝑘𝑘0𝑘𝑘0 , 𝑘𝑘1 Gen(1𝜆𝜆 )𝑘𝑘1𝑅𝑅 1 Expand(𝑘𝑘1 )Security: 𝑘𝑘0 , 𝑅𝑅 1 (𝑘𝑘0 , 𝑅𝑅1 𝑅𝑅0 Expand 𝑘𝑘0 )Peter Scholl6
Landscape of PCGs“Gentria” LWE “Cryptomania” DDH low-degree PRG LWE low-degree PRG“Lapland” LPN“Minicrypt” OWFGeneral additivecorrelations[BCGIKS 19]Low-degree correlations [BCGIO 17](1/poly error)Low-degree correlations [BCGIKS 19]vector-OLEOT, constant degreecorrelationsLinear correlationsTruth tablesPeter Scholl[BCGI 18][BCGIKS 19][GI 99, CDI 05][BCGIKS 19]8
Background: LPN and LWE(spot the difference!)Given 𝐴𝐴 𝑍𝑍𝑝𝑝𝑚𝑚 𝑛𝑛 :LWE 𝑝𝑝 2 𝑠𝑠 𝑍𝑍𝑝𝑝𝑛𝑛 𝑒𝑒 is small𝐴𝐴𝑠𝑠 𝑒𝑒mod 𝑝𝑝 𝑢𝑢LPN 𝑝𝑝 2 𝑝𝑝 2 (arithmetic generalization/RLC) 𝑠𝑠 𝑍𝑍𝑝𝑝𝑛𝑛 𝐻𝐻𝐻𝐻(𝑒𝑒) is smallPeter Scholl9
LWE and LPN: what are they good for?Additive HEFHECryptomaniaMinicryptPRG SKESig.PKEFEOTHSS/Succinct MPC*low noiseTodayLPNlownoise“MPCfriendly” PRGPeter SchollLWE*for low deg. functions10
Simple PRGs from LPN“Primal” construction(𝑠𝑠, 𝑒𝑒)𝑛𝑛 𝑚𝑚 log 𝑡𝑡bits𝑚𝑚𝑛𝑛𝐴𝐴𝑠𝑠 “Dual” construction𝑒𝑒𝑡𝑡 𝐻𝐻𝐻𝐻(𝑒𝑒)𝑒𝑒𝑚𝑚 log 𝑡𝑡bits(𝑚𝑚 𝑛𝑛)𝑚𝑚𝐻𝐻𝑒𝑒Security: both equiv. to LPN (if 𝐻𝐻 is parity-check matrix of code 𝐴𝐴)Limited to quadratic stretchPeter SchollArbitrary poly stretch best attack: exp(𝑡𝑡)11
Blueprint: How to exploit sparse noise for PCGsStep 1: Compress secret-shares of sparse vector with �� 𝑒𝑒0 𝑒𝑒1𝑒𝑒1Step 2: Use 𝑒𝑒 as seed for PRG 𝑒𝑒 𝐻𝐻 𝑒𝑒Peter Scholl12
I: PCG for oblivious transfer from LPNPeter Scholl13
Oblivious Transferb {0,1}𝑋𝑋𝑏𝑏OT𝑋𝑋0 , 𝑋𝑋1 Problem: OT is expensive (“public-key”) OT extension: many OTs from a few base OTs symmetric crypto [IKNP 03] Problem: communication 𝑂𝑂(𝑛𝑛𝑛𝑛) for 𝑛𝑛 OTs Silent OT extension: communication sublinear in 𝑛𝑛Peter Scholl14
Towards silent OT extensionCorrelated OT𝑏𝑏𝑖𝑖 , 𝑣𝑣𝑖𝑖 , (𝑤𝑤𝑖𝑖 , 𝑤𝑤𝑖𝑖 𝑦𝑦)𝑣𝑣𝑖𝑖 𝑤𝑤𝑖𝑖 𝑏𝑏𝑖𝑖 𝑦𝑦cr hash[IKNP 03]localGoal: a PCG for correlated OTi.e. compression of:𝑏𝑏𝑣𝑣⃗Random OT𝑏𝑏𝑖𝑖 , 𝑣𝑣𝑖𝑖 , (𝑤𝑤𝑖𝑖0 , 𝑤𝑤𝑖𝑖1 )𝑏𝑏𝑖𝑖𝑣𝑣𝑖𝑖 𝑤𝑤𝑖𝑖𝑣𝑣⃗ 𝑤𝑤 𝑦𝑦 𝑏𝑏Peter Schollderand.OT𝑏𝑏𝑖𝑖 , 𝑣𝑣𝑖𝑖 , (𝑚𝑚𝑖𝑖0 , 𝑚𝑚1𝑖𝑖 )𝑏𝑏𝑣𝑣𝑖𝑖 𝑚𝑚𝑖𝑖 𝑖𝑖𝑦𝑦⃗𝑤𝑤15
Silent OT Extension: OverviewSetupReceiverSenderseedseedPPRFsparse 𝑒𝑒⃗uniformLPN 0,1𝑚𝑚Shares of 𝑦𝑦 𝑒𝑒:⃗.𝑦𝑦 𝔽𝔽2𝜆𝜆localcomp. correlated OTsPeter SchollRandom OTs16
Main tool: puncturable PRF PRF 𝐹𝐹 0,1𝜆𝜆 𝑘𝑘 Gen(1𝜆𝜆 ) 1, , 𝑁𝑁 0,1𝜆𝜆 Master key: allows evaluating 𝐹𝐹 𝑘𝑘, 𝑥𝑥 for all 𝑥𝑥 𝑘𝑘 Punc(𝑘𝑘, 𝛼𝛼) Punctured key: can evaluate at all points except for 𝑥𝑥 𝛼𝛼 Security: 𝐹𝐹(𝑘𝑘, 𝛼𝛼) is pseudorandom, given 𝑘𝑘 Simple tree-based construction from a PRG:[BW13], [BGI 13], [KPTZ 13]Peter Scholl𝑘𝑘 𝜆𝜆,𝑘𝑘 𝜆𝜆 log 𝑁𝑁17
Key observation: puncturable PRF compressessparse vectorsSetupReceiver𝛼𝛼 {1, , 𝑁𝑁}𝑘𝑘 Gen(1𝜆𝜆 )𝑘𝑘 Punc(𝑘𝑘, 𝛼𝛼)𝛼𝛼, 𝑘𝑘 0𝑧𝑧 at pos. 𝛼𝛼Sender𝑧𝑧 𝐹𝐹 𝑘𝑘, 𝛼𝛼 𝑦𝑦Eval at all 𝑥𝑥 𝛼𝛼 . 0 0 1 0𝑦𝑦 𝛼𝛼)𝐹𝐹(𝑘𝑘, Eval at 1, , 𝑁𝑁0 Shares compressed from 𝜆𝜆 𝑁𝑁 to 𝜆𝜆 log 𝑁𝑁 bits Can tweak to multiply by arbitrary 𝑦𝑦 𝔽𝔽2𝜆𝜆Peter Scholl𝑘𝑘 𝑦𝑦 𝔽𝔽2𝜆𝜆18
From weight-1 vectors to weight-𝑡𝑡 vectorsApproach 1: addition .Approach 2: concatenation𝑦𝑦 𝑒𝑒1 𝑦𝑦 𝑒𝑒𝑡𝑡.Weight e.g. 𝑡𝑡 4Expansion cost: 𝑂𝑂(𝑡𝑡 𝑁𝑁) (naïve)𝑂𝑂(𝑁𝑁) (batch codes [BCGI18, SGRR 19])Peter Scholl𝑁𝑁𝑂𝑂 𝑡𝑡 𝑂𝑂(𝑁𝑁)𝑡𝑡Note: regular error pattern19
From sparse products to correlated OT Recall, have shares: Want: uniform vector .Publiclinear 𝐻𝐻weight 𝑡𝑡Publiclinear 𝐻𝐻 . 𝑦𝑦 (𝐻𝐻𝐻𝐻)Pseudorandomunder LPN!Peter Scholl20
Setup protocol: inside the puncturable PRFBased on [Doerner-shelat ‘17]Suppose Receiver hasfor first 2 levels:Use OT to transfer nextLeft/right:OTRecoverPeter Scholl𝛼𝛼(sum of L, sum of R)OTs for all levels can bedone in parallel!(Unlike [Ds 17] for DPF)22
Recap: silent OT extension Setup protocol: 2 rounds from any 2-round OT Cost: 𝑂𝑂(𝜆𝜆 log 𝑁𝑁) base Ots Silent expansion (𝑁𝑁 OTs): 𝑂𝑂(𝑁𝑁 log 𝑁𝑁) PRF evaluations 1 multiplication 𝐻𝐻 𝑥𝑥 Implies two-round OT extension on chosen inputs Can convert from random chosen in parallel with setup First concretely efficient two-round OT extension(bypass [GMMM 18] impossibility via LPN)Peter Scholl23
Extras: active security, implementation Active security: Lightweight PPRF consistency checks for malicious sendero Allows selective failure attacks – sender can guess 1 bit of LPN erroro Assume problem is hard with 1-bit leakage 10-20% overhead on top of semi-honest Implementation: Main challenge: fast mult. by 𝐻𝐻 Quasi-cyclic 𝐻𝐻: polynomial mult. mod 𝑋𝑋 𝑛𝑛 1 Security based on quasi-cyclic syndrome decoding / ring-LPNPeter Scholl24
Runtimes (ms) for n 10 million random 8100101LAN (10 Gbps)WAN (100 MBps)WAN (10 MBps)IKNP vs silent OTTotal comm: 160 MB vs 127 kBPeter Scholl26
II: PCG for OLE correlations from LPN andring-LPNPeter Scholl27
Degree-2 correlation:Oblivious Linear Evaluation (OLE)𝑥𝑥 𝑍𝑍𝑝𝑝𝑦𝑦 𝑎𝑎𝑎𝑎 𝑏𝑏OLE𝑎𝑎, 𝑏𝑏 𝑍𝑍𝑝𝑝Related: multiplication triples Obtained from 2 random OLEs (two parties)Peter Scholl28
Main tool: FSS for point functions Point function 𝑓𝑓𝛼𝛼,𝛽𝛽 : 1, , 𝑁𝑁 0,1𝑓𝑓𝛼𝛼,𝛽𝛽 𝑥𝑥 𝛽𝛽0𝑠𝑠0𝑦𝑦0𝜆𝜆Gen 𝛼𝛼, 𝛽𝛽Eval at {1, , 𝑁𝑁}if 𝑥𝑥 𝛼𝛼o. w.𝑦𝑦0 𝑦𝑦1 (00 𝛽𝛽 00)Peter Scholl𝑠𝑠1𝑦𝑦129
PCG for tensor product from LPN and FSS[BCGIKS ’19] Pick 𝑒𝑒, 𝑓𝑓 with 𝐻𝐻𝐻𝐻 𝑡𝑡 Tensor product 𝑒𝑒 𝑓𝑓 is sparse Distribute shares of 𝑒𝑒, 𝑓𝑓 and 𝑒𝑒 𝑓𝑓 With FSS for O(𝑡𝑡 2 ) points𝑓𝑓𝑒𝑒Peter Scholl30
PCG for tensor product from LPN and FSS[BCGIKS ’19]𝑠𝑠0𝑅𝑅0𝑡𝑡-sparse 𝑒𝑒, 𝑓𝑓𝑡𝑡 2 - point FSS for 𝑒𝑒 𝑓𝑓Eval at {1, , 𝑛𝑛2 }𝑅𝑅0 𝑅𝑅1 𝑒𝑒 𝑓𝑓𝐻𝐻 (𝑅𝑅0 𝑅𝑅1 ) 𝐻𝐻 𝑇𝑇 𝐻𝐻𝐻𝐻 (𝐻𝐻𝐻𝐻)Peter Scholl𝑠𝑠1𝑅𝑅131
Applications of PCG for tensor product Deg-2 correlations: 𝑛𝑛 OLEs or Beaver triples with 𝑜𝑜(𝑛𝑛) communication Computation: Ω(𝑛𝑛2 ) Extends to deg-𝑑𝑑 (cost: Ω(𝑛𝑛𝑑𝑑 )) PCG for deg-𝑑𝑑 homomorphic secret-sharing for deg-𝑑𝑑 functions Let (Gen, Expand) be PCG for R [𝑟𝑟, 𝑟𝑟 𝑟𝑟, , 𝑟𝑟 𝑑𝑑 𝑟𝑟] Share(x): apply Gen and make 𝑥𝑥𝑥 𝑥𝑥 𝑟𝑟 public Evalp: write 𝑝𝑝(𝑥𝑥) as 𝑝𝑝𝑝(𝑟𝑟), where 𝑝𝑝𝑝 is determined by 𝑥𝑥𝑥, and linear in RPeter Scholl32
Efficient PCG for OLE from ring-LPN[ongoing work] Idea: Replace tensor product with polynomialmultiplication Similar to [BV11] for FHE𝑒𝑒, 𝑓𝑓 𝑍𝑍𝑝𝑝 [𝑋𝑋] Take sparse polys 𝑒𝑒, 𝑒𝑒 ′ , 𝑓𝑓, 𝑓𝑓𝑓𝑒𝑒 𝑓𝑓′′ Distribute shares of 𝑒𝑒, 𝑒𝑒 (𝑓𝑓, 𝑓𝑓 ) Outputℎ𝑒𝑒 𝑒𝑒 ′ ℎ𝑓𝑓 𝑓𝑓 ′ mod (𝑋𝑋 𝑛𝑛 1)for public, random ℎ 𝑍𝑍𝑝𝑝 [𝑋𝑋]Peter Schollmod 𝑋𝑋 𝑛𝑛 1Linear in 𝑒𝑒, 𝑒𝑒 ′ (𝑓𝑓, 𝑓𝑓 ′ )34
Efficient PCG for OLE from ring-LPN[ongoing work] Cost: for 1 OLE in 𝑍𝑍𝑝𝑝 𝑋𝑋 /(𝑋𝑋 𝑛𝑛 1) 𝑂𝑂(𝑡𝑡 2 𝑛𝑛 log 𝑛𝑛) computationGives 𝑛𝑛 OLEs in 𝑍𝑍𝑝𝑝 if 𝑋𝑋 𝑛𝑛 1 splits into linear factors mod 𝑝𝑝 Security: Arithmetic ring-LPNℎ, ℎ 𝑠𝑠 𝑒𝑒mod (𝑝𝑝, 𝐹𝐹(𝑋𝑋)) Does not appear significantly weakerPeter Scholl35
Conclusion PCG for OT from LPN Random OT (and correlated OT): practical, almost zero communication (previously: 𝜆𝜆 bits per OT) Two-round OT extension PCG for OLE From LPN (expensive) Efficient from fully splitting ring-LPN Open problems: Optimize OT: better codes Security of arithmetic ring-LPN Efficient PCGs for more correlations:o Truth tables (active security), random bits (ℤ𝑝𝑝 ), garbled circuits Peter Scholl36
Thank you!Efficient Pseudorandom Correlation Generators: Silent OT Extension and MoreBoyle, Couteau, Gilboa, Ishai, Kohl, Schollhttps://ia.cr/2019/129Two-Round OT Extension and Silent Non-Interactive Secure ComputationBCGIKS Rindalhttps://ia.cr/2019/1159Code: https://github.com/osu-crypto/libOTePeter Scholl37
“Cryptomania” DDH low-degree PRG Low-degree correlations [BCGIO 17] (1/poly error) LWE low-degree PRG Low-degree correlations [BCGIKS 19] “Minicrypt” OWF Linear correlations [GI 99, CDI 05] Truth tables [BCGIKS 19] Landscape of PCGs. Peter Scholl 8 “Lapland” LPN vector-O
We highly recommend using your MPC hardware’s sound card (Akai Pro MPC X/Live/Touch ASIO). If you need to use the internal sound card on a Windows computer, we recommend downloading the latest ASIO4ALL driver at asio4all.com. To view the MPC software user guide, click the Help menu in the MPC software, select MPC Help, and select
MN SU-MPC ING March 2008 Page 1 of 9 INSTRUCTION MANUAL ALSATOM SU 50-MPC, SU 100-MPC, SU 140-MPC, SU 140/D-MPC This unit is manufactured by ALSA APPARECCHI MEDICALI S.R.L., Via C. Bonazzi 16, 40013 Castel Maggiore (BO), Italy, that guarantees its safety,
CHAPTER 10 Aggregate Demand I 13 Solving for Y: (1 MPC) MPC Y T MPC 1MPC Final result: Y T The tax multiplier def: the change in income resulting from a 1 increase in T : MPC 1MPC Y T CHAPTER 10 Aggregate Demand I 14 0.8 0.8 4 10.8 0.2 Y T If MPC 0.8, then the tax multiplier equals The tax multiplier
MPC Renaissance and MPC Studio are unrivaled instruments for music production. The new flagship is a fully integrated hardware/software system: MPC Renaissance allows you to create using classic hardware controls and an integrated pop-up display, while its exclusive MPC
A STATISTICAL TEST SUITE FOR RANDOM AND PSEUDORANDOM NUMBER GENERATORS FOR CRYPTOGRAPHIC APPLICATIONS Reports on Computer Systems Technology The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the nation's
Real-time MPC has been implemented and evaluated in the physical testbed. † Three special efforts are made to enable real-time implementation of MPC. † Load fluctuations on the shipboard are addressed using real-time MPC. † A filter-based algorithm is used to validate the effectiveness of MPC. †
Michael Fullan – November 8, 2017, MPC/IL ASCD Partnership Event 12 Deep Leadership: Maximizing Impact MPC Resources & Supports — Member/Partner Benefi ts Legal Breakfasts and Professional Support Network 13 Current MPC Executive Board Members/Partners/Honorary Members 14 MPC 2016-17 Calendar 15 Registration Pages 16 / 17 / 18 / 19
accounting items are presumed in law to give a true and fair view. 8 There is no explicit requirement in the Companies Act 2006 or FRS 102 for companies entitled to prepare accounts in accordance with the small companies regime to report on the going concern basis of accounting and material uncertainties. However, directors of small companies are required to make such disclosures that are .
