In the case of sponge construction, it is shown to be differentiable from a RO. In the paper by Bertoni et al., what is meant by the node being saturated. How does it become saturated and the condition which leads to error in the simulator was not clear.

Paper link: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=09F733C00E75E6BB3E3537ACFAE4396E?doi=


1 Answer 1


Saturation is defined in section 4.1 as the condition $R \cup O = C$, where $O$ is the set of supernodes with outgoing edges and $R$ is the set of rooted supernodes and $C$ is the equivalence class of all the nodes with equal "C" part.

The idea is that any query to the compression oracle will reveal a single path in the graph only when the starting node is rooted. If the starting node is not rooted, a random path is chosen but not revealed to the adversary.

To accomplish that, we avoid rooted supernodes with outgoing edges; otherwise, this reveals more paths to the adversary. Therefore, the simulator cannot use this trick once the graph is saturated, i.e. $O = C$, and the replies will not be consistent anymore.

The theorem is that saturation only happens after $2^c$ queries, where $c$ is the capacity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.