The power and limits of preprocessing in cryptography
Abstract/Contents
- Abstract
- Preprocessing refers to a computation that is executed before one is given the inputs to a certain computation task. Preprocessing can be used to speed up some cryptographic systems but also to speed up cryptanalytic attacks. This thesis explores the power and limits of preprocessing for both of these goals. First, we study algorithms with preprocessing for some of the most central problems that underpin the security of modern-day cryptosystems. We give new lower bounds for generic algorithms with preprocessing for the discrete-logarithm, CDH, and DDH problems. We also present new connections between the task of inverting functions with preprocessing and other areas of theoretical computer science. These connections shed light on the gap between the best known upper and lower bounds for the function-inversion problem and give rise to better algorithms for well-studied problems in complexity theory and data structures. We then turn to using the power of preprocessing to construct new protocols for private information retrieval. Our protocols allow fast (sublinear-time) private database lookups without increasing the server-side storage requirements. Finally, we present Checklist -- a system that uses these protocols for private blocklist lookups. In Checklist, a client can determine whether a particular string appears on a server-held blocklist, without leaking its string to the server. We implement and evaluate Checklist in the context of the "Safe Browsing" blocklist, which all major browsers use to prevent web clients from visiting malware-hosting URLs.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kogan, Dmitry |
|---|---|
| Degree supervisor | Boneh, Dan, 1969- |
| Thesis advisor | Boneh, Dan, 1969- |
| Thesis advisor | Reingold, Omer |
| Thesis advisor | Wootters, Mary |
| Degree committee member | Reingold, Omer |
| Degree committee member | Wootters, Mary |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Dmitry Kogan. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/sn383mk8063 |
Access conditions
- Copyright
- © 2021 by Dmitry Kogan
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...