The disclosure relates to a method (20) for a serving device (3) of establishing a computational puzzle for use in communication between a client device (2) and the serving device (3). The method (20) comprises establishing (21), in the serving device (3), the computational puzzle (p) based on a key shared by the client device (2) and the serving device (3) and on a solution (s′, s″) to the computational puzzle (p). Further method (30) in a serving device is provided, methods (60, 70) for client devices (2), serving devices (3), client devices (2), computer programs and computer program products.