CryptoDB
Wei Dai
NOTE: imports for ToSC and TCHES are no longer functioning.
Publications
Year
Venue
Title
2021
TCHES
SEAL-Embedded: A Homomorphic Encryption Library for the Internet of Things
📺
Abstract
The growth of the Internet of Things (IoT) has led to concerns over the lack of security and privacy guarantees afforded by IoT systems. Homomorphic encryption (HE) is a promising privacy-preserving solution to allow devices to securely share data with a cloud backend; however, its high memory consumption and computational overhead have limited its use on resource-constrained embedded devices. To address this problem, we present SEAL-Embedded, the first HE library targeted for embedded devices, featuring the CKKS approximate homomorphic encryption scheme. SEAL-Embedded employs several computational and algorithmic optimizations along with a detailed memory re-use scheme to achieve memory efficient, high performance CKKS encoding and encryption on embedded devices without any sacrifice of security. We additionally provide an “adapter” server module to convert data encrypted by SEAL-Embedded to be compatible with the Microsoft SEAL library for homomorphic encryption, enabling an end-to-end solution for building privacy-preserving applications. For a polynomial ring degree of 4096, using RNS primes of 30 or fewer bits, our library can be configured to use between 64–137 KB of RAM and 1–264 KB of flash data, depending on developer-selected configurations and tradeoffs. Using these parameters, we evaluate SEAL-Embedded on two different IoT platforms with high performance, memory efficient, and balanced configurations of the library for asymmetric and symmetric encryption. With 136 KB of RAM, SEAL-Embedded can perform asymmetric encryption of 2048 single-precision numbers in 77 ms on the Azure Sphere Cortex-A7 and 737 ms on the Nordic nRF52840 Cortex-M4.
2021
ASIACRYPT
Chain Reductions for Multi-Signatures and the HBMS Scheme
📺
Abstract
Existing proofs for existing Discrete Log (DL) based multi-signature schemes give only weak guarantees if the schemes are implemented, as they are in practice, in 256-bit groups. This is because the underlying reductions, which are mostly in the standard model and from DL, are loose. We show that relaxing either the model or the assumption suffices to obtain tight reductions. Namely we give (1) tight proofs from DL in the Algebraic Group Model, and (2) tight, standard-model proofs from well-founded assumptions other than DL. We first do this for the classical 3-round schemes, namely $\BN$ and $\MuSig$. Then we give a new 2-round multi-signature scheme, $\MSB$, as efficient as prior ones, for which we do the same. These multiple paths to security for a single scheme are made possible by a framework of chain reductions, in which a reduction is broken into a chain of sub-reductions involving intermediate problems. Overall our results improve the security guarantees for DL-based multi-signature schemes in the groups in which they are implemented in practice.
2020
TCC
Super-Linear Time-Memory Trade-Offs for Symmetric Encryption
📺
Abstract
We build symmetric encryption schemes from a pseudorandom
function/permutation with domain size $N$ which have very high
security -- in terms of the amount of messages $q$ they can securely
encrypt -- assuming the adversary has $S < N$ bits of memory. We aim
to minimize the number of calls $k$ we make to the underlying
primitive to achieve a certain $q$, or equivalently, to maximize the
achievable $q$ for a given $k$. We target in
particular $q \gg N$, in contrast to recent works (Jaeger and
Tessaro, EUROCRYPT '19; Dinur, EUROCRYPT '20) which aim to beat the
birthday barrier with one call when $S < \sqrt{N}$.
Our first result gives new and explicit bounds for the
Sample-then-Extract paradigm by Tessaro and Thiruvengadam (TCC
'18). We show instantiations for which $q =\Omega((N/S)^{k})$.
If $S < N^{1- \alpha}$, Thiruvengadam and Tessaro's weaker bounds
only guarantee $q > N$ when $k = \Omega(\log N)$. In contrast, here,
we show this is true already for $k = O(1/\alpha)$.
We also consider a scheme by Bellare, Goldreich and Krawczyk (CRYPTO
'99) which evaluates the primitive at $k$ independent random
strings, and masks the message with the XOR of the outputs. Here, we
show $q= \Omega((N/S)^{k/2})$, using new combinatorial bounds
on the list-decodability of XOR codes which are of independent
interest. We also study best-possible attacks against this
construction.
2019
ASIACRYPT
The Local Forking Lemma and Its Application to Deterministic Encryption
Abstract
We bypass impossibility results for the deterministic encryption of public-key-dependent messages, showing that, in this setting, the classical Encrypt-with-Hash scheme provides message-recovery security, across a broad range of message distributions. The proof relies on a new variant of the forking lemma in which the random oracle is reprogrammed on just a single fork point rather than on all points past the fork.
Coauthors
- Mihir Bellare (2)
- Wei Dai (5)
- Viet Tung Hoang (1)
- Lucy Li (1)
- Deepika Natarajan (1)
- Stefano Tessaro (2)
- Xihu Zhang (1)