We explore ideas for speeding up HFE-based signature schemes. In particular, we propose an HFEv^− system with odd characteristic and a secret map of degree 2. Changing the characteristic of the system has a profound effect, which we attempt to explain and also demonstrate through experiment. We discuss known attacks which could possibly topple such systems, especially algebraic attacks. After testing the resilience of these schemes against F4, we suggest parameters that yield acceptable security levels.