Security Definitions on Time-Lock Puzzles

Time-lock puzzles allow one to encapsulate a message for a pre-determined amount of time. The message is required to be concealed from any algorithm running in parallel time less than the pre-determined amount of time. In the previous works, the security of time-lock puzzles was formalized in an indistinguishability manner. However, it is unclear whether it directly meets the security requirements of time-lock puzzles. In this work, we define semantic security for time-lock puzzles, which captures the security requirements of the time-lock puzzle more directly. We consider three computational restrictions of an adversary and see how the security relationship changes. At first, in the traditional setting, we observe that it is difficult to prove that the semantic security implies the indistinguishability, same as the opposite implication. Secondly, in a slightly relaxed setting, we show that it is possible to prove that the semantic security implies the indistinguishability. By contrast, we observe that it is difficult to prove the opposite implication. Thirdly, in the more relaxed setting, we show that it is possible to prove that semantic security is equivalent to the indistinguishability. This shows that an indistinguishability meets the security requirements of time-lock puzzles in a certain restriction.