Hybrid Post Quantum Cryptography

While lattice based post-quantum cryptography schemes such as Falcon and Dilithium have been standardized, they haven’t been battle-tested widely over the years like RSA and Elliptic Curve vased crypto-schemes. It's possible that newer category of attacks on Lattice based cryptography may come to light.

Because of these reasons, it's preferable to use a hybrid signature scheme that uses two crypto schemes behind the scenes: a PQC scheme and a classical scheme (EdDSA). This hybrid model is required to provide a hedge against Lattice based cryptography schemes such as Falcon getting broken on classical computers in the interim.

When quantum computers capable enough to break EdDSA become available, the hybrid model will still provide protection against quantum computer attacks, since a post quantum crypto scheme is used in the hybrid model.

This hybrid model will be abstracted away so that users do not have to worry about managing two sets of keys. To users, it will be just one composite key to manage and use. Likewise, higher-level developers do not have to worry about the hybrid model, since it will be abstracted away.

Some disadvantages of the hybrid model are increased complexity, increased risk of implementation bugs, increased compute time, increased storage, and bandwidth requirements. However, the security benefits of the hybrid model outweigh these disadvantages.

Deterministic Key Generation

A deterministic version of key generation has also been added. For example, this can be used for seed phrase based wallet generation for blockchains. The size of the seed is 80 bytes; 48 bytes for Falcon and 32 bytes for ed25519. The seed should be generated using a CSPRNG.

Warning

This is test software, not yet ready for production use. Do not use in production systems!

Falcon

Falcon is a Post Quantum Digital Signature Scheme that has been standardized by NIST. This repository is based on the Falcon512 reference imlpementation at Round 3 submission of Falcon.

EdDSA

The classical digital signature algorithm used is EdDSA (ed25519). The implementation used is TweetNaCl, a self-contained public-domain C library. (https://tweetnacl.cr.yp.to/)

Randombytes

The random implementation is based on (https://github.com/dsprenkels/randombytes), which itself is based on libsodium randombytes.

Source

https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Falcon-Round3.zip

SHA256: fd58f0454f6bfb4713734e60b2d2d75d96fbae62d5180fceeef1039df5362f44

Layout

Performance

These numbers were evaluated on an AWS t2.medium instance over 10000 iterations (single threaded), running Ubuntu. Note that this instance type has burstable CPU performance, hence the following numbers are approximate. The reference implementation of Falcon512 from NIST Round 3 and ed25519 implementation from (https://tweetnacl.cr.yp.to/) was used.

Generate Key Pair : 25 ms (40 per second)
Sign: 8.5 ms (115 per second)
Sign Open: 3.6 ms (280 per second)
Verify: 3.6 ms (280 per second)

Building

Linux/macOS

Install dependencies:

On Ubuntu:

  apt-get update
  sudo apt install astyle cmake gcc ninja-build libssl-dev python3-pytest python3-pytest-xdist unzip xsltproc doxygen graphviz python3-yaml

On macOS, using a package manager of your choice (we've picked Homebrew):

 brew install cmake ninja openssl@1.1 wget doxygen graphviz astyle
 pip3 install pytest pytest-xdist pyyaml

Get the source:

 git clone https://github.com/dogeprotocol/hybrid-pqc.git
 cd hybrid-pqc

and build:

 mkdir build && cd build
 cmake -G Ninja -DBUILD_SHARED_LIBS=ON ..
 ninja

Windows

Binaries can be generated using Visual Studio 2019 with the CMake Tools extension installed. The same options as explained above for Linux/macOS can be used and build artifacts are generated in the specified build folders.

If you want to create Visual Studio build files, e.g., if not using ninja, be sure to not pass the parameter -GNinja to the cmake command as exemplified above. You can then build all components using msbuild, e.g. as follows: msbuild ALL_BUILD.vcxproj and install all artifacts e.g. using this command msbuild INSTALL.vcxproj.

Web Assembly WASM

Install emsdk https://www.tutorialspoint.com/webassembly/webassembly_installation.htm
Goto directory of emsdk and run: emsdk_env.bat
Create build folder. For example: c:\github\hybrid-pqc\wasm\build

Run the following command, replacing appropriate paths:

 emcc -s WASM=1 -s EXPORTED_FUNCTIONS="['_free', '_malloc']"  -s "EXPORTED_RUNTIME_METHODS=['getValue','writeArrayToMemory']" C:/github/hybrid-pqc/wasm/hybrid-pqc.c C:/github/hybrid-pqc/random/randombytes.c C:/github/hybrid-pqc/falcon512/codec.c C:/github/hybrid-pqc/falcon512/common.c C:/github/hybrid-pqc/falcon512/fft.c C:/github/hybrid-pqc/falcon512/fpr.c C:/github/hybrid-pqc/falcon512/keygen.c C:/github/hybrid-pqc/falcon512/nist.c C:/github/hybrid-pqc/falcon512/rng.c C:/github/hybrid-pqc/falcon512/shake.c C:/github/hybrid-pqc/falcon512/sign.c C:/github/hybrid-pqc/falcon512/vrfy.c C:/github/hybrid-pqc/tweetnacl/tweetnacl.c C:/github/hybrid-pqc/hybrid/hybrid.c -o C:/github/hybrid-pqc/wasm/build/hybrid-pqc.html

Contributing

Thank you for considering to help out with the source code!

Please reach out in our Discord Server for any questions.
Pull requests need to be based on and opened against the main branch.

License

This Falcon implementation is provided under the MIT license, whose text is included at the start of every source file. Random bytes and Hybrid also have their own license files (MIT License).

PavanAnanthSharma/hybrid