Constituent Search via Attributes

Greetings-

I can easily perform 'fluent' type constituent searches against the API from my own application, but I'm wondering if anyone has ever done any searches based on Attributes. So, I know the name of the Attribute (RE_Cons_ID) I'm trying to search, but don't know if there is a mechanism in the Tess API (REST or SOAP) to allow this.

Thanks for any info!

Jason