N.M. Stat. § 46-6-1
That whenever any recognizance, stipulation, bond or undertaking is required to be given by the laws of this state, conditioned for the faithful performance of any duty or from doing or refraining from doing anything in such recognizance, stipulation, bond or undertaking specified, which bond is now required or permitted to be given with one or with two or more sureties, the execution of the same, or the guaranteeing of the performance of the condition thereof shall be sufficient if executed or guaranteed solely by a corporation incorporated under the laws of the United States or of any state or territory having power to guarantee the fidelity of persons holding positions of public or private trust; and to execute guarantee bonds and undertakings in special proceedings, and in all judicial proceedings: provided, that such company is qualified under the act of congress entitled "An act relative to recognizances, bonds and undertakings, and to allow certain corporations to be accepted as surety thereon," approved August 13, 1894: and, provided further, that said corporation, if not incorporated under the laws of the state of New Mexico, shall comply with the laws of the state authorizing foreign corporations to do business therein: and, provided further, that all recognizances, stipulations, bonds or undertakings executed under the provisions of said sections shall be subject to the approval and acceptance as to the form and sufficiency of the execution thereof by the person or authority by law authorized to approve and accept the same.
NMS § 46-6-1