Hybrid PQC DSA using ed25519 + Falcon

[Doge Protocol]

Hi PQC community,

In some scenarios, it may be preferable to use a Hybrid DSA crypto-schemes, as a short term hedge against lattice based cryptography broken, since they haven't been battle tested widely over years. 

While Hybrid PQC is a contentious topic, for some use-cases like blockchains, if the underlying DSA gets broken on classical computers, the entire ecosystem can get destroyed with little or no chances of recovery, since all blockchain data is public. Hence hybrid seems more preferable here.

Would be great if community can give feedback on a hybrid scheme; the scheme itself is simple, with the sk, pk and signature being a concatenation of the classical and pq counterparts. 

Are there any security risks (other than implementation bugs) of using two signature algorithms in conjunction as one? The actual implementations of these individual schemes are not modified anyway, but rather just called one after another and appended.

Signature Size :  798 + message length

SK size : 2242 bytes (32 + 1281)

PK size: 929 bytes (32 + 897)

A simple PoC using EdDSA + Falcon is shared below (absolutely not meant for production use yet, it is only a rough PoC at this point).

This implementation uses Round 3 Falcon 512 reference implementation and ed25519 implementation from https://tweetnacl.cr.yp.to/

https://github.com/DogeProtocol/hybrid-pqc

[Mike Ounsworth]

Hi,

 

Coupling lattice with ECDSA in the way you suggest is in fact preferred by several European government bodies:

 

ENISA (Europe):

“A solution to this might be to augment, instead of simply replacing, current modern cryptosystems with PQC systems.”

“Start with a system that encrypts and/or signs using elliptic-curve cryptography. Add an extra layer that also encrypts and/or signs using post-quantum cryptography.”

https://www.enisa.europa.eu/publications/post-quantum-cryptography-integration-study, October 2022

 

 

 

BSI (Germany):

“post-quantum algorithms should generally not be used alone, but only in hybrid mode, i.e. in combination with a classical procedure.”

https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Brochure/quantum-safe-cryptography.html

 

 

ANSSI (France):

“the role of hybridation in the cryptographic security is crucial and will be mandatory for phases 1 and 2 presented in the sequel.”

https://www.ssi.gouv.fr/uploads/2022/01/anssi-technical_position_papers-post_quantum_cryptography_transition.pdf

 

 

 

 

A straightforward composite mode – where the public key is a concatenation of multiple public keys, and the signature is a concatenation of multiple signatures – has minimally more implementation complexity than a single signature, but only in that it requires an extra for-loop, which I would hope cryptographic engineers can implement correctly. Conceptually these are multiple independent signatures over the same message and so we should ask about cross-algorithm attacks. We’ve done this sort of thing before, like when Windows binaries were signed by both RSA-SHA1 and RSA-SHA2, or document formats such as S/MIME or PGP-based systems that are capable of carrying signatures. While more cryptanalysis is probably needed in this area, it’s hard to imagine how knowing the signature of a given message on multiple algorithms could lead to a key recovery or forgery attack.

https://datatracker.ietf.org/doc/draft-ounsworth-pq-composite-keys/

 

 

---
Mike Ounsworth
Software Security Architect, Entrust

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Doge Protocol
Sent: Friday, February 3, 2023 1:17 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] [pqc-forum] Hybrid PQC DSA using ed25519 + Falcon

 

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

---

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/802c600c-c2ab-4e29-aac6-1416271fb191n%40list.nist.gov.

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

[Doge Protocol]

Thanks for the information. It is helpful.