论文标题
单一的平方可验证延迟函数从已知顺序组中的时锁拼图
Single Squaring Verifiable Delay Function from Time-lock Puzzle in the Group of Known Order
论文作者
论文摘要
可验证的延迟函数（VDF）是一个函数，该函数需要评估指定的顺序时间$ t $，但可以通过$ω（\ log {t}）$ - 时间进行验证。对于有意义的安全性，$ t $最多可以是安全参数$λ$中的次数，但没有下限。 VDF在从随机信标到可持续区块链的几种应用中很有用，但在实践中确实很少见。所有这些VDF中的验证需要$ω（λ，\ log {t}）$顺序时间。本文得出了可验证的延迟功能，该功能在$ o（1）$ - 顺序时间中可验证。关键的观察结果是，先前的作品对其顺序使用了次指数的代数假设。相反，我们从多项式顺序的假设中得出了VDF，即已知顺序的群体拼图。特别是，我们表明，即使已知组的顺序，延迟参数是多项式绑定的，即$ t \ le \ mathtt {poly}（λ）$，也可以依次是固定的拼图。作为附加优势，我们的VDF仅需要一个顺序的平方来验证。因此，在我们的VDF中，验证所需的顺序努力是固定的，并且独立于延迟参数$ t $。
A Verifiable Delay Function (VDF) is a function that takes a specified sequential time $T$ to be evaluated, but can be verified in $Ω(\log{T})$-time. For meaningful security, $T$ can be at most subexponential in the security parameter $λ$ but has no lower bound. VDFs are useful in several applications ranging from randomness beacons to sustainable blockchains but are really rare in practice. The verification in all of these VDFs requires $Ω(λ, \log{T})$ sequential time. This paper derives a verifiable delay function that is verifiable in $O(1)$-sequential time. The key observation is that the prior works use subexponentially-hard algebraic assumptions for their sequentiality. On the contrary, we derive our VDF from a polynomially-hard sequential assumption namely the time-lock puzzle over the group of known order. In particular, we show that time-lock puzzle can be sequentially-hard even when the order of the group is known but the delay parameter is polynomially-bounded i.e., $T \le \mathtt{poly}(λ)$. As an add-on advantage, our VDF requires only one sequential squaring to verify. Thus, in our VDF, the sequential effort required for verification is fixed and independent of the delay parameter $T$.
