An embodiment method for vehicle messaging includes obtaining initial trust information that includes a root public key (RPK), and obtaining a first pool of group certificate (GC) sets and a first vehicle authentication certificate that includes a first encrypted serial number. The method also includes: selecting from the first pool a first GC and a first group private key (Gpk); determining a first signature in accordance with a first message and a digest function; sending a first datagram that includes the first message and the first signature; receiving a second datagram that includes a second GC and a second signature, the second GC duplicating a GC in the first pool; receiving a third datagram that includes a third GC and a third signature, the third GC not duplicating any GC in the first pool; and verifying the second and third datagrams in accordance with the digest function and RPK.