Rivest’s “distinguished point” (DP) method is a variable length hash chain where

Question

Rivest’s “distinguished point” (DP) method is a variable length hash chain where all chain end points have the same d-bit suffix. In the precomputation phase, a chain is computed until a value is output with the proper suffix. During the on-line phase, the precomputed chains are checked only if a reduction on a hash value results in an output with the d-bit suffix.

(d) How many expected table lookups are required when using DP as compared to without using DP? Explain your answer.

(e) What is the practical benefit of using tables built using DPs? Explain your answer.

Explanation / Answer

distinguished points method:-

it is the method of quicly inverting the one way function using the pre computed table.The distinguished point method was suggested by Rivest . Rather than fixing the length of each Hellman chain, the iteration Xi j,k = fi(Xi j,k1 ) is continued until an Xi j,k.For example, if one wants the average chain length to be t = 2d , DP are typically defined to be points whose first d bits are all zero.

The original Hellman’s approach suffers from a serious practical drawback. An attacker needs to perform T = t 2 random disk accesses that are extremely time consuming in practice. This issue was solved by Rivest who proposed to use so called distinguished points (DP) as end points of the chains.

d) expected table lookups are required when using DP as compared to without using DP,this was mailny used to decrease the number of tables ,as compared to the original hellman's approach during the online phase,so in this the number of table lookups is reduced by a factor of 2d

The use of distinguished points reduces the number of random disk accesses/lookups by a factor t, which is necessary for practical attacks. the average length of chains generated online is expected to be about 2d . In this paper, we shall refer to this trade-off method as Hellman+DP.

e) in the old hellman method the major drawback was that most of the rime was spent in resolving the false alarm .so to resolve that distinguished point method was very useful,and also it reduced the number of table lookups as compared to the old method.

*it is aslo usefull to minimize the hard disk bottleneck problem and also optmimized the method..

for example: if one is searching in a dictionary, and an intermediate values does not match or meet the distinguished criteria ,then that is not required to looked upor checked from the hard disk,it dont have to follow the algorithm to check the result again and again from the hard disk,so it will reduce the time of search.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.