Approximate probability distributions for long hash chains in the random oracle model

The aim of the thesis is to improve the probabilistic model used for one-way hash chains in Evaluating the Security of One-way key Chains in TESLA-based GNSS Navigation Message Authentication Schemes by Caparra, Sturaro, Laurenti and Wullems. In the first chapter we introduce some fundamental notions and useful results that will be used throughout the thesis. Then we give a description of what hash chains are and which are their applications. In particular, we focus on the TESLA protocol, in order to have a better understanding of the model we will be working on. In the second chapter we define a probabilistic model for hash chains and then we proceed to study its properties. Then we analyze the attack described in the above-mentioned article and derive general upper and lower bounds on the probability of success of the attack, by relaxing an assumption made in the paper which results to be unnecessary. In the final chapter we aim to find a probability distribution that well approximate our model, at least asymptotically. To do so we aim to give an upper bound on the Kullback–Leibler Divergence between the model and our target distribution to later derive an upper bound on the total variational distance through Pinsker inequality. Unfortunately we could not complete the task and we conclude the thesis with an intermediate result about these bounds.