Preparing for a Quantum-Resistant Era

Poster (2023, June 30)

Highly Vectorized SIKE for AVX-512

in IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) (2022, February), 2022(2), 41-68

It is generally accepted that a large-scale quantum computer would be capable to break any public-key cryptosystem used today, thereby posing a serious threat to the security of the Internet’s public-key ... [more ▼]

It is generally accepted that a large-scale quantum computer would be capable to break any public-key cryptosystem used today, thereby posing a serious threat to the security of the Internet’s public-key infrastructure. The US National Institute of Standards and Technology (NIST) addresses this threat with an open process for the standardization of quantum-safe key establishment and signature schemes, which is now in the final phase of the evaluation of candidates. SIKE (an abbreviation of Supersingular Isogeny Key Encapsulation) is one of the alternate candidates under evaluation and distinguishes itself from other candidates due to relatively short key lengths and relatively high computing costs. In this paper, we analyze how the latest generation of Intel’s Advanced Vector Extensions (AVX), in particular AVX-512IFMA, can be used to minimize the latency (resp. maximize the throughput) of the SIKE key encapsulation mechanism when executed on Ice LakeCPUs based on the Sunny Cove microarchitecture. We present various techniques to parallelize and speed up the base/extension field arithmetic, point arithmetic, and isogeny computations performed by SIKE. All these parallel processing techniques are combined in AVXSIKE, a highly optimized implementation of SIKE using Intel AVX-512IFMA instructions. Our experiments indicate that AVXSIKE instantiated with the SIKEp503 parameter set is approximately 1.5 times faster than the to-date best AVX-512IFMA-based SIKE software from the literature. When executed on an Intel Core i3-1005G1 CPU, AVXSIKE outperforms the x64 assembly implementation of SIKE contained in Microsoft’s SIDHv3.4 library by a factor of about 2.5 for key generation and decapsulation, while the encapsulation is even 3.2 times faster. [less ▲]

"Just for the sake of transparency": Exploring Voter Mental Models Of Verifiability

in Electronic Voting, Sixth International Joint Conference, E-Vote-ID 2021, Bregenz, Austria, October 5-8 (2021, October)

Verifiable voting schemes allow voters to verify their individual votes and the election outcome. The voting protocol Selene offers verification of plaintext votes while preserving privacy. Misconceptions ... [more ▼]

Verifiable voting schemes allow voters to verify their individual votes and the election outcome. The voting protocol Selene offers verification of plaintext votes while preserving privacy. Misconceptions of verification mechanisms might result in voters mistrust of the system or abstaining from using it. In this paper, we interviewed 24 participants and invited them to illustrate their mental models of Selene. The drawings demonstrated different levels of sophistication and four mental models: 1) technology understanding, 2) meaning of the verification phase, 3) security concerns, and 4) unnecessary steps. We highlight the misconceptions expressed regarding Internet voting technologies and the system design. Based on our findings, we conclude with recommendations for future implementations of Selene as well as for the design of Internet voting systems in general. [less ▲]

Batching CSIDH Group Actions using AVX-512

in IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) (2021, August), 2021(4), 618-649

Commutative Supersingular Isogeny Diffie-Hellman (or CSIDH for short) is a recently-proposed post-quantum key establishment scheme that belongs to the family of isogeny-based cryptosystems. The CSIDH ... [more ▼]

Commutative Supersingular Isogeny Diffie-Hellman (or CSIDH for short) is a recently-proposed post-quantum key establishment scheme that belongs to the family of isogeny-based cryptosystems. The CSIDH protocol is based on the action of an ideal class group on a set of supersingular elliptic curves and comes with some very attractive features, e.g. the ability to serve as a “drop-in” replacement for the standard elliptic curve Diffie-Hellman protocol. Unfortunately, the execution time of CSIDH is prohibitively high for many real-world applications, mainly due to the enormous computational cost of the underlying group action. Consequently, there is a strong demand for optimizations that increase the efficiency of the class group action evaluation, which is not only important for CSIDH, but also for related cryptosystems like the signature schemes CSI-FiSh and SeaSign. In this paper, we explore how the AVX-512 vector extensions (incl. AVX-512F and AVX-512IFMA) can be utilized to optimize constant-time evaluation of the CSIDH-512 class group action with the goal of, respectively, maximizing throughput and minimizing latency. We introduce different approaches for batching group actions and computing them in SIMD fashion on modern Intel processors. In particular, we present a hybrid batching technique that, when combined with optimized (8 × 1)-way prime-field arithmetic, increases the throughput by a factor of 3.64 compared to a state-of-the-art (non-vectorized) x64 implementation. On the other hand, vectorization in a 2-way fashion aimed to reduce latency makes our AVX-512 implementation of the group action evaluation about 1.54 times faster than the state-of-the-art. To the best of our knowledge, this paper is the first to demonstrate the high potential of using vector instructions to increase the throughput (resp. decrease the latency) of constant-time CSIDH. [less ▲]

A Survey of Requirements for COVID-19 Mitigation Strategies

in Bulletin of The Polish Academy of Sciences: Technical Science (2021), 69(4), 137724

Lightweight Post-quantum Key Encapsulation for 8-bit AVR Microcontrollers

in Liardet, Pierre-Yvan; Mentens, Nele (Eds.) Smart Card Research and Advanced Applications, 19th International Conference, CARDIS 2020, Virtual Event, November 18–19, 2020, Revised Selected Papers (2020, November)

Recent progress in quantum computing has increased interest in the question of how well the existing proposals for post-quantum cryptosystems are suited to replace RSA and ECC. While some aspects of this ... [more ▼]

Recent progress in quantum computing has increased interest in the question of how well the existing proposals for post-quantum cryptosystems are suited to replace RSA and ECC. While some aspects of this question have already been researched in detail (e.g. the relative computational cost of pre- and post-quantum algorithms), very little is known about the RAM footprint of the proposals and what execution time they can reach when low memory consumption rather than speed is the main optimization goal. This question is particularly important in the context of the Internet of Things (IoT) since many IoT devices are extremely constrained and possess only a few kB of RAM. We aim to contribute to answering this question by exploring the software design space of the lattice-based key-encapsulation scheme ThreeBears on an 8-bit AVR microcontroller. More concretely, we provide new techniques for the optimization of the ring arithmetic of ThreeBears (which is, in essence, a 3120-bit modular multiplication) to achieve either high speed or low RAM footprint, and we analyze in detail the trade-offs between these two metrics. A low-memory implementation of BabyBear that is secure against Chosen Plaintext Attacks (CPA) needs just about 1.7 kB RAM, which is significantly below the RAM footprint of other lattice-based cryptosystems reported in the literature. Yet, the encapsulation time of this RAM-optimized BabyBear version is below 12.5 million cycles, which is less than the execution time of scalar multiplication on Curve25519. The decapsulation is more than four times faster and takes roughly 3.4 million cycles on an ATmega1284 microcontroller. [less ▲]

Short paper: Mechanized Proofs of Verifiability and Privacy in a paper-based e-voting Scheme

in International Conference on Financial Crypto Workshop on Advances in Secure Electronic Voting (2020, February)

A Survey of Requirements for COVID-19 Mitigation Strategies. Part I: Newspaper Clips

E-print/Working paper (2020)

Towards Model Checking of Voting Protocols in Uppaal

in Proceedings of the Fifth International Joint Conference on Electronic Voting E-VOTE-ID 2020 (2020)

The design and implementation of a trustworthy e-voting system is a challenging task. Formal analysis can be of great help here. In particular, it can lead to a better understanding of how the voting ... [more ▼]

The design and implementation of a trustworthy e-voting system is a challenging task. Formal analysis can be of great help here. In particular, it can lead to a better understanding of how the voting system works, and what requirements on the system are relevant. In this paper, we propose that the state-of-art model checker Uppaal provides a good environment for modelling and preliminary verification of voting protocols. To illustrate this, we demonstrate how to model a version of Pret-a-Voter in Uppaal, together with some natural extensions. We also show how to verify a variant of receipt-freeness, despite the severe limitations of the property specification language in the model checker. The aim of this work is to open a new path, rather then deliver the ultimate outcome of formal analysis. A comprehensive model of Pret-a-Voter, more accurate specification of requirements, and exhaustive verification are planned for the future. [less ▲]

Post-Quantum Anonymous Veto Networks

in E-Vote-ID 2020 (2020)