基于格的可截取签名方案

Extraction signatures are a type of digital signatures with special functions. Extraction signatures allow the signature holder to delete sensitive data blocks in the signed data and generate a valid signature for the extracted data without interacting with the original signer. Since its proposal in 2001, extraction signatures have been one of the research hotspots in the field of cryptography, and have been widely used in many applications such as e-government system, e-commerce, electronic medical records, smart grids, and XML files. However, currently no extraction signature scheme can resist quantum attacks. With the advent of the post-quantum cryptographic era, it is necessary to design a quantum-resistant extraction signature scheme. This paper combines lattice-based digital signature schemes and preimage sampleable technique, and proposes a lattice-based extraction signature scheme. The security of this extraction signature scheme is based on small integer solution problems. This paper uses the lattice-based sampleable technique to prove that this scheme satisfies unforgeability and privacy under adaptive chosen-message attacks. Furthermore, G-trapdoors are applied in this scheme, which improves the performance of the key generation algorithm and simplifies the input matrix of the preimage sampling algorithm, so as to optimize the performance of this scheme. Finally, the scheme is implemented with SageMath compiler. The experiment results show that this lattice-based extraction signature scheme has good practicability.