Cryptography Reference
In-Depth Information
never touches the r-th index. Thus, the index r will retain its state value
r if index j G does not touch it. The probability of this event is
r−τ−1
1− 1
N
over all the intermediate rounds. Hence the first part of the probability
is
r−τ−1
1− 1
N
P(S τ [r] = X)
.
Case II: In the second case, suppose that S τ [r] = X and S τ [t] = X for
some t = r. In such a case, only a swap between the positions r and t
during rounds τ +1 to r−1 of PRGA can make the event (S r−1 [r] = X)
possible. Notice that if t does not fall in the path of i G , that is, if the
index i G does not touch the t-th location, then the value at S τ [t] can
only go to some position behind i G , and this can never reach S r−1 [r],
as i G can only go up to (r−1) during this period. Thus, we must have
2 ≤ t ≤r−1 for S τ [t] to reach S r−1 [r]. Observe that the way S τ [t] can
move to the r-th position may be either a one hop or a multi-hop route.
In the easiest case of single hop, we require j G not to touch t until i G
touches t, and j G = r when i G = t, and j G not to touch r for the next
r−t−1 state updates. Total probability comes to be
t−τ−1 1
N
r−t−1
1− 1
N
1− 1
N
P(S τ [t] = X)
r−τ−2
= P(S τ [t] = X) 1
N
1− 1
N
.
Suppose that it requires (n + 1) hops to reach from S τ [t] to S r−1 [r].
Then the main issue to note is that the transfer will never happen if the
position t swaps with any index which does not lie in the future path
of i G . Again, this path of i G starts from probability r−t−1
N
for the first
hop and decreases approximately to r−t−1
mN at the m-th hop. We would
also require j G not to touch the location of X between the hops, and
this happens with probability
r−τ−2−n . Combining all, we get
the second part of the probability as approximately
1− N
n
r−τ−2−n
r−t−1
mN
1− 1
N
P(S τ [t] = X)
m=1
n
r−τ−2−n
P(S τ [t] = r)
n!N
r−t−1
N
1− 1
N
=
.
It is easy to see that for n = 0, the multihop case coincides with the
single hop case.
Search WWH ::




Custom Search