There has been an increasing interest in the design and use of key escrow schemes in recent times. This paper proposes a new key escrow protocol based on Boolean permutations and analyses its properties. It shows that the verification of the shares of key escrow agencies is easy and secure. In addition this protocol provides forward security as well as the capability to fully disclose the escrowed private keys in the case of guilty users. The paper also proposes methods for constructing practical trapdoor Boolean permutations with a low storage complexity. Apart from the proposal of the key escrow protocol itself, this paper describes some of the key properties of Boolean permutations which make them suitable for their use in the design of cryptosystems.