Message-ID: <CADPMZDDRg45=Wmq7ENf97w=kSHt=Wik5s8S3bG-qm+9Zd_hrHw@mail.gmail.com>
Date: Tue, 13 Mar 2018 04:30:11 -0500
From: denis bider <denisbider.ietf@...il.com>
To: Poul-Henning Kamp <phk@....freebsd.dk>
Cc: discussions@...sword-hashing.net
Subject: Re: [PHC] How to: A super-efficient cryptographic accumulator?

Yeah, but... I'm *still* not so sure. :) People said we couldn't have a
digital currency either! The coins would be GIGABYTES in length! :D

This is not fractal compression because we do not intend to decompress. We
are definitely throwing away data. What we want is a compressed *oracle*,
however.

The size of X I estimated if using a hash function (8 bytes?!) was clearly
ridiculous. What I proposed was to generate X by brute-forcing it as a
counter input to a pseudo-random function that generates a string 32*N bits
in size. If N is the number of passwords we are encoding, then to encode 1
billion passwords, the random string needs to have 32 billion bits - and
they all must be zero. Clearly, an X that we arrive at this way must be
about 32 billion bits in size. So, uh... 4 gigabytes.

But what if... say... instead of a hash function - *mod N* arithmetic?

Suppose we represent the passwords we want to store using primes P1, P2,
... Pn. We generate:

X = P1 * P2 * ... * Pn *mod N*

Of course, when we do "*mod N*", we are losing information. But how fast?

Are you sure that arguments against fractal compression also apply to
highly lossy compression like this? ZIP won't compress a PNG, but JPG will
;)


On Tue, Mar 13, 2018 at 3:56 AM, Poul-Henning Kamp <phk@....freebsd.dk>
wrote:

> --------
> In message <CADPMZDBq_CsD2ztxBX4J0FZLyf8Stm+Bz=AOPs6
> Adq7frGmi1g@...l.gmail.com>, denis bider writ
> es:
>
> >For example, the best measure
> >for password safety is probably to prevent users from using any of
> billions
> >of known revealed passwords, but the compressed database is 5 GB in size:
> >[...]
> >Now. I sort of have this intuition that it=E2=80=99s possible to compress
> this crap
> >into 20 bytes.
>
> This is basically the old "fractal compression" idea all over again.
>
> It always goes more or less like this:
>
> 1. Look at the digits of PI or E, they look awfully random and are
>    very hard to compress.
>
> 2. Yet, we have this incredibly simple formula for generating them
>    (insert favourite PI or E expression here).
>
> 3. What an amazing compression ratio!
>
> 4. There must be some function which similarly emits the MPG stream
>    of Lord Of The Rings
>
> 5. Profit!
>
> This thinking suffers both from logical fallacies and factual
> misunderstandings.
>
> Ad 1: While it is generally a good indicator of entropy that you
> cannot compress some data, it is not a proof that the data is random,
> you may simply be using the wrong compression algorithm.
>
> Ad 2: Deterministically generated data, no matter what its entropy
> might be, is never random, even when you do not know the formula
> which generated the data.
>
> Ad 3: The reason the compression ratio is so amazing is that PI
> or E has infinite length.  Normally we use only about 8-16 digits
> of either and it's way more compact than your formula to just
> write down those digits.  (Footnote: 355/113)
>
> Ad 4: Yes, there is undoubtedly such a function, but there is no
> reason to think that it is significantly smaller than the *finite*
> length bitstream you are trying to produce with it.
>
> Ad 5: No, because finding the magic LOTR function has complexity
> far exceeding the size of the known universe.
>
> Poul-Henning
>
> --
> Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
> phk@...eBSD.ORG         | TCP/IP since RFC 956
> FreeBSD committer       | BSD since 4.3-tahoe
> Never attribute to malice what can adequately be explained by incompetence.
>

Content of type "text/html" skipped

Powered by blists - more mailing lists