Traditionally, cryptography is about achieving secrecy and authenticity and other desired functionalities while withstanding adversarial behaviors, which can be viewed as the battle between the honest parties and the adversaries. After more than three decades of research, Cryptography has become an extremely rich field with a great impact in practice. Theoretically, it has evolved far beyond the traditional goal of secure communication and enables us to realize seemingly contradictory tasks, such as zero-knowledge proofs, secure multi-party computation, and computation over encrypted data, with rigorous security guarantees. On the practical side, it serves as fundamental building blocks for protecting modern cyber-security; every single time a connection is made to Google or any of thousands of websites, we are using cryptography. Modern web commerce won’t survive for a second without it.
We have been devoted to research in cryptography on both theoretical and practical sides. Dr. Bo-Yin Yang is a co-author of the widely-used Ed25519 Digital Signature Scheme. Ed25519 will be included in the FIPS 186-5 standard by the U.S. National Institute of Standards and Technology (NIST), and is used by hundreds of millions of users. Bo-Yin and Dr. Bow-Yaw Wang also pioneered research on HACS (High Assurance Crypto Software, formal verification of cryptographic software). On the theoretical side, Dr. Kai-Min Chung has worked on fundamental problems in several theoretical topics such as zero-knowledge proofs and cryptography in the (parallel) RAM model.
With the recent rapid development of quantum technology in building quantum computers, it becomes imperative to understand the effect of quantum power in cryptography. Principally, quantum computing devastates currently deployed public-key cryptography in the form of Shor’s algorithm. It is, in fact, one of the few currently confirmed killer applications of quantum computing. Shor’s algorithm is fundamentally a period-finding method and breaks RSA and ECC (Elliptic Curve Cryptography). While the advent of quantum computers was slower than expected, a NIST report cautiously puts the time that quantum computers will break ECC as early as 2030.
Given the challenge to migrate to new cryptography infrastructure throughout the society, it is a pressing issue to be addressed today. This is not only pressing but serious in terms of both cost --- which can be inferred from the cost of the Y2K transition --- and time, as industry has taken about two decades and has not fully transitioned to AES. Post-quantum cryptography (PQC) is a fast-growing field that addresses this challenge by developing cryptosystems (usually public-key cryptosystems) that are secure against quantum adversaries.
We can also regard quantum power as a double-edged sword. Although it is much less likely to become practical in the foreseeable future, quantum computing enhances the power of honest parties to achieve stronger functionality or security. There has been a rich development in theoretical cryptography exploring various exciting possibilities when we (the honest parties), and not just they (the adversaries), have quantum computers.
Post-quantum Cryptography
Cryptography is the field where quantum computing has made the earliest and visible real-world impact: NIST started discussing a post-quantum new standard in 2015 and finally called for proposals in 2016 with a deadline in 2017. In the last four years, almost every real-world cryptographer was involved in the design, implementation or cryptanalysis of post-quantum public-key cryptosystems.
NIST is currently in round 2 of the process of standardizing post-quantum cryptography; 82 entries were initially submitted of which 69 were considered proper and complete and invited to the first candidates’ conference in April 2018. PQC researchers from around the world participated in the standardization process: they began to study and break first-round candidates very shortly after their announcement and publication. Out of the remaining 50 or so unbroken candidates, NIST picked 26 (17 encryption schemes and 9 digital signatures) to advance to the second round. A second candidates’ conference was held in August 2019. Round 3 is expected to begin in June 2020. With selected cryptosystems coming from the finalist candidates will be announced in 2022, and standardization will take another 1-3 years. This process is broadly similar to the AES and SHA-3 NIST competitions.
Dr. Bo-Yin Yang has worked at post-quantum cryptography for more than a decade and is an internationally known scholar in this field. He has sat on the Steering Committee of PQCrypto, the international workshop series on PQC, since its earliest days. His team was the only team of participants from Taiwan in the NIST call for proposals in 2017.
Bo-Yin is an expert in the class of cryptosystems known as multivariates, whose hardness is based on the difficulty of solving multivariate nonlinear systems of equations. He has had many theoretical and practical results on multivariates and has a hand in the current design of almost all extant multivariate cryptosystems. Bo-Yin’s team submitted two proposals to NIST for their PQC competition. One of his proposals, Rainbow, is a Round 2 Candidate and will likely make Round 3. He also studies the design, attack, and realization of other PQC, principally lattice-based cryptosystems. He had held first place in various lattice cryptanalysis challenges over the years. His handiwork can be seen in other post-quantum cryptosystems. One of his principal contributions was an algorithm for high-speed constant-time computation of greatest common divisors and modular multiplicative inverses.
This is of paramount importance when generating keys for NTRU and related cryptosystems.
The advantage of the quantum adversaries is not limited to quantum computation, but also the ability to process quantum information, exploit entanglement, and make quantum superposition queries, which naturally arise in various contexts such as leakage and tampering resilient cryptography and constructions in the random oracle (RO) model. From the theoretical aspect, it is fundamental to understand the power of such advantages and reasons about security against such adversaries, which is also relevant to determine the concrete security of practical post-quantum cryptosystems. Our work on this aspect focuses on developing techniques to prove security against quantum adversaries in the presence of quantum (side) information, as well as security in the quantum random oracle model.
Quantum Cryptography
In contrast to post-quantum cryptography, which focuses on securing classical crypto constructs against quantum adversaries, the general field of quantum cryptography broadly explores what can be achieved when the honest parties also have quantum power. As a well-known example, quantum-key distribution (QKD) enables secure communication with information-theoretic security, which is impossible classically. As another example, when the data becomes quantum, a natural question is whether we can encrypt quantum data and perform computation over encrypted quantum data as for the classical data. While such research may not become practical in the foreseeable future, quantum cryptography is an exciting multidisciplinary field that combines state-of-the-art techniques from cryptography, quantum physics, complexity theory, and information theory. In turn, quantum cryptography also provides a rich context to develop deep insights and new techniques to advance the study of these fields.
Dr. Kai-Min Chung is a theorist who has worked on various theoretical aspects in (post-)quantum cryptography for nearly a decade. He has served on the program committee of major international cryptography conferences such as CRYPTO, Eurocrypt, Asiacrypt, QCrypt, and TCC. Besides the theoretical topics on post-quantum cryptography mentioned above, he has worked on several topics in quantum cryptography, such as device-independent cryptography, secure multiparty quantum computation, and classical delegation of quantum computation, and used techniques from quantum cryptography to answer conjectures in quantum complexity theory. We highlight two of these research works below.
The first work is on the topic of device-independent cryptography, which designs protocols for classical parties to securely exploit the quantum power of untrusted quantum devices. Our work on this topic constructed the only device-independent randomness amplification (DI-RA) protocol under provably minimal assumptions. Specifically, the DI-RA protocol can certifiably generate truly random bits given a weak source with sufficient min-entropy without any structural assumptions. In contrast, other existing works require structured Santha-Vazirani sources and certain conditional independence assumptions. Our protocol also implies a strong form of a dichotomy theorem on the intrinsic randomness in fundamental physics asserting that either our Nature is fully deterministic, or totally unpredictable events certifiably exist in Nature.
Our recent work develops techniques in quantum cryptography to study the power of classical-quantum hybrid computation with low-depth quantum computation, and answer conjectures by Scott Aaronson and Richard Jozsa. Given that quantum computation will be restricted to have low depth, such hybrid models capture the computation power available in the near term, but the power of such hybrid models is unclear. Jozsa conjectured in 2006 that any polynomial-time quantum computation can be simulated in a hybrid model motivated by measurement-based quantum computation. On the other hand, Aaronson conjectured an oracle separation between BQP and another type of hybrid model (first mentioned in 2005, and also in 2011 and 2014). Building on techniques from quantum cryptography, we showed an oracle separation between BQP and both hybrid models. Our results proved Aaronson’s conjecture and showed that Jozsa’s conjecture cannot hold relative to oracles.