  Digital signatures are basic cryptographic tools to provide authentication
and integrity in the emerging ubiquitous systems in which resource-constrained
devices are expected to operate securely and efficiently. However, existing
digital signatures might not be fully practical for such resource-constrained
devices (e.g., medical implants) that have energy limitations. Some other
computationally efficient alternatives (e.g., one-time/multiple-time
signatures) may introduce high memory and/or communication overhead due to
large private key and signature sizes.
  In this paper, our contributions are two-fold: First, we develop a new
lightweight multiple-time digital signature scheme called Signer Efficient
Multiple-time Elliptic Curve Signature (SEMECS), which is suitable for
resource-constrained embedded devices. SEMECS achieves optimal signature and
private key sizes for an EC-based signature without requiring any EC operation
(e.g., EC scalar multiplication or addition) at the signer. We prove SEMECS is
secure (in random oracle model) with a tight security reduction. Second, we
fully implemented SEMECS on 8-bit AVR microprocessor with a comprehensive
energy consumption analysis and comparison. Our experiments confirm up to 19x
less battery-consumption for SEMECS as compared to its fastest (full-time)
counterpart, SchnorrQ, while offering significant performance advantages over
its multiple-time counterparts in various fronts. We open-source our
implementation for public testing and adoption.
