Applied Cryptography CS 6260
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 6260 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/234105/cs-6260-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Applied Cryptography
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
CS 6260 Numbertheoretic primitives As no encryption scheme besides the OneTimePad is unconditionally secure we need to find some building blocks hard problems assumptions to base security of our new encryption schemes on Block ciphers and their PRF security is not an option since now we don t have shared keys in the publickey asymmetrickey setting Let s consider the discrete log related problems and the RSA problem Discretelog related problems 0 Let G be a cyclic group and let m G The discrete logarithm function DLogG ga G Zm takes a E G and returns i E Z such that gi a m 0 There are several computational problems related to this function 0 Discrete logarithm DL problem Computational Diffie Hellman CDH problem Decisional Diffie Hellman DDH problem Problem Given Figure out Discrete logarithm DL g1 1 Computational Di ieHellman CDH g gy gzy Decisional Di ieHellman DDH g1gygz Is 2 E my mod 0 DL problem M Let G be a cyclic group and let m G Let g be a generator Consider the following experiment associated with an adversary A Experiment Expdgl AA z e Zm X e g E lt A X If g X then return 1 else return 0 The dl advantage of A is defined as Advggw Pr ExpggA 1 o The discrete logarithm problem is said to be hard in G if the dl advantage of any adversary with reasonable resources is small CDH w Let G be a cyclic group of order m Let g be a generator Consider the following experiment associated with an adversary A Experiment Expgllg A If Z gm then return 1 else return 0 The cdh advantage of A is defined as Advgigm Pr Exng A 1 The computational Diffie Hellman CDH problem is said to be hard in G if the cdh advantage of any adversary wi h reasonable resources is small DDH M Let G be a cyclic group of order m Let g be a generator Consider the following experiments associated with an adversary A Experiment EXPdaEgr1 A Experiment Expdacgrow z lt Zm z lt Zm 1 i Zm y i Zm 2 lt my mod m 2 i Zm Xeg YltgyZltgz Xeg YltgyZltgz deAX7Y72gt dean72 Return 01 Return 01 The ddh advantage of A is defined as Adv l A Pr Expdg 1A 1 7 Pr ExpdgflgoA 1 The decisional Diffie Hellman DDH problem is said to be hard in G if the ddh advantage of any adversary with reasonable resources is small Relations between problems Fix a group and a generator Can solve gt Can solve gt Can solve DL CDH DDH DDH s CDH gt DL hard hard hard The computational complexity of the problems depend on the choice of a group For most groups there is an algorithm that solves the DL problem in OG12 Let s consider GZl for a prime p Claim DDH is easy Let p 2 3 be a prime let GZl and let g be a generator of G Then there is an adversary A with running time Op3 such that 1 Advg fgm 5 CS 6260 Some number theory Let Z 2 1 0 1 2 denote the set of integers Let 2 1 2 denote the set of positive integers and N 0 1 2 the set of non negative integers If a N are integers with N gt 0 then there are unique integers r q such thata Nq rand 0 S rlt N We associate to any positive integer N the following two sets ZN 0 1 N 1 Z iEZ1SiSN 1 and gcdiN1 Groups Def Let G be a non empty set and let denote a binary operation on G We say that G is a group if it has the following properties 1 Closure For every a b e G it is the case that a b is also in G N Associativity For every a b c e G it is the case thatabcabc U Identity There exists an element 1 e G such that a11aaforallaeG 4 Invertibility For every a e G there exists a unique beGsuchthatabba1 inverse denoted a 1 Fact Let N be a positive integer Then ZN is a group under addition modulo N and Z is a group under multiplication modulo N 0 In any group we can define an exponentiation operation ifi 0 then a39 is defined to be 1 ifigt0thena39aaaitimes ifi lt 0 then ai a 1 a 1 a 1 j i times 0 For all a e G and all ij e Z aij iaj aij aij al ai 1a 1i The order of a group is its size Fact Let G be a group and let m G be its order Then am 1 for all a e G Fact Let G be a group and let m G be its order Then a39 a39 med m for all a e G and all i e Z Example Let us work in the group 22 1 2 4 5 8 10 11 13 16 17 19 20 under the operation of multiplication modulo 21 m12 586 mod 21 586 mm 12 mod 21 52 med 12 mod 21 25 mod 21 4 If G is a group a set S g G is called a subgroup if it is a group in its own right under the same operation as that under which G is a group 0 If we already know that G is a group there is a simple way to test whether S is a subgroup 1 1 it is one ifand only ifx y is the inverse of y in G e S for all X y e S Here y 0 Fact Let G be a group and let S be a subgroup of G Then the order of S divides the order of G Algorithms and their running times Since in cryptography we will be working with BIG numbers the complexity of algorithms taking numbers as inputs is measured as a function of the bit length of the numbers 39 Eg PrintinBinary A where A2k takes k operations Some basic algorithms Algorithm Input Output Running Time INTDIV aN NgtO qr WithaNq randO r ltN Oa MOD aN N gt O a mod N Oa EXTGCD 16 ab y 00 1675 With d gcdab 16 65 Oa MODADD a bN 11 g ZN a 6 mod N 0N MODMULT a bN 11 g ZN ab mod N ON2 MODINV aN a E Z V be ZR with ab El mod N ON2 MODEXP a7n7N a E ZN aquot mod N NF EXPG 171 1 E G aquot E G 2 71 Goperations Cyclic groups and generators If g e G is any member of the group the order of g is defined to be the least positive integer n such that 9n 1 I gn1 denote the set of group elements generated by g This is a subgroup of order n We let ltggt g i 6 Zn gogl Def An element 9 of the group is called a generator of G if ltggtG or equivalently if its order is mG Def A group is cyclic if it contains a generator If g is a generator of G then for every a e G there is a unique integer i e Zm such that g a This i is called the discrete logarithm of a to base 9 and we denote it by DLogG ga DLogG 9a is a function that maps G to Zm and moreover this function is a bijection The function of Zm to G defined by i gt gi is called the discrete exponentiation function Exampe Let p 11 Then 211 12345678910 has order p 1 10 We find the subgroups generated by group elements 2 and 5 We raise them to the powers 09 i012345 6 7 8 9 H 2imod11 2 4 8 5 10 9 7 3 6 simodu 5 3 4 9 1 H 5 3 4 9 lt2gt 12345678910zlt1 2 is a generator and thus Zf l is cyclic lt5gt 1I3I4I5I9 a123456 10 DLOng1Za O H 00 w 4 Q3 Choosing cyclic group and generators The discrete log function is conjectured to be one way hard to compute for some cyclic groups G Due to this fact we often seek cyclic groups Examples of cyclic groups Z for a prime p 0 a group of prime order We will also need generators How to chose a candidate and test it Fact Let G be a cyclic group and let m G Let poil p n be the prime factorization of m and let mi mpi for i 1n Then 9 e G is a generator of G if and only if forall i 1 n gmiqt 1 Fact Let G be a cyclic group of order m and let 9 be a generator of G Then GenG gl 6 G i e Zquot and GenG m Example Let us determine all the generators of the group 21 Its size is m 11 10 and the prime factorization of 10 is 21 51 Thus the test for whether a given a E Z l 1 is a generator is that a2 1 mod 11 and a5 1 1 mod 11 a 1 2 3 4 5 6 7 8 9 10 a2 mod 11 1 4 9 5 3 3 5 9 4 1 a5 mod 11 1 10 1 1 1 10 10 10 1 10 Genzi 1 2678 Double checking Zi 110 Z i o 1379 2i 6 G i e 210 21 23 27 29 mod 11 2678 Algorithm for finding a generator The most common choice of a group in crypto is Z for a prime p Idea Pick a random element and test it Chose p st the prime factorization of the order of the group p 1 is known Eg chose a prime p st p2q1 for some prime q Algorithm FIND GENp q lt p 12 found lt 0 While found y 1 do inZ laP l If 92 modp 7 1 and gq modp 7 1 then found lt 1 EndWh e Return 9 The probability that an iteration of the algorithm is successful in finding a generator is GenZ IZZI 2 4429 7 2q 2 sow 1 p 3 Squares and nonsquares Def An element a of a group G is called a square or quadratic residue if it has a square root meaning there is some b e G such that b2 a in G We let QRG g e G g is quadratic residue in G We are mostly interested in the case where the group G is Z for some integer N Defs An integer a is called a square mod N or quadratic residue mod N if a mod N is a member of QRZI Q If b2 a mod N then b is called a square root of a mod N An integer a is called a non square mod N or quadratic non residue mod N if a mod N is a member of 21 QRZf V Def Let p be a prime Define the Legendre symbol of a 1 if a is a square mod p Jpa 0 ifamodp0 71 otherwise Example QRz 1 a12345678 a2 mod 11 10 495335941 li QRZi 11 3 4 5 9 Recall that 21 is cyclic and 2 is a generator Fact A generator is always a non square But not all non squares are generators a 1 2 3 4 5 6 7 8 1 8 2 4 9 7 3 6 5 71 71 71 71 71 9 0 0 131409311201 J11a Fact Let p 2 3 be a prime and let g be a generator of 2 Then QRZI gi i E Zp1 and i is even and QRZI p 12 Facts Let p 2 3 be a prime Then Jpa 113771 mod p for any a e Z 9 E 1 mod p for any generator g of Z Jpab mod p Jpa o Jpb for any a e 2 Jpgmy mod p 1 if and only if Jpgm mod p 1 or Jpgy mod p 1 for any generator g of Z and any xy e ZP1 P1rxlti 231 ylti 21H Jpgw 1 34 for any generator g of Z Groups of prime order Def An element h of a group G is called non trivial if it is not equal to the identity element of the group Fact Any non trivial member of a group of prime order is a generator of the group Fact Let q 2 3 be a prime such that p 2q 1 is also prime Then QRZI is a group of prime order q Furthermore if g is any generator of 2 then g2 mod p is a generator of QRZ Fact Let g be a generator of a group of prime order q Then for any element Z of the group 1 1i 39f Z 1 lt q 1 271 1 q Pr wiZqyampZqgzyZ gtQH QIH Signcryption It 5 often destrab e to achweve both prwacv ahd authent th h the pub c kev setthg S gncrvpt on S a pubhc kev p m the that assures prwacv and authent c tv otttahsm tted data S gncrvpt on must be cons dered m the twoauser or mu thuser setthg Signcryption A scheme AS 5 Specw ed a kev generat on a gortthm K a stghcwptm a gor thrh gc and a destghcwptm a gor thrh Dgc ASKSCDS me SDKNEKS L Sender S Recewer R 1t 5 requw ed that for everv MEMsgSp and everv t K DXCKSDKFVEKS CSDKFVEKS ND M Security of signcryption A srgncrvptron scheme rs not Srmpw an asvmmetnc crvpt on scheme strong secur tv notrons m terms or pnvacv INDVCCA and authentrctv INTVCTXT can be de ned somewhat srmrrarrv to those tor authentrcated encrvptron However as we cannot onW cons der the smg eauser settmg anvmore we mav consrder outsrder and rnsrder securrtv dependmg on whether an adversarv rs an outs der gwen or v the pubhc kevs or an rnsrder knows the secret kev o a sen er or a recewer twoauser and murtruser secur tv the atter needs to onsrder a possrbmtv or dentrtv fraud As before an rnterestrng ouestron rs how to properrv compose an asvmmetrrc encrvpt on scheme and a drg tar srgnature scheme m order to get a secure srgncrvpt on Some results It an encrvptron scheme rs IND CDA secure and a srgnature scheme rs SUF CMA secure then Encrvptathenasrgn srgncrvptron scheme de ned naturaHv rs IND CCA and wry TgtltT secure in the outs der tworuser moder To rnsure secur tv m the murtruser moder one needs to whenever encrvptrng somethrng add the pub c kev or the sender to a message to encrvpt whenever srgnrng somethrng add the pub c kev or the recewer to a message to srgn Public Key Infrastructure PKI Asvmmetrrc crvptographv assumes that pubhc kevs are pubr c pubhc kevs are authent c and ted to users39 rdent tres users39 secret kevs have not been comprormsed DKI39S goa rs to support thrs settmg ake the PKI Work we need to trust someone e g a 39 To m trusted thrrd partv a a Certrrrcat on Author tv cm User IDU pkU Ven es the D t arandum haHenge g 3 pr R message to 5 rgn D39SignskU R Ven s that VFpkU R c CA cert ignskCAvlDUpkgvexpdatev User 1 err Ven es that VHpkcA row pkwexp date 39 The PKI 5 50 makes the cem ed puch kevs the correspondmg rdentrtres and the certrtcates pubhc mamtams the puch cem cate revocatTon hst CRL The DKI mav be hrerarchrcaT WTth CA5 cemfwng other CA5 x 509 T5 the standard for dTg taT cem cates deveToped bv the InternatonaT TeTecommunrcatrons Umon ITU Secret key sharing Secu tv otau Svmmet c and asvmmet c schemes rehes on Secrecv ota secret kev How to make a secret kev more Secret An Tdea Tet39s spT t a secret kev Kand store the shares h drrrerent pTaces e g on n drrrerent computers such that anv t shares aHoW to reconstruct K TftVI computers become compromTSed We are stm ne h that no one can Tearn anvthmg about Kfrom H shares To do anv harm an adversarv must compromrse t computers ThTs T5 tnrsecret shanng scheme Shamir s secret sharing Let p be a Targe p me To tn share a secret zeZp Choose t 1 random e ements of Zp a a Letagz vTeW these as the coet crents ota pownomranot degree t 1 t 1 meanmg xmagaxHIHX storeyi z on each computer i To recover the secret gwen t parrs i yi tor res use the Lagrange rnterpoTatron to nd 1 do f0 Exes y les as The scheme T5 unconthTonaHv Sew Can be pre computed if There are severaT Weaknesses ot the ShamTr39s secret sharhg protocoT Tfsome Dames cheat durmg the secret reconstruchon the secret cannot be recovered and others cannot detect cheatmg the deaTer needs to be trusted A verrhabTe secret shanng protocoT aHoWS to overcome these drrrcu tres 1t T5 aTso desrabTe that Dames be abTe to perform Secretrkev operatrons decrvphon or STgmng such that no partv hons the whoTe secret kev at anv m e I Thresho d Schemes aHoW to achweve tth Recall symmetric setting A 111113 K Public key asymmetric setting Asymmetric encryption schemes A scnerne AE is specified a key generation aigor tnrn K an encrypt on aigoritnrn E and a decryption aigor tnrn D AEKi39D MsgSppkrmessage space i Receiver R sender s It is required tnat tor eyery pk5k tnat can be output by K and eyery MEMSgSpQDk ifCEpkM tnen DskCM A sender rnust know tne receiver39s pubiic key and rnust be assured tnat tnis pubiic key is autnentic reaiiy beiongs to tne receiyer Tnis is ensured be tne pilt1 processes Wnicn are not part of encryption Uniike in a syrnrnetr c encryption tne asyrnrnetr c encryption aigor tnrn is neyer statetui Messages WiH often be group eiernents encoded as bitstrings Whenever necessary Indistinguishability under chosenplaintext attacks FTXAEM E D pksk3k For aw adver ary A and a bu bcoh Taer an expe mem Exp 39w ket b Experiment Expjg m m pksk 9 7C 27 u A5wltLRltrrbgtgt Return 5 The expenme return b The NDVCPA wva age 039 AT Adv A P Exp g39w wg 1 e PExp 2quot A 1 Ah a ymmemc ewerypuoh cheme AET Thar uhgur habTe uhaercho e r p am ex attack ANDVCPA ecuren Tor aw adver ary A mh tea ensue 4 M T urce Adv r ma co etoo INDCPA is not always enough Bleichenbacher s attack on a previous version of SSL 4 mvahd cwphertext C mvahd cwghe ext 0 OK HEE S sessmn key 4 mvahd cwghertext Indistinguishability under chosenciphertext attacks FTXAEM E D pksk3k For an adver ay A and abu bcoh Tder aw expehmewt Ebrpenmenc Exp g hA 31C k k Eh Alum Lt A queued Duo on ecxphelrexc pzevtougxy renamed by 5KltLRlt b then lemln 0 else Rerum b The NDCCA advantage 039 AT Adv quot A FxExp g39m 1rPxExp g39Mquota11 Ah a y metrrcehoypuoh chemeAET Thar uhgur ame uhaerwo em aphe39tex attack NDVCCA ecure mor any adver ay A mh rea ohabTe re ouroe Adv quotP A r maWdo eto o IND CCA a IND CDA In the hterature vou can meet the oehmtrohs Where an adversarv makes a smgTe querv to the LR encrvphon orader Theorem 1 Let AEKED be an asvmmetr c encrvpt on schem Let B be an ndrcpa adversarv who makes at most o cpa adversarv e same ruhmhg trme ma mg a most 1 querv to rts LR encrvpt on orade and Such hat Adv x 39mtB s o Adv 39 Agt Theorem 2 Let B be an Tndrcca adversarv who makes at most q quen to t5 vpt on orade T en there ewsts n e5 R eh Tndrcca adversarv A makm at most one querv to rts LR encrvphon orade the same number of decrvptwon ouerres and havmg the same ruhmhg trme Such that AdV R 39m lt gerAdV 39mw Proof ofTh 2 Th 1 eas v foHoWS from Th 2 The prootueee a mbr d argument We Wm conswder q expe ments assocwated W th B Exp LAB Exp AAB t Expidf We de ne Pg F1Exp1 lt3l and Wm make 1t 5t P1Exp quot 5 1 P1Exp quot 5 1 and hence Adv 39tw PqrP 22 a 1 Pltqgt ZIP1 Plt1gt PW 11 a q 1 ZNWZW 1 a We Wm construct mdaccaaadversarv A 50 that PxExpLS39 ltAgt q 2 e1 1 magma1 1 q 20m andthus Aavzgg39wa Adv grwaog 0mm H 1ltMa M 7 F 7 Experiment ExpgstB l U pksk 4 7c 79 H Hs ltgt7gtaltgt men c imam an Pk Elie C A zpktMa 5st Ratmn C Note that H k eakm 0 and Ham 2 pkltLRlt 1 and therefore P P1 Expg gme 1 121 Exp 52214 5 1 W Advexsazy AFMLN hgtgt 1 agtltPk 7 a at I 1 q Subwutme 05M0M1 7 a 7 1 Lt 7 lt Ithan c imam Erst Lt 7 I then c i ykLRMa M b EnaLt Lt 7 gt Ithan c sMMa Erst Return 0 End Subxauhne d i BM Wat gtPk Return 11 PxBtpj 39quot A1za m pa1pggwa1emei 1971 12 magw11 magewemez met gm lq mgwmet pqmgwegduez met 5 gm 3 t 1 gm Let G be a ch c group of or The EIGamal scheme der n and Tet g be a generator of G The ETGarnaT encrvpt on scherne 554K E D assocTated to Gg Ts as toHows Algonchm Tc Algonchm XM Algonchm DzYW a zn LfMgcchentecmnt Key Xef yeszegy MeWK Realm Xa K eXyT W e KM Recmn M REM YT W Secuthv depends on the choTce otG The EIGamal scheme in z for a prime p In thTs group the ETGarnaT Ts INDVCPA Tnsecure narnew there XTStS an adversarv A WTth Tndrcpa advantage 1 The Tdea gTven a chhertextA can compute JDUVT Adversaxy A5XLR Wm M a T tw y W germane MT 5 warn24 aapmayonm 1 mm e1 m qen 5 e 71 else 5 Ende f WO 02 5 mod p than 12mm 0 else letum 1 Ende MW MK JAB105 MM Note that MO Ts a square and M1 Ts not th xtbo then JDUVTO Hence Pr 3 1quot A 1 1 and PrExp G A JPWs Tt b1 then mel man The ETGarnaT Ts IND CDA secure Tn groups where the DecTsonaT DT TeaHeHman DDH orooTern Ts hard Te Tn QRZ39 athe suogrouo ofquadrat c resTdues of 239 Where o2o1 and do are orTrnes It s a CVCMC group of orTrne order INDCCA insecurity of EIGamaI ETGarnaT Ts not IND CCA secure regardTess ot the cho ce of group G Adversary AMM Tbgtgtvvrltgt X Le Ma M be any we discmcc elemem of G Y W A XLKM0M1Z W e W9 M a DAY W If M Mag then return 0 else mum 1 KT W KquotW M 92YTW D 9 May The Tndacca advantage otA Ts 1 and A maks Just one LR encrvphon and 1 decrvptTon querv and makes 2 group rnuTtToTTcat ons Hybrid encryption Hybrid encryption 0 Let A5 00553 be an asymmetric encryption scheme and o Asymmetric encryption uses numbertheoretic operations and 7 s s s let 55 2C 5 3 be a symmetric encryption scheme s t is slower than symmetric encryption that often uses block h fk f 55 I h f ciphers t e set 0 eys or is a ways in t e message space 0 45 Then the associated hybrid scheme E 2035 is as 0 Also we often want to encrypt long messages follows 0 In practice one usually Algorithm 3pkMg Algorithm 55140 1 encrypts a randomly chosen symmetric key K using an o KS l 0 TSISAM Parse on Sonics asymmetric encryption algorithm and then i t en mum i K TDsklc gt on 9 55km c a 0208 If K L then return L 2 encrypts a message using a symmetric encryption Reth C M H DMCS algorithm and K Return M o This is called hybrid encryption 0 Note that the hybrid scheme is an asymmetric encryption scheme Hybrid encryption 0 Proof The proof willuse a hybridargument We will define a Theorem Let M Ku gu Dugt be an asymmetric encryption sequence of 4 experiments assOCIated w th B scheme and let SE 206233 be a symmetric encryption Exp37 Expp any Expi lgBgt7 Exp3gt scheme st the set of keys f0 55 is always in the message space of 45 Let E 2035 be the associated hybrid and de ne scheme as defined on the previous slide Then for any Huh3 Pr EXPltB ll adversary B there exist adversaries A00 A00 01 A st indicpa It will be the case that o Ade lB v v P1 0 7 Pr Ex md39 Pa391B 71 g Advj g mmow Adw m 141110 quv PaA 7 P070 Pr and A0010 A1011 have time complexity of B make the same and thus Adv ipaw P number of queries each of length k symmetric key length A5 and A has time com lex ty of B and makes only one query E l E p s P107P11P117P01P017P00 o Collorary If the components are INDCPA then the lPlt1gt0 P1gt1llP1gt1 P0gt1l lP0gt1 P0gt0l associated hybrid scheme is also INDCPA We will construct adversaries P01 713mm P11 713mg P107P11 S Adv 39 PaAeroe Adv PaltAgt S AdVl gicpalAlm and the theorem statement will follow Aooo1r A Aooo1 51 We now define the 4 experiments that use different oracles H8520 MEXV which H5 gt For all possible bits X 3 de ne Oracle H MDM1 w Oracle H53 ltMDM1 Experlment EXPEB KB Am K1 A KB 5K5 K1 A pk sk A 20 5amp5me u as 5me u 943 5 s d H BHSPk Rpm HG l then return l HG l then return l C lt pk C lt pk 1 Return 1 O H 0205 O H 0205 Return 0 Return 0 Oracle H5 ltMDM1 Kg Ho K1 we 05 Assam H05 l then return l Oracle Hrfg MmMI Kg 10 K1 HO Sivan E If 05 L then return L 1 Check that H170 13070 c A amok c H 0205 Return 0 Return 0 6 We now construct adversaries Aoo m A1011 Adversary 5500 Hbgtpk Adversary Af le lbgtgtpk Subroutine 05MnMr Subroutine OEMDM1 D A K5 K A K5 05 A 55KnaMD If as l then return l 0 i rLRKurKrrb D A K5 K1 A K5 05 A 55KDM1 If as l then return l 0 5rltLRltKrrKerbll Return 0005 Return 0005 End Subroutine End Subroutine diBOSIvah diBmmgch Return d Return d Check that Pr Expj g wl A01 00 1 Pr ExpB l Pr Expj Pa 0AmD 1 Pr Expil B 1 Adng cpwlma PO17POO Similarly for A1011 e now construct A As A can make only 1 query the construction will require another sequence of hybrid arguments Ema 83 Exph AB ExpB Define 131 P1EB1 Oracle H kMo M1 Experiment ExptA AB jj1 pksklt1Ca Ko le K1lt11CS dLBH51Hpk Ifj g i Return d then 0511 85K0 else Cs Asian EndIf If C5 L then return L C A 5apk C e 0 05 Check that Return C P01 P0 and P11 Pq P11 7P01 Pltqgt 7Plt0gt Pq7Pq71Pq717A7P1P17P0 iiPlt gtePlt elgtt 11 Adversary A ltLRW5 pksklt 30 Ii1q Subroutine 95M0 M1 7 H j 1 K0 amp KS K1 amp m If 339 lt I then CS amp 58K0 EndIf If 339 I then CS amp LRMOM117 EndIf If 339 gt I then CS amp 58K0 Endh If CS L then return L c amp mph 1 Return CECE End Subroutine d i 30 pk Return 1 Check that PrEXP Pa 1A 1i 1 PO39 prinxp Pa D11ilt Pltte1 Analyzing A we get Advg g39 PaA Pr Expgg39 Pa391A 1 7 PI Exp 39 Pa39 A 1 g V Z PrEng grcPa71A 1 i 1 t 1 Pr 1 1 11 g V e Z Pr Expg 39 Pa39 A 1i 1 t Apr 1 t 71 q q prprum e ZPlt271APrIl 11 Randomized FDHRSA P550 P550 is a randomized variant of the FDHRSA scheme It has the same key generation algorithm PSSO also uses H 01 all a random function to which all parties have oracle access to and it has a parameter 5 Algorithm SignggqdM Algorithm VF 9M 0 I 01S Parse 0 as 71 where lrl s yeHMM yeHMM zeydmodN lszInodNy Return 71 Then return 1 else return 0 Security of P550 0 Theorem Under the RSA assumption the P550 signature scheme is ufcma secure in the random oracle RC model Let Krsa be an RSA generator and let DS be the P550 signature scheme Let F be an adversary making at most qhmh queries to its hash oracle and at most q ng queries to its signing oracle where qhmh 1 Then there exists an quign adversary I with comparable resources st Advg cmaF S Adv kealt1 qhash51gt 39qsig Other signature schemes 0 Let s consider several signature schemes whose security relies on the hardness of the DL problem 0 Schnorr signature scheme Algoritm Kk Algoritm SignskM pick a kbit prime p st p2q1 ksz pick geZFJ oforderq V q x z Ykgy mod p ckHMllY ng skycgtlt mod q Picka hash function H0lquot Zq Return Y s Return HgpqXHygyqulel Algoritm VFpkMYS ck HMllY If gsYgtltc mod p then return 1 else return 0 Other signature schemes 0 ElGamal signature scheme Algoritm Kk Algoritm SignskM pick a kbit prime p s pick a generator g of 2 szpq 3 kap71 Ykgy mod p X sky l HMllY7gtltY mod p71 Pickahash function H0lquot Zpi1 Return Ys Return HgpqXHygyqulel Algoritm VFpkMYs If XYYSgHMllYl mod p then return 1 else return 0