### 这是一份UBC Math – The University of British Columbia的密码学作业代写成功案例

Homework 2
$(40+6$ points $)$
Due on 11:59pm Nov. 20th.
Solution must be typed, preferably using LaTeX.
You can collaborate with one other student in class. Please acknowledge your collaborator and all public resources that you use.

### Part 1 — Computational Indistinguishability

Problem 1.

Task (a) – Properties of Computational Indistinguishability
(6 points)
Let $\left{X_{n}\right},\left{Y_{n}\right}$ and $\left{Z_{n}\right}$ be distribution ensembles satisfying the following: (1) for every $n \in \mathbb{N}$, distributions $X_{n}, Y_{n}$ and $Z_{n}$ are over domain ${0,1}^{n}$ and are efficiently samplable, and (2) $\left{X_{n}\right} \approx$ $\left{Y_{n}\right}$ and $\left{Y_{n}\right} \approx\left{Z_{n}\right}$, where ” $\approx$ ” denotes computational indistinguishability.

Decide whether the following pairs of distribution ensembles are computationally indistinguishable or not.
(i) $\left{X_{n} \oplus 1^{n}\right}$ and $\left{Y_{n} \oplus 1^{n}\right}$.
Here $\oplus$ is the $X O R$ opeartion and $1^{n}$ is the $n$-bit all 1 string.
(ii) $\left{X_{n} | Y_{n}\right}$ and $\left{Y_{n} | Z_{n}\right}$.
Here, $A_{n} | B_{n}$ is the distribution of $a | b$, when sampling $a$ from $A_{n}$ and $b$ from $B_{n}$ independently.
(iii) $\left{M\left(X_{n}, Y_{n}\right)\right}$ and $\left{M\left(Y_{n}, Z_{n}\right)\right}$.
Here, $M$ is a randomized algorithm that on input $(a, b)$, samples a random bit $i \stackrel{5}{\leftarrow} U_{1}$, and outputs $a$ if $i=0$ and $b$ if $i=1$. Moreover, $M\left(A_{n}, B_{n}\right)$ is the distribution of $M(a, b)$, when $a$ is sampled from $A_{n}$ and $b$ is sampled from $B_{n}$ independently.
For each of the above questions,

• (1 pts) Answer Yes, they are computationally indistinguishable, or No.
• (1 $\mathbf{~ p t s})$ If you answer is Yes, argue why the ensembles are indistinguishable, using the two properties “closure under efficient computation” and “transitivity” introduced in class. If your answer is No, describe a distinguisher that can distinguish the two ensembles.

### Part 2 — Pseudo-Random Generators (PRG)

Problem 2.

Task (b) – An alternative definition fo PRG.
(6 points)
Given an efficiently-computable function $G$ with $|G(x)|=l(|x|)$, consider the following experiment $\operatorname{Exp}{n}^{A}$ defined for an adversary $A$ and parameter $n$ : Experiment $\operatorname{Exp}{n}^{A}$ : Proceed in the following three steps.

• Sample a random bit $b \stackrel{L}{\leftarrow}^{\$}$. • If$b=0$, sample a random$x \stackrel{\$}{\leftarrow} U_{n}$ and set $y=G(x)$.
If $b=1$, sample a random $y \leftarrow U_{l(n)}$.
• Output $b^{\prime} \stackrel{\$}{\leftarrow} A(y)$Say that$G$is a$P R G$if for every non-uniform PPT adversaries$A$, there is a neligible function$\varepsilon$, such that, $$\operatorname{Pr}\left[b=b^{\prime}\right] \leq 1 / 2+\varepsilon(n)$$ (i) (2 pts) Describe formally the definition of PRG introduced in class. (ii) (2 pts) Argue informally why the above definition is equivalent to the definition introduced in class. (iii) (2 pts) Prove formally this equivalence. ### Part 2 — Pseudo-Random Generators (PRG) Problem 3. Task (b) – From PRF to PRG (6 points) Let$F:{0,1}^{n} \times{0,1}^{n} \rightarrow{0,1}^{n}$be a PRF. Construct a PRG$G$, such that, for all input$x$, the output length$|G(x)|=100|x|$(i.e, on input an$n$-bit$x$, the output$y=G(x)$has$100 n$bits). (i) (2 pts) Describe your candidate PRG G. (ii) (2 pts) Argue informally why your candidate function$G$is a PRG, given that$F$is a PRF. (iii) (2 2 ts) Prove formally the security of your candicate function$G$, by arguing contra-positive and giving security reduction. Task (c) – From PRF to PRF (10 points) Suppose we have constructed a PRF function$F:{0,1}^{k} \times{0,1}^{m} \rightarrow{0,1}^{l}$, where the input and output length$m=m(k)$and$l=l(k)$are polynomial in$k$. Show that now, for any polynomial$l^{\prime}(k)$, we can construct a PRF$F^{\prime}$with the same key and input lengths$m=m(k) l=l(k)$, but with output length$l^{\prime}=l^{\prime}(k)$. (i) (2pts) Case 1: If$l^{\prime}(n) \leq l(n)$, how to construct$F^{\prime}$from$F$? (ii) (2pts) Case 2: If$l^{\prime}(n)>l(n)$, how to construct$F^{\prime}$from$F$? You may use PRG in your construction (iii) (4pts) Argue informally why your function$F^{\prime}$is a PRF. (iv) (2pts) Prove fomally that your construction$F^{\prime}\$ for Case 2 is a PRF, by arguing contra-positive and giving security reduction.

matlab代写请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

## Course Search

Keyword(s)SearchReset

## Search Results

Course Prefix:CSECourse #: 365Keywords: showing 0 to 1

### CSE 365LR Introduction to Computer Security

View ScheduleCSE 365LR Introduction to Computer SecurityLecture

This is an undergraduate-level course intended for junior and senior-level students and will teach them introductory concepts of computer security. The main foci of this course will be network, web security, and application security. Part of the work will be dedicated to ethical aspects of security, and online privacy. The course will be heavily hands-on, as opposed to theoretical teaching.Credits: 4