# 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.