Efficient and resilient key discovery based on pseudo-random key pre-deployment