Table of contents:

1. 1. Introduction
2. 2. The double-lock method
3. 3. Post-Quantum Cryptography Signatures
4. 4. Is quantum supremacy even a threat?
5. 5. Aliens

Introduction

Recent advancements in quantum computing have urged some people to seek post-quantum schemes for key-exchange that are not vulnerable to Shor’s algorithm.

But the past actions of the very institutions that propose these new quantum-schemes have introduced backdoors in the past. And indeed, new research shows that the new proposed quantum proof algorithms can be used with a backdoor.

Today, I want to propose a simple, yet old, key-exhange protocol that is not vulnerable to quantum-computing attacks: The double-lock-method. This shifts the quantum-burden to the signature algorithm. We will today explore some quantum-proof signing algorithms that could be used together with the double-lock-method for post-quantum security.

The double-lock method

Consider the following scenario: Victoria wants to send a Box with a secure key inside to the PrimeaGen. Now Victoria puts the key into the box, locks the box with her key and sends it to the PrimeaGen. The PrimeaGen then receives the key, adds his own signed lock to the Box and sends it back to Victoria. Victoria verifies that it is the PrimeaGen’s lock on the Box. She then removes her lock and sends the box back to the PrimeaGen. The box is now locked only with the PrimeaGen’s lock and the PrimeaGen can open it to retrieve Victoria’s secret.

In code

In pseudocode it could look like this:

victorias_key_to_share = secureRandom512bit()
victorias_nonce = sha512(victorias_key_to_share + 'victoria')
victorias_encrypted_key = ChaCha20(key: victorias_private_key, nonce: victorias_nonce, plaintext: victorias_key_to_share)

victorias_signature = signWithFalcon(victorias_encrypted_key)

victorias_cipher_friend_request = {
  'public_key_falcon': victorias_falcon_public_key,
  'victorias_encrypted_key': victorias_encrypted_key,
  'signature': victorias_signature
}

This is the friend request Victoria sends to the Primeagen. Then the Primeagen receives the Friend Request. Based on the falcon_public_key, the Primeagen can verify that it’s Alices lock. Once he verified the signature of Alice, he can proceed to add his own lock:

primeagens_secret_nonce_ingredient = SecureRandom512bit()
primeagens_nonce = SHA512(primeagens_secret_nonce_ingredient + victorias_cipher_friend_request)
doubly_encrypted_key_to_share = ChaCha20(key: primeagens_private_key, nonce: primeagens_nonce, plaintext: victorias_encrypted_key) # Encrypt Victoria's key

primeagens_signature = signWithFalcon(doubly_encrypted_key_to_share)
doubly_locked_friend_request = {
  'public_key_falcon': primeagens_falcon_public_key,
  'doubly_encrypted_key_to_share': doubly_encrypted_key_to_share,
  'signature': primeagens_signature
}

Primeagen accepts the friend request: He sends the doubly locked cipher friend request back to Victoria. First, Victora verifies that that the new lock comes from the Primeagen based on the falcon public_key of the doubly-locked friend-reuest. After verification, Victoria takes off her lock:

victorias_nonce = SHA512(victorias_key_to_share + 'victoria')
victorias_key_to_share_encrypted_by_victoria = ChaCha20(key: victorias_private_key, nonce: victorias_nonce, ciphertext: doubly_locked_friend_request['doubly_encrypted_key_to_share'])
final_response_to_primeagen = {
  'victorias_key_to_share_encrypted_by_victoria': victorias_key_to_share_encrypted_by_victoria
}

Finally, Victoria confirms the acceptance of the friend-request by sending her final response back to the primeagen. The Primeagen can now finally compute:

primeagens_nonce = SHA512(primeagens_secret_nonce_ingredient + victorias_cipher_friend_request)
victorias_key_to_share = ChaCha20(key: primeagens_private_key, nonce: primeagens_nonce, ciphertext: final_response_to_primeagen['victorias_key_to_share_encrypted_by_victoria'])

Post-Quantum Cryptography Signatures

Below is a comparison of quantum-proof signature schemes.

For Locality Social Cloud, we have the following considerations:

• Generating or restoring private keys is a RARE event
• Sharing public keys happens considerably more often; for example whenever you add a new friend in a messenger app.
• But the most frequent operation in our case is verifying and signing signatures.

Messages in our case may contain a very small payload. This ecludes Merkle-Tree-based signature schemes like SPHINCS+ and XMSS for our use case; It is a bad idea to sign a 500-byte payload with a 30-kb-key.

Out of the three remaining signature schemes, Rainbow and GeMSS have considerably larger public key sizes of 125kb - 1 MB, while Falcon only has a public key size of up to 1.8 KiB.

For this reason, we propose using a combination of ChaCha20, Falcon and Double-lock-key-exchange for post-quantum security.

Is quantum supremacy even a threat?

While the claims of big tech companies to achieve general quantum supremacy has to be taken with a large grain of salt, it may very well be that quantum-computers may one day see the light of day. Even if it takes another 100 years, the question is: Do you want your data still be encrypted in 100 years? Because the issue is this: Attackers are already gathering key-exchanges for later use.

Let us suppose, we send a key exchange through a WebSocket. Now that WebSocket runs on the secure variant of the WebSocket, which is WSS. WSS, like HTTPS and almost everything else, is based on ECDH, more specifically on Curve25519.

Now if we have a little traffick-sniffer that sniffs your traffic and stores it for later use and the traffick-sniffer gets hold of a qauntum computer in 40 years strong enough to break ECDH, then the attacker can first decipher the key-exchange based on Curve25519 he recorded and then, in the second instance, perhaps decipher another round of ECDH key-exchange built in to your app’s security protocol.

The traffick-sniffer can now recover all of your exchanged secrets and thus, decrypt all traffic he has ever recorded, that was exchanged between you and another user.

If you value long-term-message-security, you should consider migrating from ECDH.

Aliens

And if that does not strike fear in your, consider extraterrestrial attackers with quantum oracles, using them to decrypt human communication. Once we make our applications quantum-proof, we are finally secure from Aliens, provided we wear a aluminum helmet as well.