## CryptoDB

### Victor Shoup

#### Publications

Year
Venue
Title
2022
EUROCRYPT
Two common variations of ECDSA signatures are {\em additive key derivation} and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed. In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient "online phase" of the protocol. Recent works have advocated for both of these variations, sometimes combined together. However, somewhat surprisingly, we are aware of no prior security proof for additive key derivation, let alone for additive key derivation in combination with presignatures. In this paper, we provide a thorough analysis of these variations, both in isolation and in combination. Our analysis is in the generic group model (GGM). Importantly, we do not modify ECDSA or weaken the standard notion of security in any way. Of independent interest, we also present a version of the GGM that is specific to elliptic curves. This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA. In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported. For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA. We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation. Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).
2021
JOFC
Gentry’s bootstrapping technique is still the only known method of obtaining fully homomorphic encryption where the system’s parameters do not depend on the complexity of the evaluated functions. Bootstrapping involves a recryption procedure where the scheme’s decryption algorithm is evaluated homomorphically. Prior to this work, there were very few implementations of recryption and fewer still that can handle “packed ciphertexts” that encrypt vectors of elements. In the current work, we report on an implementation of recryption of fully packed ciphertexts using the HElib library for somewhat homomorphic encryption. This implementation required extending previous recryption algorithms from the literature, as well as many aspects of the HElib library. Our implementation supports bootstrapping of packed ciphertexts over many extension fields/rings. One example that we tested involves ciphertexts that encrypt vectors of 1024 elements from ${\text {GF}}(2^{16})$ GF ( 2 16 ) . In that setting, the recryption procedure takes under 3 min (at security level $\approx 80$ ≈ 80 ) on a single core and allows a multiplicative depth-11 computation before the next recryption is needed. This report updates the results that we reported in Eurocrypt 2015 in several ways. Most importantly, it includes a much more robust method for deriving the parameters, ensuring that recryption errors only occur with negligible probability. Many aspects of this analysis are proved, and for the few well-specified heuristics that we made, we report on thorough experimentation to validate them. The procedure that we describe here is also significantly more efficient than in the previous version, incorporating many optimizations that were reported elsewhere (such as more efficient linear transformations) and adding a few new ones. Finally, our implementation now also incorporates Chen and Han’s techniques from Eurocrypt 2018 for more efficient digit extraction (for some parameters), as well as for “thin bootstrapping” when the ciphertext is only sparsely packed.
2020
TCC
We show that a slight variant of Protocol SPAKE2+, which was presented but not analyzed in [Cash, Kiltz, Shoup 2008], is a secure *asymmetric* password-authenticated key exchange protocol (PAKE), meaning that the protocol still provides good security guarantees even if a server is compromised and the password file stored on the server is leaked to an adversary. The analysis is done in the UC framework (i.e., a simulation-based security model), under the computational Diffie-Hellman (CDH) assumption, and modeling certain hash functions as random oracles. The main difference between our variant and the original Protocol SPAKE2+ is that our variant includes standard key confirmation flows; also, adding these flows allows some slight simplification to the remainder of the protocol. Along the way, we also (i) provide the first proof (under the same assumptions) that a slight variant of Protocol SPAKE2 from [Abdalla, Pointcheval 2005] is a secure *symmetric* PAKE in the UC framework (previous security proofs were all in the weaker BPR framework [Bellare, Pointcheval, Rogaway 2000]); (ii) provide a proof (under very similar assumptions) that a variant of Protocol SPAKE2+ that is currently being standardized is also a secure asymmetric PAKE; (iii) repair several problems in earlier UC formulations of secure symmetric and asymmetric PAKE.
2018
CRYPTO
HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of “packed” ciphertexts. An important operation is applying a known linear map to a vector of encrypted data. In this paper, we describe several algorithmic improvements that significantly speed up this operation: in our experiments, our new algorithms are 30–75 times faster than those previously implemented in HElib for typical parameters.One application that can benefit from faster linear transformations is bootstrapping (in particular, “thin bootstrapping” as described in [Chen and Han, Eurocrypt 2018]). In some settings, our new algorithms for linear transformations result in a $6{\times }$6× speedup for the entire thin bootstrapping operation.Our techniques also reduce the size of the large public evaluation key, often using 33%–50% less space than the previous HElib implementation. We also implemented a new tradeoff that enables a drastic reduction in size, resulting in a $25{\times }$25× factor or more for some parameters, paying only a penalty of a 2–$4{\times }$4× times slowdown in running time (and giving up some parallelization opportunities).
2015
JOFC
2015
EUROCRYPT
2014
CRYPTO
2011
ASIACRYPT
2010
PKC
2010
JOFC
2010
CRYPTO
2009
JOFC
2009
EUROCRYPT
2008
EUROCRYPT
2008
CRYPTO
2008
PKC
2005
EUROCRYPT
2005
JOFC
2004
EUROCRYPT
2004
CRYPTO
2003
CRYPTO
2002
CRYPTO
2002
EUROCRYPT
2002
JOFC
2002
JOFC
2001
CRYPTO
2001
CRYPTO
2000
EUROCRYPT
2000
EUROCRYPT
2000
EUROCRYPT
1999
JOFC
1998
CRYPTO
1998
EUROCRYPT
1998
EUROCRYPT
1997
EUROCRYPT
1996
CRYPTO
1996
EUROCRYPT
1996
EUROCRYPT
1990
CRYPTO

#### Program Committees

TCC 2010
PKC 2008
TCC 2007
Crypto 2005 (Program chair)
Crypto 2003
Crypto 2000
Eurocrypt 1999
CHES 1999