Graduate Thesis Or Dissertation
 

New constructions and applications for homomorphic secret sharing and function secret sharing

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/7p88cq86c

Descriptions

Attribute NameValues
Creator
Abstract
  • A secret sharing scheme allows a dealer to distribute a secret with a set of parties, such that only a certain subset of parties can collaborate and learn the shared secret. Traditional secret sharing schemes have been used as building blocks in various subdomains of cryptography. Recently, two new extensions were introduced - homomorphic secret sharing (HSS) and its dual function secret sharing (FSS), both of which have found a number of applications in cryptography. This thesis focuses on introducing extensions and generalizations of these original secret sharing schemes and exploring new cryptographic applications. Homomorphic secret sharing is analogous to fully homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. HSS was first introduced by Boyle, Gilboa, and Ishai (Crypto 2016), who give a construction based on the Decisional Diffie-Hellman assumption. Previous constructions of HSS either had nonnegligible correctness error and polynomial-size plaintext space or were based on the stronger Learning With Error assumption. In this thesis we present the first homomorphic secret sharing (HSS) construction that simultaneously overcomes both the above mentioned shortcomings. We also present two new applications of our technique: a two-server Oblivious RAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate. A function secret sharing scheme (which can be viewed as the dual version of HSS) is used to secret share a function, which can be homomorphically evaluated on any input by a set of parties. FSS for certain classes of functions has been optimized and used as a building block for cryptographic protocols including private information retrieval (PIR), Oblivious RAM and secure data aggregation. In this work we specifically focus on optimizing FSS for the problem of structured private set intersection. A structured PSI protocol allows two parties to securely compute the intersection of their sets, where one party’s input set has a publicly known structure. Security here implies no party learns anything more than the intersection of the two sets. We introduce a relaxed definition of standard FSS, which we term as weak FSS and de-randomizable FSS, both of which give semi-honest and malicious secure structured PSI protocols respectively. We focus on the design of these relaxed FSS constructions for various geometric objects including union of disjoint l-infinity balls. The proposed constructions have share size and evaluation cost orders of magnitude improved than traditional FSS constructions. We also study a weaker version of programmable function secret sharing, where one of the FSS shares is independent of the set being secret shared. Further, we show how this primitive can be used to construct efficient PIR protocols in the preprocessing model from one-way functions.
License
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details JaspalSingh2023.pdf 2023-09-11 Public Download