1
$\begingroup$

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.

Edit:

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.

Edit #2:

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.

$\endgroup$
  • $\begingroup$ Does the ordering of the comparison have to be the same as the lexicographical ordering of the secret seeds? $\endgroup$ – poncho Jan 1 at 18:38
  • $\begingroup$ That would be preferable. If not there needs to be some way of translating. $\endgroup$ – Adam Ierymenko Jan 2 at 1:51
  • $\begingroup$ I edited and added one conceivable way but one that's maybe a bit slow. $\endgroup$ – Adam Ierymenko Jan 2 at 1:52
  • $\begingroup$ Added real world use case info since this might also help. $\endgroup$ – Adam Ierymenko Jan 8 at 14:01
  • $\begingroup$ In your real world example (which I assume details the real problem you're solving), I'm missing why hiding the actual public key is important. If someone where able to deduce the actual public key value from the database entries, what security goal do not you achieve? $\endgroup$ – poncho Jan 8 at 16:47
1
+50
$\begingroup$

If I understand you correctly, you want that given $\mathit{pk}, \mathit{pk}'$, one can publicly decide whether or not $\mathit{sk} < \mathit{sk}'$ (lexicographically) for the corresponding secret keys.

Such a signature scheme would inherently be insecure. This is because given your public key $\mathit{pk}^*$, anyone would be able to run a binary search to find the underlying secret key $\mathit{sk}^*$.

For example, the attacker could choose $\mathit{sk} = 10000000$, compute the corresponding $\mathit{pk}$ and then run the lexicographic comparison on $\mathit{pk}$ and $\mathit{pk}^*$ to find out whether or not your key $\mathit{sk}^*$ starts with a 1. If so, checking whether $\mathit{sk}^*$ is still lexicographically larger than $11000000$ can be done similarly and reveals the next bit, etc.

After $n$ comparisons (assuming n-bit secrets), the secret key is revealed. Of course, this also generalizes to larger alphabets.

$\endgroup$
  • $\begingroup$ Hmm... yeah I was thinking about it and came to a similar conclusion. $\endgroup$ – Adam Ierymenko Jan 9 at 15:18
  • $\begingroup$ I came up with a different scheme: use a longer identifier that combines a hash plus an ordering value followed by a public key. That way the identifiers sort properly but are still blinded with regard to significant identifying information. $\endgroup$ – Adam Ierymenko Jan 9 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.