Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question
From: Maaartin on 17 Apr 2010 15:39
On Apr 17, 7:37 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> Unless I err, finding collisions is not quite as easy, because f1 and f2
> are bound to have only 0 and 1 in their ternary expression, and it is
> extremely unlikely f2 thus constructed will match this condition.

This is what I missed.

> >> Note: just change LCM(p-1,q-1) to (p-1) if n is a prime p.
> >> Note: I am not optimistic that replacing 3 by a bigger value might be
> >> enough to get rid of the requirement that the factorization of n is unknown.
>
> > IIUYC, it can't help, you only need to express f to a different base.
>
> I'd say that it can at best increase slightly the minimum z for the
> attack to work and/or the memory resources needed by the attacker.

With z = ceil(log(LCM(p-1,q-1)) / log(2)) + 1 is 2^^z > LCM(p-1,q-1),
so f1!=f2 exist with the same remainder, so there're collisions
(independent of the base). This says nothing about the complexity and
nothing about the minimum z for the second preimage, but it's not
important. It seems like using prime modulus is no good idea.

> I'll try to have a look at that. Now it is time for some social
> activity, and the next 10 days will be busy professionally.
>
> Although not linked to a reference hard problem, your idea of matrix of
> elements of GF(256) is interesting, and computationally practical.

Probably using a matrix over GF(p) with some p allowing for fast
modular reduction could be faster. For example, with p=2^^130+5 (taken
from Poly1305), a 2x2 matrix would suffice for 512 bits. But I have no
idea, what field would give more security, if any.
From: NoXenu on 13 May 2010 06:27
On Apr 15, 6:21 pm, Maaartin <grajc...(a)seznam.cz> wrote:
> 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.

Even if P != NP, their result may not be sufficient for the existence
of practical OWFs.
Complexity theoretic OWF = "in the worst case" (there exists few
inputs where the preimage cannot be computed efficiently)
Cryptographic OWF = "in the average case" (for any random input,
preimage cannot be computed)


to OP: can you describe exactly what properties you need for the OWF
(or `hash')? It is not fully clear what you have in mind, since you
didn't define what are inputs, outputs, a, k, n etc.


From: Maaartin on 17 May 2010 04:39
On May 13, 12:27 pm, NoXenu <amitabh...(a)gmail.com> wrote:
> to OP: can you describe exactly what properties you need for the OWF
> (or `hash')? It is not fully clear what you have in mind, since you
> didn't define what are inputs, outputs, a, k, n etc.

Sure. Moreover, what I wanted is not as associative function, I
described it wrongly. I wanted a pair of functions (F, H) where F is
associative and

H(concat(a, b)) = F(H(a), H(b))

holds for any the messages a and b of length divisible by N, where N
is a fixed constant (something like 1 kB). Such a hash function allows
a sort of fast and simple incremental computation, e.g., for files
where data gets appended - you only need to remember H(m'), where m'
is m truncated to the largest possible multiple of N.

Tree hashing allows a similar incremental computation, but you need to
remember more intermediate data.


First  |  Prev  | 
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