Massachusetts Institute of Technology Handout 276.857: Network and Computer Security October 31, 2002Professor Ronald L. RivestProblem Set 5This problem set is due on Thursday, November 7, 2002 at the beginning of class. Late homeworkswill not be accepted.At the end of each problem, tell us how each person contributed (writing, designing, coding, proofreading, moral support, etc).Problem 5-1. SPKI/SDSIIn SPKI/SDSI certificates are “cumulative”: no certificate invalidates any other certificate. In thisway, certificates can be used in a natural way to form groups. For example, the certificates:Kta −→ Kmit kevin fuKta −→ Kmit thien loc nguyendefines the group “ta” for the key K (which might be the 6.857 2002 key, say). Each certificateadds a new possible meaning (or member) to the name (i.e. group) K ta.Please consider the following modification to SPKI/SDSI, and present your evaluation of it in termsof utility, security, ease-of-use, workability, applicability for the web-access application described inclass, and/or other criteria you feel relevant. Limit your discussion to one page.In this proposed modification, everything works as usual, except for reducing name certs. Theseare certs of the form:KA −→ K0By definition, these are certs with only a key on the right-hand side.The modification is that a new reducing name cert with the same left-hand side as a previous certis intended to replace the previous cert. (Assume that each cert contains its date of issue, so thatpriority can be determined.) Thus, at most one reducing name cert should be valid for a givenkey/identifier pair at a given time. The goal is primarily to allow for smooth key rollover, so thata party can replace his old public key with his new one when it seems desirable to do so.Problem 5-2. Term projectsIn 1 or 2 pages, give us a status report on your term project. Provide responses to commentswritten on your proposal. Here are optional suggestions for your status report. Give updates onany decisions you may have changed. If you are implementing something, let us know how faralong you are. If you needed to obtain permission from others (e.g., the MIT committee on testingof human subjects), let us know how things are progressing. List any requests for help or specialequipment.Handout 27: Problem Set 5 2Problem 5-3. Zero knowledgeThis problem investigates a way to show in zero-knowledge that a ciphertext c = gmrNmod N2isthe Paillier encryption of either m = 0 or m = 1.The proof consists of a sequence of t rounds.Each round has three messages.First message (Prover −→ Verifier):The Prover picks a random bit m0∈ {0, 1}, and sends the ciphertexts c0= gm0r0Nmod N2and c00= g1−m0r00Nmod N2to the Verifier: c0and c00are Paillier encryptions of 0 and 1in a random order.Second message (Verifier −→ Prover):The Verifier sends a random bit b ∈ {0, 1} to the Prover.Third message (Prover −→ Verifier):• If b = 0: The Prover shows that c0and c00encrypt 0 and 1 in some order, by revealing therandomization parameters r0, r00used in their encryption.• If b = 1:– If m = m0, then the Prover shows that c and c0encrypt the same message by revealingthe Nthroot of c/c0.– Else m = 1 − m0, then the Prover shows that c and c00encrypt the same message byrevealing the Nthroot of c/c00.(a) CompletenessShow that if c encodes m = 0 or m = 1, then the Prover always succeeds (i.e., the Verifiernever fails in its check of the third message).(b) SoundnessShow that if c does not encode m = 0 or m = 1, then the Prover will be caught with somesignificant probability.(c) Zero-knowledgeShow that this protocol is ZK, by showing how the Verifier can generate transcripts on itsown that have exactly the same distribution as the transcripts generated by interacting withthe Prover according to the protocol above.In all the questions, you can make any reasonable assumptions you can
View Full Document
Unlocking...