New Concepts in Public-Key Encryption and Pseudorandom Generators
Explore the latest advancements in public-key encryption, local pseudorandom generators, and the low-degree method in cryptography. Discover ABW-like public-key encryption, Goldreich's function, pseudorandomness claims, and more in this innovative research work.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method ANDREJ BOGDANOV ANDREJ BOGDANOV PRAVESH KOTHARI PRAVESH KOTHARI ALON ROSEN ALON ROSEN OTTAWA OTTAWA CMU CMU BOCCONI/REICHMAN BOCCONI/REICHMAN TCC | Dec 2023
In search of a new PKE [Applebaum-Barak-Wigderson 10]: Three public-key encryption candidates Based on different assumptions This work: New ABW-like public-key encryption Fine-grained (quasi-poly) security Guided by the low-degree method cryptography hardness of statistical inference
ABW-like Public-key Encryption Public key: A pseudorandom generator ??: 0,1? 0,1? ??? 0 :??? for random ? 0,1? ??? 1 : random ? 0,1? ???:Use trapdoor in ? to distinguish ??? 0 from ??? 1 The challenge: How to plant trapdoor in ? Statistical (ABW1): ????? ?? Computational (ABW2, this work): ????? ?? In either case: ??????? ?? ??? 0 = = ??? 1
Goldreichs Function ??? Input: ? 0,1? Output: ? 0,1? ? bits ? ? bits
Goldreichs Function ??? Input: ? 0,1? Output: ? 0,1? ??= ? ???) ? ? ?1,?2,?3,?4,?5 = ?? 1 ?? 2 ?? 3 ?? 4?? 5
Goldreichs Function ??? Input: ? 0,1? Output: ? 0,1? ??= ? ???) ? ? ?1,?2,?3,?4,?5 = ?? 1 ?? 2 ?? 3 ?? 4?? 5
Pseudorandomness of ??? Claim Claim: When ? ?3/2 there is an efficient distinguisher* (*) with advantage 1 ? 1 Distinguisher: View ??? as noisy linear equations When ? ?3/2, equations collide (birthday) XOR colliding equations to cancel out linear part Remaining noise bit is 1/4-biased Use bias to distinguish ??? from random
Short linear dependencies Collisions length 2 linear dependencies mod 2 Linear dependency of length 2 bias 1/22 Linear dependency of length bias 1/2 short linear dependency large bias distinguisher This work: Plant dependencies of length 0= ? log?
Short linear dependencies mod 2 ? 0 ? 0 0 0 0 0 0 0 0 0 0 ? 0 0 0 0 0 ? 0 0 0 ? 0 ? 0 0 0 0 0 0 0 0 0 0 ? 0 0 ? 0 0 ? 0 0 0 0 0 0 0 0 0 0 0 ? 0 0 ? 0 0 0 ? 0 0 0 0 0 ? 0 0 0 0 0 0 0 0 ? 0 0 0 0 0 ? 0 0 0 ? 0 0 ? 0 0 0 0 0 0 0 0 0 ? 0 0 ? 0 0 0 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 0 0 ? 0 ? 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 0 ? 0 0 ? 0 0 ? 0 0 0 0 0 0 ? 0 0 0 0 0 0 ? 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 ? 0 0 ? 0 0 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 ? 0 0 0 0 0 ? 0 0 0 ? 0 0 ? 0 0 0 ? 0 0 0 0 0 0 0 0 0 0 ? 0 0 ? 0 0 0 0 ? ? 0 0 ? 0 0 0 0 0 0 0 0 0 ? 0 0 0 0 0 ? 0 0 0 ? 0 0 0 ? 0 0 0 0 0 ? 0 0 0 0 ? 0 ? 0 0 0 0 ? 0 0 0 0 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 0 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 ? 0 ? 0 0 0 0 0 0 0 ? 0 0 0 ? 0 0 0 0 0 0 ? 0 0 0 0 0 ? 0 0 0 0 ? ? 0 0 0 0 ? 0 0 ? 1 1/poly ? ? + 1 ? = ?1.5 ? planted ?2? 1 o 1 [FKO 06] ? log?
Hyperloops ? 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 Definition Definition: A hyperloop is a 3-hypergraph in which each vertex has degree 2 (more generally, even degree) length hyperloop length linear dependency
A Hyperloop = 6 ? = 9
A Planted Hyperloop Plant ?? identical hyperloops Conjecture: indistinguishable from random ?
Planted distribution Conjecture Conjecture: ????? ?? against ? log ? time Sufficient for security (assuming ?? is a PRG) Not clear if necessary ?and ? are not statistically close ? unlikely to have ?? hyperloops of length ? log?
The low-degree method If no degree-? polynomial distinguishes then no ? ?-time algorithm distinguishes For many high-dimensional product distributions best known distinguishers are low degree Not sound: does not model algebraic attacks Can be useful guide in noisy linear algebra type constructions with noticeable security error (? 1)
Low-degree distinguishers Degree-?? s capture any ?-local statistic If ? and ? are graphs then ? can count the number of copies of any subgraph with ? edges A natural distinguisher: test if ? ? > ? for some threshold ? Leap of faith: ?????,? models advantage of ? ?-time [BHKKSP 16, HKPRSS 17, H 18, KWB 19]
Small-set expanding hyperloops 0= 14, ? = 1/8, ? = 9 No deg- 1 ? ? distinguisher can detect this 0= 14 vertex hyperloop with 1 advantage when ? < ?3/2 1/8
Statistical inference Input: independent samples ?1, ,??from some distribution ?1 with planted signal Estimation (search): find signal Hypothesis testing (decision): distinguish from some fixed null distribution ?0 Computational-to-statistical gaps: hard(?) easy impossible # samples ????? ?????
