CryptoDB
Tung Chou
Affiliation: Technische Universiteit Eindhoven
Publications
Year
Venue
Title
2017
CHES
McBits Revisited
Abstract
This paper presents a constant-time fast implementation for a high-security code-based encryption system. The implementation is based on the “McBits” paper by Bernstein, Chou, and Schwabe in 2013: we use the same FFT algorithms for root finding and syndrome computation, similar algorithms for secret permutation, and bitslicing for low-level operations. As opposed to McBits, where a high decryption throughput is achieved by running many decryption operations in parallel, we take a different approach to exploit the internal parallelism in one decryption operation for the use of more applications. As the result, we manage to achieve a slightly better decryption throughput at a much higher security level than McBits. As a minor contribution, we also present a constant-time implementation for encryption and key-pair generation, with similar techniques used for decryption.
2010
EPRINT
Fast Exhaustive Search for Polynomial Systems in $F_2$
Abstract
We analyze how fast we can solve general systems of multivariate
equations of various low degrees over \GF{2}; this is
a well known hard problem which is important both in itself and
as part of many types of algebraic cryptanalysis. Compared to the standard
exhaustive-search technique, our improved approach is more
efficient both asymptotically and practically.
We implemented several optimized versions of our techniques on CPUs and GPUs. Modern graphic cards allows our technique to run more than 10 times faster than the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a NVIDIA GTX 295 video card (USD 500) in 21 minutes.
With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the power of GPUs in solving many types of combinatorial and cryptanalytic problems.
Program Committees
- CHES 2020
- CHES 2017
- PKC 2016
Coauthors
- Daniel J. Bernstein (3)
- Charles Bouillaguet (2)
- Hsieh-Chung Chen (1)
- Chen-Mou Cheng (3)
- Chitchanok Chuengsatiansup (1)
- Andreas Hülsing (1)
- Tanja Lange (1)
- Ruben Niederhagen (4)
- Claudio Orlandi (1)
- Peter Schwabe (2)
- Adi Shamir (2)
- Christine van Vredendaal (1)
- Bo-Yin Yang (3)