Important disclaimer: it's been a long time since I was looking into searchable encryption, and I'm not well-informed on the topic. Don't count on my understanding here; it's likely I've missed some things in this answer.
Searchable encryption is hard, and you're asking for a lot. As of Jan 2025, I'm not aware of any published library that can achieve this. It might1 be technically possible to do this securely - meaning, it achieves all your goals while the security of the encryption is weakened by no more than the degree inherent in the attacker knowing that the plaintext is constrained to values which match the validation rules - but the compute costs could rapidly become enormous, especially with large messages and/or variable-length regexes.
Searchable encryption approaches do exist, and more advanced ones are an area of active research. However, they tend to have serious limitations in confidentiality (exposing information about the ciphertext even if no specific byte range is necessarily decryptable), practicality (requiring excessive storage space or compute time), and/or applicability (usable only with restricted search queries, messages that match certain common structures, or similar). Regexes in particular are hard. Searchable encryption can also sometimes run into the problem of only getting "fuzzy" matching, which can result in false positives (in your scenario, a valid input that incorrectly gets flagged as invalid).
In this answer, I'm going to be looking at the two approaches that @Ja1024 shared: a 2014 paper called "RESeED: A secure regular-expression search tool for storage clouds" by Salehi et al, and a 2017 paper titled "Pattern Matching on Encrypted Streams" by Desmoulins et al, which introduces "Searchable Encryption with Shiftable Trapdoors" or SEST. I'm not sure2 that either is fully capable of solving your need. However, even if not, SEST is remarkably close, and it may be in the future that some such searchable encryption algorithm is widely available.
RESeED proposes building on a familiar form of searchable encryption, "public key encryption with keyword search" or "PEKS", wherein strings you may want to search for are encrypted along with the message. RESeED introduces some elements to make the search more generic - allowing searching for keywords, and regular expressions whose tokens are such "keywords", that were not known at encryption time - without greatly bloating the storage space.
That's very impressive, but it contains some severe limitations. First, it uses a fuzzy match; the purpose of the algorithm is to support creating essentially a search index that allows the data owner to identify encrypted messages matching a particular search query (without revealing either the messages or the query to the storage provider), whereupon the owner downloads the identified messages and presumably decrypts them, searches them directly, and throws out any false positives. That's not the use case you're looking at here, and although efforts can be taken to reduce the risk of false positives, it comes at the cost of storage size and compute and only asymptotically approaches zero (though being close enough to zero is in fact good enough; that's the principle underlying e.g. all password hashing and digital signing based on secure hash functions). Second, it depends on an "alphabet division" whereby the symbols of the message are divided into "core" symbols that make up the searchable tokens, and "separator" symbols that delimit tokens. This is fine if (e.g.) your messages consist of English text; separators would be characters like punctuation and whitespace, while everything else (printable) would be core. Unfortunately, that means you can't really search on substrings of a token, and in particular doesn't really allow searching for a specific character (symbol) that appears embedded in various tokens (words); you would need to search for all possible tokens containing that symbol. Furthermore, while I'd need to do more reading to confirm this3, I suspect that the existence of the data structures involved here - which functionally implement an encrypted search index - leak data if an actor without the key is permitted to perform the searches; such an "attacker" could infer things about the tokens based on how many messages they appear in (using e.g. word frequency statistics) and thus about those messages themselves (especially if they can watch the structures update as new messages are added).
SEST is more promising. It focuses on a completely different use case, where the key holder and message transport provider (or "gateway") are in a cooperative but mutually untrusting relationship, and the gateway needs to inspect the encrypted traffic for various contents without decrypting it. This much more closely matches your use case. It's also far more focused on preserving the confidentiality of the messages. However, SEST still differs from your scenario somewhat: it proposes a separate sender and recipient, and uses public key cryptography rather than symmetric encryption; these may or may not pose a problem. SEST is also less focused on regular expressions, but in a way that's probably beneficial to your use case; it focuses on the ability to search out arbitrary patterns - including single symbols and wildcards - but this can be used to build regular expression matches too.
However, SEST also has limitations. It requires public keys linear in the size of the message, which is potentially very large. The ciphertext is also large, though again at least it is only linear in size of the message. The search process itself is expensive, especially for short "keywords" (queries, which can contain wildcards) in long messages; the optimizations that can be performed for plain-text matching aren't available. (On the other hand, it is at least highly parallelizable.) A potential further complication is that SEST is built using "trapdoors": search query values that are applied to the ciphertext in order to find matches, but which can only be created by the holder of the private key (recipient), and are not readily inspectable by the gateway. The gateway (who, like the sender, has the public key) is able to verify simple trapdoors by encrypting strings that should or should not match the trapdoor and testing them, but this requires using public key encryption rather than symmetric keys. It also is not clear to me that this is secure against a scenario wherein the recipient (user), hoping to sneak something past the gateway (storage service), creates a trapdoor that appears to match the gateway's requested query but doesn't reliably do so. It's easy - though somewhat computationally expensive - to test for that with simple search queries (like "contains the character 'x'"), but regexes are much harder. As an example, the difference between the regexes /foo.*bar/ and /foo[^~]*[^q]*[^&]*bar/ is quite hard to experimentally detect, in terms of what they'll match. A gateway (validator) that thinks it has a trapdoor for the former but actually has one for the latter will miss an attacker who intentionally embeds the characters ~, q, &, in that order, in between the forbidden foo...bar portions. Given how SEST works, and depending on the regexes that you're actually checking, that might not be a problem in practice (you can check for /foo.*bar/ by separately checking for foo and bar, which are "normal" search strings and thus relatively easy to validate trapdoors for, and comparing the indices at which they appear)... but it might also be a huge problem in practice. You'd also need to figure out a way to either convert your design to asymmetric cryptography, or wrap SEST within symmetric cryptography, without compromising the security of the design.
With all that said, the fact that there have been at least4 two papers on searchable encryption with regular expressions, one now over a decade old, is hopeful. You should definitely do some research and may want to come back with a more specific question,
1 I stress "might" here for two reasons. First, because this is largely untested academic cryptography, and much likelier than established primitives and constructions to contain errors that weaken the security (and even if the design is secure, any given implementation may well not be, as they won't yet be extensively reviewed). Second, because the specific properties you are requesting don't exactly match any cipher I'm aware of, and trying to adapt an advanced cryptographic primitive to a different use case than intended is fraught indeed.
2 I am not a cryptographer, and my work with cryptography is generally confined to the application of well-known primitives and constructions to specific, but not especially novel, applications. This is well outside of that, and you should consider seeking those with greater expertise.
3 Specifically, I'd need to do a bunch of reading about PEKS, which I expect leaks considerable privacy when used with arbitrary, rather than specific predefined, tokens.
4 I'd love to dig into this topic more, but it's already taken me multiple hours of research to write this answer, which is way more than I really more of my weekend than I endorse spending on a single StackExchange answer, no matter how intriguing.
