Ladhe Signatures: Compact Hash-Based Signatures from Additive Prime Decompositions

We introduce Ladhe, a compact hash-based authentication primitive whose private key is an ascending tuple of distinct odd primes summing to a public prime P, and whose public key is the hash of an indexed-pair compression of these primes. The one-time variant is a single-use commitment-and-opening: the public key commits to a secret witness; a signature opens the commitment alongside the message. We prove security against the natural No-Query Forgery (NQF) game — an adversary, given only the public key, cannot produce a valid signature — by reduction to preimage resistance of SHA-256 in the random oracle model. The NQF reduction uses an explicit oracle simulator with target embedding (Theorem 2). A multi-key analysis (Proposition 1) gives a tight union bound; we additionally treat non-uniform precomputation attacks via the Hellman tradeoff. Full EUF-CMA security is recovered in the many-time variant via standard Merkle aggregation that binds messages into leaf hashes, following the SPHINCS+ template [14]. The arithmetic structure of the private key enables compact one-time signatures (the primes themselves, no Merkle path) and a fast structural verifier (k primality checks plus a single hash evaluation). The reference parameter set targets NIST PQC Category 5 via SHA-256, with three measured operating points (|P|= 256, 512, and 1024 bits) trading KeyGen latency against signature footprint. We give the full construction, security analysis in the random oracle model with explicit bounds, an IANA-registered algorithm identifier (Private Enterprise Number 65644, registered April 2026), an open-source Python reference implementation, and a public cryptanalysis bounty. We do not claim machine-verified proofs in the style of Barbosa et al. [19]. We make explicit where our argument is informal and invite community engagement (formal verifica- tion, structural cryptanalysis, advisor review) prior to production use. Efficient KeyGen at cryptographic parameter sizes remains the principal open problem.