We present PFLASH, an asymmetric digital signature scheme appropriate for smart card use. We present parameters for several security levels in this low resource environment and bootstrap many technical properties (including side-channel resistance) exposed in the evaluation of predecessors of this scheme.

PFLASH is a multivariate signature scheme with a specific set of parameters. Specifically, PFLASH is a pC^∗− scheme which means that geometrically the scheme can be viewed as a morphism of a monomial permutation, restricting the domain and range to two subspaces of an n-dimensional vector space over a finite field F_q.

PFLASH is a direct descendent of the SFLASH signature scheme which was recommended by NESSIE in 2003 and subsequently broken in 2007. Since that time we have developed a greater understanding of security for these so called “big field schemes.” PFLASH provably resists a large class of attacks on multivariate cryptosystems, a class which includes all known attacks on multivariate cryptosystems. While this doesn’t constitute a guarantee of the security of PFLASH, it does imply that any attack on the system will require a fundamental mathematical advance which the scientific community has not discovered in the nearly two decades since the first suggestion of pC^∗− schemes.

The performance of PFLASH is comparable to that of its parent SFLASH, being roughly q/2 times slower. This level of efficiency still makes PFLASH faster than RSA and far easier to implement on a smart card without an arithmetic coprocessor. The public key size is far larger than RSA, but the scheme far outperforms RSA, does not suffer nearly as much to poor random number generation and still fits easily on the cheapest smart cards.

Optimization of this scheme and simulations in the smart card environment is a continuing project the results of which will be included in the full version of this manuscript.