Cryptographic primitives from the lattice isomorphism problems

Abstract

The Lattice Isomorphism Problem (LIP) is an emerging foundation for post-quantum cryptography thanks to the pioneering work of Ducas and van Woerden (EUROCRYPT '22). That work lays the foundation for LIP in cryptography with a zero-knowledge proof of knowledge (ZKPoK), a key-encapsulation mechanism, and a digital signature scheme which is further developed into the efficient signature Hawk (ASIACRYPT '22) using structured lattices. However, as compared to the development of lattice-based cryptography from the Short Integer Solution (SIS) and Learning with Errors (LWE) problems, LIP-based cryptography is yet to cover a rich variety of functionalities beyond the two basic ones: encrypting and digitally signing messages. This work is an effort to extend the landscape of LIP-based cryptography from the above basic primitives to more advanced ones by adapting techniques used in SIS-based and LWE-based primitives to LIP. We provide a public-key encryption (PKE) which encrypts plaintexts of integral vectors, and it comes with a zero-knowledge proof of plaintext knowledge. We use this PKE as a commitment scheme in the construction of a ZKPoK for quadratic relations, so this ZKPoK has a straightline extractor naturally. Using the same ZKPoK in non-interactive mode by Fiat-Shamir transformation, we introduce the first LIP-based blind signature scheme which is the blinded version of the digital signatures of Ducas and van Woerden. The security of our scheme stems from a new one-more Close Vector Problem (omCVP) assumption. This assumption is arguably an analogue of the one-more-SIS assumption by Agrawal et al. (CCS '22) and the one-more Short Vector Problem in Hawk signatures. To ensure confidence in omCVP, we provide a cryptanalysis attempt and convince that our parameter choice is in the safe zone.