<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<div tabindex="-1" class="x_fEEQbbifEC8quzJXH0sd x_TiApUvaZOn0aLkSUHRf7 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" 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 data-markjs="true" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">Alex</span>ander
<span data-markjs="true" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">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$" target="_blank" rel="noopener noreferrer" data-auth="NotApplicable" title="https://orecchia.net/event/theory-lunch/" style="margin:0" data-linkindex="1"><span style="margin:0"><span style="margin:0"><span data-markjs="true" class="markov6559ods" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">Theory</span></span></span> <span style="margin:0"><span data-markjs="true" class="mark23266aud8" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">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$" target="_blank" rel="noopener noreferrer" 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" data-linkindex="2"><span style="margin:0"><span style="margin:0"><span style="margin:0"><span style="margin:0"><span data-markjs="true" class="markov6559ods" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">Theory</span></span></span></span></span><span style="margin:0"> </span><span style="margin:0"><span style="margin:0"><span data-markjs="true" class="mark23266aud8" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="">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>
</body>
</html>