I'm happy to say that I've recently published the paper "On the Adaptive Security of FROST," in collaboration with my co-authors Elizabeth Crites, Jonathan Katz, Stefano Tessaro, and Chenzhi Zhu.
In this paper, we prove the full adaptive security of FROST, meaning that we show that FROST achieves adaptive security up to (t-1) corruptions. Adaptive security is a stronger notion of security for threshold schemes, where when proving unforgettability of FROST, we assume the adversary can adaptively choose which participants to corrupt at any point during the security experiment, as opposed to choosing the full set of participants to corrupt at the beginning of the security experiment (which is the case when proving static security).
As a reminder, adaptive security is a stronger notion of theoretical security over static security. Static security models a security experiment with the adversary picking corrupted parties all at once, at the beginning of the experiment, before it is allowed to interact with honest participants in the protocol. Adaptive security allows the adversary to adaptively corrupt participants throughout its interaction in the protocol. Hence, adaptive security models real-world attacks more closely. It is always possible to prove adaptive security by what we call "complexity leveraging" and static security- where static challenger guesses the corrupted parties up front, then runs the adaptive adversary, and aborts if the adversary corrupts a participant that it did not guess. However, this "complexity leveraging+static" approach incurs tightness loss in the proof, and hence it is desirable to write proofs of adaptive security with improved tightness.
Hence, the main contribution of this paper is to give a tight(er) proof of full adaptive security for FROST in the Random Oracle Model (ROM) and Algebraic Group Model (AGM), under the Algebraic One-More Discrete Logarithm (AOMDL) problem. We additionally show adaptive security for t/2 participants in the ROM+AOMDL only.
Additionally, our proof of full adaptive security requires a new assumption that we refer to as the Low-Dimensional Vector Representation (LDVR) problem, shown below.
The real question is, why do we need the LDVR assumption to prove the full adaptive security of FROST? I'll refer to the paper for technical details, but the LDVR assumption comes into play when showing a reduction to the AOMDL assumption in the AGM, which critically relies on the adversary outputting the representation of \( R^* \) for its FROST forgery \( (R^* , z^*) \). It is possible the adaptive adversary could output a representation that is valid, but would not allow the AOMDL reduction to succeed. This bad case is captured by the LDVR assumption. Because we assume the LDVR assumption is hard, then our AOMDL reduction is sound.
One natural question to consider is whether the assumptions of AOMDL+AGM are actually inherent to proving the adaptive security of FROST, or if it is possible to establish this proof under weaker assumptions. For that question, I will refer to our recent impossibility results on the adaptive security of key-unique threshold signatures, as FROST is likewise key-unique. Our impossibility results show two outcomes: 1) it is impossible to prove adaptive security for key-unique threshold signatures under non-interactive computational assumptions, and 2) it is impossible to prove adaptive security of key-unique threshold Schnorr signatures under rewinding+(A)OMDL. The use of the AGM in our proof of adaptive security for FROST allows us to define a straight-line (non-rewinding) reduction. Hence, while the AGM is not strictly required, it is indeed important to define a non-rewinding reduction, and so it is likely hard to imagine how to establish an alternative proof of adaptive security for FROST under weaker assumptions.
Overall, I am relieved that we now have an established proof of full adaptive security for FROST (beyond the baseline static+complexity leveraging proof, that is possible for any threshold signature with static security). It is interesting that we needed a new assumption to establish this proof, and I am curious to see how (or if) the LDVR assumption is employed to establish adaptive security of schemes beyond FROST.
