Methods, devices, and computer program products for transmitting and receiving discovery and paging messages in a wireless communication device are described herein. In one aspect, a wireless apparatus operable in a wireless communication system includes a receiver configured to receive a discovery packet from a first device, the discovery packet including a first public key and information advertising a service provided by the first device. The wireless apparatus further includes a processor configured to generate a paging request packet, the paging request packet including a second public key and information indicating interest in the service provided by the first device. The processor is further configured to generate an encryption key based at least in part on the first public key and the second public key and encrypt at least a portion of the paging request packet using the generated encryption key. The wireless apparatus further includes a transmitter configured to transmit the encrypted paging request packet including the second public key and the information indicating interest in the service to the first device.