The best cryptographic protocol ever!

Cryptographic protocols are broken so often. Current crypto protocols use outdated algorithms. They’re usually incomplete, leaving multiple insecure choices to implementers. This post will solve all these problems once and for all. We will use modern crypto algorithms which are safe against powerful quantum computers. Furthermore, we will modify state-of-the-art algorithms to make them faster, safer and easier to use. We will specify practical deployment guidelines to mitigate all known practical attacks. Finally, our protocol is based on solid cryptographic foundations and are proven safe in the standard model, i.e., attacks are impossible.

To completely specify our protocol, we will describe key exchange, key server, digital signature, side-channel protection, record encryption, replay attack protection and compression algorithm.

Key exchanges

Matrix-based key exchange

  1. Alice → Bob: xG
  2. Bob → Alice: yG
  3. The shared secret is y(xG)= xyG= x(yG).

Advanced math tells us that there is a map from xG to x, so using the described map, knowing xG, yG helps finding the secret x, y and hence the shared secret xyG.

Therefore, we will use advanced lattice-based key exchange instead of DH. Don’t be afraid of the terminology lattice, they’re just matrices that you’ve learned in your undergrad course. Matrix-based key exchange is proven safe against quantum computers and hence it’s safe against classical computers. The drawback of matrix-based key exchange is it has noise. Noise is annoying, no one likes noise. We will modify state-of-the-art matrix-based key exchange to completely remove noise.

The protocol where A is a matrix.

  1. Alice → Bob: Ax
  2. Bob → Alice: yA

3. The shared key is (yA)x = yAx = y(Ax).

Our protocol is proven safe based on the below theorem.

  • Quantum resistance matrix assumption (QRM): given matrix A and vector Ax, it’s impossible to compute x even with the help of quantum computers.
  • Theorem: Our matrix-based key exchange is safe against eavesdropping adversaries if QRM is true.
  • Proof: Only available in the extended version upon request.

Quantum key distribution (QKD)

Digital signature

We’ll combine 2 best digital signatures into 1 digital signature that is short, aggregable and safe against quantum computers. Our proof of security is based on the following generic theorem.

  • Composition theorem: when we combine 2 safe protocols, the result is a safe protocol.

Quantum safe digital signature XMSS (eXtended Merkle Signature Scheme)

BLS aggregate signatures

Sign-sign algorithm

Transparent key server

RESTless key server

Blockchain-based key server

Furthermore, we think that a simple blockchain is not enough because the blockchain leaks the public keys. Therefore, we’ll deploy zero-knowledge proof to prove the existence of public keys without even revealing them.

Side-channel protection

Using leakage-resilient cryptography

Constant-time signature verification

Compress-encrypt-compress algorithm

Record encryption

Replay attack protection

Random number generator

Optimized modulo operation

Rejection sampling algorithm

Patent issue

--

--

Senior security engineer @Google. Black Hat Speaker USA 2021, ASIA 2022. Personal account. https://github.com/cryptosubtlety

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Quan Thoi Minh Nguyen

Senior security engineer @Google. Black Hat Speaker USA 2021, ASIA 2022. Personal account. https://github.com/cryptosubtlety