1
$\begingroup$

A hybrid scheme is a combination of a classical and a post-quantum scheme. In the hybrid model, if even the post-quantum section is broken, the hybrid scheme is still secure against non-quantum attacks. But, as far as we know, NSA doesn't like hybrid schemes, for example NSA didn't consider hybrids in her new updated CNSA guidance. But unfortunately, NSA never say anything about his decisions. I have two questions about hybrid PQC schemes:

1- If I understand correctly, in hybrid schemes the input date is first encrypted/signed by classical section's algorithm and then the output of classical section is encrypted/signed by the post-quantum section (or vice versa). Is it correct? I couldn't find any paper/draft/RFC about the exact structure of hybrid schemes. Is there any RFC/standard?

2- Beside complexity and performance issues of hybrid schemes, are there any other downsides for hybrid schemes? How secure are they? Are attacks like (quantum) meet-in-the-middle attacks possible?

$\endgroup$
1
  • 1
    $\begingroup$ I think it's pretty clear that everybody should use a hybrid solution. $\endgroup$ Sep 11, 2022 at 7:46

1 Answer 1

6
$\begingroup$

If I understand correctly, in hybrid schemes the input date is first encrypted/signed by classical section's algorithm and then the output of classical section is encrypted/signed by the post-quantum section (or vice versa). Is it correct?

There is no "standard" way (or at least, not yet - things are still evolving). What you suggest is do able, however there may be more practical approaches.

For signatures, the obvious approach is to have each signature algorithm (both the classical and the post-quantum algorithm) sign the message separately, and then you staple the two signatures together (just concatenate the two signatures if the signature lengths of fixed/dependent on the public keys, or alternatively use a TLV or BER-encoding). To verify, the verifier would separate out the signatures, and verify each one independently (and presumably fail if either one of the signature verification checks fail).

For public key encryption, well, we typically don't use the public key algorithm to directly encrypt the message; instead we select a random symmetric key, use our public key algorithm to encrypt that, and encrypt the actual message with the random symmetric key (this is an older meaning of 'hybrid'; combining symmetric and asymmetric crypto). If we are doing that anyways, what we can do is pick two random values $R_1, R_2$, encrypt $R_1$ with the classical algorithm, encrypt $R_2$ with the postquantum algorithm, and then use $R_1 \oplus R_2$ as a symmetric key to encrypt the message - that means that an attacker would need to break both public key algorithms (or the symmetric algorithm) to recover the data.

As for KEMs, well, that's trickier; your best bet would be to pass both KEM shared secrets through a Key Derivation Function (KDF), and use that. If we assume that the KDF used is strong, that again means that the the classical and the postquantum KEM outputs would need to be recovered by an attacker to recover the KDF output

  1. Beside complexity and performance issues of hybrid schemes, are there any other downsides for hybrid schemes?

I would disagree with the complexity issue, at least in the short term for many scenarios. If we're in a 'brownfield' situation, that is, we need to communicate with both unupgraded systems (which only understand classical algorithms) and upgraded ones, we'll need to have implementations of both the classical and postquantum system. And, if you go through my suggestions, the additional complexity (stapling in the signature case, xor in the public key encryption case, a KDF in the KEM case) is fairly minimal (I did omit the necessity of negotiating the hybrid mode - that could also be minimized).

The other downside is public key/ciphertext/signanture size; however if the classical algorithm is an ECC one, well, that's so short (compared to what the postquantum algorithm uses), that's also fairly minimal.

How secure are they? Are attacks like (quantum) meet-in-the-middle attacks possible?

As you can see in all my examples, the hybrid approach is no weaker than a single system approach (with the sole exception that in the KEM case, we need to assume a good KDF). That is, if we had an oracle that could break our hybrid system, we could use that oracle to break both the classical and the postquantum algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.