SIDH Library is a fast and portable software library that implements state-of-the-art supersingular isogeny cryptographic schemes. The chosen parameters aim to provide security against attackers running a large-scale quantum computer, and security against classical algorithms.
Switch branches/tags
Nothing to show
Clone or download
Latest commit 77044b7 Jul 24, 2018
Permalink
Failed to load latest commit information.
KAT Add files via upload Dec 8, 2017
Visual Studio Add files via upload Dec 8, 2017
src Update fp_x64_asm.S Jul 24, 2018
tests Update arith_tests-p751.c Jul 24, 2018
.gitignore Initial commit Apr 17, 2017
CONTRIBUTING.md Create CONTRIBUTING.md Apr 18, 2017
LICENSE Initial commit Apr 17, 2017
Makefile Update Makefile Jul 24, 2018
README.md Update README.md Jul 24, 2018

README.md

SIDH v3.0 (C Edition)

The SIDH library is an efficient supersingular isogeny-based cryptography library written in C language. Version v3.0 of the library includes the ephemeral Diffie-Hellman key exchange scheme "SIDH" [1,2], and the CCA-secure key encapsulation mechanism "SIKE" [4]. These schemes are conjectured to be secure against quantum computer attacks.

Concretely, the SIDH library includes the following KEM schemes:

  • SIKEp503: matching the post-quantum security of AES128.
  • SIKEp751: matching the post-quantum security of AES192.

And the following ephemeral key exchange schemes:

  • SIDHp503: matching the post-quantum security of AES128.
  • SIDHp751: matching the post-quantum security of AES192.

The library was developed by Microsoft Research for experimentation purposes.

Contents

Main Features

  • Supports IND-CCA secure key encapsulation mechanism.
  • Supports ephemeral Diffie-Hellman key exchange.
  • Supports two security levels matching the post-quantum security of AES128 and AES192.
  • Supports a peace-of-mind hybrid key exchange mode that adds a classical elliptic curve Diffie-Hellman key exchange on a high-security Montgomery curve providing 384 bits of classical ECDH security.
  • Protected against timing and cache-timing attacks through regular, constant-time implementation of all operations on secret key material.
  • Support for Windows OS using Microsoft Visual Studio and Linux OS using GNU GCC and clang.
  • Provides basic implementation of the underlying arithmetic functions using portable C to enable support on a wide range of platforms including x64, x86 and ARM .
  • Provides optimized implementations of the underlying arithmetic functions for x64 platforms with optional, high-performance x64 assembly for Linux.
  • Provides an optimized implementation of the underlying arithmetic functions for 64-bit ARM platforms using assembly for Linux.
  • Includes Known Answer Tests (KATs), and testing/benchmarking code.

New in Version 3.0

  • Added support for SIKE [4], an IND-CCA secure key encapsulation protocol based on supersingular isogenies.
  • Added a new parameter set over the prime p503 that matches the post-quantum security of AES128.
  • The implementations are significantly more compact and faster. Among other optimizations, the library exploits a new tripling formula from [5] and the fast three-point ladder algorithm from [6].
  • Removed the code implementing public key compression [3]. The old compression code can be accessed here. Note that a faster compression implementation [7] is available in a fork of SIDH. In this case, public keys are reduced from 564 to 330 bytes, but the computing time suffers almost a two-fold slowdown.
  • Added Known Answer Tests (KATs).

Supported Platforms

SIDH v3.0 is supported on a wide range of platforms including x64, x86 and ARM devices running Windows or Linux OS. We have tested the library with Microsoft Visual Studio 2015, GNU GCC v5.4, and clang v3.8. See instructions below to choose an implementation option and compile on one of the supported platforms.

Implementation Options

The following implementation options are available:

  • Portable implementations enabled by setting OPT_LEVEL=GENERIC.
  • Optimized x64 assembly implementations for Linux enabled by setting ARCH=x64 and OPT_LEVEL=FAST.
  • Optimized ARMv8 assembly implementation for Linux enabled by setting ARCH=ARM64 and OPT_LEVEL=FAST.

Follow the instructions in the sections "Instructions for Linux" or "Instructions for Windows" below to configure these different implementation options.

Instructions for Linux

By simply executing:

$ make

the library is compiled for x64 using clang, optimization level FAST, and using the special instructions MULX and ADX. Optimization level FAST enables the use of assembly, which in turn is a requirement to enable the optimizations using MULX/ADX.

Other options for x64:

$ make ARCH=x64 CC=[gcc/clang] OPT_LEVEL=[FAST/GENERIC] USE_MULX=[TRUE/FALSE] USE_ADX=[TRUE/FALSE] SET=[EXTENDED]

Setting SET=EXTENDED adds the flags -fwrapv -fomit-frame-pointer -march=native. When OPT_LEVEL=FAST (i.e., assembly use enabled), the user is responsible for setting the flags MULX and ADX according to the targeted platform (for example, MULX/ADX are not supported on Sandy or Ivy Bridge, only MULX is supported on Haswell, and both MULX and ADX are supported on Broadwell, Skylake and Kaby Lake architectures). Note that USE_ADX can only be set to TRUE if USE_MULX=TRUE.

Options for x86/ARM:

$ make ARCH=[x86/ARM] CC=[gcc/clang] SET=[EXTENDED]

Options for ARM64:

$ make ARCH=[ARM64] CC=[gcc/clang] OPT_LEVEL=[FAST/GENERIC] SET=[EXTENDED]

As in the x64 case, OPT_LEVEL=FAST enables the use of assembly optimizations on ARMv8 platforms.

Different tests and benchmarking results are obtained by running:

$ ./arith_tests-p503
$ ./arith_tests-p751
$ ./sike503/test_SIKE
$ ./sike751/test_SIKE
$ ./sidh503/test_SIDH
$ ./sidh751/test_SIDH

To run the KEM implementations against the KATs, execute:

$ ./sike503/PQCtestKAT_kem
$ ./sike751/PQCtestKAT_kem

The program tries its best at auto-correcting unsupported configurations. For example, since the FAST implementation is currently only available for x64 and ARMv8 doing make ARCH=x86 OPT_LEVEL=FAST is actually processed using ARCH=x86 OPT_LEVEL=GENERIC.

Instructions for Windows

Building the library with Visual Studio:

Open the solution file SIDH.sln in Visual Studio, choose either x64 or Win32 from the platform menu and then choose either Fast or Generic from the configuration menu (as explained above, the option Fast is not currently available for x86). Finally, select "Build Solution" from the "Build" menu.

Running the tests:

After building the solution file, there should be 6 executable files: arith_tests-P503.exe and arith_tests-P751.exe, to run tests for the underlying arithmetic, test-SIDHp503.exe and test-SIDHp751.exe, to run tests for the key exchange, and test-SIKEp503.exe and test-SIKEp751.exe, to run tests for the KEM.

Using the library:

After building the solution file, add the generated P503.lib and P751.lib library files to the set of References for a project, and add P503_api.h and P751_api.h to the list of header files of a project.

License

SIDH is licensed under the MIT License; see License for details.

The library includes some third party modules that are licensed differently. In particular:

  • tests/aes/aes_c.c: public domain
  • tests/rng/rng.c: copyrighted by Lawrence E. Bassham
  • tests/PQCtestKAT_kem<#>.c: copyrighted by Lawrence E. Bassham
  • src/sha3/fips202.c: public domain

Contributors

The field arithmetic implementation over p751 for 64-bit ARM processors (ARM64 folder) was contributed and is copyrighted by David Urbanik (dburbani@uwaterloo.ca).

Other contributors include:

  • Joost Renes, while he was an intern with Microsoft Research.

References

[1] Craig Costello, Patrick Longa, and Michael Naehrig, "Efficient algorithms for supersingular isogeny Diffie-Hellman". Advances in Cryptology - CRYPTO 2016, LNCS 9814, pp. 572-601, 2016. The extended version is available here.

[2] David Jao and Luca DeFeo, "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". PQCrypto 2011, LNCS 7071, pp. 19-34, 2011.

[3] Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik, "Efficient compression of SIDH public keys". Advances in Cryptology - EUROCRYPT 2017, LNCS 10210, pp. 679-706, 2017. The preprint version is available here.

[4] Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, David Jao, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Joost Renes, Vladimir Soukharev, and David Urbanik, "Supersingular Isogeny Key Encapsulation". Submission to the NIST Post-Quantum Standardization project, 2017.
The submission package is available here.

[5] Craig Costello, and Huseyin Hisil, "A simple and compact algorithm for SIDH with arbitrary degree isogenies". Advances in Cryptology - ASIACRYPT 2017, LNCS 10625, pp. 303-329, 2017. The preprint version is available here.

[6] Armando Faz-Hernández, Julio López, Eduardo Ochoa-Jiménez, and Francisco Rodríguez-Henríquez, "A faster software implementation of the supersingular isogeny Diffie-Hellman key exchange protocol". IEEE Transactions on Computers (to appear). The preprint version is available here.

[7] Gustavo H. M. Zanon, Marcos A. Simplicio Jr., Geovandro C. C. F. Pereira, Javad Doliskani, and Paulo S. L. M. Barreto, "Faster isogeny-based compressed key agreement". PQCrypto 2018, LCNS 10786, pp. 248-268, 2018. The preprint version is available here.

Contributing

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.