《1-2 PSI 在隐私计算中的发展和应用.pdf》由会员分享,可在线阅读,更多相关《1-2 PSI 在隐私计算中的发展和应用.pdf(40页珍藏版)》请在三个皮匠报告上搜索。
1、安全求交集在隐私计算中的发展和应用段普蚂蚁集团共享智能2022年7月Roadmap安全求交集(PSI)定义PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合ReferencesRoadmap安全求交集(PSI)定义定义我们还需要什么?PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合References安全求交集(PSI)定义Private Set IntersectionAlice has set X and Bob has set Y.After PSI computation,Alice learns X Y and nothing elseAlice cannot kn
2、ow Bobs elements that dont belong to X YProvable security我们还需要什么?Normally different methods should be presented for PSI at this pointLets do something elseAssume there is a PSI protocolWhat else do we need from PSI?Roadmap安全求交集(PSI)定义PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合ReferencesTwo-Party Semi-Honest PSIOn
3、ly for the intersectionIntersection is disclosed and non-intersection is kept secretOnly for two partiesAlice and BobOnly semi-honest secureAttacker strictly follow protocol,but is curious for the other partys secret information Two-Party Semi-Honest PSI(contd)Challenge 1:隐藏非交集元素(hiding)Cryptographi
4、cally secure“hiding”When two elements are not equal,some kind of“noise”must be attached such that unmatched elements cannot be exhaustively computedChallenge 2:计算交集元素(comparing)When two elements are equal,their equality should be able to disclosed in some wayChallenge 3:效率高(efficiency)PSI protocol i
5、s practical for large-scale applicationMethod1:PSI Based on Diffie-Hellman Key ExchangeDiffie-Hellman Key Exchange PSI 3Basic Idea:“double encryption”with commutative propertyHiding:“Encryption”hides elementComparing:commutative propertyEfficiencyLinear to communication costStill a mainstream implem
6、entation of PSIMany enhancements on crypto primitives Design a crypto method that can meet all the requirements Diffie-Hellman Key Exchange(contd)Discrete Logarithm Problem(DLP):given g,x and y as three large positive integers,assume gx=y mod p,given y,g,p,how to find x is a“hard problem”It is effic
7、ient to compute gxmod pEfficiencyIt is hard to find x given y,g,pHidinggxymod p is equal to gyxmod p(communicative property)Comparingg,x,p and y need to satisfy a bunch of conditions of cryptography to make this hard problem crypto hardCrypto detail omit herePSI based on DHMethod2:OPRF-based PSIProt
8、ocols 5Idea Sender computes a“secret”function on his set and the result is sent to the receiverReceiver also computes her set on this“secret”function by interacting with the sender Receiver compares received results from the sender with her own resultHiding”Secret”function:sender cannot know receive
9、rs data,receiver cannot know the“secret”functionComparingData after“secret”function can be comparedEfficiencyMost of the operations are efficient crypto operations,very less PKI operationsOblivious Pseudo-Random Functions(OPRF)OPRF:given a key k from sender and an input element e from receiverComput
10、e Fk(e)Receiver knows the output of Fk(e),but does not know kSender learns nothing about the output or the input element eOPRF for PSIReceiver evaluates OPRF on his set with k from senderReceiver does not know senders kSender does not know receivers setSender evaluates ORPF on his own set and sends
11、the results to receiverReceiver finds the intersection by comparing plaintexts of the results from sender and his own OPRF resultsOblivious Pseudo-Random Functions(OPRF)(contd)Oblivious Pseudo-Random Functions(OPRF)(contd)SecurityOPRFPerformanceHigh computation and communication costKKRT PSI Protoco
12、lTwo-Party Semi-Honest Secure PSI(contd)应用白/黑明单,撞库,等等.还有什么?交集使用?多方PSI?计算模型?安全模型?非对称PSI?其他特殊需求交集使用MotivationIntersection may“NOT”be common knowledge between PSI partiesData in an intersection belongs to othersFor example,Alice has an account at Bank A and an account Bank B,both registered with her un
13、ique IDIs it OK for Bank A and B to find Alice as a common customer through PSI?Challenge:交集“可用不可见”交集使用Case 1:intersection is confidential,but cardinality is neededOnly cardinality is disclosed to authorized partyMethodPHE+Polynomial evaluation 8DH-based PSI with shuffle 20交集使用Case 2:intersection is
14、 confidential,follow-up computation on the secret intersection is needed 9Intersection is”encrypted”,data associated with the“encrypted”intersection is used for follow-up secure computationsFor example,PSI with payload(PSI-P)on intersection where intersection itself is hidden as an intermediate resu
15、ltMethodCircuit-based PSI 9DH-PSI with permutation and PHE 20交集使用Case 3:intersection is confidential,but still need to get usedFor example,joint ads marketingMethodFHE-PSI+Differential Privacy 10DH-PSI+Differential Privacy多方PSI常规多方PSIMotivationIntersection of N parties is neededChallengeIntersection
16、 between any two parties cannot be disclosedMethodPHE+Polynomial representation 8OPPRF 11多方PSI特殊多方PSIMotivationIntersection between some two parties may need to get computed and disclosed to some specific partyChallengeRequirements change case by case Need to customize solutionMethodRegular PSI prot
17、ocols with customizations计算模型One-way Model 125MotivationOnly one party should learn the intersectionFor example,client submits contact list to a new social media serviceClient learns the set intersection and server learns nothing other than client input sizeMethod:OPRF-based PSI,etc.Mutual Model 3 M
18、otivationBoth two parties should learn the intersectionFor example,find common users between two banksMethodDH-PSI,etc.计算模型Outsourced/Delegated/Server-Aided PSI:two clients executed PSI on their outsourced data through the help from an untrusted third partyMotivation:participant cannot complete PSI
19、computation,e.g.,resource-constrained devicesChallenge:the third party only aid the computation without obtaining the final resultThe third party may be provided by large cloud service providerSo usually assume cloud is not colluded with clientsThe third party should learn nothing about the PSI resu
20、ltEven cardinality should NOT be leaked to the cloudUsually the model is that the cloud helps on PSI and obtains an encrypted matching result and sends the matching result to clients.Then the clients decrypt the matching resultMethodPolynomial representation+PHE+PRF 12安全模型Semi-Honest Secure PSI Moti
21、vationSimple,efficientMost of the PSI protocol implemented are semi-honestChallengeSecurity assumption is too strong,only consider passive adversary,i.e.,even an attacker strictly follows the protocolMethodPSI based on DH,OPRF,etc.1235安全模型Malicious Secure PSI MotivationImproved securityMore realisti
22、c security assumption,consider malicious adversaryMalicious adversary definitionChallengeMore computing and communication overheadMethodPSI protocols based with extra authentication are in this category 713非对称PSIMotivationOne party holds a much larger number of element than the other partyFor exampl
23、e,client-server scenarioMethodECC-OPRF-PSI 21Cache the larger set and only“compute”the smaller set before matchingFHE PSI 1415其他特殊需求Size-hiding 16Business scenario with customized requirementsRoadmap安全求交集(PSI)定义PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合ReferencesPSI最新进展Optimize offline phaseUse latest OT 17Repla
24、ce OT with VOLE 6Replace Cuckoo hashing with new primitivesIntroduce Probe-and-Xor-of-Strings(PaXos)13Introduce Oblivious Key-Value Store(OKVS)5Support secure computation on intersectionProgrammable OPRF 9PSI with DP 10PSI最新进展亿级计算:高带宽+高算力分钟级别完成Roadmap安全求交集(PSI)定义PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合Referenc
25、es安全求交集+差分隐私What is Differential Privacy(DP)?Add noise to make it hard to tell whether an element is in a set or notPSI Intersection UseMotivation:add DP noise to intersection such that the intersection statistically is”correct”,but any single element in the intersection is“DP hard”to determine if i
26、t is owned by both two partiesIndividual element in the intersection is protected by differential privacyJoint marketingChallenge:intersection is encrypted,but one party needs to correctly add false positive elementMethodFHE-PSI+DP 10Very inefficientDH-PSI+DPImprove Performance 18Decrease the length
27、 of padding with DP安全求交集+可信执行环境MesaTEE 19Opensource solution for PSI on TEETEE creates saltParties hash data with salt for PSIPSI done at TEEResults sent back to parties Efficient and flexibleNot like crypto solution,trust root at TEERoadmap安全求交集(PSI)定义PSI功能和分类PSI最新进展PSI和其他隐私计算技术结合ReferencesReferenc
28、es1 Benny Pinkas,Thomas Schneider,Michael Zohner.Faster Private Set Intersection based on OT Extension,USENIX Security 20142 Benny Pinkas,Thomas Schneider,Michael Zohner.Scalable Private Set Intersection Based on OT Extension,ACM Transactions on Privacy and Security,20183 Rakesh Agrawal,Alexandre V.
29、Evfimievski,and Ramakrishnan Srikant.Information sharing across private databases.Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data,20034 Emiliano De Cristofaro and Gene Tsudik.Practical private set intersection protocols with linear computational and bandwidth comple
30、xity,IACR Cryptology ePrint Archive,2009:491,20095 Vladimir Kolesnikov,Ranjit Kumaresan,Mike Rosulek,and Ni Trieu.Efficient batched oblivious PRF with applications to private set intersection.Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,20166 Peter Rindal and
31、 Phillipp Schoppmann.VOLE-PSI:fast OPRF and circuit-psi from vector-ole,Advances in Cryptology-EUROCRYPT 2021,20217 Peter Rindal and Srinivasan Raghuraman.Blazing fast PSI from improved OKVS and subfield VOLE.IACR Cryptology ePrintArchive,2022:320,20228 Lea Kissner and Dawn Song,Privacy-Preserving S
32、et Operations,Crypto 2005.9 Benny Pinkas,Thomas Schneider,Oleksandr Tkachenko,and Avishay Yanai.Efficient circuit-based PSI with linear communication.Advances in Cryptology-EUROCRYPT 201910 Bailey Kacsmar,Basit Khurram,Nils Lukas,Alexander Norton,Masoumeh Shafieinejad,Zhiwei Shang,Yaser Baseri,Marya
33、m Sepehri,Simon Oya,Florian Kerschbaum,Differentially Private Two-Party Set Operations,2020 IEEE European Symposium on Security and Privacy.References(contd)11 Vladimir Kolesnikov,Naor Matania,Benny Pinkas,Mike Rosulek,and Ni Trieu.Practical multi-party private set intersection from symmetric-key te
34、chniques.Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security,201712Abadi,Aydin,Sotirios Terzis,Roberto Metere,and Changyu Dong.Efficient Delegated Private Set Intersection on Outsourced Private Datasets,IEEE Transactions on Dependable and Secure Computing,2017.13 Be
35、nny Pinkas,Mike Rosulek,Ni Trieu,and Avishay Yanai.PSI from paxos:Fast,malicious private set intersection.Advances in Cryptology-EUROCRYPT 202014 Hao Chen,Kim Laine,Peter Rindal,Fast Private Set Intersection from Homomorphic Encryption,ACM CCS 201715 Hao Chen,Zhicong Huang,Kim Laine,Peter Rindal,Lab
36、eled PSI from Fully Homomorphic Encryption with Malicious Security,CCS 201816 Giuseppe Ateniese,Emiliano De Cristofaro,Gene Tsudik.(If)Size Matters:Size-Hiding Private Set Intersection,PKC 201117 Benny Pinkas,Mike Rosulek,Ni Trieu,and Avishay Yanai.Spot-light:Lightweight private set intersection fro
37、m sparse OT extension.Advances in Cryptology-CRYPTO 201918 Adam Groce,Peter Rindal,and Mike Rosulek,Cheaper Private Set Intersection via Differentially Private Leakage,PoPETS201919 MesaTEE,https:/ Mihaela Ion,Ben Kreuter,Ahmet Erhan Nergiz,Sarvar Patel,Shobhit Saxena,Karn Seth,Mariana Raykova,David Shanahan,Moti Yung,On Deploying Secure Computing:Private Intersection-Sum-with-Cardinality,EuroS&P,202021 Amanda Cristina Davi Resende and Diego de Freitas Aranha,Faster Unbalanced Private Set Intersection,FC2018隐语(SecretFlow)https:/ you!