## CryptoDB

### Mike Hamburg

#### Publications

**Year**

**Venue**

**Title**

2021

TCHES

Chosen Ciphertext k-Trace Attacks on Masked CCA2 Secure Kyber
📺
Abstract

Single-trace attacks are a considerable threat to implementations of classic public-key schemes, and their implications on newer lattice-based schemes are still not well understood. Two recent works have presented successful single-trace attacks targeting the Number Theoretic Transform (NTT), which is at the heart of many lattice-based schemes. However, these attacks either require a quite powerful side-channel adversary or are restricted to specific scenarios such as the encryption of ephemeral secrets. It is still an open question if such attacks can be performed by simpler adversaries while targeting more common public-key scenarios. In this paper, we answer this question positively. First, we present a method for crafting ring/module-LWE ciphertexts that result in sparse polynomials at the input of inverse NTT computations, independent of the used private key. We then demonstrate how this sparseness can be incorporated into a side-channel attack, thereby significantly improving noise resistance of the attack compared to previous works. The effectiveness of our attack is shown on the use-case of CCA2 secure Kyber k-module-LWE, where k ∈ {2, 3, 4}. Our k-trace attack on the long-term secret can handle noise up to a σ ≤ 1.2 in the noisy Hamming weight leakage model, also for masked implementations. A 2k-trace variant for Kyber1024 even allows noise σ ≤ 2.2 also in the masked case, with more traces allowing us to recover keys up to σ ≤ 2.7. Single-trace attack variants have a noise tolerance depending on the Kyber parameter set, ranging from σ ≤ 0.5 to σ ≤ 0.7. As a comparison, similar previous attacks in the masked setting were only successful with σ ≤ 0.5.

2020

TCHES

Faster Montgomery and double-add ladders for short Weierstrass curves
📺
Abstract

The Montgomery ladder and Joye ladder are well-known algorithms for elliptic curve scalar multiplication with a regular structure. The Montgomery ladder is best known for its implementation on Montgomery curves, which requires 5M+4S+1m+8A per scalar bit, and 6 field registers. Here (M, S,m,A) represent respectively field Multiplications, Squarings, multiplications by a curve constant, and Additions or subtractions. This ladder is also complete, meaning that it works on all input points and all scalars. Many protocols do not use Montgomery curves, but instead use prime-order curves in short Weierstrass form. These have historically been much slower, with ladders costing at least 14 multiplications or squarings per bit: 8M + 6S + 27A for the Montgomery ladder and 8M+ 6S + 30A for the Joye ladder. In 2017, Kim et al. improved the Montgomery ladder to 8M+ 4S + 12A + 1H per bit using 9 registers, where the H represents a halving. Hamburg simplified Kim et al.’s formulas to 8M+ 4S + 8A + 1H per bit using 6 registers. Here we present improved formulas which compute the Montgomery ladder on short Weierstrass curves using 8M+ 3S + 7A per bit, and requiring 6 registers. We also give formulas for the Joye ladder that use 9M+3S+7A per bit, requiring 5 registers. One of our new formulas supports very efficient 4-way vectorization. We also discuss curve invariants, exceptional points, side-channel protection and how to set up and finish these ladder operations. Finally, we show a novel technique to make these ladders complete when the curve order is not divisible by 2 or 3, at a modest increase in cost. A sample implementation of these techniques is given in the supplementary material, also posted at https://github.com/bitwiseshiftleft/ladder_formulas

2019

CRYPTO

Quantum Security Proofs Using Semi-classical Oracles
📺
Abstract

We present an improved version of the one-way to hiding (O2H) Theorem by Unruh, J ACM 2015. Our new O2H Theorem gives higher flexibility (arbitrary joint distributions of oracles and inputs, multiple reprogrammed points) as well as tighter bounds (removing square-root factors, taking parallelism into account). The improved O2H Theorem makes use of a new variant of quantum oracles, semi-classical oracles, where queries are partially measured. The new O2H Theorem allows us to get better security bounds in several public-key encryption schemes.

2019

TCC

Tighter Proofs of CCA Security in the Quantum Random Oracle Model
Abstract

We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE). We give new, tighter security reductions for several constructions. Our main result is an improved reduction for the security of the
$$U^{\not \bot }$$
-transform of Hofheinz, Hövelmanns, and Kiltz (TCC’17) which turns OW-CPA secure deterministic PKEs into IND-CCA secure KEMs. This result is enabled by a new one-way to hiding (O2H) lemma which gives a tighter bound than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability and non-deterministic PKEs. However, we assume that the derandomized PKE is injective with overwhelming probability.In addition, we analyze the impact of different variations of the
$$U^{\not \bot }$$
-transform discussed in the literature on the security of the final scheme. We consider the difference between explicit (
$$U^{\bot }$$
) and implicit (
$$U^{\not \bot }$$
) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (
$$U^{\not \bot }$$
) or just from the message (
$$U^{\not \bot }_m$$
).

2017

CHES

A Side-Channel Assisted Cryptanalytic Attack Against QcBits
Abstract

QcBits is a code-based public key algorithm based on a problem thought to be resistant to quantum computer attacks. It is a constant-time implementation for a quasi-cyclic moderate density parity check (QC-MDPC) Niederreiter encryption scheme, and has excellent performance and small key sizes. In this paper, we present a key recovery attack against QcBits. We first used differential power analysis (DPA) against the syndrome computation of the decoding algorithm to recover partial information about one half of the private key. We then used the recovered information to set up a system of noisy binary linear equations. Solving this system of equations gave us the entire key. Finally, we propose a simple but effective countermeasure against the power analysis used during the syndrome calculation.

2007

EPRINT

Space-Efficient Identity Based Encryption Without Pairings
Abstract

Identity Based Encryption (IBE) systems are often constructed
using bilinear maps (a.k.a. pairings) on elliptic curves. One
exception is an elegant system due to Cocks which builds an IBE
based on the quadratic residuosity problem modulo an RSA composite
N. The Cocks system, however, produces long ciphertexts. Since
the introduction of the Cocks system in 2001 it has been an open
problem to construct a space efficient IBE system without
pairings. In this paper we present an IBE system in which
ciphertext size is short: an encryption of an L-bit message
consists of a single element in Z_N plus L+1 additional
bits. Security, as in the Cocks system, relies on the quadratic
residuosity problem. The system is based on the theory of ternary
quadratic forms and as a result, encryption and decryption are
slower than in the Cocks system.

#### Program Committees

- CHES 2018

#### Coauthors

- Andris Ambainis (1)
- Nina Bindel (1)
- Dan Boneh (3)
- Craig Gentry (1)
- Shai Halevi (1)
- Julius Hermelink (1)
- Kathrin Hövelmanns (1)
- Andreas Hülsing (1)
- Michael Hutter (1)
- Mark E. Marson (1)
- Rafail Ostrovsky (1)
- Edoardo Persichetti (1)
- Robert Primas (1)
- Mélissa Rossi (1)
- Simona Samardjiska (1)
- Thomas Schamberger (1)
- Silvan Streit (1)
- Emanuele Strieder (1)
- Dominique Unruh (1)
- Christine van Vredendaal (1)