Python代写 | CSE 107: Introduction to Modern Cryptography Homework 3

本次美国代写是一个Python现代密码学的Homework

Homework 3

You may discuss the problems in general terms in a group of size at most three. You are expected
to write up your solutions yourself. Please credit your collaborators on your submission. You may
use your course notes and slides to solve these problems.

This complements the PlayCrypt version of this problem set. You need turn in only the latter, on
Gradescope. This version is being given out so that you can see what the problems look like in
mathematical notation. Do not rename your homework file from hw3.py.

We suggest that you start with this version. Work out a solution using pencil and paper. Move to
implementation in PlayCrypt only after that.

As usual our convention is that the running time of an adversary does not include the time taken
by game procedures to compute responses to adversary queries.

Problem 1 [10 points] Let k; n >= 8 be integers and let F: {0; 1}k x {0; 1}n —— {0; 1}n be a family
of functions. Let TF be the time to compute F. Let K be the key-generation algorithm that returns
a random k-bit string as the key K. Let E be the following encryption algorithm:

The message space is the set of all strings whose length is a positive multiple of n, meaning these
are the allowed messages. The first line above indicates that M is broken into n-bit blocks, with
M[i] denoting the i-th block and m the number of blocks. (For example if n = 4 and M = 01101011
then M[1] = 0110 and M[2] = 1011 and m = 2.) The ciphertext C is (2 + m)n bits long, with
C[0] being 2n bits and C[i] being n bits for i = 1; : : : ;m. By lsb(X) we denote the least significant
(rightmost) bit of X. (For example, lsb(011) = 1.)

1. [3 points] Specify decryption algorithm D such that SE = (K; E;D) is a symmetric encryption
scheme satisfying the correct decryption condition of Slide 3. If the input ciphertext has length
(2 + m)n then the running time of D should be O(m
(TF + n)).

2. [7 points] Show that this scheme is not IND-CPA secure by presenting a O(TF + n)-time
adversary A making one query to its LR oracle and achieving Advind-cpa
SE (A) >= 0:9.