How to Construct Random Functions
We assume that functions that are one-way in a very weak sense exist. We prove that in probabilitic polynomial time it is possible to construct deterministic polynomial time computable functions g:{1,…,2^k} -> {1,…,2^k} that cannot be distinguished by an probabilistic polynomial time algorithm fr...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149054 |
| _version_ | 1811087083834441728 |
|---|---|
| author | Goldreich, Oded Goldwasser, Shafi Micali, Silvio |
| author_facet | Goldreich, Oded Goldwasser, Shafi Micali, Silvio |
| author_sort | Goldreich, Oded |
| collection | MIT |
| description | We assume that functions that are one-way in a very weak sense exist. We prove that in probabilitic polynomial time it is possible to construct deterministic polynomial time computable functions g:{1,…,2^k} -> {1,…,2^k} that cannot be distinguished by an probabilistic polynomial time algorithm from a random function. Loosely speaking, g provides random access to a K2^k -bit long pad whose entries record the outcome of independent coin flips. This complexity theoretic result has many important applications in Cryptography, Protocols, and Hashing. |
| first_indexed | 2024-09-23T13:39:31Z |
| id | mit-1721.1/149054 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:39:31Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490542023-03-30T03:36:54Z How to Construct Random Functions Goldreich, Oded Goldwasser, Shafi Micali, Silvio We assume that functions that are one-way in a very weak sense exist. We prove that in probabilitic polynomial time it is possible to construct deterministic polynomial time computable functions g:{1,…,2^k} -> {1,…,2^k} that cannot be distinguished by an probabilistic polynomial time algorithm from a random function. Loosely speaking, g provides random access to a K2^k -bit long pad whose entries record the outcome of independent coin flips. This complexity theoretic result has many important applications in Cryptography, Protocols, and Hashing. 2023-03-29T14:23:30Z 2023-03-29T14:23:30Z 1982-11 https://hdl.handle.net/1721.1/149054 MIT-LCS-TM-244 application/pdf |
| spellingShingle | Goldreich, Oded Goldwasser, Shafi Micali, Silvio How to Construct Random Functions |
| title | How to Construct Random Functions |
| title_full | How to Construct Random Functions |
| title_fullStr | How to Construct Random Functions |
| title_full_unstemmed | How to Construct Random Functions |
| title_short | How to Construct Random Functions |
| title_sort | how to construct random functions |
| url | https://hdl.handle.net/1721.1/149054 |
| work_keys_str_mv | AT goldreichoded howtoconstructrandomfunctions AT goldwassershafi howtoconstructrandomfunctions AT micalisilvio howtoconstructrandomfunctions |