• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 1 out of 4 pages
Exam (elaborations)

CMPT 404 — Cryptography and Protocols

Document preview thumbnail
Preview 1 out of 4 pages

Outline Solutions to Exercises on Message Authentication Schemes, CCA Security and Number Theory. 1. Given f : f0; 1gn ! f0; 1gn, define f0 : f0; 1g2n ! f0; 1g2n as follows: for x; r 2 f0; 1gn define f0(x◦r) = f(x) ◦ r. (Where ◦ denotes concatenation.) Prove that if f(·) is a one-way permutation then so is f0(·). Note first that if f is a permutation then so is f0. Suppose that f0−1 is computable in polynomial time. Then, given y = f(x), set y0 = y ◦ 0 where 0 is the all-zero string of appropriate length. Find x ◦ 0 = f0−1(y0). Thus f−1 is computable in polynomial time, a contradiction. 2. Consider the following variant of CMA-security for MACs: instead of giving the adversary black boxes for both the signing and verification algorithms, give it only a black box for the signing algorithm. Let’s call this definition CMA’-security. That is, A pair of algorithms (Sign; Ver) (with Sign : f0; 1gn × f0; 1gm ! f0; 1gt, Ver : f0; 1gn × f0; 1gm × f0; 1gt ! f0; 1g) is a (T; ")-CMA’-secure MAC if for every x; k, Verk(x; Signk(x)) = 1 andf or every T-time Adv, if we run the following experiment: • Choose k − f0; 1gn • Give adversary access to black box for Signk(·) • Adversary wins if it comes up with a pair hx0; s0i such that (a) x0 is not one of the messages that the adversary gave to the black box Signk(·) and (b) Verk(x0; s0) = 1. Then the probability Adv wins is at most ". (Sign; Ver) is CMA’-secure if there are super-polynomial functions T; " such that for every n, (Sign; Ver) is (T (n); "(n))-CMA’-secure. In other words, there is no polynomial-time Adv that succeeds with polynomial probability to break it. A MAC scheme has unique tags if for every message there is only one tag that passes verification. An equivalent way of stating this property is that the verification algorithm on input x and t outputs 1 if and only if Sk(x) = t. Note that the MAC scheme we saw in class has this property. Prove that for MACs with unique tags, CMA security and CMA’ security are equivalent (e.g., such a scheme is (T; ")-CMA secure if and only if it is (T 0; "0)-CMA’ secure for some T 0,"0 polynomially related to T; ". (The condition of unique tags is important — if a MAC scheme does not have unique tags then these notions may not be equivalent.) Since in the case of CMA-security an adversary is more powerful than for CMA’-security, every CMA-secure MAC is also CMA’-secure. So let (Sign; Ver) be a T; "-CMA’ secure MAC. Suppose that it is not CMA-secure, and Adv is an efficient adversary. We construct an efficient adversary Adv0 that does not get access to the verification box, and therefore yields a contradiction with CMA’-security of (Sign; Ver). Adv0 - choose k at random from f0; 1g - run Adv - whenever Adv asks to sign a message P return Signk(P ) - whenever Adv asks to verify a pair (P; s), output 1 if s = Signk(P ), otherwise output 0 - when Adv comes up with a pair (P; s), output this pair To show violation of CMA’-security it suffices to observe that on a verification request (P; s) the new adversary Adv0 answers 1 if and only if s = Signk(P ), and, due to the unique tag property, if and only if Ver(P; s) = 1. Therefore Adv0 perfectly simulates verification requests of Adv, and so violation of CMA’-security follows from violation of CMA-security by Adv.


Document information

Uploaded on
November 12, 2022
Number of pages
4
Written in
2022/2023
Type
Exam (elaborations)
Contains
Questions & answers
$10.69

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
BESTGRADED
5.0
(2)
Sold
33
Followers
24
Items
1951
Last sold
1 year ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions

Whoops! We can’t load your doc right now. Try again or contact support.