# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 1 Introduction  
Nowadays, digital signatures are widely used in various security applications to provide authentication, integrity, and non-repudiation. RSA [1] and ECDSA [2] are two of the most widely used digital signature schemes. The security of RSA and ECDSA is based on the difficulty of factoring and computing discrete logarithms, respectively. However, in 1994, [PERSON] proposed a polynomial-time quantum algorithm for integer factorization and discrete logarithm problems [3]. If a large-scale quantum computer is built, RSA and ECDSA cannot be used anymore. Thus, alternative digital signature schemes which are resilient to attacks by quantum computers are needed. They are called post-quantum cryptography [4, 5]. Various post-quantum signature schemes such as lattice-based [6], multivariate [7], code-based [8], and hash-based have been studied. Lattice-based signature schemes are relatively fast with a reasonably small signature size. However, it is difficult to calculate the quantitative security level and the security is not proven against quantum adversaries. Multivariate signature schemes are relatively fast with an extremely small signature size. However, it is also difficult to estimate the security of multivariate signature schemes against quantum attacks. Code-based signature schemes have a reasonably small signature size and it is possible to calculate the quantitative security level to some extent. However, code-based signature schemes need too large keys to be secure against quantum attacks. Hash-based signature schemes receive a lot of attention in that it is possible to calculate the quantitative security level and the security is also proven [9]. Moreover, hash-basedsignature schemes are considered to be a good candidate for the security of IoT devices due to their simplicity of implementation and customization [10,11]. The hash-based signature schemes XMSS (eXtended Merkle Signature Scheme) [12] and SPHINCS [13] were introduced in 2011 and 2015, respectively. XMSS is stateful, meaning that the signer and the verifier have to maintain their own state information, while SPHINCS is stateless. SPHINCS introduces a few-time signature scheme named HORST (HORS with Trees). HORST is an improvement of a few-time signature scheme HORS (Hash to Obtain Random Subset) [14]. In the context of SPHINCS, each full signature should contain not only a HORST signature but also a HORST public key. HORST uses a Merkle tree to reduce the public key size to a single hash value. However, HORST as well as HORS suffers from pretty large signature sizes. HORSIC (Hash to Obtain Random Subset and Integer Composition) [15] is a few-time signature scheme for broadcast authentication in wireless sensor networks. HORSIC reduces the signature size compared to HORS and HORST. Whereas HORS and HORST use only a cryptographic hash function \(H\), making it infeasible to find two different messages that will produce the same \(k\)-element subset, HORSIC decreases the probability of forgery by using another cryptographic hash function \(G\) and a bijective function \(C_{k,z}\) as well as \(H\) to make it infeasible to find two different messages that will produce the same \(k\)-part integer composition as well as the same \(k\)-element subset. The security analysis of HORSIC is performed on the unrealistic assumption that it is impossible for an adversary to invert the one-way permutation \(f\). In fact, the probability of inverting \(f\) is not zero, but negligible. The security analysis should consider the probability of inverting \(f\). This paper proposes HORSIC+, an improvement of HORSIC. HORSIC+ differs from HORSIC in that HORSIC+ does not apply \(f\) as a plain function to the signature key, but uses a member of a function family which is second-preimage resistant, undetectable, and one-way. In addition, HORSIC+ uses the chaining function \(c^{s}(x,\vec{r})\) similar to W-OTS\({}^{+}\)[16]. These enable the strict security proof without the need for the used function family to be a permutation or collision resistant.