Thanks Erik, but it's not exactly that. It's a more complex scheme.
I'm sending data (let say items) from one party to another (for
example party0 and party1) through "Proxy". Each item has its own id.
Another party is a "Comparator". Comparator compares data (with
additional common random data) hashes from party0 and party1 not
knowing the source data and says to proxy which id is a duplicate
(party1 already has it) and proxy drops this item. It's a part of
bigger scheme and its aim is to remove duplicates. And yes - false
collisions are a problem, but statistically not significant.
I used to use MD5 hashes. Now I'm using Alder32 checksum from VMPC one
way function output.
Regards,
Zacheusz Siedlecki
On Mon, Dec 28, 2009 at 4:05 AM, Erik Heidt <erik.heidt (at) artofinfosec (dot) com [email concealed]> wrote:
> Zacheusz,
> Let me restate the question to ensure I understand it...
> 1. You have a list of things x1,x2,...,xn
> 2. There may be duplicate items in this list
> 3. The items in the list are complex data structure and do not lend
> themselves to quick comparison (such as integer)
> Your plan is to create a hash of each item ( h1 for x1, h2 for x2, etc... )
> and then compare the hash. Is this correct ?
> If so...
> - Not all Hash functions are cryptographic. I think you would be better off
> using a non-cryptographic hash for the de-duplication portion of your
> project. (more on hashes in
> general http://en.wikipedia.org/wiki/Hash_function)
> If you items (x1, x2,... ) are relatively small I would probably recommend
> using a simple 32-bit checksum
> If the items are large, I would recommend using CRC-32 (and finding/using
> public code)
> If you are storing the items in a RDBS, I would check to see what hashes the
> db can provide
> If the hash h1 != h2 then you are pretty sure x1 != x2, but if h1 == h2 you
> have to check byte for byte if x1 == x2 or not (false collision). As a
> result, the thing that you are going to have to balance is how fast the hash
> process is vs. how often (and time consuming) the byte by byte compare is.
> (I think that CRC-32 will give you much lower false collisions, but probably
> take more time to perform the actual hashes.)
> Personally, I would start with a 16 or 32 bit checksum and see if the hash
> performance and collision rates are adequate. If they are not, I would
> change the hash to CRC-32.
> I hope this helped.
> Erik
>
>
> On Sun, Dec 27, 2009 at 3:09 PM, Zacheusz Siedlecki <z.acheusz.s (at) gmail (dot) com [email concealed]>
> wrote:
>>
>> I've implemented a multiparty exploration of association rules. It
>> involves computationally expensive encryption while calculating a set
>> union. At first I want to delete most of duplicates to eliminate the
>> cost of encryption of them, but comparison has to be very fast to
>> achieve profit.
>> Regards,
>> Zacheusz
>>
>> On Sun, Dec 27, 2009 at 6:57 AM, Gregory Rubin <grrubin (at) gmail (dot) com [email concealed]> wrote:
>> > I think that a critical part of this question is "What are you trying
>> > to accomplish and why?" You state that you need a secure comparison,
>> > but that collision resistance doesn't matter. You also seem to be
>> > extremely concerned with speed. While there are times when you need
>> > blazing fast throughput, you can almost always afford the time
>> > necessary to do good crypto. (They aren't exactly on wimpy machines
>> > either.)
>> >
>> > With some answers and guidance around there, why might be able to
>> > better guide you.
>> >
>> > So, what are you doing and why?
>> >
>> > Greg
>> >
>> > On Wed, Dec 23, 2009 at 2:56 PM, Zacheusz Siedlecki
>> > <Zacheusz.Siedlecki (at) gmail (dot) com [email concealed]> wrote:
>> >> I'm looking for fast one way hash function for secure
>> >> comparison.Collision resistance doesn't matter. It should be much
>> >> faster than MD5.
>> >> The scheme works like this: two parties compute hash of their data and
>> >> send to a third party then the third party compares the data not
>> >> knowing the original data.
>> >> Can anybody help me, please?
>> >> Regards,
>> >> Zacheusz
>> >>
>> >
>
>
I'm sending data (let say items) from one party to another (for
example party0 and party1) through "Proxy". Each item has its own id.
Another party is a "Comparator". Comparator compares data (with
additional common random data) hashes from party0 and party1 not
knowing the source data and says to proxy which id is a duplicate
(party1 already has it) and proxy drops this item. It's a part of
bigger scheme and its aim is to remove duplicates. And yes - false
collisions are a problem, but statistically not significant.
I used to use MD5 hashes. Now I'm using Alder32 checksum from VMPC one
way function output.
Regards,
Zacheusz Siedlecki
On Mon, Dec 28, 2009 at 4:05 AM, Erik Heidt <erik.heidt (at) artofinfosec (dot) com [email concealed]> wrote:
> Zacheusz,
> Let me restate the question to ensure I understand it...
> 1. You have a list of things x1,x2,...,xn
> 2. There may be duplicate items in this list
> 3. The items in the list are complex data structure and do not lend
> themselves to quick comparison (such as integer)
> Your plan is to create a hash of each item ( h1 for x1, h2 for x2, etc... )
> and then compare the hash. Is this correct ?
> If so...
> - Not all Hash functions are cryptographic. I think you would be better off
> using a non-cryptographic hash for the de-duplication portion of your
> project. (more on hashes in
> general http://en.wikipedia.org/wiki/Hash_function)
> If you items (x1, x2,... ) are relatively small I would probably recommend
> using a simple 32-bit checksum
> If the items are large, I would recommend using CRC-32 (and finding/using
> public code)
> If you are storing the items in a RDBS, I would check to see what hashes the
> db can provide
> If the hash h1 != h2 then you are pretty sure x1 != x2, but if h1 == h2 you
> have to check byte for byte if x1 == x2 or not (false collision). As a
> result, the thing that you are going to have to balance is how fast the hash
> process is vs. how often (and time consuming) the byte by byte compare is.
> (I think that CRC-32 will give you much lower false collisions, but probably
> take more time to perform the actual hashes.)
> Personally, I would start with a 16 or 32 bit checksum and see if the hash
> performance and collision rates are adequate. If they are not, I would
> change the hash to CRC-32.
> I hope this helped.
> Erik
>
>
> On Sun, Dec 27, 2009 at 3:09 PM, Zacheusz Siedlecki <z.acheusz.s (at) gmail (dot) com [email concealed]>
> wrote:
>>
>> I've implemented a multiparty exploration of association rules. It
>> involves computationally expensive encryption while calculating a set
>> union. At first I want to delete most of duplicates to eliminate the
>> cost of encryption of them, but comparison has to be very fast to
>> achieve profit.
>> Regards,
>> Zacheusz
>>
>> On Sun, Dec 27, 2009 at 6:57 AM, Gregory Rubin <grrubin (at) gmail (dot) com [email concealed]> wrote:
>> > I think that a critical part of this question is "What are you trying
>> > to accomplish and why?" You state that you need a secure comparison,
>> > but that collision resistance doesn't matter. You also seem to be
>> > extremely concerned with speed. While there are times when you need
>> > blazing fast throughput, you can almost always afford the time
>> > necessary to do good crypto. (They aren't exactly on wimpy machines
>> > either.)
>> >
>> > With some answers and guidance around there, why might be able to
>> > better guide you.
>> >
>> > So, what are you doing and why?
>> >
>> > Greg
>> >
>> > On Wed, Dec 23, 2009 at 2:56 PM, Zacheusz Siedlecki
>> > <Zacheusz.Siedlecki (at) gmail (dot) com [email concealed]> wrote:
>> >> I'm looking for fast one way hash function for secure
>> >> comparison.Collision resistance doesn't matter. It should be much
>> >> faster than MD5.
>> >> The scheme works like this: two parties compute hash of their data and
>> >> send to a third party then the third party compares the data not
>> >> knowing the original data.
>> >> Can anybody help me, please?
>> >> Regards,
>> >> Zacheusz
>> >>
>> >
>
>
[ reply ]