Multi-User Collisions: Applications to Discrete Logs, Even-Mansour and Prince
In this paper, the authors investigate the multi-user setting both in public-key and in secret-key cryptanalytic applications. In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, i.e., the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users. One possible scenario is to recover a single key in a large set of users more efficiently than to recover a key in the classical model. Another possibility is, after some shared pre-computation, to be able to learn individual keys very efficiently.