Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question
From: Maaartin on 15 Apr 2010 05:48
Is there any cryptographic associative hash function? I'd like to have
a collision-resistant function, where the input would be a sequence of
fixed-size blocks (of a couple of KB), which would allow to compute
the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
It should work by first computing the hashes of all blocks using a
standard hash function and combining the hashes using an associative
(and non-commutative) operation.

I've only found very theoretic papers on associative complexity-
theoretic one-way functions proving their existence iff P!=NP, which
didn't help me at all.
From: Francois Grieu on 15 Apr 2010 08:30
On 15/04/2010 11:48, Maaartin wrote:
> Is there any cryptographic associative hash function? I'd like to have
> a collision-resistant function, where the input would be a sequence of
> fixed-size blocks (of a couple of KB), which would allow to compute
> the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
> It should work by first computing the hashes of all blocks using a
> standard hash function and combining the hashes using an associative
> (and non-commutative) operation.
>
> I've only found very theoretic papers on associative complexity-
> theoretic one-way functions proving their existence iff P!=NP, which
> didn't help me at all.

If the above theoretical results holds, you obviously won't come across
a practical associative hash function before the P!=NP debate is over;
don't hold your breath.

Francois Grieu
From: Maaartin on 15 Apr 2010 09:21
On Apr 15, 2:30 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> If the above theoretical results holds, you obviously won't come across
> a practical associative hash function before the P!=NP debate is over;
> don't hold your breath.

But they speak about complexity-theoretic functions, i.e., the
preimage can't be computed in polynomial time. AFAIK, there's no such
proof for any commonly used hash function. Whatever the polynomial
time should mean for fixed size hash.
From: Francois Grieu on 15 Apr 2010 11:26
On 15/04/2010 11:48, Maaartin wrote:
> Is there any cryptographic associative hash function? I'd like to have
> a collision-resistant function, where the input would be a sequence of
> fixed-size blocks (of a couple of KB), which would allow to compute
> the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
> It should work by first computing the hashes of all blocks using a
> standard hash function and combining the hashes using an associative
> (and non-commutative) operation.

A hash function H(a,b) = F(h(a),h(b)) with h any standard cryptographic
hash function and F an associative function would most likely not be
associative in the common definition: H(H(a,b),c)) = H(a,H(b,c)).

What would be your definition of "cryptographic associative hash
function" then ? Is it
- H(a) is a cryptographic hash function
- F is an associative function
- we define H(a,b) = F(H(a),H(b)), then
H(a,b,c) = F(H(a,b),H(c)) = F(H(a),H(b,c)) and so on
- some security property holds.

Which property ?

Francois Grieu
From: Maaartin on 15 Apr 2010 12:09
On Apr 15, 5:26 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> On 15/04/2010 11:48, Maaartin wrote:
> > Is there any cryptographic associative hash function? I'd like to have
> > a collision-resistant function, where the input would be a sequence of
> > fixed-size blocks (of a couple of KB), which would allow to compute
> > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
> > It should work by first computing the hashes of all blocks using a
> > standard hash function and combining the hashes using an associative
> > (and non-commutative) operation.
>
> A hash function H(a,b) = F(h(a),h(b)) with h any standard cryptographic
> hash function and F an associative function would most likely not be
> associative in the common definition: H(H(a,b),c)) = H(a,H(b,c)).

Right. In order to compute H(x) you need to split the message x in
fixed-sized blocks first, i.e., with x = concat(x[0], x[1], x[2], ...,
x[N-1]) compute F(h(x[0]), F(x[1], F(x[2], ....))) or in infix
notation h(x[0]) op h(x[1]) op ... op h(x[N-1]). Currently, I don't
care about messages with a size being not a multiple of the blocksize.

You may apply h only on arguments of the proper size.

> What would be your definition of "cryptographic associative hash
> function" then ? Is it
> - H(a) is a cryptographic hash function
> - F is an associative function
> - we define H(a,b) = F(H(a),H(b)), then
> H(a,b,c) = F(H(a,b),H(c)) = F(H(a),H(b,c)) and so on

Right, but only for a, b, and c consisting of a whole number of
blocks.

Let H(a)=h(a) for length(a) = blocksize, and let H(concat(a, b)) =
F(H(a), H(b)) for any a, b with a length being a multiple of the
blocksize. This definition is consistent because of the associativity
of F.

> - some security property holds.
> Which property ?

I don't know what is achievable. I'd like to have collision-
resistance, if possible.

Obviously, for a commutative F, collisions would be trivial, but I
want associativity and no commutativity.
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question