2nd PQC Standardization & Migration Workshop
Farcaster Consulting Group, LLC
Brian LaMacchia is currently serving as the first Executive Director of the MPC Alliance, a consortium of over 50 companies and academic institutions formed to accelerate awareness, acceptance, and adoption of multi-party computation (MPC) technology. Brian retired from Microsoft Corporation in December 2022 after a 25+-year career with the company where he was Microsoft’s Distinguished Engineer for Cryptography and head of the Security and Cryptography team within Microsoft Research.
He is an Adjunct Associate Professor in the Luddy School of Informatics, Computing, and Engineering at
Indiana University Bloomington, an Affiliate Faculty member of the Paul G. Allen School of Computer Science and Engineering at the University of Washington. Brian also currently serves as Treasurer of the International Association for Cryptologic Research (IACR), a member of the Technical Advisory Board of Quantum Computing Inc. (NASDAQ: QUBT), an Advisor to Quantropi, Inc., and as a Vice President of the Board of Directors of Seattle Opera. Brian received S.B., S.M., and Ph.D. degrees in Electrical Engineeringand Computer Science from MIT in 1990, 1991, and 1996, respectively.
Talk: The PQC Transition: Making Progress, But Still a Long Road Ahead
The transition to post-quantum cryptography (PQC) entered a new phase with the announcement in July 2022 by the US National Institute of Standards and Technology (NIST) of the first group of quantum-
resistant public-key algorithms selected for standardization. Over the past 17 months work has now started to update our commonly used security protocols with these new algorithms, while NIST’s PQC activity continues to finish standardizing these initial selections and to continue investigating additional
algorithms for potential future standardization.
His talk will start by exploring the history and current landscape of the PQC algorithm standardization process, including how we got to this point, the NIST roadmap ahead, and the projected timelines for NIST’s future PQC deliverables. He will then turn to look at PQC-related protocol standardization activities over the last year, including work in various IETF working groups and at ISO, and how individuals and companies can participate in those processes.
He will conclude with a discussion of concrete steps to take today to prepare for your own transition to PQC and what resources are available to help.
Shivam Bhasin is a Principal Research Scientist and Programme Manager (Cryptographic Engineering) at Centre for Hardware Assurance, Temasek Laboratories, Nanyang Technological University Singapore.
He received his PhD in Electronics & Communication from Telecom Paristech in 2011, Advanced Master in Security of Integrated Systems & Applications from Mines Saint-Etienne, France in 2008. Before NTU, Shivam held position of Research Engineer in Institut Mines-Telecom, France. He was also a visiting researcher at UCL, Belgium (2011) and Kobe University (2013). His research interests include embedded security, trusted computing and secure designs. He has co-authored several publications at recognized journals and conferences. Some of his research now also forms a part of ISO/IEC 17825 standard.
Talk: PQLeaks: Practical Side-Channel and Fault Attacks on Post-Quantum Lattice-based Cryptography
The impending threat of large-scale quantum computers to classical RSA and ECC-based public-key cryptographic schemes prompted NIST to initiate a global level standardization process for Post-Quantum Cryptography (PQC). Three out of the four winning schemes are based on hard problems over structured lattices, known as lattice-based cryptographic schemes.
This talk will highlight practical Side-Channel Analysis (SCA) & Fault Injection Analysis (FIA) vulnerabilities in lattice-based cryptographic cryptography, with particular focus on Kyber.
In several cases, the attacker only requires minimal or almost no knowledge of the implementation to mount such practical attacks. Identified vulnerabilities can also target few protected implementations. The talk also touches upon threat of backdoor insertion in PQC modules. Finally, we motivate more research towards the development of efficient and secure countermeasures for real-world security of lattice-based schemes.
Wei-Chih Hong received the B.S. and M.S. degrees in electrical engineering and the Ph.D. degree in communications engineering from National Taiwan University, Taipei, in 1996, 1998, and 2010, respectively. From 1999 to 2003, he worked as an Assistant Researcher with the Telecommunication Laboratories, Chunghwa Telecom. From 2010 to 2014, he conducted postdoctoral research with Technische Universität Darmstadt, Germany, and Academia Sinica, Taiwan. Before joining BTQ in 2022, he taught at Feng Chia University for 8 years. He now works as the head of hardware engineering and leads a team for developing hardware accelerators for PQC and ZKP systems in BTQ. His research interests include cryptographic engineering, side channel analysis, and the application of machine learning techniques in information security.
Talk: preon: a zk-SNARK based signature scheme
General-purpose proving systems have been undergoing rapid development in recent years.
A generalpurpose proving system is a Fiat-Shamir transformed interactive protocol in which a prover can convince a verifier that the prover knows a secret witness for the truthfulness of a somewhat general statement. When this statement is about knowledge of a secret, we can construct signature schemes, e.g., following the MPC-in-thehead paradigm, as well as based on zk-STARK.
One may (rightly) expect that a major drawback of such an approach is the overhead in terms of space and time one needs to pay in constructing a signature scheme from a general-purpose proving system, as we do not have access to any of the optimization opportunities brought about by specialization. However, we argue for this approach because it can bring a long-term advantage as follows. Once we have a (secure) signature scheme constructed from a general-purpose proving system like this, the flexibility of the latter would easily allow us to enhance the functionalities of the former and build at a minimum cost advanced schemes like group signatures, attribute-based signatures, functional signatures, ..., to name a few, by proving a suitable (and potentially more complicated) statement in the proving system. Thus, the tremendous amount of investment that goes into a unified process of security analysis, standardization, implementation, deployment,
as well as post-deployment continual improvement and optimization can pay lucrative dividends across a broader and fast-growing landscape of applications, compared with the alternative approach of independently standardizing all these different signature schemes individually, necessarily having to start from scratch and repeating much of the work every time.
Following this philosophy, I will introduce preon, a signature scheme constructed on top of the Aurora zk-SNARK in this talk, detailing some of the trade-offs made in its design, as well as lessons learned in the process.
Academia Sinica and University of Southern Denmark
Ruben Niederhagen is Associate Research Fellow at Academia Sinica in Taiwan and Associate Professor at the University of Southern Denmark in Denmark. He obtained his PhD at Eindhoven University of Technology in the Netherlands in 2012.
His research fields are Applied and Embedded Cryptography as well as Cryptanalytic Implementations.
He is co-submitter of the code-based key-encapsulation scheme Classic McEliece to the NIST standardization process.
Talk: State of the Art of Code-Based Cryptography
This talk gives a brief introduction to code-based cryptography and thenpresents the state of the art of code-based cryptography.
Matthias J. Kannwischer
Matthias J. Kannwischer is the Research Director at the Quantum Safe Migration Center (QSMC)
- a newly established center based in Taiwan aiming to accelerate the adoption of quantum-safe cryptography. He received his PhD in applied post-quantum cryptography from Radboud University
(Nijmegen, The Netherlands) and was supervised byPeter Schwabe and Bo-Yin Yang. Prior to joining QSMC, he was a post-doctoral researcher at Academia Sinica (Taipei, Taiwan)and a PhD student
at the Max Planck Institute for Security and Privacy (Bochum, Germany) and Radboud University (Nijmegen, The Netherlands). He is a co-submitter of OV and MAYO, and a maintainer of the pqm4 post-quantum software framework.
Talk: Oil-and-Vinegar and MAYO: All the condiments you need for achieving tiny quantum-safe signatures
With the upcoming standardization of Kyber, Dilithium, Falcon, and SPHINCS+, we are taking large steps towards a quantum-safe future. However, for some applications, those schemes have undesirable performance characteristics, motivating the study of different constructions. In particular,
NIST has launched a new competition aimed at standardizing additional signature schemes that provide very small signatures and fast verification. One of the promising families of quantum-safe cryptosystems is based on the hardness of solving multivariate quadratic (MQ) equations, allowing the construction of signature schemes with very small signatures and fast signing and verification.
In this talk, I will present two submissions to the NIST competition for additional signatures: Oil-and-Vinegar (OV) and MAYO. OV dates back to 1997 and has withstood many years of security analysis.
We propose modern parameters achieving 128-byte signatures and 44 KB public keys for the recommended parameter set. MAYO is a variation of OV which has been proposed in 2021.
One of the proposed parameter sets achieves 321-byte signatures and 1168-byte public keys.
Both OV and MAYO achieve very high performance, often competitive with lattice-based cryptography.
Surya Mathialagan is a fourth year PhD student at MIT, working with Vinod Vaikuntanathan and Virginia Vassilevska Williams. She is broadly interested in algorithms and cryptography, and has recently been working on problems related to oblivious RAMs, memory checking and fully homomorphic encryption.
Talk: Obfuscating Pseudorandom Truth-Tables and Applications to FHE and SNARGs
We define and construct obfuscation schemes for function families with pseudorandom truth tables, from the learning with errors (LWE) and the evasive LWE assumptions. Evasive LWE (Wee, Eurocrypt 2022; Tsabary, Crypto 2022) is a relatively new hardness assumption that has proved fruitful in constructing several cryptographic primitives (such as witness encryption, optimal broadcast encryption, and unbounded-depth attribute-based encryption) that we have so far not been able to construct from LWE.
We show two applications of pseudo-random truth table (PRTT) obfuscation:
Unleveled fully homomorphic encryption: We show how to use PRTT obfuscation together with any leveled FHE scheme to construct an unleveled FHE scheme, capable of homomorphically computing circuits of arbitrary depth. Previously, unleveled FHE schemes required either circular security type assumptions or full-fledged indistinguishability obfuscation.
Designated-Verifier Succinct Non-Interactive Arguments for UP: We show how to use PRTT obfuscation to construct a succinct non-interactive argument system (SNARG) with a designated verifier in the common reference string model. Our argument system works for the subclass of NP languages (called uniqueP or UP) where each instance has at most one witness, and is reusably and adaptively sound. Previously, (even designated verifier) SNARGs for such a large class of languages required either knowledge assumptions or full-fledged indistinguishability obfuscation. We construct our SNARG by first constructing a witness PRF (Zhandry, TCC 2016), a strengthening of the notion of a constrained PRF, for UP, and subsequently using witness PRFs generically to get a designated verifier SNARG.
Both these results rely on the subexponential LWE and the evasive-LWE assumptions, together with the existence of a pseudorandom function in NC1 (which follows from, e.g. the Ring-LWE assumption). With this instantiation, these constructions are plausibly post-quantum secure.
Joint work with Spencer Peters and Vinod Vaikuntanathan
Radboud University Nijmegen
Krijn Reijnders is a fourth-year PhD student at the Radboud University Nijmegen in The Netherlands. His research focuses on cryptanalysis and design of post-quantum cryptography, in particular code-based and isogeny-based cryptography. He is a co-submitter of the code-based scheme MEDS to the NIST Standardization process for post-quantum signatures. His most recent work aims to optimize the verification speed of SQIsign, another candidate in the NIST Standardization process. Lastly, he is the founder and co-organizer of The Isogeny Club, which organizes events in isogeny-based cryptography.
Talk: The Roadmap to Practical SQIsign
With SIKE, isogeny-based cryptography was on the verge of practical, real-world cryptography. The devastating attacks of the summer of 2022, however, have pushed the field back into the ‘research’ phase. The signature scheme SQIsign, with its unique characteristics among post-quantum signature schemes, is the new flagship of isogeny-based cryptography, and recent research is pushing this scheme closer and closer to being practical. In this talk, we describe the previous and current developments in SQIsign and sketch a detailed view of its verification process. We then argue what the next steps for SQIsign should be to improve its performance and analyze how close SQIsign verification really is to a theoretically optimal speed. This leads to a roadmap for SQIsign which describes several
stages it needs to pass to be considered mature, and we give realistic estimates for its performance in each stage. We also consider future applications of SQIsign where its unique small keys prove essential, such as embedded devices and post-quantum TLS, and where SQIsign could shine if we are able to push its performance close to the sketched optimum.
Hebrew University and Ben Gurion University
Last year Ph.D student at the Hebrew University and Ben Gurion University, M.Sc in mathematical logic from the Hebrew University.
Talk: Protecting Quantum Procrastinators with Signature Lifting: A Case Study in Cryptocurrencies
Post-quantum cryptography allows operating securely in the presence of quantum adversaries, but is generally only helpful if preparations have been made in advance to migrate to post-quantum schemes. Our work deals with procrastinators: user who remain reliant on pre-quantum cryptography after quantum adversaries emerged.
We focus on digital signatures and present a novel technique called signature lifting that, in some circumstances, allows users to create post-quantum signatures verifiable by keys derived from pre-quantum schemes.
The condition for applying signature lifting is that a "post-quantum step" is required to compute the public-key from the secret-key. This condition is most prevalent in the context of cryptocurrencies, where signatures are used to prove ownership of digital assets. We show how, in many cases, the ownership can be proven in a quantum secure way despite relying on keys derived from pre-quantum signature schemes. We use this insight to construct a modification of existing blockchains that can securely spend coins held by procrastinators. Our protocol improves upon preexisting solutions in several ways. In particular, it is the only protocol that allows paying transaction fees from the spent coin, rather than relying on access to coins that are already post-quantum.
Joint work with Or Sattath