PhD Thesis Defense: Ojaswi Acharya, Practical Advances in Modern Cryptographic Primitives
Content
Speaker:
Abstract:
Modern cryptographic primitives have evolved from supporting basic functionalities 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 existing prior work.
Our first focus is functional encryption (FE), which enables the evaluation of a function on encrypted messages using a functional secret key. This primitive, however, does not allow evaluating a specific function directly on ciphertexts without any secret key. Here, a different primitive, named function-revealing encryption (FRE), is desired, which allows one to compute a fixed function of the underlying messages using their ciphertexts only. Applications such as machine learning and information retrieval require pairwise inner products of encrypted data vectors. We construct an inner-product FRE scheme and prove its security in the generic bilinear group model. We also construct an inner-product FE scheme that is more efficient than prior such schemes, and 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 and analytics. 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 like fully homomorphic encryption. 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 signature schemes require a threshold \emph{t} number of signers to provide partial signatures on the same message to form a valid signature. Fully adaptive security means an adversary cannot produce a new valid signature even when it may corrupt up to t-1 signers and observe other valid signatures. While Sparkle+ has been proven secure for static corruption and a limited adaptively chosen set of corrupt signers, a previous proof of fully adaptive security has been shown incorrect. We propose a novel hardness assumption under which Sparkle+ satisfies this security notion and even has a tight reduction. We establish the 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.
Advisor:
Adam O'Neill