Homework #4

This corrects typos in problem 4, where “conditional probabilities” should be “conditional entropies”, and problem 5 item (b), in which there should be set braces around the formula to the right of the equal sign.

Due: March 5, 2021
Points: 100

Questions

(25 points) Suppose composite machine catdog (see Section 9.4.1) receives no HIGH inputs. Does it emit the same value from the left and the right? If so, prove it; if not, give a counterexample.
(25 points) Consider again the algorithm in Figure 9–7. The power used is another side channel for most instantiations of this algorithm. Explain how this side channel works. How might you add sufficient noise to it to render it unusable?
(15 points) Prove that for n = 2, H(X) is maximal when p₁ = p₂ = 1/2.
(15 points) Consider the statement
```
if (x = 1) and (y = 1) then z := 1 
```
where x and y can each be 0 or 1, with both equally likely and z is initially 0. Compute the conditional entropies H(x | z′) and H(y | z′).
(20 points) Let L = (S_L, ≤_L) be a lattice. Define:
1. S_IL = { [a, b] | a, b ∈ S ∧ a ≤_L b }
2. ≤_IL = { ([a₁, b₁], [a₂, b₂]) | a₁ ≤_L a₂ ∧ b₁ ≤_L b₂ }
3. lub_IL([a₁, b₁], [a₂, b₂]) = (lub_L(a₁, a₂), lub_L(b₁, b₂))
4. glb_IL([a₁, b₁], [a₂, b₂]) = (glb_L(a₁, a₂), glb_L(b₁, b₂))
Prove that the structure IL = (S_IL, ≤_IL) is a lattice.

Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
Email: mabishop@ucdavis.edu

ECS 235B, Foundations of Computer and Information Security
Version of February 23, 2021 at 12:21AM

You can also obtain a PDF version of this.