Algebraic Restriction Codes and their Applications
summary
Defines an algebraic restriction code that encodes X0,X1 via a random N×M matrix R (M>N) so R·Xhat = X, forcing only scalar-on-X0-plus-X1 evaluations to decode correctly while any arbitrary matrix evaluation yields a uniform value because A and R do not commute. Uses this to build a rate-one two-message oblivious transfer that is statistically sender-private with no setup (or under DDH), gives an explicit matrix-based construction and a second variant needing a strengthened XR lemma.
AI-written summary · about
chapters (6)
- 0:00Start
- 4:27Public-Key Encryption Linearly Homomorphic Encryption
- 5:46Linearly Homomorphic Encryption as OT
- 8:24Algebraic Restriction Codes
- 11:26Details
- 11:54References
related talks
48mOutput-Compressing Randomized Encodings and Applications
58mObfuscation I
01h 02mObfuscation II
41mHigh-Rate Fair-Density Parity-Check Codes
56mToward Obfuscation from Affine Determinant Programs
01h 06mObfuscation: Past, Present, and Possible Futures
01h 04mHow to Encrypt a Functionality
44mCoding Theory in Almost Linear Time and Sublinear Space