Polynomial-time in the interface inputs alon

A. First, the properties that are implicitly required in the definition of the components in Definitions 7.1 and 7.31 are verified, including the property to be polynomial-time in the interface inputs alone. 

To make the components polynomial-time in the interface inputs alone, each value mkj that is received in a signature is first tested with mk test, and it is verified that each value that should be an inner node of the tree, and thus a hash value, is of length len° k). Similarly, a collision in a valid proof of forgery must either consist of acceptable one-time main public keys or values of length len°(k). ... 

Moreover, the new scheme is polynomial-time in the interface inputs alone if the underlying signature scheme is. ... 

Proof sketch. The implicit and explicit requirements from Definitions 7.1 and 7.31 and the property to be polynomial-time in the interface inputs alone are easy to see. Among the criteria from Theorem 7.34, effectiveness of authentication is easily derived from that in the one-time scheme, and the security for the risk bearer is completely identical to that in the underlying one-time scheme. (Recall that the fact that the signer s entity bases many one-time key pairs on the same prekey makes no formal difference at all in Criterion 2 of Theorem 7.34.)... 

---