<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div>Reminder that Theory Lunch Seminar is happening in less than an hour!<br>
</div>
<br>
<div></div>
<br>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Olga Medrano Martin del Campo<br>
<b>Sent:</b> Monday, April 25, 2022 3:43 PM<br>
<b>To:</b> theory@mailman.cs.uchicago.edu <theory@mailman.cs.uchicago.edu><br>
<b>Subject:</b> Theory Student Lunch - Wednesday April 27th, 2022</font>
<div> </div>
</div>
<div dir="ltr">
<div class="x_elementToProof" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<div class="x_elementToProof" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<div tabindex="-1" class="x_x_fEEQbbifEC8quzJXH0sd x_x_TiApUvaZOn0aLkSUHRf7 x_x_allowTextSelection">
<div dir="ltr">
<div dir="ltr" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif"><span style="background-color:white; margin:0"><span style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><span style="font-family:"Trebuchet MS",Trebuchet,sans-serif"></span>Hi
all! <br>
</font></span></span></span></span></span></div>
<div dir="ltr" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif"><span style="background-color:white; margin:0"><span style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><br>
</font></span></span></span></span></span></div>
<div dir="ltr" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif"><span style="background-color:white; margin:0"><span style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em">Theory
Student will take place this Wednesday, April 27th, from 12:30 to 1:30 at JCL390, and our speaker will be Alex Hoover.<br>
</font></span></span></span></span></span></div>
<div dir="ltr" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif"><span style="background-color:white; margin:0"><span style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><br>
</font></span></span></span></span></span></div>
<div dir="ltr">
<div style="color:black; font-size:12pt; font-family:Calibri,Arial,Helvetica,sans-serif">
<div style="background-color:white; margin:0">
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0">
<div style="margin:0"><b style="color:#313131; font-size:16px; word-spacing:1px"><font style="font-size:1.13em">Title: A Lower Bound for One-Round Oblivious RAM</font></b></div>
<div style="margin:0"><b style="color:#313131; font-size:16px; word-spacing:1px"><font style="font-size:1.13em"><br>
</font></b></div>
<div style="margin:0"><span style="color:#313131; font-size:16px; margin:0; word-spacing:1px"><font style="font-size:1.13em"><b>Zoom:
</b><a href="https://uchicago.zoom.us/j/98193460374?pwd=UzFtVU9LTnBLWW9vSklCc2tkZUIwdz09" data-auth="NotApplicable" title="https://uchicago.zoom.us/j/98193460374?pwd=UzFtVU9LTnBLWW9vSklCc2tkZUIwdz09">[lihk</a>]</font></span></div>
<div style="margin:0"><span style="color:rgb(49,49,49); word-spacing:1px; font-size:13pt"><b><br>
</b></span></div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="color:rgb(49,49,49); word-spacing:1px; font-size:13pt"><b>Abstract:</b></span><b style="color:rgb(49,49,49); font-size:1.13em; word-spacing:1px"> </b><span style="font-size:1.13em; word-spacing:1px; font-family:"Open Sans","Clear Sans","Helvetica Neue",Helvetica,Arial,"Segoe UI Emoji",sans-serif; margin-top:0.8em; margin-bottom:0.8em; box-sizing:border-box; color:rgb(51,51,51)!important"><span style="box-sizing:border-box"></span></span><span>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.</span></div>
</div>
</div>
<div style="background-color:white; margin:0">
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0">
<div><span style="font-family:"Trebuchet MS",Trebuchet,sans-serif"></span><br>
</div>
</div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span>Based on a TCC'20 paper</span><span style="font-family:"Trebuchet MS",Trebuchet,sans-serif"></span><span> by David Cash, Andrew Drucker,
<span>Alex</span>ander <span>Hoover</span>.</span></div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0">
<div style="margin:0">
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:rgb(51,51,51)!important; font-family:Open Sans,Clear Sans,Helvetica Neue,Helvetica,Arial,Segoe UI Emoji,sans-serif; background-color:white!important; margin:0.8em 0px; box-sizing:border-box"><span style="box-sizing:border-box"></span></span><span style="color:#201F1E; font-size:12pt; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px"></span></font></div>
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:#201F1E; font-size:15px; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px"><br>
</span></font></div>
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:#201F1E; font-size:15px; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px"><br>
</span></font></div>
<div dir="auto" style="margin:0"><font style="color:#313131; font-size:1.13em; word-spacing:1px"><span style="color:#201F1E; font-size:15px; font-family:trebuchet ms,sans-serif; background-color:white; margin:0; word-spacing:0px">~~~<br>
</span></font></div>
<div dir="auto" style="margin:0"><font face="trebuchet ms,sans-serif"><b>COVID Policy:<span style="margin:0"> </span></b>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. </font></div>
</div>
</div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><font size="4"><br>
</font></div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="font-size:large; margin:0">[<a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!oOnZ3-9vk_IPd8KFkxpESFmuvq-esvE12qbIVPh8cOicyNKum5xoCKMZ3ZHqkvy7BHo$" data-auth="NotApplicable" title="https://orecchia.net/event/theory-lunch/" style="margin:0"><span style="margin:0"><span style="margin:0"><span class="x_markov6559ods">Theory</span></span></span> <span style="margin:0"><span class="x_mark23266aud8">Lunch</span></span> Webpage</a>]<br>
</span></div>
<div style="color:#201F1E; font-size:15px; background-color:white; margin:0"><span style="font-size:large; margin:0">[<a href="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$" data-auth="NotApplicable" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" style="margin:0"><span style="margin:0"><span style="margin:0"><span style="margin:0"><span style="margin:0"><span class="x_markov6559ods">Theory</span></span></span></span></span><span style="margin:0"> </span><span style="margin:0"><span style="margin:0"><span class="x_mark23266aud8">Lunch</span></span></span><span style="margin:0"> </span>Calendar</a>]</span><span style="font-size:10pt; margin:0px"></span></div>
</div>
</div>
</div>
</div>
</div>
<br>
</div>
<div><br>
</div>
<br>
</div>
</div>
</body>
</html>