We show that supersingular Abelian varieties can be used to obtain higher MOV security per bit, in all characteristics, than supersingular elliptic curves. We give a point compression/decompression algorithm for primitive subgroups associated with elliptic curves that gives shorter signatures, ciphertexts, or keys for the same security while using the arithmetic on supersingular elliptic curves. We determine precisely which embedding degrees are possible for simple supersingular Abelian varieties over finite fields and define some invariants that are better measures of cryptographic security than the embedding degree. We construct examples of good supersingular Abelian varieties to use in pairing-based cryptography.