Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory

05/02/2022
∙
by   Vipin Singh Sehrawat, et al.
∙
0
∙

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

Please sign up or login with your details

Continue with:
Or login with email
Enter Password
Re-enter Password

Forgot password? Click here to reset
Success!
Error Icon An error occurred

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×
Pro

Consider DeepAI Pro

Subscribe to DeepAI Pro
DeepAI Pro
Provides a limited generation allowance each month. When exceeded, you are charged overage rates available at deepai.org/pricing. Also includes an ad-free experience and API access. Renews automatically until canceled. Non-refundable.
Subtotal
Total due today

Payment

Add DeepAI credits
DeepAI credits
One-time purchase. Credits are added to your wallet after payment.
Subtotal
Total due today

Payment