Tata Institute of Fundamental Research
Randomness in Private Sequential Stateless Protocols
STCS Student Seminar
Speaker:
Hari Krishnan P A (TIFR)
Organiser:
Sourav Roy
Date:
Friday, 6 Dec 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A significant body of work is devoted to understanding the power of randomness in private computation. In this work, we make further progress on this by studying the randomness in a simple model of private computation called 'Private Stateless Sequential (PSS)' model. We show that the functions which can be computed 1-privately (i.e., 1 semi-honest corruption) with O(1) randomness using a speak-O(1)-times protocols are exactly those which can be computed with a constant-width read-O(1) branching programs.
This is a joint work with Varun Narayanan, Manoj Prabhakaran and Vinod M. Prabhakaran.
| Speaker: | Hari Krishnan P A (TIFR) |
| Organiser: | Sourav Roy |
| Date: | Friday, 6 Dec 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
A significant body of work is devoted to understanding the power of randomness in private computation. In this work, we make further progress on this by studying the randomness in a simple model of private computation called 'Private Stateless Sequential (PSS)' model. We show that the functions which can be computed 1-privately (i.e., 1 semi-honest corruption) with O(1) randomness using a speak-O(1)-times protocols are exactly those which can be computed with a constant-width read-O(1) branching programs.
This is a joint work with Varun Narayanan, Manoj Prabhakaran and Vinod M. Prabhakaran.