Non-malleable Codes Against Constant Split-state Tampering

on YouTube ↗30m

" summary

Constructs the first explicit constant-rate for c=10 non-malleable code in the c split-state model, with exponentially small error and an efficient encoder that samples a uniform element from the extractor inverse image while the decoder is the seeded non-malleable extractor. The proof builds an extractor via additive combinatorics: polynomial encodings, coordinate-wise multiplication, and product estimates guarantee leftover entropy; composing with known reductions yields codes down to c=2 and improves prior n^{1/7} error to exponential.

AI-written summary · about

" chapters (23)

1. 0:00Intro
2. 0:27Circumventing Classical Bounds Can we circumvent classical tradeoffs on rate vs. error tolerance? -Relax requirements.
3. 1:07New view of corrupting codewords
4. 1:42Additive tampering functions
5. 2:30Algebraic Manipulation Detection Codes [Cramer, Dodis, Fehr, Padro, Wichs] With focus on error detection, no restriction on wt(e). Randomized encoder: Enc Deterministic decoder: Dec, can also output 'error
6. 3:36Handle More Tampering Functions?
7. 8:17An easy F
8. 8:45General setting
9. 8:59Tampering functions in the C-split-state model
10. 10:18Non-malleable codes in the C-split-state model
11. 12:07Outline
12. 12:36Codes from extractors
13. 12:51Randomness Extractors [Nisan-Z]
14. 14:49Aside: Extractors & List Decoding
15. 21:19Seedless Normalleable Multi-source Extractors
16. 22:10NM Codes from NM Extractors
17. 23:13Encoding Efficiently
18. 24:18Additive Combinatorics A=set of integers, A+A=set of pairwise sums.
19. 26:20Achieving Intermediate Goal
20. 26:59Actual Seedless NM Extractor
21. 27:16A sum-product estimate over Fp4
22. 27:53Conclusions • First constant-rate non-malleable code in C-split- state model for any Cro(n).
23. 28:29Open Questions

" related talks

• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 23mRobust Constant-Time CryptographyRanjit Jhala, Sunjay Cauligi, Deian Stefan, Matthew Kolosick, Basavesh Ammanaghatta Shivakumar, Marco Patrignani, Marco Vassena · PriSC 2023
• 33mInteraction Preserving Compilers for Secure ComputationGiulio Malavolta, Nico Döttling, Vipul Goyal, Justin Raizes · ITCS 2022
• 33mError Correction for Streaming MessagesMeghal Gupta · Sketching and Algorithm Design 2023
• 58mFast Cryptographic Code via Partial EvaluationAdam Chlipala · PEPM 2023
• 27mComputation Over the Noisy Broadcast Channel with Malicious PartiesGillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Klim Efremenko · ITCS 2021
• 33mObfuscation with Constant Multiplicative Size OverheadPrabhanjan Ananth · Securing Computation (Simons Institute, June 2015)
• 26mConstant-Time Callees with Variable-Time CallersCesar Pereida García, Billy Bob Brumley · 26th USENIX Security Symposium (USENIX Security '17)