Post-Quantum Cryptography

[paragonie-security]

Not today, but some day soon, the Internet may need post-quantum cryptography. NIST is currently putting forth the initial effort to standardize some asymmetric KEMs and signature algorithms for a post-quantum Internet.

There has been some debate on the IETF's CFRG mailing list about whether to switch immediately to post-quantum algorithms, or to implement a hybrid approach. Our internal consensus is on a hybrid signature scheme.

In a future release, we will need to add a definition for a new signature algorithm. This will be a hybrid algorithm consisting of Ed25519 and a post-quantum algorithm.

I've included a sketch for a hybrid signature scheme based on FALCON-512 below.

Example: Ed25519 + FALCON-512

Note: A real implementation would use distinct value objects to prevent misuse.

Key Generation

<?php
const PQ_PREFIX_EDDSA  = 'libgossamer_ed25519';
const PQ_PREFIX_FALCON = 'libgossamer_falcon512';

function hybrid_keygen(string $seed): array
{
    // Derive independent, deterministic seeds from the long-term 512-bit secret
    $eddsa_seed = hash_hkdf('sha512', $seed, 32, PQ_PREFIX_EDDSA . $seed);
    $falcon_prng_seed = hash_hkdf('sha512', $seed, 32, PQ_PREFIX_FALCON . $seed);

    // Generate two keypairs (one classical, one post-quantum)
    $eddsa_keypair = sodium_crypto_sign_seed_keypair($eddsa_seed);
    $falcon_keypair = crypto_sign_falcon512_seed_keypair($falcon_prng_seed);

    // Grab components
    $eddsa_secret = sodium_crypto_sign_secretkey($eddsa_keypair);
    $falcon_secret = crypto_sign_falcon512_secretkey($falcon_keypair);
    $eddsa_public = sodium_crypto_sign_publickey($eddsa_keypair);
    $falcon_public = crypto_sign_falcon512_publickey($falcon_keypair);

    return [
        $eddsa_secret . $falcon_secret,
        $eddsa_public . $falcon_public
    ];
}

// 512-bit random byte seed; store this value
$seed = random_bytes(64);
[$secret, $public] = keygen($seed);

Signing

<?php
function hybrid_sign(string $message, string $secret_key): string
{
    $eddsa_sk = mb_substr($secret_key, 0, 64, '8bit');
    $falcon_sk = mb_substr($secret_key, 64, null, '8bit');
    
    $eddsa_sig = sodium_crypto_sign_detached($message, $eddsa_sk);
    $falcon_sig = crypto_sign_falcon512_detached($message, $falcon_sk);
    return $eddsa_sig . $falcon_sig;
}

Verifying

<?php
function hybrid_verify(string $signature, string $message, string $public_key): bool
{
    $eddsa_pk = mb_substr($public_key, 0, 32, '8bit');
    $falcon_pk = mb_substr($public_key, 32, null, '8bit');
    $eddsa_sig = mb_substr($signature, 0, 64, '8bit');
    $falcon_sig = mb_substr($signature, 64, null, '8bit');
    
    $eddsa_valid = sodium_crypto_sign_verify_detached($eddsa_sig, $message, $eddsa_pk);
    $falcon_valid = crypto_sign_falcon512_verify_detached($falcon_sig, $message, $falcon_pk);
    return $eddsa_valid && $falcon_valid;
}

Remarks

By unifying two signature algorithms into one single "hybrid" algorithm, and treating it as if it was just EdDSA (or equivalent), we can prevent an entire class of algorithm misuse vulnerabilities.

Users would be expected to retain a 512-bit (64 byte) secret key, which will be used to create an Ed25519 keypair and PRNG seed for a FALCON-512 keypair. The result would be a single keypair.

• The first 64 bytes of the hybrid secret key will be an Ed25519 secret key. The remaining bytes will be the FALCON-512 secret key.
• The first 32 bytes of the hybrid public key will be an Ed25519 public key. The remaining bytes will be the FALCON-512 public key.
• The first 64 bytes of each signature will be an Ed25519 signature. The remaining bytes will be the FALCON-512 signature.

As you can see, this pattern can be generalized to any post-quantum signature algorithm. (We chose FALCON-512 for this example because it's an attractive candidate in terms of bandwidth and performance.)