What is the minimum number of unique pairs of
inputs to a one-time pass needed to verify that a secret is equal to a given
s where the output is an integer with of at most
digits base-10 digits.
My back-of-a-napkin calculation is the ceiling of:
s)) ÷ log10(
For example, in the case where the secret is a 64 bit integer (264 cardinality) and the number of base-10 digits is 6 (106 cardinality), then
ceiling(64/6) = 11 pairs of unique inputs that result in the same known digests indicates that the secrets are equal.
s is from the ASCII set and a maximum length of 100 characters then the cardinality would be 127100 and there are 6 base-10 digits then the number of digest/input pairs needed to verify equality of secrets be ~ 127100 / 106 (i.e. "hard")?
I might be way off in my calculations here, but I was just curious.
Edit: Here is my rationale for the napkin calculation.
With every successive
input that equals a
digest we can reduce the space of the
secret accordingly. The question is whether the space decreases linearly, exponentially, polynomially, or otherwise.
Where the cardinality of both the secret and output are the same, then we can verify that we have the secret with one pair of input and output.
If the cardinality of the secret is an iota larger than the output, we need two pairs.
If the cardinality of the secret is double the cardinality of the output, we still need two pairs.
If the cardinality of the secret is double plus an iota, we need three pairs.
And so on.
It would seem to be provable inductively.
In other words, there is an homomorphism from each pair of (input, digest) that maps to a space the size of the output cardinality on the secret space. Each pair therefore reduces the secret space by the size of the homomorphism (i.e. the cardinality of the output).
So the calculation to be answered is how many times the cardinality must be reduced in order to cover the entire secret space, and my thinking is:
cardinality(s) / 10digits?
EDIT Upon consideration the cardinality of the secret is at most the cardinality of the resultant hash, which for the OTP linked example is SHA1 and known to be reducible to around 261.
Thus the napkin-based complexity, if correct, would be
log2(2^60) ÷ log10(6) ~= 10.167.
The answer then to the specific example of the OTP linked (the one used by Google Authenticator and others) is: One will need eleven inputs and digests to confirm that one has the secret-as-hashed.