PQC Standardization & Migration Workshop

5 December 2022
Online and Onsite at Hotel Regent Taipei, Taiwan
Collocated with Asiacrypt 2022

Organizing Committee

  • Chen-Mou Cheng (BTQ AG)
  • Kai-Min Chung (Academia Sinica)
  • Jintai Ding (Tsinghua University)
  • Tsuyoshi Takagi (University of Tokyo)
  • Bo-Yin Yang (Academia Sinica)

Invited Speaker

  • Jimmy Chen (WiSECURE Technologies)
  • Jintai Ding (Tsinghua University)
  • Matthias Kannwischer (Academia Sinica)
  • Eunkyung Kim (Samsung)
  • Po-Chun Kuo (BTQ AG)
  • Ting-Gian Lua (BTQ AG)
  • Adrian Marotzke (NXP Semiconductors)
  • Dustin Moody (NIST)
  • Shiho Moriai (NICT)
  • Peter Schwabe (MPI-SP)
  • Daniel Smith-Tone (NIST)
  • Keita Xagawa (NTT)


Dustin Moody: What's next for NISTPQC

Abstract: In July 2002, NIST announced the PQC algorithms selected for standardization after five years of study. While this selection marks the beginning of the end of NIST's PQC initial standardization process, there is still much work that lies ahead. In this talk I will outline the future directions for NIST PQC efforts.

Bio: Dustin Moody is a mathematician in the NIST Computer Security Division. Dustin leads the post-quantum cryptography project at NIST. He received his Ph.D. from the University of Washington in 2009. His area of research deals with elliptic curves and their applications in cryptography.

Po-Chun Kuo: NIST Compliant Signature Aggregation

Abstract: NIST announced the standard for PQC in July 2022. The smallest size of signatures in the NIST standard is 0.7 KB, 2.4KB, and 8 KB for Falcon, Dilithium, and Sphics+, respectively. We present a signature aggregate method based on the zk-SNARK proving system to reduce a batch of Falcon signatures. Our algorithm aggregates 1487 signatures and outputs a proof of size 108 KB, which is around 10x smaller. In this talk, we will present our signature aggregate algorithm and explain how we optimize the proof.

Bio: Po-Chun Kuo received his Ph.D., M.S., and B.S. in electrical engineering from National Taiwan University in 2020, 2011, and 2010, respectively. He is currently the CTO of BTQ and aims to build a post-quantum secure and efficient blockchain. His research interests include consensus algorithms, cryptography, and high-performance computing.

Coffee break
Jintai Ding: Practical Improvements on BKZ Algorithm

Abstract: Lattice problem such as NTRU problem and LWE problem is widely used as the security base of post-quantum cryptosystems. Currently doing lattice reduction by BKZ algorithm is the most efficient way to solve it. In this paper, we give several further improvements on BKZ algorithm, which can be used for different SVP subroutines base on both enumeration and sieving. These improvements in combination provide a speed up of about 10 times in total. which is significant in concrete attacks. Using these new techniques, we solved the 656 dimensional ideal lattice challenge in only 380 thread hours (also with a enumeration based SVP subroutine), much less than the previous records (which costs 4600 thread hours in total). With these improvements enabled, we can still simulate the new BKZ algorithm easily. which is very useful for analyzing concrete attacks on lattice-based cryptography.

Bio: Jintai Ding is a professor at the Yau Mathematical Sciences Center at Tsinghua University and the director of Ding Lab in Privacy Protection and Blockchain Security at Beijing Institute of Mathematical Sciences and Applications. Before that he was a Charles Phelps Taft professor at the Department of Mathematical Sciences at the University of Cincinnati. He received B.A. from Xian Jiao tong University in 1988, M.A. from the University of Science and technology of China in 1990 and Ph.D from Yale in 1995. He was a lecturer at the Research Institute of Mathematical Sciences of Kyoto University from 1995 to 1998. In 2006-2007, he was a visiting professor and Alexander Von Humboldt Fellow at TU Darmstadt. He received the Zhong Jia Qing Prize from the Chinese Mathematical Society in 1990 for his Master Thesis. His research was originally in quantum affine algebras and its representation theory, where he was credited for the invention of the Ding-Iohara-Miki algebra. His current interest is in post-quantum cryptography, in particular, multivariate cryptography, latticed-based cryptography and quantum-proof blockchain. He was a co-chair of the 2nd ,10th and 11th international conference on post-quantum cryptography. He and his colleagues developed the Rainbow signature and the LWE-based key exchange schemes. Rainbow, which he designed, is a third round candidate for the NIST post-quantum standardization process. He and his colleagues completely broke a NIST second round post-quantum signature candidate LUOV and a third round candidate GeMSS (HFEv-), which won the honorable mention for the best paper award in Crypto 2021. He is one of the designer of Kyber, which was selected as the only KEM for the NIST post-quantum standard and he licensed his patent for use in Kyber to NIST.

Daniel Smith-Tone: Multivariate Cryptography

Abstract: The Road from Theory to Standard Abstract: In this talk we discuss some of the breakthroughs in cryptanalysis we have witnessed since the beginning of NIST's post-quantum standardization process and how they have impacted the general state of the field and the trust we can place in these constructions. With this context established, we consider the challenges facing a multivariate digital signature scheme in NIST's upcoming digital signature onramp.

Bio: Daniel Smith-Tone is part of the Cryptographic Technology Workgroup at the National Institute of Standards and Technology where he contributes to the Post-Quantum Cryptography Standardization Project. He is also a Professor of Mathematics at the University of Louisville.

Jimmy Chen: PQC on HSM of Various Form Factors

Abstract: A Hardware Security Module (HSM) is a specialized, highly trusted physical device that performs all primary cryptographic operations, including encryption, decryption, authentication, signature signing, key exchange, and key management. HSMs provide a dedicated, secure, tamper-resistant environment to protect data, keys, and cryptographic operations. On July 5, 2022, NIST announced that four Post-Quantum Cryptography (PQC) algorithms, Crystals-Kyber, Crystals-Dilithium, Falcon, and SPHINCS+ were selected for standardization. We implemented Crystals-Kyber and Crystals-Dilithium on EAL 5+ security crypto-controller with 32-bit CPU and 32 KB RAM. Also, we implemented SPHINCS+ on military-grade secure FPGA. Equipped with the above PQC-ready secure crypto-controller and FPGA, our HSMs are crypto-agile in various form factors, including PCIe cards, USB tokens, and MicroSD cards.

Bio: Jimmy, Jiun-Ming Chen is Chairman of WiSECURE Technologies. Co-founders of IKV Technology and QSancus Inc. 20 years’ experience in HW module and SW of cryptography. Adjunct faculty member with Outstanding Teaching Award in NTU since 2003. Courses of cryptography, cryptanalysis, FinTech with blockchain & cryptocurrency delivered in the departments of Math, EE, CSIE, and EMBA.

Lunch break
Peter Schwabe: Formosa Crypto

Abstract: In my talk I will briefly introduce the "Formosa Crypto" project -- an effort that combines state-of-the art in computer-verified proofs and cryptographic engineering to build high-assurance cryptographic software. A particular focus will be on libJade, a high-assurance cryptographic library written in the jasmin programming language which aims at providing high-performance formally verified post-quantum crypto.

Bio: Peter Schwabe is research group leader at MPI-SP and professor at Radboud University. He graduated from RWTH Aachen University in computer science in 2006 and received a Ph.D. from the Faculty of Mathematics and Computer Science of Eindhoven University of Technology in 2011. He then worked as a postdoctoral researcher at the Institute for Information Science and the Research Center for Information Technology Innovation of Academia Sinica, Taiwan and at National Taiwan University. His research area is cryptographic engineering; in particular the security and performance of cryptographic software. He published more than 60 articles in journals and at international conferences presenting, for example, fast software for a variety of cryptographic primitives including AES, hash functions, elliptic-curve cryptography, and cryptographic pairings. He has also published articles on fast cryptanalysis, in particular attacks on the discrete-logarithm problem. In recent years he has focused in particular on post-quantum cryptography. He co-authored the "NewHope" and "NTRU-HRSS" lattice-based key-encapsulation schemes which were used in post-quantum TLS experiments by Google and he is co-submitter of seven proposals to the NIST post-quantum crypto project, all of which made it to the second round, five of which made it to the third round, and 3 of which were selected after round 3 for standardization.

Matthias Kannwischer: Implementing the NIST PQC standards on microcontrollers

Abstract: In July 2022, the US National Institute of Standards and Technology (NIST) announced the first set of post-quantum schemes to be standardized: Kyber, Dilithium, Falcon, and SPHINCS+. In this talk, I am going to present the state-of-the-art of those to-be-standardized schemes on the Arm Cortex-M4 which is NIST's primary microcontroller optimization target. I will present the most recent results of the benchmarking framework pqm4 for all four schemes. While for Falcon and SPHINCS+ there has been very little progress in implementation performance lately, there exist very recent improvements to the speed and memory consumption of Kyber and Dilithium. I will present those new implementation techniques.

Bio: Matthias Kannwischer is a post-doctoral researcher at Academia Sinica in Taipei, Taiwan. He received his MSc in IT Security from TU Darmstadt in 2017 and defended his doctoral thesis on Polynomial Multiplication for Post-Quantum Cryptography at Radboud University in April 2022. His research focuses on the implementation of post-quantum cryptography, in particular lattice-based cryptography on Arm processors. He is one of the creators of pqm4 - a benchmarking and testing framework for post-quantum cryptography on the Arm Cortex-M4.

Keita Xagawa: Anonymity of NIST PQC KEMs

Abstract: We investigate anonymity, one of "beyond CCA security", of all NIST PQC Round 3 KEMs in the quantum random oracle model (QROM).

Bio: Keita Xagawa received his B.S. degree from Kyoto University and M.S. and D.S. degrees from Tokyo Institute of Technology in 2005, 2007 and 2010, respectively. Dr. Xagawa joined NTT, Nippon Telegraph and Telephone Corporation, in 2010. His research work focuses on public-key cryptography and post-quantum cryptography.

Coffee break
Shiho Moriai: Japan CRYPTREC Activities on PQC

Abstract: CRYPTREC (Cryptography Research and Evaluation Committees) is a project to evaluate and monitor the security of cryptographic techniques used in Japanese e-Government systems.  In this talk we will introduce some activities on security analysis toward quantum-safe society, including survey reports on the effect of quantum computers on the security of symmetric-key cryptographic schemes (FY2019) and on Shor’s algorithm for integer factorization and solving discrete logarithm problems (FY2020). This presentation also introduces our ongoing activities for publishing the CRYPTREC Guideline on PQC.

Bio: Shiho Moriai is the Director General of Cybersecurity Research Institute, National Institute of Information and Communication Technology (NICT). Her background is design, analysis, standardization, and deployment of cryptographic technologies. She now oversees R&D in cybersecurity and cryptographic technologies and cybersecurity trainings conducted in Cybersecurity Research Institute, NICT. She was awarded the Industrial Standardization Award by the Minister of Economy, Trade and Industry in 2011, and Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology in 2014.

Eunkyung Kim: Why You Should Prepare for PQC Migration Now

Abstract: As the standardization of NIST's PQC algorithm is nearing completion, discussions on PQC migration are also being actively conducted. NCCoE of NIST launched the 'Migration to Post-Quantum Cryptography' project in June 2022 involving multiple vendors, including Samsung SDS, to develop practices to facilitate the migration process. In this talk, we revisit why we should start preparing for PQC migration now, regardless of when cryptographically relevant quantum computers are being developed. Finally, Samsung SDS's research activities for PQC algorithm standardization and PQC migration are briefly introduced.

Bio: Eunkyung Kim got her PhD from Ewha Womans University in 2018 and joined Samsung SDS, where she is currently a Senior Engineer. Her research interest spans Cloud Security, Crypto-Agility, Elliptic-curve Cryptography, Homomorphic Encryption, Post-Quantum Cryp- tography, and PQC Migration.

Adrian Marotzke: To NTT or not to NTT: Polynomial multiplication

Abstract: Algorithms based on structured lattices are very popular as a candidates for PQC algorithms, as demonstrated by the to-be standardization of algorithms like Kyber and Dilithium. A core operation in these algorithms is polynomial multiplication. In software, the use of the number theoretic transform (NTT) has become ubiquitous, even in algorithms where implementing NTT is non-trivial, such as Saber or NTRU Prime. However, in hardware, it is a different story: Here, alternative multiplication algorithms such as Karatsuba and schoolbook multiplication have shown to also be efficient. This talk will highlight these different multiplication strategies, with a focus on the schoolbook algorithm. Both FPGAs and ASICs are considered, as well as high-performance and low area implementations, rounded off with an analysis of masked polynomial multipliers.

Bio: Adrian Marotzke is a PhD Student in the CTO System Innovation Team of NXP Semiconductors in Hamburg, and the Hamburg University of Technology. He is researching in the field of secure and efficient hardware implementations of Post-Quantum-Cryptography. As part of the submission team of the PQC-Scheme NTRU Prime, he is also taking part in the standardization process of NIST.

Ting-Gian Lua & Chen-Mou Cheng: Keelung: A domain-specific language for developing ZK applications

Abstract: Zero-knowledge (ZK) proof techniques are revolutionizing the world of blockchains and Web3. However, developing ZK applications is still a labor-intensive task and an error-prone process, partly because the development tools are still far from mature. We present Keelung, a domain-specific language and development toolkit for ZK applications. By raising the abstraction level, Keelung makes it easy for the programmer to focus on the business logic rather than the low-level nuts and bolts of the underlying ZK proving system. Last but not least, embedding Keelung into Haskell allows its programmers to leverage Haskell's extensive libraries and rich ecosystem, making ZK application development no more painful than it needs to be.

Bio: Ting-Gian Lua received his B.S. (2014) and M.S (2017) in Computer Science from National Chiao-Tung University. He is a PL enthusiast, lifelong Category Theory learner. He writes Haskell and Agda for a living. He is also into Linguistics and video games.

Call for Presentations

In July 2022, NIST officially announced four candidates for PQC standardization. This is certainly a landmark milestone after nearly six years of hard work by the PQC research community all over the world; yet it is also just only the beginning of a long and extensive process of migration to post-quantum cyberspace, requiring even greater efforts from not only the research community but also the cybersecurity industry as a whole. Therefore, the organizing committee of this workshop is calling for presentations from both academia and industry on topics related to the challenges and potential solutions, as well as strategies and guidelines pertaining to PQC standardization and migration in the next few years. Please submit a title, abstract, and speaker bio for a 15–30 minute talk to cheng@btq.li before the deadline of 15 Nov 2022 if you are interested. Selection will be based on the relevance and merits of the submissions, whose results will be announced roughly two weeks before the workshop.