CppCon 2018: “Multi-Precision Arithmetic for Cryptology in C++, at Run-Time and at Compile-Time”

Niek J. Bouman “Multi-Precision Arithmetic for Cryptology in C++, at Run-Time and at Compile-Time”
—
—
In the talk, I will present a new C++17 library for multi-precision arithmetic for integers in the order of 100--500 bits. Many cryptographic schemes and applications, like elliptic-curve encryption schemes and secure multiparty computation frameworks require multiprecision arithmetic with integers whose bit-lengths lie in that range.

The library is written in “optimizing-compiler-friendly” C++, with an emphasis on the use of fixed-size arrays and particular function-argument-passing styles (including the avoidance of naked pointers) to allow the limbs to be allocated on the stack or even in registers. Depending on the particular functionality, we get close to, or significantly beat the performance of existing libraries for multiprecision arithmetic that employ hand-optimized assembly code.

Beyond the favorable runtime performance, our library is, to the best of the author’s knowledge, the first library that offers big-integer computations during compile-time. For example, when implementing finite-field arithmetic with a fixed modulus, this feature enables the automatic precomputation (at compile time) of the special modulus- dependent constants required for Barrett and Montgomery reduction. Another application is to parse (at compile-time) a base-10-encoded big-integer literal.

In this talk, I will focus on some Modern C++ language features that I've used to write the library and design its API (e.g., std::array, variadic templates, std::integer_sequence, constexpr, user-defined literals, using-declarations and decltype, and combinations thereof). Also, I will show some benchmarks, and will argue that the integer types offered by the library compose well with STL containers or other libraries (like Eigen for matrix/linear algebra operations).

I will also present some results on formal verification of correctness and the "constant-time" property:
- Correctness is verified using a tool named SAW (Software Analysis Workbench), which tries to prove equivalence between the compiled C++ code (represented as LLVM bitcode) and a behavioral specification given in a high-level functional language;
- "Constant-timeness" is a property that is crucial for implementations of cryptographic protocols to prevent timing attacks. In particular, I succeeded to verify my C++ code with "ct-verif", a tool for verifying the constant-time property for C programs (which was, in its original form, incompatible with C++ due to usage of non-ANSI C in one of its header files)

The library is on Github (Apache 2 licensed)
—
Niek J. Bouman, Eindhoven University of Technology
Researcher Secure Multiparty Computation

2017 - now Postdoc TU/e SODA (Scalable Oblivious Data Mining) project, Eindhoven University of Technology, the Netherlands 2016-2017 Senior Researcher Fraud Detection @ ABN AMRO Bank, Amsterdam, the Netherlands 2014-2016 Postdoc at Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland PhD (2012) Quantum Cryptography/Quantum Information Theory from CWI/Universiteit Leiden, the Netherlands BS'05 MS’07 Electrical Engineering from Universiteit Twente, Enschede, the Netherlands
—

*-----*
*-----*

[압둘하미드이드리스]

How did you calculate the computational overhead?