This is a cryptography assignment. Problems are theory and proof-based
Assignment #2 Due date: Wednesday, April 28, 2021, 11:59pm Course: Introduction to Cryptography Quarter: Spring 2021 Instructor: Prabhanjan Ananth Instructions • This assignment is worth 100 points. • Please read all the instructions very carefully. • Submissions must be made on Gradescope. The enrollment code is on Slack. • Make sure that the handwriting in your solutions is legible (using LATEX to typeset your solutions is appreciated a lot!). Be precise and concise in your solutions. Explain your solutions clearly and provide mathematical proofs wherever necessary. • Write the solution to each problem on a separate page. • If you don’t know how to solve a problem, write “I don’t know” and you get 20% of the points. • You are allowed to collaborate with at most two more students on these assignments. However, everyone is expected is write up the solutions on their own and submit it individually. Clearly state the names of all your collaborators. • Do not use any theorem or lemma from the internet that was not taught in the class. Use only the material covered in the class to solve these problems. • More importantly, have fun solving these problems! 1 Free Hand Problem 1 [10 points] Are the following functions negligible or non-negligible? Justify your answer. 1. 51(=) = 5 (=) · =2 , for some constant 2 > 0 and some negligible function 5 (=) 2. 52(=) = =− log log = Problem 2 [15 points] Recall that two ensembles {-=}, {.=} where -= , .= ∈ {0, 1}?>;H(=) are computationally indistin- guishable if for any efficient adversaryA, there exists a negligible function &(=) such that |Pr[A(1= , G) = 1; G ← -=] − Pr[A(1= , H) = 1; H ← .=]| ≤ &(=) Let 5 : {0, 1}∗ → {0, 1}∗ be a polynomial-time computable function. Show that if {-=}, {.=} are computationally indistinguishable, then { 5 (-=)}, { 5 (.=)} are also computationally indistinguish- able. [Hint: Use reductions.] Problem 3 [15 points] If {-=}, {.=} are computationally indistinguishable, and {.=}, {/=} are computationally indis- tinguishable, show that {-=}, {/=} are computationally indistinguishable. Problem 4 [15 points] Give examples of non-negligible functions 51(=) and 52(=) such that 51(=) · 52(=) is actually a negligible function. Problem 5 [25 points] Let � : {0, 1}= → {0, 1}3= be a secure pseudorandom generator, prove that the following pseu- dorandom generators are secure. B, A ∈ {0, 1}= below are perfectly random strings. You can think of them as the seeds of the PRG. 1. �1(B) : {0, 1}= → {0, 1}2= , �1(B) = �(B)[2=]. That is, �1(B) is obtained by dropping the last = bits of �(B). 2. �2(A, B) : {0, 1}2= → {0, 1}6= , �2(A, B) = (�(A), �(B)). Problem 6 [20 points] 1. Is the following function 5 : {0, 1}= → {0, 1}= a one-way function? ∀G ∈ {0, 1}= , 5 (G) = G + 10 (mod 2=)1. 1Here G ∈ {0, 1}= is interpreted as a number between 0 and 2= − 1. For instance, 10 ≡ (0 . . . 001010)2 2 2. Suppose 5 : {0, 1}= → {0, 1}= is a one-way function. Using 5 , can you construct another function 5 ′ : {0, 1}= → {0, 1}=+1 such that 5 ′ is also a one-way function but not a secure pseudorandom generator. 3 Assignment #1 Due date: Wednesday, April 14, 2021, 11:59pm Course: Introduction to Cryptography Quarter: Spring 2021 Instructor: Prabhanjan Ananth Instructions • This assignment is worth 60 points. • Please read all the instructions very carefully. • Submissions must be made on Gradescope. The enrollment code is on Slack. • Make sure that the handwriting in your solutions is legible (using LATEX to typeset your solutions is appreciated a lot!). Be precise and concise in your solutions. Explain your solutions clearly and provide mathematical proofs wherever necessary. • Write the solution to each problem on a separate page. • If you don’t know how to solve a problem, write “I don’t know” and you get 20% of the points. • You are allowed to collaborate with at most two more students on these assignments. However, everyone is expected is write up the solutions on their own and submit it individually. Clearly state the names of all your collaborators. • Do not use any theorem or lemma from the internet that was not taught in the class. Use only the material covered in the class to solve these problems. • More importantly, have fun solving these problems! 1 Rectangle Free Hand Problem 1 [20 points] Consider the following (=, �) -blockwise permutation cipher: it applies a permutation � : [=] → [=] where [=] = {0, 1, 2, . . . , = − 1} to the messages in a blockwise manner. That is, on input a message <, •="" wefirst="" remove="" all="" white="" spaces="" and="" punctuations.="" we="" then="" divide="" themessage="" into="" blocks="" of="" size="." for="" instance,="" for="=" 3,="" a="" message="" ‘math="" is="" great’="" is="" divided="" into="" the="" following="" blocks:="" mat,his,gre,at.="" also,="" the="" last="" block="" might="" have="" fewer="" than="letters." •="" for="" each="" block="" comprising="" of="" the="" letters=""><1 ,="" .="" .="" .="" ,=""><= ,="" permute="" the="" block="" to="" be=""><�(1) ,="" .="" .="" .="" ,=""><�(=). if="" the="" final="" block="" contains="" fewer="" than="characters," then="" this="" block="" is="" not="" permuted.="" that="" is,="" if="" �="" :="" {1,="" 2,="" 3}="" →="" {1,="" 2,="" 3}="" is="" a="" cyclic="" shift="" by="" 1,="" i.e.="" �(1)="2," �(2)="3," �(3)="1," then="" the="" block="" ‘mat’="" is="" permuted="" as="" ‘atm’,="" ‘his’="" is="" permuted="" as="" ‘ish’,="" ‘gre’="" is="" permuted="" as="" ‘reg’="" and="" finally,="" ‘at’="" is="" not="" permuted="" since="" it="" only="" comprises="" of="" 2="" letters.="" •="" finally,="" output="" the="" concatenation="" of="" all="" the="" permuted="" blocks.="" the="" order="" of="" the="" permuted="" blocks="" will="" be="" the="" same="" as="" the="" order="" of="" the="" original="" blocks.="" that="" is,="" the="" ciphertext="" of="" the="" message="" ‘math="" is="" great’="" is="" ‘atmishregat’.="" recover="" the="" original="" messsage="" and="" state="" the="" parameters="" (="," �)="" for="" the="" following="" ciphertexts.="" you="" should="" assume="" that="" the="" original="" message="" is="" a="" valid="" english="" sentence.="" 1.="" ‘cnoetehdemsegaestihwuorynwkoey="" 2.="" ntriducoiontocrtptoyrapghy="" problem="" 2="" [10="" points]="" show="" that="" the="" following="" two="" statements="" are="" equivalent.="" letd1="" andd2="" be="" probability="" distributions="" over="" a="" finite="" set="" x.="" •="" d1="" andd2="" are="" identically="" distributed.="" that="" is,="" for="" any="" g0="" ∈="" x,="" pr[g="G0;" g="" ←="" d1]="Pr[G" =="" g0;="" g="" ←="" d2].="" •="" for="" any="" algorithma="" (adversary)="" that="" outputs="" a="" single="" bit,="" pr[a(g)="1;" g="" ←="" d1]="Pr[A(G)" =="" 1;="" g="" ←="" d2].="" we="" call="" such="" an="" adversary="" a="" ‘distinguisher’="" since="" it="" tries="" to="" distinguish="" whether="" the="" sample="" g="" was="" from="" distributiond1="" ord2.="" problem="" 3="" [10="" points]="" let="" (gen,enc,dec)="" be="" a="" correct="" encryption="" scheme="" which="" has="" equal="" mes-="" sage="" length="" and="" ciphertext,="" i.e.="" •="" gen="" samples="" a="" key="" :="" ∈="" k="" .="" •="" enc="" :="" {0,="" 1}="→" {0,="" 1}="takes" as="" input="" an="-bit" message="" and="" outputs="" an="-bit" ciphertext.="" •="" dec="" :="" {0,="" 1}="→" {0,="" 1}="takes" as="" input="" an="-bit" ciphertext="" and="" outputs="" an="-bit" message.="" 2="" we="" would="" like="" to="" know="" how="" the="" security="" is="" affected="" if="" we="" encrypt="" messages="" twice,="" with="" two="" inde-="" pendently="" generated="" keys.="" formally,="" define="" a="" new="" encryption="" scheme="" (gen′,enc′,dec′)="" as="" follows:="" •="" gen′="" independently="" samples="" two="" values="" :1="" ←="" gen(),="" :2="" ←="" gen(),="" and="" outputs="" (:1="" ,="" :2)="" ∈="" k="" ×k="" as="" the="" key.="" •="" enc′((:1="" ,="" :2),=""><) =="" enc(:2="" ,enc(:1="" ,=""><)) for="" any="" message="">< ∈="" {0,="" 1}="and" key="" (:1="" ,="" :2)="" ∈="" k="" ×k="" .="" •="" dec′(2,=""><) =="" dec(:1="" ,dec(:2="" ,="" 2))="" for="" any="" ciphertext="" 2="" ∈="" {0,="" 1}="and" key="" (:1="" ,="" :2)="" ∈="" k="" ×k="" .="" prove="" that="" if="" (gen,enc,dec)="" satisfies="" one-time="" perfect="" security,="" then="" (gen′,enc′,dec)="" satisfies="" one-="" time="" perfect="" security.="" problem="" 4="" [20="" points]="" suppose="" that="" you="" observe="" a="" coin="" toss,="" but="" you="" don’t="" knowwhether="" the="" coin="" is="" fair="" or="" biased="" towards="" heads.="" your="" goal="" is="" to="" decide="" if="" it’s="" fair="" based="" on="" the="" outcome="" you="" observe.="" formally,="" let="" �="" (the="" coin="" toss)="" be="" a="" random="" variable="" that="" takes="" values="" in="" {heads,="" tails}.="" there="" are="" two="" complementary="" events,="" �fair="" and="" �biased,="" such="" that="" pr[�="heads" |="" �fair]="Pr[�" =="" tails="" |="" �fair]="1" 2="" ,="" pr[�="heads" |="" �biased]="3" 4="" ,="" pr[�="tails" |="" �biased]="1" 4="" .="" furthermore,="" the="" coin="" has="" equal="" chance="" of="" being="" fair="" or="" biased,="" i.e.="" pr[�fair]="Pr[�biased]" =="" 1/2.="" (a)="" design="" an="" algorithma="" that="" given="" �="" as="" input="" the="" outcome="" of="" a="" coin="" toss,="" guesses="" if="" the="" coin="" biased.="" correctly="" guessingmeans="" correctly="" outputting="" the="" indicator="" variable="" �fairness="" which="" satisfies="" pr[�fairness="fair" |="" �fair]="Pr[�fairness" =="" biased="" |="" �biased]="1." a="" should="" output="" guess="" ∈="" {fair,="" biased}="" and="" satisfy="" the="" condition:="" pr[guess="�fairness;" guess←a(�)]="" ≥="" 5/8,="" that="" is,a="" correctly="" guesses="" the="" fairness="" of="" the="" coin="" with="" probability="" at="" least="" 5/8.="" (b)="" calculate="" the="" success="" probability="" of="" your="" algorithm="" a="" in="" part="" (a)="" when="" the="" outcome="" is="" heads,="" that="" is,="" calculate="" the="" conditional="" probability="" pr[guess="�fairness;" guess←a(�)="" |="" �="heads]." 3="" assignment="" #1="" solutions="" course:="" introduction="" to="" cryptography="" quarter:="" spring="" 2021="" instructor:="" prabhanjan="" ananth="" problem="" 1="" 1.="=" 4,="" �(1)="3," �(2)="2," �(3)="4," �(4)="1." 2.="=" 4,="" �(1)="2," �(2)="3," �(3)="4," �(4)="1." problem="" 2="" forward="" direction:="" an="" algorithm="" is="" a="" mapping="" g="" →="" a(g).="" since="" g="" is="" identically="" sam-="" pled="" ,a(g)="" is="" identically="" distributed.="" 1="" back="" direction:="" prove="" by="" contradiction,="" if="" d1="" ,d2="" are="" not="" identical,="" we="" show="" there="" exists="" a="" dis-="" tinguisher.="" let’s="" say="" pr[g="G0;" g="" ←="" d1]=""> Pr[G = G0; G ← D2]. The distinguisher outputs 1 whenever it sees G0, and outputs 0 otherwise. You can verify that Pr[A(G) = 1; G ← D1] > Pr[A(G) = 1; G ← D2] Problem 3 By one-time perfect security of (Gen,Enc,Dec), for any messages <1 ,=""><2 ∈="" {0,="" 1}="the" distributionsd1,d2="" are="" identical,="" where="" d8="{Enc(:1" ,=""><8); :1 ← gen()} for 8 ∈ {1, 2}. after applying enc with a key generated by gen, the two distributions remain identical2. hence, d′1 andd′2 are identical, where :1="" ←="" gen()}="" for="" 8="" ∈="" {1,="" 2}.="" after="" applying="" enc="" with="" a="" key="" generated="" by="" gen,="" the="" two="" distributions="" remain="" identical2.="" hence,="" d′1="" andd′2="" are="" identical,="">