Post-Quantum Noise with SIDHp751

This page describes an extension of Post-Quantum Noise with New Hope to also include support for the post-quantum SIDHp751 algorithm; paper, reference code.

Note: This experiment explores whether it is possible to run a fully post-quantum handshake with SIDHp751. In practice it would be better to mix classical and post-quantum operations in a handshake to gain the strengths of both systems.

SIDHp751

The SIDHp751 algorithm is a Diffie-Hellman scheme based on supersingular isogeny. Key sizes are as follows:

• Private keys: 48 bytes
• Public keys: 768 bytes
• Shared secret: 192 bytes

The paper claims that the security level is 128-bit quantum and 192-bit classical.

SIDHp751 is much closer to classical DH schemes like Curve25519 and Curve448 than New Hope. SIDHp751 only supports ephemeral keys for now.

Note: the paper describes an ephemeral Diffie-Hellman key exchange. It is insecure to use it as is with static keys.

The API is more "balanced" than New Hope, but it requires different keypair and shared secret generation functions on each side:

a = GENERATE_KEYPAIR_ALICE()              b = GENERATE_KEYPAIR_BOB()
                         a.public      ->
                                       <- b.public
shared = DH_ALICE(a.private, b.public)    shared = DH_BOB(b.private, a.public)

Implementing Noise tokens with SIDHp751

Noise tokens can be implemented almost "as is" with SIDHp751. The only special detail to handle is which keys are Alice and which keys are Bob so as to use the appropriate primitives.

In the Noise-C experiment, the initiator's e and s objects are labelled as Alice and the re and rs objects are labelled as Bob. The responder labels the e and s objects as Bob and the re and rs objects are labelled as Alice. These label assignments are reversed for fallback patterns.

Because SIDHp751 uses different primitives for Alice and Bob, Noise implementations must generate static keypairs differently depending upon whether the party will be the initiator or the responder. If the party could perform either role then two sets of static keypairs will need to be generated ahead of time, with the specific keypair chosen when the handshake is started.

Suggested changes to the Noise specification

The Noise specification currently assumes that DHLEN is the same for public keys and DH outputs. This is not the case for SIDHp751 or New Hope. Suggest splitting into DHLEN_PUBLIC and DHLEN_SHARED.

For New Hope, the DHLEN_PUBLIC value is different for Alice and Bob (1824 and 2048 bytes respectively). Instead of being a global constant, suggest changing it to a property of the key; e.g. e.DHLEN_PUBLIC and re.DHLEN_PUBLIC.

There also needs to be some way to specify the labels (Alice or Bob) for all key objects during Initialize() so that later DH operations know how to use each object. Setting the label may also change the DHLEN_PUBLIC value for the object.

Suggest changing the definition of Initialize() to include:

• Sets the s, e, rs, and re variables to the corresponding arguments.
• For regular patterns:
  • If initiator is true, then label s and e as Alice and label rs and re as Bob.
  • If initiator is false, then label s and e as Bob and label rs and re as Alice.
• For fallbacks patterns, reverse the above labelling (initiator is Bob, responder is Alice).

New Hope needs to know the ephemeral public key for Alice to generate the public key for Bob. This can be accomplished by adding an extra argument to GENERATE_KEYPAIR() and modifying WriteMessage() to perform e = GENERATE_KEYPAIR(re). If e is labelled as Bob, then the New Hope back end can obtain the parameters provided by Alice from the supplied re argument. An error will occur if re is empty at that point.

SIDPHp751 in Noise-C

The sidh branch of Noise-C contains an experimental implementation of the details described above. All handshake patterns are working.

The performance of the reference code is not great though. Even with the AMD64 assembly version, keypair generation is more than 100 times slower than with New Hope (by contrast, shared secret generation is quite fast).

Because Noise requires the use of ephemeral keys, all handshake types will incur a significant performance penalty if SIDHp751 is used.