CS547A Homework set #5

Due Tuesday December, 5 2000 in class at 14:30 SHARP

Exercises (from Stinson’s book)

• 7.4 •

Suppose **n=pq**, where **p** and **q** are two (secret) distinct large primes such that **p=2p _{1}+1** and

Now, suppose that **n = 603241** and **a = 11** are used to define a hash function **h** of this type. Suppose that we are given three collisions for **h:**

**h(1294755) = h(80115359) = h(52738737)**.

Use this information to factor **n**.

• 7.5 •

Suppose **h _{1} : {0,1}^{2m} ->{0,1}^{m}** is a strongly collision-free hash function.

(a) Define **h _{2} : {0,1}^{4m} ->{0,1}^{m}** as in

(b) For an integer **i>1**, define a hash function **h _{i} : {0,1}^2^{i}m ->{0,1}^{m}** recursively from

FIGURE 7.13 Hashing 4m bits to m bits

- write
**x**in**{0,1}**as^{4m}**x = x**, where_{1}||x_{2}**x**in_{1},x_{2}**{0,1}**^{2m} - define
**h**._{2}(x) = h_{1}(h_{1}(x_{1}) || h_{1}(x_{2}))

FIGURE 7.14 Hashing 2^{i}m bits to m bits

- write
**x**in**{0,1}^2**as^{i}m**x = x**, where_{1}||x_{2}**x**in_{1},x_{2}**{0,1}^2**^{i-1}m - define
**h**._{i}(x) = h_{1}(h_{i-1}(x_{1}) || h_{i-1}(x_{2}))

• 9.3 •

Suppose that Alice uses the *Schnorr *Scheme with **p=122503**, **q=1201**, **t=10** and **a=11538** (as in Exercise 9.2). Now suppose that **v = 51131**, and Olga has learned that

**a ^{ 3}v^{148} = a^{ 158}v^{1077} (mod p)**.

Show how Olga can compute Alice’s secret exponent **a**.

• 9.7 •

Suppose that Alice is using the *Guillou-Quisquater *Scheme with **n = 199543**, **b=523** and **v = 146152**. Suppose that Olga has discovered that

v^{456}101360^{b} __=__ v^{257}36056^{ b} (mod n).

Show how Olga can compute **u**.

Other Exercises

Goldwasser-Micali

Let **n=p*q**, the product of two primes, and let **y** be an element of **QNR _{n}[+1].** Remember that the

Let **GM(m _{1}),GM(m_{2})** be the

Imagine the government witnessed Bob's transmission of both messages to Alice and they wish to have some minor information about the messages as follows.

- Show how Bob can prove that both
**GM(m**were encryptions of the same message_{1}),GM(m_{2})**m**without disclosing anything at all about it._{1}=m_{2} - Show how Bob can prove that
**GM(m**were encryptions of messages_{1}),GM(m_{2})**m**and_{1}**m**that differed in an_{2}**even**or**odd**number of positions, without disclosing anything else about them. - Assume
**m**have even length,_{1},m_{2}**|m**. Show how Bob can prove that_{1}|=|m_{2}|=2k**GM(m**were encryptions of different messages_{1}),GM(m_{2})**m**by disclosing nothing except for the fact that they differed somewhere among all but one of the positions. (Bob can but aside one encrypted bit at a fixed position of_{1}<>m_{2}**GM(m**and_{1})**GM(m**, and then prove that the remaining truncated messages are different without disclosing anything about them except for the fact that they differ). Explain why we need messages of even length_{2})**2k**. - How much uncertainty is left about
**m**when only learning that they differ ? How much uncertainty is left about_{1},m_{2}**m**when learning that they differ by the method suggested in (c) ?_{1},m_{2}

(in both cases assume that the a priori uncertainty was maximum.)