Logarithmic guarantees for randomized search trees
Let's consider a different example: a hash table. While usually the hash function is fixed in advance, it is also possible for it to be chosen randomly when the hash table is initialized.

If we want to mount a Denial of Service attack on a hash table, we need to feed it many keys that hash to the same value. If the hash function is weak and known, then we can easily do it. If the hash function is weak and unknown, then it could be difficult or even impossible.

When the authors say that the priorities are kept hidden from the user, they mean that the randomness used in the data structure is not "public". In our hash table example, it means that the user of the hash table doesn't know which hash function was chosen. If the user knew the hash function then she could mount a DoS attack. If she doesn't, then such an attack becomes much more difficult.

In practice we don't necessarily think of the user as malicious; however, we want a guarantee on the running time which is independent of how the data structure is used. Suppose that we use a treap or a randomized BST in some algorithm, in a very specific way. If the algorithm has access to the randomness&mdash;for example, if it is fixed&mdash;then perhaps its specific access pattern results in bad performance. However, if the algorithm acts independently of the randomness, then bad performance only happens with small probability.