当前位置：文档之家 › A threshold pseudorandom function construction and its applications

A threshold pseudorandom function construction and its applications

  • 格式：pdf
  • 大小：192.62 KB
  • 文档页数：16

AThresholdPseudorandomFunction

ConstructionandItsApplications

JesperBuusNielsen󰀤

BRICS󰀁󰀁DepartmentofComputerScienceUniversityofAarhusNyMunkegadeDK-8000ArhusC,Denmark

Abstract.Wegivethefirstconstructionofapracticalthresholdpseudo-randomfunction.Theprotocolforevaluatingthefunctionisefficientenoughthatitcanbeusedtoreplacerandomoraclesinsomeprotocolsrelyingonsuchoracles.Inparticular,weshowhowtotransformtheeffi-cientcryptographicallysecureByzantineagreementprotocolbyCachin,KursaweandShoupfortherandomoraclemodelintoacryptographi-callysecureprotocolforthecomplexitytheoreticmodelwithoutloosingefficiencyorresilience,therebyconstructinganefficientandoptimallyre-silientByzantineagreementprotocolforthecomplexitytheoreticmodel.

1Introduction

ThenotionofpseudorandomfunctionwasintroducedbyGoldreich,Goldwasser

andMicali[GGM86]andhasfoundinnumerableapplications.Apseudorandom

functionfamilyisafunctionFtakingasinputakeyKandelementx,wewrite

FK(x),whereforarandomkeytheoutputofFKcannotbedistinguishedfrom

uniformlyrandomvaluesifonedoesnotknowthekey.Ifonehavetorequire

thattheinputofFKisuniformlyrandomfortheoutputofFKtolookuniformly

random,wesaythatFisweakpseudorandom.

Oneimmediateapplicationofpseudorandomfunctionsisusingthemforim-

plementingrandomoracles:Consideraprotocolsettingwithnparties.Ac-

thresholdrandomoraclewithdomainDisanidealfunctionality(ortrusted

party).Aftercpartieshaveinput(evaluate,x),wheresayx∈{0,1}∗,the

functionalitywillreturnauniformlyrandomvaluerxR←Dtoallpartiesthat

input(evaluate,x).Thisfunctionalitydefinesauniformlyrandomfunctionfrom

{0,1}∗toD.Numerousprotocolconstructionsareknownthatcanbeproved

secureassumingthatarandomoracleisavailable.However,anyimplementation

ofsuchaprotocolmustalsoprovideanimplementationoftheoracle.Inprac-

tice,ahashfunctionisoftenusedtoreplacea1-randomoracle,butthenthe

implementationisonlysecureifanadversarycandonobetterwiththehash

󰀁buus@brics.dk.󰀁󰀁BasicResearchinComputerScience,CentreoftheDanishNationalResearchFoundation.404J.B.Nielsen

functionthanhecouldwiththeoracle.Thisissomethingthatingeneralcannot

beproved,butmustbeabeliefbasedonheuristics—infact,forsomeprotocols,

thisbeliefisalwayswrong[CGH98,Nie02].

Incontrast,pseudorandomfunctionscanbeusedtoimplementrandomora-

cleswithoutlossofsecurity.ThiscanbedonebygeneratingKatthebeginning

oftheprotocolandlettingrx=FK(x)whenrxisneeded.Itishoweverclearly

necessarythatnopartyshouldknowthekeyofFK,sincetheoutputofapseudo-

randomfunctiononlylooksrandomtopartieswhodonothavethekey.Therefore

thekey—andhencealsoabilitytoevaluatethefunction—mustbedistributed

amongthepartiesusing,forinstance,athresholdsecret-sharingscheme.

OurResultsInthispaperweconstructanewpseudorandomfunctionfamily.

ThekeywillbeaprimeQ,whereP=2Q+1isalsoaprime,arandom

valuexfromthesubgroupQPofZ∗PoforderQ,alongwith2lrandomvalues

{αj,b}j=1,...,l,b=0,1fromZQ.Thefunctionfamilymapsfromthesetofstringsof

lengthatmostltoQP,andgivenσ=(σ1,...,σm)∈{0,1}≤l,theoutputwill

bex󰀁mi=1αi,σimodP.Weprovethisfunctionfamilysecureunderthedecisional

Diffie-Hellman(DDH)assumption.

Moreimportantly,wegiveasecuren-partyprotocolforevaluatingthefunc-

tion.Ourprotocolisfortheasynchronousmodelwithauthenticatedpublicpoint-

to-pointchannels.Thisisaveryrealisticmodelofcommunicationandcanbe

efficientlyimplemented[CHH00].Theprotocolisstaticallysecureaslongasless

thann/3partiesmisbehave.Insomeapplicationstheprotocolcancommunicate

asmuchasO(ln2k)bitsperevaluation,wherekisthesecurityparameter(for

eachexponenteachpartysendstoeachotherpartykbits).However,inmany

usesthecommunicationcomplexitywillbeO(n2k)bits.

Todemonstratetheapplicabilityofournewthresholdpseudorandomfunc-

tion,wedescribehowtoimplementefficientByzantineagreement(BA)inthe

complexitytheoreticmodel,byreplacingtherandomoraclesintheprotocol

[CKS00]withourthresholdpseudorandomfunction.Theresultingprotocolhas

thesameresilienceastheprotocolin[CKS00],namelyresilienceagainstamali-

ciouscoalitionofonethirdoftheparties.Ithasthesamecommunicationcom-

plexityofO(n2k)bitsperactivationandthesame(constant)roundcomplexity

uptoasmallconstantfactor.Aspartoftheimplementationweshowhowto

replacetherandomoraclesinthethresholdsignatureschemefrom[Sho00]by

ourthresholdpseudorandomfunction.

RelatedWorkThenotionofdistributedpseudorandomfunction,whichissim-

ilartoourthresholdpseudorandomfunction,wasintroducedbyNaor,Pinkas

andReingoldin[NPR99].Theydonotdefinedistributedpseudorandomfunc-

tionsinageneralmultipartycomputationmodel—theirmodelismoread-hoc

andimplementation-near.Sincetherearedifferencesbetweenthetwonotions,

wehavechosenadifferentnameforourdefinition.

Untilnowthemostefficientknownconstructionofthresholdpseudorandom

functionswasusinggeneralmultipartycomputationtechniquesorcoin-tosspro-

合集下载

vrf协议

vrf协议

vrf协议

VRF（Verifiable Random Function）协议是一种用于生成可验证随机值的密码学协议。它可以在不使用第三方机构的情况下生成随机数值，以此实现安全信息传输。VRF协议被广泛应用于数字货币的挖矿、随机网络访问控制等方面。以下是对VRF协议的介绍和解析。

VRF协议是由西蒙·伯林哈德（Simon Birnbach）等人在2002年提出的。协议基于一个公私钥对，使用一个单向函数构建的伪随机函数和一组证明算法。在VRF协议中，保密性、完整性和不可抵赖性都得到了保障。

VRF协议中的单向函数指的是一种无法逆向计算的函数，即使是知道了函数的输出值，也无法计算出输入值。这保证了VRF协议生成的随机数值不会被预测或者被篡改。而证明算法则确保了随机数值的可验证性，即可以证明该数值来自于该公私钥对，且没有被篡改。

在VRF协议中，任何人都可以生成一个公私钥对，并使用私钥对消息进行签名。签名过程使用伪随机函数来保证签名的可验证性和不可抵赖性。而验证签名的过程使用证明算法，验证者可以验证消息的确来自于该公私钥对，并且没有被篡改。这种验证过程可以应用于数字货币挖矿和网络访问控制等场景中。

然而，VRF协议并不是完美的，其安全性和可用性都面临一定的挑战。其中一个问题是VRF协议需要进行多次单向函数加密计算，而这会导致VRF协议的运算速度变慢，影响了其应用的实时性。另外，VRF协议仍然面临着来自于量子计算攻击的威胁，需要找到更安全的加密算法来保护数据。

总之，VRF协议是一个重要的密码学协议，其基于单向函数和证明算法来保证生成可验证随机值的安全性和可靠性。然而，VRF协议仍然存在一些挑战和问题，需要持续不断地进行改进和完善，以适应现代计算和安全环境的需求。

Bibliography

Bibliography

Bibliography

[1]H.L.Abbott,LowerboundsforsomeRamseynumbers,DiscreteMath.2(1972),289–293.

[2]A.Agresti,CategoricalDataAnalysis,JohnWileyandSons,NewYork,1990,xvi+558pp.

[3]D.Aldous,OntheMarkov-chainsimulationmethodforuniformcombinatorialsimulation

andsimulatedannealing,.Sci.1(1987),33–46.

[4]D.Aldous,SomeinequalitiesforreversibleMarkovchains,J.LondonMath.Soc.25(1982),

564–576.

[5]N.Alon,Eigenvaluesandexpanders,Combinatorica6(1986),86–96.

[6]N.AlonandF.R.K.Chung,Explicitconstructionoflinearsizedtolerantnetworks,Discrete

Math.72(1988),15–19.

[7]N.Alon,F.R.K.ChungandR.L.Graham,Routingpermutationsongraphsviamatchings,

SIAMJ.Disc.Math.7(1994),513–530.

[8]N.Alon,man,Betterexpandersandsuperconcentrators,J.Algorithms

8(1987),337–347.

[9]man,λ1isoperimetricinequalitiesforgraphsandsuperconcentrators,

四大安全会议论文题目

四大安全会议论文题目

2009and2010Papers:Big-4SecurityConferences

pvo

October13,2010

NDSS2009

1.DocumentStructureIntegrity:ARobustBasisforCross-siteScriptingDefense.

Y.Nadji,P.Saxena,D.Song

2.AnEfficientBlack-boxTechniqueforDefeatingWebApplicationAttacks.

R.Sekar

3.Noncespaces:UsingRandomizationtoEnforceInformationFlowTrackingandThwartCross-SiteScriptingAttacks.

M.VanGundy,H.Chen

4.TheBlindStoneTablet:OutsourcingDurabilitytoUntrustedParties.

P.Williams,R.Sion,D.Shasha

5.Two-PartyComputationModelforPrivacy-PreservingQueriesoverDistributedDatabases.

S.S.M.Chow,J.-H.Lee,L.Subramanian

6.SybilInfer:DetectingSybilNodesusingSocialNetworks.

G.Danezis,P.Mittal

7.Spectrogram:AMixture-of-Markov-ChainsModelforAnomalyDetectioninWebTraffic.

YingboSong,AngelosD.Keromytis,SalvatoreJ.Stolfo

8.DetectingForgedTCPResetPackets.

NicholasWeaver,RobinSommer,VernPaxson

9.CoordinatedScanDetection.

【CN110061850A】变色龙哈希函数的碰撞计算方法及可编辑区块链构造方法【专利】

【CN110061850A】变色龙哈希函数的碰撞计算方法及可编辑区块链构造方法【专利】

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号 (43)申请公布日 (21)申请号 201910338232.0(22)申请日 2019.04.24(71)申请人 电子科技大学地址 611731 四川省成都市高新区（西区）西源大道2006号(72)发明人 张小松　黄可　牛伟纳　谢鑫　蒋天宇　葛洪麟　(74)专利代理机构 成都弘毅天承知识产权代理有限公司 51230代理人 李春霖(51)Int.Cl.H04L 9/32(2006.01)H04L 9/30(2006.01)

(54)发明名称变色龙哈希函数的碰撞计算方法及可编辑区块链构造方法(57)摘要本发明公开了一种变色龙哈希函数的碰撞计算方法，其系统公钥和哈希碰撞由k个用户节点基于环的形式共同计算得到，缺少任何一方都会导致碰撞无法正确产生，从而实现安全可信的计算碰撞，避免碰撞结果或恶意获取或利用的问题。还公开一种基于环的变色龙哈希函数的计算碰撞方法的可编辑区块链构造方法，系统密钥由多个用户节点共同计算产生，当需要计算哈希碰撞时，需要多个用户联合起来构成一个环，然后使用各自的私钥共同计算碰撞，从而对相应的区块发起重新编辑，实现去中心化的可编辑区块

链。

权利要求书1页 说明书5页 附图1页CN 110061850 A2019.07.26

CN 110061850

A1.一种变色龙哈希函数的碰撞计算方法，其特征在于：方法如下：系统初始化：设置系统公开参数；系统哈希密钥生成：k个用户节点组成一个环，根据设置的公开参数和用户的私钥，环内的每一个用户按照环的顺序，依次参与计算系统公钥，并共同得到一个系统公钥；哈希计算：根据公开参数、身份信息、消息、和计算得到的系统公钥，计算变色龙哈希值和变色龙随机数；碰撞计算：根据公开参数，基于用户各自的私钥和计算得到的系统公钥、变色龙哈希值、变色龙随机数、变色龙随机数对应的消息，再结合新的消息，环内每一个用户按照环的顺序，分别使用各自的私钥共同参与计算哈希碰撞，通过计算哈希碰撞的结果推导得到满足碰撞的新的变色龙随机数。2.根据权利要求1所述的变色龙哈希函数的碰撞计算方法，其特征在于：所述设置系统公开参数步骤具体包括：先选择安全参数，根据安全参数选取素数q，并选取阶为q生成元为g的一个GDH群G，再选取两个哈希函数H0：{0，1}*→G*，H1：{0，1}*→Zq，其中Zq为q阶整数群，系统公开参数为paramTCH＝{g，q，G，H0，H1}。3.根据权利要求1所述的变色龙哈希函数的碰撞计算方法，其特征在于：所述进行密钥生成步骤中，k个用户通过一个群管理员协商组成环。4.根据权利要求1所述的变色龙哈希函数的碰撞计算方法，其特征在于：所述进行哈希计算的步骤如下：根据公开参数、身份信息和消息，先计算不同身份信息对应的随机数，再选择一个随机数计算变色龙随机数和变色龙哈希值。5.一种基于权利要求1-5任一项所述变色龙哈希函数的碰撞计算方法的可编辑区块链构造方法，其特征在于：方法如下：区块链初始化：链管理员选择k个节点组成一个环负写区块链，执行所述系统初始化步骤和密钥生成步骤产生系统公开参数和各个节点的私钥以及系统公钥，链管理员将产生的系统公开参数写入初始区块中，然后将区块链的控制权转移给节点；写区块链：区块链初始化步骤完成后，选择的k个节点基于工作量证明机制，反复计算哈希达成共识，然后对区块内容执行所述哈希计算步骤，将得到的变色龙哈希值和变色龙随机数写入区块头中；重新编辑区块链：选择的k个节点组成一个环对区块链上的一个区块执行重新编辑，并对新的区块链内容执行所述碰撞计算步骤，得到满足碰撞的新变色龙随机数，将该新变色龙随机数记录在新的区块上。6.根据权利要求5所述的基于变色龙哈希函数的碰撞计算方法的可编辑区块链构造方法，其特征在于：所述写区块步骤中，完成上述步骤内容后，还包括其它任意节点对其中一个区块进行验证步骤，具体为：将区块的内容和对应的变色龙随机数，重新执行上述哈希计算步骤，将得到的变色龙哈希值与存储在区块头的变色龙哈希值相比较得到验证结果。7.根据权利要求5所述的基于变色龙哈希函数的碰撞计算方法的可编辑区块链构造方法，其特征在于：所述重新编辑区块链步骤中，完成上述步骤内容后，还包括其它任意节点对重新编辑后的区块进行验证的步骤，验证的步骤具体为：对新的内容和新变色龙随机数，重新执行上述哈希计算步骤，将得到的变色龙哈希值与存储在区块头的变色龙哈希值相比