11th event on December 8th 2023

The next Tokyo Crypto Day will be held on December 8th (Fri) at the Musashino R&D center.

Place: The conference room in Musashino R&D center, 3-9-11 Midochi-cho, Musashino-shi, Tokyo 180-8585

Registration: No registration is required. Please follow instructions at the reception desk to enter the conference room.

- Speakers -

- Program -

  1. 9:15 - 10:15 Andrej Bogdanov Classical simulation of one-query quantum distinguishers
  2. 10:30 - 11:30 Siyao Guo Time-space tradeoffs for Function Inversion
  3. 13:00 - 14:00 Alon Rosen Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
  4. 14:15 - 15:15 Takashi Yamakawa Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
  5. 15:30 - 16:30 Yasunari Suzuki Design and Resource Estimation of Realistic Fault-Tolerant Quantum Computing

- Abstracts -

- Classical simulation of one-query quantum distinguishers

Andrej Bogdanov

Abstract: A distinguisher is an algorithm that tells whether its input was sampled from one distribution or from another. The computational complexity of distinguishers is relevant in cryptography, pseudorandomness, and statistical inference.

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over n-bit strings. Our focus is on a single quantum query, which is already quite powerful: Aaronson and Ambainis (STOC 2015) constructed a pair of distributions that is 𝜀-distinguishable by a one-query quantum algorithm, but O(𝜀k/√n)-indistinguishable by any non-adaptive k-query classical algorithm.

We show that every pair of distributions that is 𝜀-distinguishable by a one-query quantum algorithm is distinguishable with k classical queries and (1) advantage min{𝛺(𝜀√(k/n)), 𝛺(𝜀^2k^2/n)} non-adaptively (i.e., in one round), and (2) advantage 𝛺(𝜀^2k/√(n log n)) in two rounds. The second bound is tight in k and n up to a (log n) factor.

Based on joint work with Tsun Ming Cheung (McGill), Krishnamoorthy Dinesh (IIT Palakkad), and John C.S. Lui (CUHK)

- Time-space tradeoffs for Function Inversion

Siyao Guo

Abstract: In function inversion, we are given a function from n bits to n bits, and want to prepare some advice of size S, such that we can efficiently invert any image in time T. Function inversion is a central task in cryptography with profound connections to data structures, communication complexity, and circuit lower bounds. In this talk, I will describe recent progress in obtaining tight time-space bounds for function inversion and its related problems.

- Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Alon Rosen

Abstract: The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new fine-grained public-key encryption scheme whose security is based on Goldreich’s pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Joint work with Andrej Bogdanov and Pravesh Kothari.

- Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle

Takashi Yamakawa

Abstract: It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠ BQP/poly or QMA ≠ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠ BQP/poly and QMA ≠ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.

- Design and Resource Estimation of Realistic Fault-Tolerant Quantum Computing

Yasunari Suzuki

Abstract: Quantum computers are not only expected to break the existing cryptography based on integer factoring but are also used as a theoretical framework for novel security protocols. In either case, quantum computers must be scaled up to a size enough for target protocols in a fault-tolerant manner with quantum error-correcting codes. Although architectures for scalable quantum computers have been theoretically studied so far, many engineering problems that have yet to be expected in the existing frameworks are observed in recent developments. To evaluate the impacts of such practical issues and estimate when quantum technologies become threatening or beneficial computers, we need a concrete system design and evaluation schemes of quantum computers that stand on realistic engineering assumptions.

In this talk, we show a full-stack software suite that enables modeling and optimization of realistic quantum computing. First, we propose quantum counterparts of standard computer technologies, such as compilers, instruction set architecture, processor pipelines, and device interfaces. Using these designs and their emulators, we show several resource estimation results that we need to go beyond state-of-the-art high-performance computers. Also, we show that the co-design of quantum devices and processor designs based on this framework can significantly mitigate the burden of quantum computer development.