Compact signatures and key recovery