Winternitz One-Time Signature (OTS) is an essential component in practical hash-based digital signature schemes that are regarded as quantum secure. This study aims to improve the efficiency of Winternitz OTS without impairing its provable security. The improvement is brought by a novel fingerprinting function that can be realized from an existing secure fingerprinting function and an efficiently computable mapping. Besides the security proof of the strongly existential unforgeability, it is shown that the proposed scheme is the optimum in the sense that it minimizes the size of hash chains needed, and thus has the smallest computational costs for signature operations among all Winternitz-style OTS.