Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory
share
We introduce a novel method to derandomize the learning with errors (LWE) problem by generating deterministic yet sufficiently independent LWE instances, that are constructed via special linear regression models. We also introduce star-specific key-homomorphic (SSKH) pseudorandom functions (PRFs), which are defined by the respective sets of parties that construct them. We use our derandomized variant of LWE to construct a SSKH PRF family. The sets of parties constructing SSKH PRFs are arranged as star graphs with possibly shared vertices, i.e., some pair of sets have non-empty intersections. We reduce the security of our SSKH PRF family to the hardness of LWE. To establish the maximum number of SSKH PRFs that can be constructed – by a set of parties – in the presence of passive/active and external/internal adversaries, we prove several bounds on the size of maximally cover-free at most t-intersecting k-uniform family of sets ℋ, where the three properties are defined as: (i) k-uniform: ∀ A ∈ℋ: |A| = k, (ii) at most t-intersecting: ∀ A, B ∈ℋ, B ≠ A: |A ∩ B| ≤ t, (iii) maximally cover-free: ∀ A ∈ℋ: A ⊈⋃_B ∈ℋ B ≠ A B. For the same purpose, we define and compute the mutual information between different linear regression hypotheses that are generated via overlapping training datasets.
READ FULL TEXT