In order to solve low efficiency and frequent updates of vehicles' public keys and private keys

a certificateless aggregate signature authentication and key agreement scheme with anonymity in vehicular Ad-Hoc network (VANET) is proposed. In our scheme

by using temporary identity and pre-signature

vehicles' privacy protection and anonymity authentication can be realized. On the other hand

the suspected vehicles can be tracked by the trust authority with the index database of the temporary identity to satisfy conditional anonymity. Meantime

if the temporary identity is changed

it is not necessary to update vehicles' public keys and private keys in this scheme

so the cost of system can be reduced. Moreover

the pairing-free aggregate signature technology is used to improve the efficiency further

which makes the number of signatures and the verification cost of the server be decreased. It is shown that our protocol is provably secure in eCK model under the computational Diffie-Hellman (CDH) assumption.