Seminars

View all Seminars  |  Download ICal for this event

Near Optimal Split-state Non-malleable Codes

Series: Theory Seminar

Speaker: Dr. Sai Lakshmi Bhavana, Post Doctoral Researcher, Microsoft Research, India

Date/Time: Apr 29 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs) which protect against tampering of a codeword of a given message into the codeword of a related message. A well-studied model of tampering is the 2-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates.
<br>
Following a long line of work, Aggarwal and Obremski (FOCS 2020) showed the first constant rate non-malleable code in the 2�??split state model; however, this constant was a minuscule 10^{-6}! In our work[1], we build a Non-malleable Code with rate 1/3 (nearly matches the rate 1/2 lower bound for this model). This work will be the focus of my talk!
<br>
[1] Rate One-Third Non-malleable Codes, STOC 2022. Divesh Aggarwal, Sruthi Sekar, Bhavana Kanukurthi, Maciej Obremski, Sai Lakshmi Bhavana Obbattu
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Arindam Khan