| Presentation | 2010-10-15 Robust Quantum Codeword-State Decoding and Pseudorandomness of the Legendre Sequence (Extended Abstract) Akinori KAWACHI, Keita XAGAWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A hardcore function is a fundamental primitive to generate pseudorandom sequences from one-way functions in cryptography and complexity theory. We present a general technique to construct a hardcore function of multi-bit output for a quantum one-way function. Our technique is based on a robust quantum query algorithm for the codeword-state decoding, which was introduced by Kawachi and Yamakami to prove a hardcore function of 1-bit output for a quantum one-way function. Our technique provides a more robust algorithm than theirs to adapt the multi-bit case. We apply our technique to proofs for new hardcore functions. The Legendre generator was proposed by Damgard in CRYPTO'88 and has been conjectured to be hardcore so far. We prove the hardcore property of the Legendre generator for a quantum one-way function by our new technique. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | hardcore functions / quantum one-way functions / Legendre sequences |
| Paper # | COMP2010-35 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/10/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Robust Quantum Codeword-State Decoding and Pseudorandomness of the Legendre Sequence (Extended Abstract) |
| Sub Title (in English) | |
| Keyword(1) | hardcore functions |
| Keyword(2) | quantum one-way functions |
| Keyword(3) | Legendre sequences |
| 1st Author's Name | Akinori KAWACHI |
| 1st Author's Affiliation | Department of Mathematical and Computing Sciences, Tokyo Institute of Technology() |
| 2nd Author's Name | Keita XAGAWA |
| 2nd Author's Affiliation | NTT Information Sharing Platform Laboratories |
| Date | 2010-10-15 |
| Paper # | COMP2010-35 |
| Volume (vol) | vol.110 |
| Number (no) | 232 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |