资源描述：
《Advanced Topics in Cryptography》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、CMSC858K—AdvancedTopicsinCryptographyJanuary27,2004Lecture1Lecturer:JonathanKatzScribe(s):JonathanKatz1IntroductiontoTheseNotesThesenotesareintendedtosupplement,notreplace,thelecturesgiveninclass.Inparticu-lar,onlythetechnicalaspectsofthelecturearereproducedhere;muchofth
2、esurroundingdiscussionthattookplaceinclassisnot.2TrapdoorPermutationsWegivetwodefinitionsoftrapdoorpermutations.Thefirstiscompletelyformal,andmapswellontothe(conjectured)trapdoorpermutationsthatareusedinpractice.Thesecondisslightlylessformal,butissimplertouseandsomewhateas
3、iertounderstand.Generallyspeaking,however,proofsofsecurityusingthesecondofthetwodefinitionscanbeeasilymodifiedtoworkforthefirstdefinitionaswell.(Strongerdefinitionsoftrapdoorpermutationsaresometimesalsoconsidered;see[1,2]forsomeexamples.)Webeginwithasyntacticdefinition,andthen
4、giveaconcreteexample.Beforegivingthedefinitionweintroducetwopiecesofnotation.Firstistheabbreviationpptwhichstandsfor“probabilistic,polynomial-time”.This,ofcourse,referstoalgorithmswhichmaymakerandomchoicesduringtheirexecutionbutwhichalwaysterminateinapolynomialnumberofste
5、ps.Thisbegsthefollowingquestion:polynomialinwhat?Todealwiththis,weintroducethenotionofasecurityparameterkwhichwillbeprovidedasinputtoallalgorithms.Fortechnicalreasons,thesecurityparameterisgiveninunaryandisthusrepresentedas1k.Insomesense,aswewillsee,alargervalueofthesecu
6、rityparameterresultsina“moresecure”scheme.(Hopefully,theconcreteexamplethatfollowswillgivesomemoremotivationforthepurposeofthesecurityparameters.)Definition1Atrapdoorpermutationfamilyisatupleofpptalgorithms(Gen,Sample,Eval,Invert)suchthat:1.Gen(1k)isaprobabilisticalgorith
7、mwhichoutputsapair(i,td).(OnecanthinkofiasindexingaparticularpermutationfidefinedoversomedomainDi,whiletdrepresentssome“trapdoor”informationthatallowsinversionoffi.)2.Sample(1k,i)isaprobabilisticalgorithmwhichoutputsanelementx∈Di(assumingiwasoutputbyGen).Furthermore,xisun
8、iformlydistributedinDi.(Moreformally,thedistribution{Sample(1k,i)}isequaltotheuniformdistributionoverDi
