Short Paper: Breaking X-VRF, A Post-quantum Verifiable Random Function

Short Paper: Breaking X-VRF, A Post-quantum Verifiable Random Function

연구 분야: Cryptography

학회: International Conference on Financial Cryptography and Data Security

Verifiable Random Functions (VRFs) are public key primitives that allow the holder of the secret key to generate pseudorandom values that are publicly verifiable. An important property of VRFs is uniqueness which guarantees a unique valid (i.e. verifiable using the public key) output for an input. X-VRF is a proposed post-quantum secure VRF that is based on XMSS, a post-quantum hash-based signature scheme that is approved by NIST. In this paper, we show a subtle discrepancy in the security proof of the uniqueness property of X-VRF that allows us to construct a concrete deterministic attack that breaks the uniqueness of X-VRF by constructing two valid outputs for an input. The attack is on the uniqueness of WOTS\(^+\) signature scheme, the one-time signature scheme used in XMSS, and directly extends to XMSS showing that XMSS is not a unique signature scheme and so X-VRF does not satisfy the uniqueness property of a secure VRF scheme. While the attack questions the proved security of X-VRF, it does not break the uniqueness of X-VRF in practice if no collision is known for the underlying hash function of WOTS\(^+\).