Star-specific Key-homomorphic PRFs from Learning with Linear Regression

Abstract

We introduce a novel method to derandomize the learning with errors (LWE) problem by generating deterministic yet sufficiently independent LWE instances that are constructed by using linear regression models, which are generated via (wireless) communication errors. 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., the pairs of sets may 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 $\mathcal{H}$, where the three properties are defined as: (i) $k$-uniform: $\forall A\in \mathcal{H}:|A|=k$, (ii) at most $t$-intersecting: $\forall A,B\in \mathcal{H},B\ne A:|A\cap B|\le t$, (iii) maximally cover-free: $\forall A\in \mathcal{H}:A⊈\bigcup _{\begin{array}{c}B\in \mathcal{H}\\ B\ne A\end{array}}B$. For the same purpose, we define and compute the mutual information between different linear regression hypotheses that are generated from overlapping training datasets.

arXiv commentThis is the preprint of a paper published in IEEE Access, vol. 11, pp. 73235-73267, 2023

References in corpus (26)

• Quantum Cryptography
• Quantum cryptography: Public key distribution and coin tossing
• Quantum random number generation
• Physical Layer Security for Massive MIMO: An Overview on Passive Eavesdropping and Active Attacks
• Using the Physical Layer for Wireless Authentication in Time-Variant Channels
• Free randomness can be amplified
• Is Entanglement Monogamous?
• Full randomness from arbitrarily deterministic events
• Orderly spectra from random interactions
• Experimental demonstration of quantum digital signatures using phase-encoded coherent states of light
• Universally Composable Quantum Multi-Party Computation
• Band structure from random interactions
• Sampling exactly from the normal distribution
• Intersecting families of sets and permutations: a survey
• What is quantum in quantum randomness?
• Deterministic networks for probabilistic computing
• Locating modifications in signed data for partial data integrity
• Man-in-the-Middle Attack Resistant Secret Key Generation via Channel Randomization
• Extremal Set Theory and LWE Based Access Structure Hiding Verifiable Secret Sharing with Malicious-Majority and Free Verification
• Bi-Homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption
• Certificate and Signature Free Anonymity for V2V Communications
• Nested Cover-Free Families for Unbounded Fault-Tolerant Aggregate Signatures
• Physical Layer Security Techniques for Future Wireless Networks
• Access Structure Hiding Secret Sharing from Novel Set Systems and Vector Families
• Matrix multiplication via matrix groups
• Non-Commutative Ring Learning With Errors From Cyclic Algebras