Key predistribution is one of the most challenging issues for secure communication in wireless sensor networks. But most of existing schemes are not scalable due to their linearly increased communication and key storage overhead. Furthermore, these protocols cannot provide sufficient security when the number of compromised nodes exceeds a critical value. In this paper, we propose a polynomial-based key predistribution scheme using matrix decomposition. Our scheme guarantees that any two sensor nodes can find a shared key between themselves. The analysis in this paper indicates that the existing schemes require a large number of keys in each sensor node to display a comparable connectivity as the proposed scheme which allows almost 100% connectivity regardless of the number of keys, and it develops an efficient encoding mechanism to optimize the network-wide storage usage. On the other hand, compared with existing schemes, our scheme has better performance in network resilience.