[Cryptography] Security properties of unkeyed hash functions

Francisco Corella fcorella at pomcor.com
Wed Oct 19 17:50:17 EDT 2016


Hi all,

As part of research on remote identity proofing, we have come up with
the concept of a "rich credential": an enhanced cryptographic
credential that allows a subject to identify him/herself to a remote
verifier by proving possession of a private key, knowledge of a
password, and possession of one or more biometric features, without a
prior relationship between the subject and the verifier, with
biometric spoofing detection by the verifier.  The concept is
described in this blog post <https://pomcor.com/2016/10/18/rich-credentials-for-three-factor-identity-verification-without-prior-relationship/> and this paper <https://pomcor.com/techreports/RichCredentials.pdf>.

A rich credential is based on the same simple cryptographic primitives
as a traditional public key certificate: a certified key pair, a hash
function, and a digital signature by the issuer.  Yet it provides
unusual privacy features: selective disclosure of subject attributes
(as provided by anonymous credentials, but without unlinkability) and
selective presentation of verification factors.

The privacy features are achieved by means of a "typed hash tree", a
variation on a traditional hash tree that provides "omission-tolerant
integrity protection".  The paper includes a proof that a typed hash
tree can be used to represent a multiset of key-value pairs, in a way
that allows key-value pairs to be removed, but not added, without
modifying the root label.

While working out the proof we ran into the problem of how to
formalize the security properties of an unkeyed, or keyless, hash
function.  We worked around the difficulty by first formally proving a
result that relates the "addition intolerance" of a typed hash tree to
the structure of the tree without reference to any security
properties, then informally justifying corollaries based on security
properties that we do not define formally, including "collision
resistance", and either "cross-collision resistance" between two hash
functions or "preimage resistance of a hash function relative to a
random or pseudo-random number generator" (depending on how salts in
the tree are generated).

Cross-collision resistance is formalized in the online draft of Boneh
and Shoup’s Graduate Course in Applied Cryptography <https://crypto.stanford.edu/~dabo/cryptobook/draft_0_2.pdf> (Section 8.1) in
terms of their concept of a "system parameterization" (Definition
2.9).  I believe the concepts of "cross-collision resistance" and
"relative preimage resistance" are new.  It should be possible to
formalize them as well using the same concept of system
parameterization.  We hope to be able to do that in the future, then
formally prove the corollaries, unless somebody beats us to it :-)

Comments on any of this would be appreciated.  If anybody makes the
effort to check the proof of Theorem 1 (Section 5.4.3), beers will be
on us the next time we meet :-)

Francisco




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161019/0b825e11/attachment.html>


More information about the cryptography mailing list