Title :
Shamir´s shared secret scheme in GF(pm)
Author :
Chor, Leong Peng ; Chong, Tan Peng
Author_Institution :
Sch. of Applied Sci., Nanyang Technol. Univ., Singapore
Abstract :
A. Shamir´s (1979) shared secret scheme is adapted to operate over an extension field GF(p)[x]/xm-ω 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 ω 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
Keywords :
cryptography; digital arithmetic; interpolation; microcontrollers; smart cards; 8-bit microcontrollers; built-in byte-multiply instruction; extension field; low-end smart card; memory trade-off; multiplicative inverse; pre-computation; pre-computed values; shared secret scheme; threshold scheme; Acceleration; Arithmetic; Computer aided instruction; Cryptography; Equations; Galois fields; Interpolation; Polynomials; Smart cards; Writing;
Conference_Titel :
TENCON 99. Proceedings of the IEEE Region 10 Conference
Conference_Location :
Cheju Island
Print_ISBN :
0-7803-5739-6
DOI :
10.1109/TENCON.1999.818451
