How is the message considered in the STROBE-based Schnorr signature example?

Paul Yu

5/11/24, 5:08 AM

I've been studying the Schnorr signature scheme and recently came across an example that uses the STROBE protocol. In the classic version of Schnorr signatures, the challenge e is calculated as e = H(m || r), where m is the message, r is an ephemeral value, and H is a cryptographic hash function. However, in the STROBE-based version of the Schnorr signature scheme, it seems that the challenge is generated based on the public key A and the ephemeral value R, with no mention of the message.

Here's the STROBE-based Schnorr signature example from paper (P.11):

// Alice has a private key k, from which she derives a secret exponent a by running
KEY[sym-key](k); a ← PRF[derive-key](b bytes)

//  When Alice needs to sign a STROBE context, she first begins
the signature using a AD[sig-scheme](name) operation
AD[sig-scheme](name)

//  She then needs a pseudorandom
value r. She calculates this determinsitically by copying the context and running
KEY[sym-key](k); 
r ← PRF[sig-determ](b bytes)

//  She calculates R := g^r and runs
AD[pubkey](A); CLR[sig-eph](R); 
c ← PRF[sig-chal](b bytes);
ENC[sig-resp](r + ac mod p);

// To verify the signature, Bob runs
AD[pubkey](A); 
R ← CLR[sig-eph](b_G bytes);
c ← PRF[sig-chal](b bytes);
s ← recv-ENC[sig-resp](log256(p) bytes)

// Bob then checks that R = g^s/A^c. This holds because g^s = g^(r+ac) = R · A^c

Notably, P.6 outline each of operations in STROBE P.9 specify the usage of operation syntax. ENC[app-ciphertext](“hello”) mean the two operations meta-CLR([[0x03, 0x05, 0x00]]); ENC(“hello”)

Can someone help me understand how the message is taken into account in the STROBE-based version of Schnorr signatures?

Thank you!

1 + 0

implementation

schnorr-signature

sponge

Score:1

Crypto

fgrieu

5/11/24, 9:15 AM

In the classic version of Schnorr signatures, the challenge $e$ is calculated as $e = H(m\mathbin\|r)$, where $m$ is the message, $r$ is an ephemeral value, and $H$ is a cryptographic hash function.

Yes. My reading is that in STROBE's Schnorr signature

The message $m$ to sign is essentially what's noted b bytes in the question, and gets hashed in the step $\mathtt{PRF}[\operatorname{sig-chal}](b\text{ bytes})$ of the paper.
The ephemeral value $r$ is what's noted R.
The challenge $e$ is what's noted c.
It's actually computed $e=H(A,r,m)$, where $A$ is the public key, noted A; and the notation for $H$ is masking some formatting and domain separation constants beside mere concatenation. Hashing $A$ “is an inexpensive way to alleviate concerns that several public keys could be attacked simultaneously”, as the ed25519 paper puts it.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How is the message considered in the STROBE-based Schnorr signature example?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.