Are there any public key signature schemes that can be compared blindly or partially homomorphically based on the private key without knowing the private key?
Example: let's say I derive a public key from a private key via a secret seed "haha this is a secret 1001" I then derive another public key from another secret seed "haha this is a secret 1002". I then want to be able to compare the public keys lexicographically without knowing these seeds.
Being able to compare the signatures would also work, but only if they can somehow be compared on the basis of the seed used to create the key pair and not on the basis of what is signed.
A little bit of a weird question, but my intuition says this might exist.
I thought of one solution but it's not very efficient. You could mandate a mapping from sortable secret keys to integers from say 0 to 2^32-1 (32 bits). Then you could just brute force search by hashing the secret keys until a public key is found whose least significant bits correspond to the ordinal. You'd then store the number of hashes required alongside the public key and compare on the public key's least significant N bits.
A more efficient way would be preferable of course.
A description of the real world application might be helpful.
I want to be able to secure a distributed decentralized database against naive sorts of denial of service attacks and collision attacks.
It's a system that maps plain text keys to plain text values but uses a hash of the key to encrypt the value and then indexes entries by a hash of the key. This means the plain text key is hidden and the value is unreadable to anyone who doesn't know what key they're looking for. (This is itself not an uncommon technique in e.g. shared deduplicating storage systems.)
BUT... even if someone doesn't know the key they could add bogus entries with what looks like the same key (its hash) and nonsense values. This would pollute the cache with junk, waste space and bandwidth, etc.
So I have this idea. Take the plain text key, hash it, use part of the hash to encrypt the value, and then use another part of the hash to derive a key pair. Then sign the entry with that key pair. Use the public key from this pair as the encrypted key in the key/value store.
This means that you cannot create valid entries for a given plain text key unless you know that key, but you can prove that you know a key without revealing it.
The sortability desire comes from a desire to support ordered iteration queries in this cache. So I want people who know a given plain text key to be able to ask for it and all the keys greater than it or all the keys between two values. This is basically blind/homomorphic querying but with this weird twist as described above.