International Association
for Cryptologic Research

<p>In LWE based cryptosystems, using small (polynomially large) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs simulation security: the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Renyi divergence based analyses that are sufficient for game-based but not simulation security.</p><p>In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially large modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used. </p>

Amortized bootstrapping offers a way to simultaneously refresh many ciphertexts of a fully homomorphic encryption scheme, at a total cost comparable to that of refreshing a single ciphertext. An amortization method for FHEW-style cryptosystems was first proposed by (Micciancio and Sorrell, ICALP 2018), who showed that the amortized cost of bootstrapping $n$ FHEW-style ciphertexts can be reduced from $\tilde O(n)$ basic cryptographic operations to just $\tilde O(n^{\epsilon})$, for any constant $\epsilon>0$. However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the asymptotic notation. In this work, we propose an alternative amortized boostrapping method with much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost, but with a hidden constant that is only linear in $1/\epsilon$, and with reduced noise growth. This is achieved following the general strategy of (Micciancio and Sorrell), but replacing their use of the Nussbaumer transform, with a much more practical Number Theoretic Transform, with multiplication by twiddle factors implemented using ring automorphisms. A key technical ingredient to do this is a new ``scheme switching'' technique proposed in this paper which may be of independent interest.

In this paper, we study both the implications and potential impact of backdoored parameters for two RSA-based pseudorandom number generators: the ISO-standardized Micali-Schnorr generator and a closely related design, the RSA PRG. We observe, contrary to common understanding, that the security of the Micali-Schnorr PRG is not tightly bound to the difficulty of inverting RSA. We show that the Micali-Schnorr construction remains secure even if one replaces RSA with a publicly evaluatable PRG, or a function modeled as an efficiently invertible random permutation. This implies that any cryptographic backdoor must somehow exploit the algebraic structure of RSA, rather than an attacker’s ability to invert RSA or the presence of secret keys. We exhibit two such backdoors in related constructions: a family of exploitable parameters for the RSA PRG, and a second vulnerable construction for a finite-field variant of Micali-Schnorr. We also observe that the parameters allowed by the ISO standard are incompletely specified, and allow insecure choices of exponent. Several of our backdoor constructions make use of lattice techniques, in particular multivariate versions of Coppersmith’s method for finding small solutions to polynomials modulo integers.

Dual EC DRBG is widely believed to have been backdoored by the U.S. National Security Agency. But there was another number theoretic PRG proposed alongside Dual EC that has seen surprisingly little attention: the Micali-Schnorr generator, standardized as MS DRBG, which is based on the hardness of RSA. It appears in early drafts of the ANSI X9.82 standard (but was eventually removed in favor of Dual EC) and the final version of ISO 18031 (alongside Dual EC). The MS DRBG standard follows a pattern eerily reminiscent of Dual EC: it incorporates a series of recommended public parameters that are intended to be used in production as the RSA modulus N. Given the known vulnerabilities in Dual EC and the identical provenance, it is reasonable to ask whether MS DRBG is vulnerable to an analogous attack: Does knowledge of the factors of (or malicious construction of) the recommended moduli imply a practical attack on the MS DRBG generator? Surprisingly, this question is not easy to answer. The security proofs of course do not go through if the factors are known, but all obvious attack strategies fail. In this talk, we give historical background on MS DRBG and describe progress toward finding the backdoor (or proving it doesn't exist). We show that any backdoor must somehow exploit the algebraic structure of RSA, rather than just the attacker's ability to invert the RSA operation. We exhibit two such backdoors in related constructions. Ultimately we were unsuccessful in fully finding a plausible backdoor in MS DRBG (or proving one doesn't exist), but we hope this talk will bring more attention to this interesting open problem with potential real-world impact.