Proxy signatures have been extensively used to solve authentication issues in mobile agent applications and authorization problems in distributed systems. However, conventional proxy signatures use traditional public key cryptosystems and are quite heavyweight. Thus, a direct application of these traditional signatures face significant performance challenges when applied to resource constrained ubiquitous computing environments. In this paper, we introduce the use of an efficient cryptographic primitive from linear feedback shift register (LFSR) sequences to build lightweight proxy signatures, suitable for resource constrained devices. We present a novel third-order LFSR sequence-based, 2-party signature scheme, SCLFSR, following a well-known Schnorr signature scheme. Using SCLFSR, we construct an efficient proxy signature, PCLFSR, which can serve as a protocol building block for performance sensitive ubiquitous computing applications. The scheme, PCLFSR, is also the first construction of a proxy signature using primitives from LFSR sequences. We perform extensive theoretical analysis including correctness and security of PCLFSR and also present a performance (computation and communication costs, storage overhead) comparison of the proposed scheme with well-known traditional constructions.