<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof" style="font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<span style="color: rgb(87, 6, 6);"><i>UNIVERSITY OF CHICAGO</i><br>
<i>COMPUTER SCIENCE DEPARTMENT</i><br>
<i>PRESENTS</i></span><br>
<b><br>
Leonid Reyzin </b></div>
<div id="divRplyFwdMsg" dir="ltr"></div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<b>Professor of Computer Science<br>
Boston University<br>
</b><br>
<b>Friday, October 25th</b><br>
<b>1:30pm - 2:30pm</b><br>
<b>In Person: John Crerar Library 346</b><br>
<br>
<b>Title: Proofs of Space with Maximal Hardness</b><br>
<br>
<b>Abstract</b>: In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases
even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.<br>
<br>
In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires
extremely depth-robust graphs, which result in impractically high complexity of the initialization process.<br>
<br>
We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space. Our construction
is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better security than previously
shown.<br>
<br>
Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every set of $\pi \cdot n$ nodes contains a subset of $\alpha_\pi \cdot n$ nodes whose induced subgraph has just one sink. We take
a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<a href="https://urldefense.com/v3/__https://eprint.iacr.org/2023/1530__;!!BpyFHLRN4TMTrA!7AJasgVG2cf5nUQlMcQdPYILrSwJUrV4oD_Ya1atnZrNiiNOa8ujsJSsahTULC8xQD7wLIjQfNH-l-t6Q_Na8Md0zDZBBF4c0vboU10$" id="OWA2005f77d-2cc4-e528-e4ae-e60e227060ee" class="OWAAutoLink" title="https://eprint.iacr.org/2023/1530" data-auth="NotApplicable">https://eprint.iacr.org/2023/1530</a></div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<img id="x_image_0" width="203" height="240" style="width: 203px; height: 240px;" size="355879" contenttype="image/png" data-outlook-trace="F:2|T:2" src="cid:d58f8dec-a7f3-4a23-a2c7-3575d9ce7c69"></div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Arial, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
<b>Host: David Cash</b></div>
<div id="x_Signature" class="x_elementToProof"></div>
</body>
</html>