Shamir's shared secret scheme in GF(p/sup m/)
Leong Peng Chor, Tan Peng Chong · 2003
A. Shamir's (1979) shared secret scheme is adapted to operate over an extension field GF(p)[x]/x/sup m/-/spl omega/ where p is an odd prime p. Both multiplication and multiplicative inverse in such a field can be efficiently computed on 8-bit microcontrollers with appropriate choice of p and exploiting the built-in byte-multiply instruction. In applications with fixed p, m, and /spl omega/ further acceleration can be achieved via a small set of pre-computed values. Pre-computation also eliminates the necessity for division at the sub-field level. A brief discussion on efficiency and memory trade-off is provided. It is found that reconstruction of a 128-bit secret under a (2,3) threshold scheme on a low-end smart card is not impractical.