A threshold digital signature scheme for a smart card based system

This paper describes an efficient k-out-of-n threshold digital signature sc heme for a smart card based system where a signer uses multiple cards so th at the signature can be issued in a dependable manner. The main feature of our method is that it does not require a secret communication path among th ese cards in the signature issuing protocol, and that it requires low commu nication and computational complexity. Former is an advantage under the cur rent export control regulation which makes hard to export more than 56-bit cipher techniques, and latter is advantage over so-called robust signature.