Re: Security of Digest Algorithm

• From: Sergey Melnik <melnik@db.stanford.edu>
• Date: Wed, 10 May 2000 12:14:39 -0700
• To: "McBride, Brian" <bwm@hplb.hpl.hp.com>
• CC: "RDF Interest (E-mail)" <www-rdf-interest@w3.org>
• Message-ID: <3919B51F.AFD4B4E6@db.stanford.edu>

Brian,

thank you very much for your effort. Clearly, naive XOR is a flop. My
goal was first to identify the desired properties of a model digest
algorithm (given statement digests). These are:

1. The algorithm must be incremental i.e. suitable for billions of
statements.
2. The algorithm is independent of the order in which statements are
introduced to the algorithm.
3. [optional] The algorithm is reversible. There exist a function R so
that given a model digest D(M) and a statement digest D(s) for s
contained in M, R(D(M), D(s)) = D(M-s).

I'm sure there exist plenty of secure algorithms that satisfy 1 and 2
(just need to find time to look them up...), however, the security may
be compromised by insisting on 3.

I'd appreciate any ideas/suggestions!

Sergey

Received on Wednesday, 10 May 2000 15:17:01 UTC