CS395T Advanced Cryptography 4/09/09Lecture 6: Problem Set 3 (cont.)/Data StorageInstructor: Brent Waters Scribe: Jimmy Yang1 OverviewToday, we went over problems 3 and 4 from the last homework. In particular, we focusedon a proof technique called the hybrid method which was needed for solving problem 4. Thenwe introduced the concepts of Data Storage and Proof-of-Retrievability.2 Problem 4Notice that the s tandard formulation of an adversary’s advantage can be transformedinto the following equivalent form (b is the simulator’s chosen bit and b′is the adversary’sguess):P r[b′= b] ≥12+ ǫ12P r[b′= 1|b = 1] +12P r[b′= 0|b = 0] ≥12+ ǫ12P r[b′= 1|b = 1] +121 − P r[b′= 1|b = 0]≥12+ ǫ12P r[b′= 1|b = 1] −12P r[b′= 1|b = 0] ≥ ǫP r[b′= 1|b = 1] − P r[b′= 1|b = 0] ≥ 2ǫIn other words, the advantage can also be seen as the d ifference in probability of theevents when the advers ary correctly guesses b′= 1, and when the adversary incorrectlyguesses b′= 1 (we don’t care too much about constants).2.1 Hybrid TechniqueRecall the standard game for CPA security:1. Challenger sends public key P K to Adversary2. Adversary sends 2 messages to the Challenger: m0and m13. Challenger chooses a random bit b ∈ {0, 1}, and sends Enc(mb) to the Adversary4. Adversary sends a guess b′of the bit b to the Challenger6-1With respect to problem 4, consider 2 possible experiments (games) that could occurbetween the C hallenger and the Adversary, depending on the value of b that was chosen instep 3: In game 0 (b = 0), the Challenger sends (Enc1(m0), Enc2(m0)). In game 1 (b = 1),the Challenger sends (Enc1(m1), Enc2(m1)). Using the new formulation of the Adversary’sadvantage given above, this becomes:P r[b′= 1| experiment 1] − P r[b′= 1| experiment 0]Let’s call these prob abilities X1and X0, respectively. Now, the standard starting pointfor a proof of security “Assume we have an adversary with advantage ǫ . . .” can be restated as“Assume we have an adversary with X1−X0≥ 2ǫ . . .”. Now consider a “hybrid” experimenth where in step 3 of the CPA game, the Challenger instead sends (Enc1(m1), Enc2(m0)).Define Xhsimilarly as P r[b′= 1| experiment h]. By the triangle inequality, we have thateither X1− Xh≥ ǫ, or Xh− X0≥ ǫ (or possibly both). Assume the former is true. Sincethe only difference between experiment 1 and experiment h is the fact that we are sendingeither Enc1(m0) or Enc1(m1), the Adversary’s d istinguishing advantage must come frombeing able to distinguish between encryptions of m0and m1. Thus, this Adversary can beused to break the first encryption scheme. In the case that the latter is true, we simplyhave an Adversary that can break the second encryption scheme.2.2 ExerciseNote: This section was not part of the lecture. It was entirely inserted by the scribe.For a better understanding of the hybrid technique, go through the steps needed to solvethe following problem, a natural extension to prob lem 4.Exercise 2.1 (k-Composition Encryption) Suppose we have k encryption schemes:((Setup1, Enc1, Dec1), . . . , (Setupk, Enck, Deck)). Now we define a new composition en-cryption scheme where Encc(m) = (Enc1(m), . . . , Enck(m)) (Setupcand Deccare definedin the obvious way). Show that if all k schemes are CPA secure, then the compositionscheme is also CPA secure.Something else to think about: how large can k be?3 Data StorageUp until now in the class, we have been concerned with the problems of confidentiality(Encryption) and integrity (Signatures) of data flowing across communication networks.Today, we move on to the problem of availability. Consider the following scenario: a clienthas a lot of data (D) it would like to store on a server (presumably the server charges a feefor this service). Thus, the client would like to be assured that the server is actually s toringits data. There has been a lot of debate about how to best model this problem (what doesit m ean to “store” data, how to convince the client its data is really being stored, is itacceptable to lose a small fraction of the data, etc), but the algorithms we will be workingwith in class are:6-2• Store(D) = (V K, SF ): The client stores its d ata D with the server. The output ofthis algorithm is a verification key V K for the client to keep, and a s tored file SF forthe server to keep.• P (SF ) ↔ V (V K): The client (V = verifier) performs an audit on the s erver (P =prover). This is an interactive protocol in which the client interacts with the serverand attempts to ascertain that the server still has the client’s data. At the end, Voutputs either true or false, depending on whether it was convin ced or not that theserver s till has its data. It should b e the case that if (V K, SF ) are the output of theStore algorithm, then V will accept.Some of the important parameters are:• audit speed: How long does it take for P and V to perform their various computationsin the interactive proto col?• bandwidth: How much data must be sent between P and V during the audit?• prover/verifier storage: How large are the files SF and VK?As a matter of functionality, if the verifier is indeed convinced that the prover still has itsdata, then we would like to be able to extract the original d ata D from the audit interaction.The following security property captures this idea:Definition 3.1 (Proof of Retrievability) If some P′convinces V with non-neg lig i bleprobability to accept, then there exists an extraction algorithm Ext such that Ext(P ↔V ) = D.In the next class we will see some constructions of these
View Full Document
Unlocking...