Question

Assume that source elements of length k are mapped in some uniform fashion into a target elements of length p. If each digit can take on one of r values, then the number of source elements is rk and the number of target elements is the smaller number rp. A particular source element xi is mapped to a particular target element yj.

a. What is the probability that the correct source element can be selected by an adversary on one try?
b. What is the probability that a different source element xk (xi,xk) that results in the same target element, yj, could be produced by an adversary?
c. What is the probability that the correct target element can be produced by an adversary on one try?

Answer 1

Answer And explanation

a)

`r^k` has 1/
`r^k` probability guess the correct source

b)

Each element in
`r^p` is mapped by
`r^k` /
`r^p` . There are
`r^k^-^p` So there are
`r^k^-^p` -1 elements.

number of target elements =
`r^k^-^p`

number of source elements =
`r^k^-^p` -1

probability =
`r^k^-^p` -1 /
`r^k`

c) Probability of the correct target element

1/
`r^p`