Abstract: As the key technology of the new generation air traffic control, automatic dependent surveillance-broadcast (ADS-B) has been deployed in most airspace around the world. The existing ADS-B message authentication schemes mainly utilize traditional public key cryptosystem to achieve data security, which are complex for computation and vulnerable to the quantum attack. We apply lattice-based cryptography to ADS-B communication security for the first time, and propose a hierarchical certificateless message authentication scheme supporting message recovery and batch verification simultaneously. The ADS-B airborne equipments are not required to manage certificates, and there is no key escrow problem. The ADS-B messages do not need to be transmitted with the signature, but can be recovered during verification. By utilizing rejection sampling and trapdoor-free technology, the proposed scheme requires just some computationally simple linear operations to realize message authentication. Our scheme is provably secure in the random oracle model under the assumption of the small integer solution (SIS). Experimental results of performance evaluation indicate that this scheme has significant performance improvement in saving computing overhead compared with related works under the same bit security level. It is very suitable for typical aeronautic electronic devices with limited computational resources.

Key words: automatic dependent surveillance-broadcast (ADS-B), lattice-based cryptography, hierar-chical certificateless message authentication, rejection sampling