APKC '23: Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop

Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].

Bit Flipping Key Encapsulation (BIKE), a shortlisted scheme that proceeded to the fourth round of NIST’s standardization project for post-quantum cryptosystems, is conducive to implementation on embedded devices due to its small key size. However, prior research has indicated the possibility of reaction attacks on this scheme with the potential of compromising private keys through decoder failures. To ensure protection against such reaction attacks, the Decoder Failure Rate (DFR) needs to be sufficiently low. Since these attacks belong to a category of chosen-ciphertext attacks (CCA), a low DFR is essential for ensuring IND-CCA security. The Black Gray Flip (BGF) decoder adopted in the BIKE offers sufficient security. However, the size of the keys needed for the required security level may still be precarious for resource-constrained devices. Therefore, in this work, we formulate and analyze the potential variants of the BGF decoder and compare their performance with the original BGF decoder. To accomplish this, we generate a large set of ciphertexts, and utilize them to compute the DFR of the various variants of the BGF decoder. Our analysis confirms that the BGF decoder with parameters adopted in the original BIKE submission to NIST performs optimally with larger block sizes, which are essential for ensuring higher security levels.

CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA’s suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber’s implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the ω -order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for ω ≤ 5. The main contribution is a new neural network training method called recursive learning. In the attack on an ω -order masked implementation, we start training from an artificially constructed neural network Mω whose weights are partly copied from a model Mω − 1 trained on the (ω − 1)-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.

This paper considers the problem of balancing traceability and anonymity in designated verifier signatures (DVS), which are a kind of group-oriented signatures. That is, we propose claimable designated verifier signatures (CDVS), where a signer is able to claim that he/she indeed created a signature later. Ordinal DVS does not provide any traceability, which could indicate too strong anonymity. Thus, adding claimability, which can be seen as a sort of traceability, moderates anonymity. We demonstrate two generic constructions of CDVS from (i) ring signatures, (non-ring) signatures, pseudorandom function, and commitment scheme, and (ii) claimable ring signatures (by Park and Sealfon, CRYPTO’19).

In card-based cryptography, which uses a physical deck of cards to realize secure multiparty computations, a one-bit value is usually encoded by a pair of cards. Thus, when performing a secure computation of an n-input Boolean function, a sequence of 2n cards representing n bits is needed for input, and some helping cards are typically added to form a protocol. In 2020, Ruangwises and Itoh constructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that a symmetric Boolean function depends only on the number of 1s in its input). At the same time, they showed that the helping cards can be eliminated if the target function is limited to “doubly symmetric” Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following for all k: when inputting exactly a number k of 1s, the output is the same as the output when inputting exactly a number n − k of 1s. In this paper, we loosen the restriction on doubly symmetric Boolean functions by fixing k = 0, and construct new protocols which require less than two helping cards for that wider class of symmetric Boolean functions. Specifically, we design a one-helping-card protocol for any n > 4, and helping-card-free protocols for n = 3 and n = 4.