Cryptographic hash with ability to ignore specific bits based on a hidden pattern? I'm looking to use password-style hashing to validate an environment, where some parts may be irrelevant. For example:

requirement = 0b1010
pattern = 0b1011
mask( a, b ) = a &amp; b
hash( a ) = &lt;any cryptographic hash&gt;
condition = hash( mask( requirement, pattern ) )

# public
environment = 0b1110
hash( mask( environment, pattern ) ) == condition
-&gt; true


So for the requirement 0b1010 and pattern 0b1011, both environments 0b1010 and 0b1110 would match (though typically there would be many more possibilities, since I expect only a small proportion of an environment to be relevant for a particular test)

The pseudo-code above would accomplish my goal, but it requires the pattern to be available in plain-text (since it must be applied to the given environment directly). The final check is performed publicly, and I would like to hide the pattern at this point, i.e.:

mask( a, b ) = ???
hash( a ) = ???
encryptedPattern = ???
condition = mask( hash( requirement ), encryptedPattern )

# public
environment = 0b1110
mask( hash( environment ), encryptedPattern ) == condition
-&gt; true


The ultimate brute-force approach would be to generate salted hashes for every matching environment (doubling-up some possibilities to hide the information about how many bits the pattern masks out) and test them all in-turn, but clearly this isn't practical once more than a few bits are considered irrelevant.

I haven't been able to find anything on hashes constructed to have deliberate collisions, or accept ranges, and I don't believe it would be possible to retain positional information through a hash while maintaining irreversibility. At the same time, this feels like something which has probably already been studied, and I'm just missing the relevant terminology to find it.

Is there any existing work on this type of check, or methods which could be extended to support it? Alternatively, is it provably impossible?



For context, my eventual plan is to extend this by checking hash( mask( hash( environment ), encryptedPattern ) ) == hash( condition ), and use the unhashed condition (which would only be available by getting the "password" correct) as a key to decrypt other data.
Suppose you had such a hash. Then anyone who knew some value for which the condition matched could find out the full pattern/mask:


You know some environment for which mask(hash( environment ), encryptedPattern ) == encryptedCondition.
You can flip one bit at a time, compute the masked hash, and see if you still get a match. If you do, that bit was masked out in the (unencrypted) mask pattern.


So possibly what you want is impossible. However, if you only need the pattern to remain hidden from those who do not know any matches, it may be possible using homomorphic encryption.


Take a suitable homomorphic encryption system that allows computing ANDs and verifying the results*. Encrypt the mask m = E(pattern) and the condition c = E(requirement).
The user encrypts a value E(environment), ANDs with the mask and compares to the condition: E(environment) &amp; m == c.


* The system must be deterministic and have E(x) &amp; E(y) = E(x&amp;y).

(Note: the use of deterministic encryption means that a user can guess and test values against pattern and requirement. This is quite weak, but conceivably there could be applications.)