Practical Advances in Modern Cryptographic Primitives

Abstract

Modern cryptographic primitives have evolved from supporting basic to more advanced functionalities, and such schemes are now getting more practical. In this thesis, we identify and rectify some limitations of such cryptographic constructions and their proofs of security. Specifically, we work with functional encryption, secure aggregation, and threshold signature schemes, and observe key functional or security limitations in prior work. Our first focus is functional encryption (FE), which enables function evaluation on encrypted messages using a functional secret key. A different primitive named function-revealing encryption (FRE) allows one to compute a fixed function of the underlying messages using their ciphertexts only. We give formal definitions and construct an inner-product FRE scheme. We also analyze the relationship between FE and FRE. Our second contribution considers secure aggregation, a classic problem that has numerous applications in privacy preserving machine learning. Secure aggregation lets many clients contribute data for aggregation without revealing their individual data. Existing practical protocols either have multiple rounds of interaction between clients and the server or rely on heavyweight cryptographic primitives. We build a non-interactive secure aggregation protocol using a novel combination of inner-product FE and a fully-linear probabilistically checkable proof (FLPCP) system. For this protocol, we use an existing FLPCP system [BBCGI’19] that we prove satisfies soundness and zero-knowledge properties even when reused for multiple proof instances. Finally, we address a pressing open question: achieving fully adaptive security for the Sparkle+ [CKM’23] threshold signature scheme. Threshold schemes require t signers to provide partial signatures to form a valid one. Fully adaptive security prevents adversaries from forging signatures even when corrupting up to t-1 signers. While Sparkle+ is secure against static corruption and a limited number of adaptive corruptions, a previous proof of fully adaptive security was shown to be incorrect. We propose a novel hardness assumption under which Sparkle+ satisfies this notion with a tight reduction. We establish hardness of this assumption in the elliptic-curve generic-group model. Our contributions close important gaps in prior work and push advanced cryptographic primitives closer to practice.