The purpose of this paper is to establish variational principles for the mechanical behavior of two-phase random elastic lattices. By restricting the attention to the systems characterized by second-order statistics, the variational bounds on the stored energy of the Hashin-Shtrikman-Willis type are established using basic tools of structural statics and linear algebra. Accuracy of the improved bounds is verified against elementary estimates as well as detailed Monte-Carlo simulations. Finally, selected numerical results related to the accuracy of the bounds are presented.</p