On (in)ability to embed data into Schnorr

In an engaging discussion on the potential for embedding data within Schnorr signatures, a notable point was raised regarding the computation of discrete logarithms in groups of a certain order and the specific challenges posed by prime-order groups such as those used in BIP340. The conversation illuminates the complexity of the discrete logarithm (DL) problem in various group structures, highlighting that for groups where the order is a product of a large prime and a power of 2 (notated as n=p*2^t), the DL problem remains difficult, exemplified by Curve25519 which has a small value of t yet maintains the hardness of the DL problem. This contrasts with the secp256k1 group utilized in BIP340, which is of prime order (t=0), thereby negating the possibility of efficiently computing the t least significant bits of the discrete logarithm k of a group element R using the Pohlig-Hellman algorithm.

The correspondence elucidates a method for embedding data within a Schnorr signature by selecting the discrete logarithm k such that its t least significant bits encode the desired data. However, this technique is not applicable to prime-order groups like secp256k1 due to their lack of subgroups with smaller orders that would facilitate such an embedding through the computation of only a portion of k's bits. The critique extends to the arguments presented against the feasibility of data embedding in BIP340 signatures, proposing that any proof against the possibility must address the inherent difficulty in computing all bits of k from R in prime-order groups, referencing a proof by Håstad-Näslund in 2003 (Håstad-Näslund 2003) which supports this necessity.

This discourse underscores the nuances of cryptographic group selection and the implications for functionalities such as data embedding in signatures. It suggests that while the argument against data embedding in BIP340 signatures might not be universally applicable across different group structures, there remains a foundational challenge in prime-order groups related to the comprehensive computation of the discrete logarithm, thus affecting the feasibility of such embeddings in these contexts.