The Limits of Provable Efficiency in Cryptography

Abstract

In this work, we examine the science of proving formal security of primitives in cryptography through security reductions, with a focus on determining the achievability of various notions of efficiency. We work towards exploring the limits of provable efficiency through both feasibility and impossibility results, and summarize our findings in two distinct areas: 1. We first examine the notion of concrete security loss in reductions from the unforgeability of unique digital signature schemes and related primitives to standard cryptographic assumptions. Specifically, we show that such reductions are inherently inefficient in the level of concrete security they demonstrate for the primitive by ruling out a particular class of security-preserving reduction: linear-preserving reductions. Our first result proves the nonexistence of such reductions from unique digital signature schemes to any standard assumption with a polynomially bounded number of communication rounds, while our second result proves a similar impossibility for reductions from the adaptive multi-key security of message authentication codes or pseudorandom functions. Both results are proven via the meta-reduction paradigm, which has been applied to prove bounds on concrete security loss in the past, but all known meta-reductions in this space prior to our results have considerable technical limitations, usually only ruling out "simple" reductions that interact with their respective adversaries non-concurrently and reduce to a limited class of non-interactive assumptions. In contrast, our results present a novel rewinding technique and a "randomness-switching" lemma that allow for the first concrete security bounds via meta-reductions that are not subject to these limitations. 2. We also prove two positive results in the area of non-interactive secure two-party computation (NISC), both of which improve on the efficiency of currently known constructions in different ways. The first result examines avenues of reducing the communication complexity of NISC protocols: we construct a NISC protocol which satisfies security with superpolynomial-time simulation (SPS) and also a notion of succinctness--where the communication complexity and receiver's running time are close to independent from the functionality f--and does so by leveraging a non-succinct NISC, an adaptive delegation scheme, and fully homomorphic encryption, all of which can be based on subexponential LWE. The second result constructs the first NISC protocol satisfying a concurrent and composable notion of "angel-based" universally composable (UC) security, demonstrating that we can achieve the optimal possible round complexity for such a protocol. This construction is based on a stand-alone secure NISC and non-interactive CCA-secure commitments; while the latter notion is only known based on complex and non-standard assumptions, we additionally demonstrate as a matching negative result that these assumptions are also necessary for UC-secure NISC (subject to perfect correctness), thus expanding on our final positive result to provide a nearly-tight characterization of the necessary and sufficient assumptions for this definition of security.