In 2023, the National Institute of Standards and Technology (NIST) announced its post-quantum cryptography (PQC) standards; CRYSTALS-Dilithium, Falcon and SPHINCS+ as digital signatures and CRYSTALS-Kyber as the key-encapsulation mechanism (KEM) (or put simply, encryption). These PQC standards are to replace today’s quantum-vulnerable cryptography algorithms, currently securing digital systems, to protect against emerging quantum computing threats. One of the main challenges in transitioning into such standards is to educate the current and future IT/Cybersecurity workforce about PQC, particularly around the practical aspects. In particular, the original proposers of the selected algorithms only provided the reference (and optimized) software implementations of them. The final NIST standard specifications will only be equipped with mathematical explanations and test vectors. Hence, there are not many custom-designed educational content, assessment, and practical tools for PQC. In this experience paper, we introduce and discuss our PQC educational program, PQCIP, targeted at industry and governmental IT/Cybersecurity professionals. PQCIP has significantly contributed to its participants’ learning and engagement by providing tailored high-quality content, hands-on assessments, and strategic planning, making them ready to develop evaluated transition plans for their organizations and/or governments. We have also created custom software interfaces for CRYSTALS-Kyber, the NIST PQC standard for KEM. Using the developed interface along with Open Quantum Safe (OQS) software library for OpenSSL, we bridge a gap in available educational tools for PQC training. This tool has been shown to enhance the participants’ understanding of PQC’s practical applications and improve their engagement with highly technical cryptographic contents.

We introduce the first candidate Lattice-based designated verifier (DV) zero knowledge sUccinct Non-interactive Argument (ZK-SNARG) protocol, named LUNA, with quasi-optimal proof length (quasi-linear in the security/privacy parameter). By simply relying on mildly stronger security assumptions, LUNA is also a candidate ZK-SNARK (i.e. argument of knowledge). LUNA achieves significant improvements in concrete proof sizes, reaching below 6 KB (compared to >32 KB in prior work) for 128-bit security/privacy level. To achieve our quasi-optimal succinct LUNA, we give a new regularity result for 'private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter (avoiding exponential smudging), and hides the coset of the re-randomization vector support set. Along the way, we derive bounds on the smoothing parameter of the intersection of short integer solution (SIS), gadget, and Gaussian perp module lattices over the power of 2 cyclotomic rings. We then introduce a new candidate linear-only homomorphic encryption scheme called Module Half-GSW (HGSW), and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW. Our implementation and experimental performance evaluation show that, for typical instance sizes, Module HGSW provides favourable performance for ZK-SNARG applications involving lightweight verifiers. It enables significantly (around 5x) shorter proof lengths while speeding up CRS generation and encryption time by 4-16x and speeding up decryption time by 4.3x, while incurring just 1.2-2x time overhead in linear homomorphic proof generation operations, compared to a Regev encryption used in prior work in the ZK-SNARG context. We believe our techniques are of independent interest and will find application in other privacy-preserving lattice-based protocols.

In this work, we study the blockchain leader election problem. The purpose of such protocols is to elect a leader who decides on the next block to be appended to the blockchain, for each block proposal round. Solutions to this problem are vital for the security of blockchain systems. We introduce an efficient blockchain leader election method with security based solely on standard assumptions for cryptographic hash functions (rather than public-key cryptographic assumptions) and that does not involve a racing condition as in Proof-of-Work based approaches. Thanks to the former feature, our solution provides the highest confidence in security, even in the post-quantum era. A particularly scalable application of our solution is in the Proof-of-Stake setting, and we investigate our solution in the Algorand blockchain system. We believe our leader election approach can be easily adapted to a range of other blockchain settings.

Payment Channel Hub (PCH) is a promising solution to the scalability issue of first-generation blockchains or cryptocurrencies such as Bitcoin. It supports off-chain payments between a sender and a receiver through an intermediary (called the tumbler). Relationship anonymity and value privacy are desirable features of privacy-preserving PCHs, which prevent the tumbler from identifying the sender and receiver pairs as well as the payment amounts. To our knowledge, all existing Bitcoin-compatible PCH constructions that guarantee relationship anonymity allow only a (predefined) fixed payment amount. Thus, to achieve payments with different amounts, they would require either multiple PCH systems or running one PCH system multiple times. Neither of these solutions would be deemed practical.In this paper, we propose the first Bitcoin-compatible PCH that achieves relationship anonymity and supports variable amounts for payment. To achieve this, we have several layers of technical constructions, each of which could be of independent interest to the community. First, we propose BlindChannel, a novel bi-directional payment channel protocol for privacy-preserving payments, where one of the channel parties is unable to see the channel balances. Then, we further propose BlindHub, a three-party (sender, tumbler, receiver) protocol for private conditional payments, where the tumbler pays to the receiver only if the sender pays to the tumbler. The appealing additional feature of BlindHub is that the tumbler cannot link the sender and the receiver while supporting a variable payment amount. To construct BlindHub, we also introduce two new cryptographic primitives as building blocks, namely Blind Adaptor Signature (BAS), and Flexible Blind Conditional Signature (FBCS). BAS is an adaptor signature protocol built on top of a blind signature scheme. FBCS is a new cryptographic notion enabling us to provide an atomic and privacy-preserving PCH. Lastly, we instantiate both BlindChannel and BlindHub protocols and present implementation results to show their practicality.

We introduce MatRiCT+, a practical private blockchain payment protocol based on “post-quantum” lattice assumptions. MatRiCT+builds on MatRiCT due to Esgin et al. (ACM CCS’19) and, in general, follows the Ring Confidential Transactions (RingCT) approach used in Monero, the largest privacy-preserving cryptocurrency. In terms of the practical aspects, MatRiCT+has 2-18× shorter proofs (depending on the number of input accounts, M) and runs 3-11× faster (for a typical transaction) in comparison to MatRiCT. A significant advantage of MatRiCT+is that the proof length’s dependence on M is very minimal (only O(logM)), while MatRiCT has a proof length linear in M. To support its efficiency, we devise several novel techniques in our design of MatRiCT+to achieve compact lattice-based zeroknowledge proof systems, exploiting the algebraic properties of power-of-2 cyclotomic rings commonly used in practical latticebased cryptography. Along the way, we design a family of “optimal” challenge spaces, using a technique we call partition-and-sample, with minimal $\ell_{1}$-norm and invertible challenge differences (with overwhelming probability), while supporting highly-splitting power-of-2 cyclotomic rings. We believe all these results to be widely applicable and of independent interest.

We introduce MatRiCT, an efficient RingCT protocol for blockchain confidential transactions, whose security is based on "post-quantum'' (module) lattice assumptions. The proof length of the protocol is around two orders of magnitude shorter than the existing post-quantum proposal, and scales efficiently to large anonymity sets, unlike the existing proposal. Further, we provide the first full implementation of a post-quantum RingCT, demonstrating the practicality of our scheme. In particular, a typical transaction can be generated in a fraction of a second and verified in about 23 ms on a standard PC. Moreover, we show how our scheme can be extended to provide auditability, where a user can select a particular authority from a set of authorities to reveal her identity. The user also has the ability to select no auditing and all these auditing options may co-exist in the same environment. The key ingredients, introduced in this work, of MatRiCT are 1) the shortest to date scalable ring signature from standard lattice assumptions with no Gaussian sampling required, 2) a novel balance zero-knowledge proof and 3) a novel extractable commitment scheme from (module) lattices. We believe these ingredients to be of independent interest for other privacy-preserving applications such as secure e-voting. Despite allowing 64-bit precision for transaction amounts, our new balance proof, and thus our protocol, does not require a range proof on a wide range (such as 32- or 64-bit ranges), which has been a major obstacle against efficient lattice-based solutions. Further, we provide new formal definitions for RingCT-like protocols, where the real-world blockchain setting is captured more closely. The definitions are applicable in a generic setting, and thus are believed to contribute to the development of future confidential transaction protocols in general (not only in the lattice setting).

As the need for lightweight cryptography has grown even more due to the evolution of the Internet of Things, it has become a greater challenge for cryptographers to design ultra lightweight stream ciphers in compliance with the rule of thumb that the internal state size should be at least twice as the key size to defend against generic Time-Memory-Data Tradeoff (TMDT) attacks. However, Recently in 2015, Armknecht and Mikhalev sparked a new light on designing keystream generators (KSGs), which in turn yields stream ciphers, with small internal states, called KSG with Keyed Update Function (KSG with KUF), and gave a concrete construction named Sprout. But, currently, security analysis of KSGs with KUF in a general setting is almost non-existent. Our contribution in this paper is two-fold. 1) We give a general mathematical setting for KSGs with KUF, and for the first time, analyze a class of such KSGs, called KSGs with Boolean Keyed Feedback Function (KSG with Boolean KFF), generically. In particular, we develop two generic attack algorithms applicable to any KSG with Boolean KFF having almost arbitrary output and feedback functions where the only requirement is that the secret key incorporation is biased. We introduce an upper bound for the time complexity of the first algorithm. Our extensive experiments validate our algorithms and assumptions made thereof. 2) We study Sprout to show the effectiveness of our algorithms in a practical instance. A straightforward application of our generic algorithm yields one of the most successful attacks on Sprout.