Linear Algebraic Approach to Strongly Secure Ramp Secret Sharing for General Access Structures with Application to Symmetric PIR

摘要

Ramp secret sharing is a variant of secret sharing whichcan achieve better information ratio than perfect schemes by allowing somepartial information on a secret to leak out. Strongly secure ramp schemes cancontrol the amount of leaked information on the components of a secret. Inthis paper, we reduce the construction of strongly secure ramp secret sharingfor general access structures to a linear algebraic problem. As a result,we show that previous results on strongly secure network coding implytwo linear transformation methods to make a given linear ramp schemestrongly secure. They are explicit or provide a deterministic algorithmwhile the previous methods which work for any linear ramp scheme arenon-constructive. In addition, we present a novel application of stronglysecure ramp schemes to symmetric PIR in a multi-user setting. Our solutionis advantageous over those based on a non-strongly secure scheme in that itreduces the amount of communication between users and servers and alsothe amount of correlated randomness that servers generate in the setup.