[CFRG] Re: Silithium - A Compact, Efficient and Non-separable Hybrid Signature

["D. J. Bernstein" <[e-mail]>]

I'm puzzled by today's comparison between Silithium and Mothma:

    https://datatracker.ietf.org/meeting/126/materials/slides-126-cfrg-sessb-silithium-a-compact-efficient-and-non-separable-hybrid-signature-01#page.2

To me the biggest difference is a Mothma advantage that seems to be
missing from the chart, namely smaller code size, coming primarily from
Mothma using ECC as a black box while Silithium doesn't.

The slides later said that implementing Silithium "in Rust with
RustCrypto takes < 150 lines of code". That's many lines of code that
might go wrong in the context of just one library, and then there are
many different libraries with many different internal interfaces.

Mothma isn't _zero_ code ("The signed message is (s2,s1,r,h,m) where m =
the message being signed, r = H(fresh randomness chosen during signing),
h = H(r,H(hybridpk),hybridsigname,appname,appcontext,m), s1 =
traditional signature of (r,h), s2 = post-quantum signature of (s1,r,h),
H = SHA3-256") but in any case a comparison chart should include
something about code size.

The reuse of existing ECC code will also tend to boost the speed of
Mothma in the real world: it's easier for Mothma than for Silithium to
plug in faster ECC signature systems or faster existing software for the
same systems. Maybe these speed advantages are outweighed by some speed
disadvantages, but I didn't see an analysis backing up the chart's claim
that Silithium is faster, never mind the question of whether the speed
difference matters.

I do understand another entry: Silithium signatures are smaller, such as
2452 bytes instead of 2484 bytes in the case of ML-DSA-44. But I don't
understand why the chart reports 2452 as a green box and 2484 as a red
box. This sounds like a claim that the difference matters; as I noted in
an earlier message, I don't find this plausible.

The other difference listed in the chart is a claim of "Yes" versus
"Cond." for "Backward compatibility", which is later defined as being
able to safely use "the ECC component of the hybrid key to sign with an
ECC algorithm (ECDSA/EdDSA)". I find this claim hard to evaluate since
I'm not sure what it's intended to mean (it's trivially "Yes" in both
cases for the first interpretation that comes to mind, and trivially
"No" in both cases for another interpretation), so I'd like to see a
clear definition and justification.

Labeling this key sharing as "backward compatibility" seems awfully
confusing. The bigger picture is that protocols upgrading from existing
ECC to new PQ have to deal with compatibility questions, whether the PQ
part is internally ECC+PQ or solo PQ. Being able to internally reuse the
ECC _code_ between existing ECC and ECC+PQ has obvious advantages---but
sharing _keys_ between the two layers doesn't resolve the compatibility
questions and shouldn't be portrayed as a compatibility feature. This
sharing complicates the ECC+PQ API to not just be the usual signature
API. Why is the sharing supposed to be a good idea rather than something
to prohibit?

I also don't understand the meaning of the statement on list that
"Edilithium is tighlty coupled with EdDSA specification", especially in
the context of saying which hash function to use. In 2015, CFRG rejected
a switch of Ed25519 to SHA-3, for example with Damien Miller objecting
that "quite a bit of deployed software" was using Ed25519 already with
SHA-512, but if the whole Silithium/Edilithium/... concept is avoiding
black-box ECC signatures anyway then why not use SHA-3? (This is another
reason that claiming "backward compatibility" is confusing.)

John Mattsson writes:
> I think new signatures specifications should be hedged.

For anyone who hasn't seen the jargon yet:

    * This particular hedging consists of generating a signing nonce as
      a hash of a long-term secret, the message being signed, and new
      RNG output for this signature.

    * If you're thinking "wait, shouldn't we just call the RNG and skip
      the step of hashing that together with other inputs?": This extra
      hashing is a defense-in-depth mechanism that sometimes ends up
      rescuing the user from real-world RNG security failures.

    * If you're thinking "wait, didn't some people say that we're
      supposed to skip defense-in-depth RNG wrappers in favor of fixing
      RNG problems _in the RNG_?": Obviously we should _try_ to fix RNG
      problems in the RNG, but using the _hope_ of success as an excuse
      to skip a low-cost defense-in-depth mechanism is hard to justify.

Having said that: Libraries often have more stringent tests for
deterministic functions than for randomized functions, so using
deterministic functions when possible tends to reduce bug rates. This is
an advantage of hashing a long-term secret and the message being signed
_without_ also hashing a new RNG output.

The basic counterargument is that extra randomization can make
side-channel attacks and fault attacks more difficult. But this argument
is weaker for Internet applications than for, say, pay-TV applications.

In libraries that know how to properly test the usage of randomness,
the testing advantage of determinism disappears. That's why lib25519
ends up randomizing signatures; for the evaluation of pros and cons see
https://lib25519.cr.yp.to/security.html. But a CFRG spec should consider
more libraries.

Anyway, this deterministic-vs.-hedged decision is inside nonce
generation and doesn't interact with other aspects of the design of a
signature system.

---D. J. Bernstein


===== NOTICES =====

IETF BCP 78, "Rights Contributors Provide to the IETF Trust", Section 5
(normative), "Rights in Contributions", provides a modification right
"unless explicitly disallowed in the notices contained in a Contribution
(in the form specified by the Legend Instructions)".

The official language from IETF's "Legend Instructions" for the
situation that "the Contributor does not wish to allow modifications nor
to allow publication as an RFC" is as follows: "This document may not be
modified, and derivative works of it may not be created, and it may not
be published except as an Internet-Draft."
<https://trustee.ietf.org/wp-content/uploads/Corrected-TLP-5.0-legal-provsions.pdf>

The same language is used in, e.g., RFC 5831. The same language hereby
applies to this document. This is not disclaiming or limiting the
applicability of IETF policies; it is strictly following IETF policies.

IESG claims that the "explicitly disallowed" provision in BCP 78 is
limited to the examples in Section 3 in BCP 78. That is incorrect. BCP
78 states that Section 5, "Rights in Contributions", is normative, while
Section 3, "Exposition of Why These Procedures Are the Way They Are", is
informative. The opt-out provision in the normative text is clear, and
cannot be limited by an informative section. BCP 78 does not give IESG
any authority to issue changes or purported clarifications of the rules.

Rationale for exercising the BCP 78 opt-out provision: I'm fine with
redistribution of copies of this document. The issue is instead with
modification, such as (1) IESG's May 2025 posting of an IESG-mangled
version of an appeal that I had filed and (2) IETF management selling
IETF mailing-list text to AI companies. This goes far beyond what
copyright law allows as fair use (such as giving quotes for purposes of
commentary). When I complained about the mangled document, the IETF
Executive Director responded not by apologizing but instead by asserting
that IETF management had the power to do whatever it wanted.