[Theory] Theory Student Lunch - Wednesday April 27th, 2022

[Olga Medrano Martin del Campo]

​Hi all!

Theory Student will take place this Wednesday, April 27th, from 12:30 to 1:30 at JCL390, and our speaker will be Alex Hoover.

Title: A Lower Bound for One-Round Oblivious RAM

Zoom: [lihk<https://uchicago.zoom.us/j/98193460374?pwd=UzFtVU9LTnBLWW9vSklCc2tkZUIwdz09>]

Abstract: We initiate a fine-grained study of the round complexity of Oblivious RAM (ORAM). We prove that any one-round balls-in-bins ORAM that does not duplicate balls must have either Ω( √ N) bandwidth or Ω( √ N) client memory, where N is the number of memory slots being simulated. This shows that such schemes are strictly weaker than general (multi-round) ORAMs or those with server computation, and in particular implies that a one-round version of the original square-root ORAM of Goldreich and Ostrovksy (J. ACM 1996) is optimal. We prove this bound via new techniques that differ from those of Goldreich and Ostrovksy, and of Larsen and Nielsen (CRYPTO 2018), which achieved an Ω(log N) bound for balls-in-bins and general multi-round ORAMs respectively. Finally we give a weaker extension of our bound that allows for limited duplication of balls, and also show that our bound extends to multiple-round ORAMs of a restricted form that include the best known constructions.
​
Based on a TCC'20 paper​ by David Cash, Andrew Drucker, Alexander Hoover.


~~~
COVID Policy: As per university policy, masking is not currently required for in-person attendance. Please note that we will have fully masked and social-distanced tables available to accommodate any attendees who would prefer such arrangements. Please contact us if you have any questions or feedback.

[Theory Lunch Webpage<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqkvy7BHo$>]
[Theory Lunch Calendar<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqEX_iTTQ$>]​



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220425/6ba7d0e1/attachment.html>