A variant of the substitution-permutation encryption network, which incorporates random permutations, is presented and shown to retain, with a very high probability, the cryptographically important property of completeness after a small number of rounds. Although the increase in crypto-cost is moderate, the advantage of the new variant is twofold, in that a proof for the freedom from an intentional trapdoor is provided and the network can offer a higher level of cryptosecurity.