International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Victor Shoup

Publications

Year
Venue
Title
2021
JOFC
Bootstrapping for HElib
Shai Halevi Victor Shoup
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
Security analysis of SPAKE2+ 📺
Victor Shoup
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
Faster Homomorphic Linear Transformations in HElib 📺
Shai Halevi Victor Shoup
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
Algorithms in HElib 📺
Shai Halevi Victor Shoup
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
OAEP Reconsidered
Victor Shoup
2002
JOFC
2001
CRYPTO
2001
CRYPTO
OAEP Reconsidered
Victor Shoup
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