Pseudorandom functions with new properties from hard lattice problems
Abstract/Contents
- Abstract
- Pseudorandom functions (PRFs) are efficiently computable, deterministic functions that are computationally indistinguishable from a truly random function. These functions are fundamental objects in cryptography that serve as a core building block in many cryptographic algorithms and protocols. In recent years, many extensions to the traditional notion of pseudorandom functions were proposed in cryptography. These advanced variants not only satisfy the traditional security property of a PRF, but also provide additional structures or functionalities that further expand the pool of applications of pseudorandom functions. It was initially believed that any constructions of these advanced variants of pseudorandom functions require strong cryptographic hardness assumptions such as the existence of multilinear maps or indistinguishability obfuscation. However, in this work, we show that one can construct a large family of these variants by relying on much weaker hardness assumptions. We provide three new constructions of advanced pseudorandom functions. Our first construction is a new key-homomorphic PRF that requires the hardness of the Learning with Errors (LWE) problem with only a polynomial-size modulus. Previous constructions required the hardness of LWE with a superpolynomial-size modulus, which is a much stronger hardness assumption. Next, we construct a private puncturable PRF that relies only on the hardness of LWE. Prior constructions required existence of multilinear maps or indistinguishability obfuscation. Finally, we construct a watermarkable PRF from LWE. All prior constructions required the existence of indistinguishability obfuscation.
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 | Kim, Sam Bit |
|---|---|
| Degree supervisor | Boneh, Dan, 1969- |
| Thesis advisor | Boneh, Dan, 1969- |
| Thesis advisor | Tan, Li-Yang |
| Thesis advisor | Wootters, Mary |
| Degree committee member | Tan, Li-Yang |
| Degree committee member | Wootters, Mary |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Sam Kim. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/wh482tm3327 |
Access conditions
- Copyright
- © 2021 by Sam Bit Kim
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...