I see a problem with the wording of this requirement:
Private key safety (needed): It should be practically impossible to derive the private key from many plaintext & signature pairs.
That's not a useful requirement, because for some signature schemes it's much less difficult to carry an attack that allows (with little extra effort) to produce signatures that pass verification, than it is to find the original private key. If we take Ed25519 with this notation
- Finding the integer $a$ (or an equivalent) from the public key would require roughly $2^{128}$ operations using variations of Pollard's rho, and then we can produce signatures that pass verification more efficiently than the original signer.
- Finding the original private key $k$ would require brute force search with expected effort exceeding $2^{255}$ SHA-512 hash.
Finding how to generate the same signatures as the original signer is yet another problem. In the case of Ed25519 it's about as hard as finding the original private key, but we can make variations where that's easier (e.g. we make a variation of Ed25519 where the hash used in the $H(k)$ step is replaced by Argon2).
For this reason, I suggest that we change the requirement to something like:
- Long-term security of a public/private key pair (needed): The same key pair should remain usable for several years, and several signatures per day, without compromising the short-term security objectives stated above.
Assuming that, the requirement
Very short signature size: The signature should be only $n\ll128$ bits
is on the wrong side of the bleeding edge of the state of the art in signature systems, at least if we stick to signature systems with appendix, that is with signature separate from the signed message as implicitly considered in the question.
All known such signature systems require at least an additional $2$ bits of signature for each doubling of the effort to break a given public key (in the sense of allowing to then produce signature of a given message with moderate effort). Meaning that asymptotically, signature size is at least about $2$ times the long-term security in bits.
The best (and AFAIK the only) scheme reaching this factor of $2$ is the BLS scheme. Signature would be at least $192$-bit for $96$-bit long-term security (which I select to match the $\approx2^{95}\ $SHA-256/year of bitcoin mining at time of writing). This is much more bits than asked for. Further, it's unclear how we can build the required pairing. The best unbroken practical proposals reach only $2.25$ to $3$ ($216$ to $288$-bit signature). See this for links.
Another contender is the original/short variation of Schnorr signature, which reaches a factor of $3$, and allows saving some bits by spending more time in the generation and verification. I think we can reach about $240$-bit signature for $96$-bit long-term security.
There is hope with signature schemes giving message recovery, that is allowing to convey at least some of the message in the signature, saving on total size transmitted. We need to change the size requirement to
- Very small signature overhead: a signed message should only be $n\ll128$ bits larger than the message is.
Now we can consider a signature system that takes a message $M$ of $m$ bits, and produces a signed message of $m+n$ bits, such that with the public key we can verify the signed message and extract the original message $M$.
The short-term security can be governed by $n$: forging an acceptable signed message requires an expected $2^{n-1}$ times more work than verifying (and further the attacker can't freely choose the message that comes out of the verification process). That make $n=64$ reasonable for short-term security in the question's context.
However the only such systems I have to propose are variations of OPSSR, and have long-term security no better than RSA with public modulus size $m+n$. Which means that for $n=64$ and long-term security equivalent to RSA-2048, we need $m$ to be at least $1984$-bit ($248$ bytes). Therefore such schemes are great for signing QR-code with that much data with low size overhead, but not "a random seed", which is presumably much shorter: $32$ bytes is ample for that.
So I don't have a solution for the problem posed, and doubt there is one allowing $\ll128$-bit overhead, long-term use of a public/private key pair, and short random message to be signed.
Update: I now explore the idea of making the "random" message an output of the signing process instead of an arbitrary input as in the standard definitions of signature (both signature with appendix and signature giving message recovery).
That's feasible, but introduces a major intrinsic limitation: when receiving an alleged (random message, signature) pair, signature verification does not demonstrate that both are genuine. It tells that if the random message is legitimate and recent, then the signature is by the legitimate holder of the private key (or an attacker with enough hashing power for a brute force attack in the timeframe since generation of the random message). We might want to mitigate this limitation by using an additional input bytestring $d$ that's assumed recent and not manipulable; e.g. published stock prices of the previous day, or/and the previous value of the random message.
Here's one way to do this based on a small variation of the original short Schnorr signature.
Setup: Let $H$ be a purposely slow $n$-bit hash for some $n\ll 128$, made using a memory-hard function such as Argon2 with suitable parameters. Let $q$ be the largest 256-bit prime, that is $q=2^{256}-189$. Let $p=q\,\left\lfloor\pi\,2^{3838}+5501\right\rfloor+1$ and $G=3^{(p-1)/q}\bmod p$, so that $g$ is a generator of the subgroup of prime order $q$ of the multiplicative group integers modulo the nothing-up-my-sleeves 4096-bit prime $p$. The Discrete Logarithm Problem in this Schnorr group is widely believed to require roughly $2^{128}$ operations modulo $p$, disregarding hypothetical CRQC, thus good for like a decade or more.
Key generation:
- draw the private key $x$ as a random secret integer in $[1,q)$
- compute and publish the corresponding public key $a=g^x\bmod p$.
Generating and signing a random number: on input the private key $x$ and public data $d$
- draw a random secret integer $y$ in $[1,q)$.
- compute $b=g^y\bmod p$
- compute the $n$-bit signature $s=H(a\mathbin\|d\mathbin\|b)$ (where $a$ and $b$ each are 512-byte bytestrings)
- compute the random number $r=y-s\,x\bmod q$
Verification: on input the public key $a$, public data $d$, alleged random message $r$ and signature $s$
- compute $b'=g^r\,a^s\bmod p$
- compute $s'=H(a\mathbin\|d\mathbin\|b')$ (where $a$ and $b$ each are 512-byte bytestrings)
- accept $s$ as a valid signature if and only if $s'=s$.
Verification against $(a,d)$ of a legitimately generated $(r,s)$ always succeeds because
$g^r\,a^s\equiv g^{y-s\,x}\,{(g^x)}^s\equiv g^y\bmod p$, hence $b'=b$, hence $s'=s$.
Security against forgery follows from that of short Schnorr signature. Our signature is shorter ($n$ bits) only because we discount the 256-bit $r$ from the signature, and we make the rest $s$ narrow by using a slow hash.
One attack to generate an $(r,s)$ pair that passes verification given only $(a,d)$ is to fix $s$ and try $r$ sequentially. The cost is dominated by an expected $2^n$ hashes: we go from one attempt to the next by multiplying the previous $b'$ by $g$, and checking if $s=H(a\mathbin\|b')$ now holds.
If in addition we know a legitimately generated $r$, we can find a valid $s$ by a similar attack. That $s$ is often but not always the one that the legitimate signer has produced, and the attack has slightly lower expected cost than the above one.
Legitimately generated $r$ are computationally indistinguishable from a 256-bit random number for one not knowing the public key $a$ or the public data $d$. However, with knowledge of that and enough hashing power, $r$ can be distinguished from random based on the fact that some 256-bit $r$ can not be produced by the legitimate generation and signature process, and are recognizable as such by checking that no $s$ exists making $(a,d,r,s)$ pass verification. I see only partial solutions to this issue: they trade better $r$ against less security against forgery (e.g. make $H$ of $n'>n$ bits, truncate the signature disclosed to the low $n$ bits of $H$, and have the verifier find the missing bits by brute force. This way the vast majority of 256-bit $r$ can be generated by the legitimate signing process, decreasing an adversary's advantage in distinguishing $r$; but for a given verification time we need to make the hash $2^{n'-n}$ times faster, thus less secure).
