Pseudorandom Strings from Pseudorandom Quantum States
- 講者林耀廷 先生 (美國聖塔芭芭拉加利福尼亞大學)
邀請人：鐘楷閔 - 時間2023-07-11 (Tue.) 10:15 ~ 12:30
- 地點資訊所新館101演講廳
摘要
A fundamental result in classical cryptography is that pseudorandom generators are equivalent to one-way functions and in fact implied by nearly every classical cryptographic primitive requiring computational assumptions. In this work, we consider a variant of pseudorandom generators called quantum pseudorandom generators (QPRGs), which are quantum algorithms that (pseudo)deterministically map short random seeds to long pseudorandom strings. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes.
Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.
Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.
Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.
Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.