Multi-signatures with proofs of possession ⇒ Multi-signatures in the KOSK model

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If a multi-signature scheme with algorithms $(\mathsf{PopProve},\mathsf{PopVrfy})$ is unforgeable in the proof-of-possession model, the scheme without them is unforgeable in the knowledge-of-secret-key model, with the same advantage — folklore.

Sketch

On a registration $\rho$ of the KOSK forger, the POP-model adversary computes $(\mathsf{sk},\mathsf{pk})=\mathsf{KeyGen}(\mathsf{pp};\rho )$ and $\pi =\mathsf{PopProve}(\mathsf{pp},\mathsf{sk},\mathsf{pk})$ and registers $(\mathsf{pk},\pi )$, which $\mathsf{PopVrfy}$ accepts by correctness; it forwards the signing sessions and the forgery unchanged.