关键词: 标准格, 认证密钥交换, 可证明安全, “挑战-应答”签名, 带误差学习问题

Abstract: A strongly secure concrete authenticated key exchange protocol is proposed based on lattice problems. Firstly, a passively secure lattice-based key exchange protocol is presented, which is different from previous generic construction based on encryption, and achieves better efficiency; secondly, following the design idea of the efficient HMQV protocol, we design a concrete lattice-based “challenge-response” signature; finally, we propose a PACK secure authenticated key exchange protocol by combining the lattice-based passively secure key exchange protocol and the lattice-based “challenge-response” signature, and specify the computing devices of all computation processes based on better balance between security and efficiency. The proposed protocol is provably secure based on the learning with error problem (LWE) and inhomogeneously short integer solution problem, and the hardness of these two problems can be based on the hardness of lattice problem assumption, thus its security is also based on the lattice problem assumptions. In addition, the proposed protocol has many superior properties, e.g., it is concrete and does not rely on any chosen ciphertext secure primitives, at the same time, it achieves implicit authentication, which provides better privacy.

Key words: standard lattice, authenticated key exchange, provably secure, “challenge-response”signature, learning with error problem (LWE)