[p2p-hackers] Homomorphic hashing and fountain codes - implementation question

[Hal Finney]

Nick Johnson writes:
> If I can be forgiven a stupid question:
> I'm reading in detail the paper 
> (http://www.scs.cs.nyu.edu/~mfreed/docs/authcodes-ieee04.pdf) on 
> homomorphic hash functions for use with Digital Fountain codes in 
> preparation for implementing it. The problem I'm coming up against is in 
> the description of the modifications to the Fountain code described on 
> page 5. With their example settings, 256 bit long sub-blocks are now 
> added modulo a 257 bit prime. This makes sense - what I don't get is how 
> to encode the result in 256 bits! What is one supposed to do if the sum 
> of the selected blocks overflows 256 bits?

I think... you would have to plan on allocating 257 bits for the output
of this process.  Blocks would be 257 bits long.  I don't know if that
is a show stopper for an implementation.

There is a possible workaround.  You could choose a prime q which was
just barely, barely, barely 257 bits long.  Let it be 2^257 plus some
number less than 2^170 or so.  In other words, let the prime q start
with 1000000... for 80+ bits of zeros.  Now the chance of a random Z_q
value happening to be > 256 bits will be vanishingly small.

Unfortunately, files are not random.  Someone could choose a file which
had special values that would overflow 256 bits.

You could fix that by first pre-randomizing the file in some reversible
way.  A suitable cryptographic primitive is called an All Or Nothing
Transform.  See http://theory.lcs.mit.edu/~boyko/aont-oaep.html for
an example.

So you'd first AONT transform the file, which would randomize the values;
then you'd use this q for the coding, which could overflow in principle
but not in practice.  In the end, after reconstructing the file, you'd
reverse the AONT transform.

In your sci.crypt posting, you also asked:

> 1) The algorithm requires two primes q and p. These primes are known to
> both the publisher and the verifiers. Will security be reduced if the
> same primes are used for all publishers, or can a single pair of primes
> be used globally?

You should be able to use the same primes globally, if the security of
the size of your primes is adequate.

> 2) What level of security does this algorithm provide with p and q
> being 1024 bit and 257 bit, respectively? Eg, how many operations or
> how much computing time would be required to compute a collision? How
> does this fare with reduced lengths of p and q? 

It is a little hard to quantify.  The security will be the minimum of the
security levels of p and q against the discrete log problem.  For q it
is easy, it is half the size of q, or about 128 bits (i.e. 2^128 work to
break it).  That should be more than enough.  For p it is harder.  I think
most people would agree that a p of 1024 bits corresponds to a security
of perhaps 80-90 bits for discrete logs.  This is somewhat marginal.

I would suggest a p of more like 2048 bits, with a 256 bit q.  There have
been a number of proposals for theoretical factoring machines, most
of which could be adapted at somewhat greater cost to finding discrete
logs.  Many people today are worried that 1024 bit keys can no longer be
considered extremely safe.  Particularly if you use the same p throughout
the system, it would be wise to use something a little bigger.

Hal Finney