[cfe-dev] [libc++] Initial attempt to make a salted hash

[Matthieu Monrocq]

It is unclear to me whether the problem you wish to solve is provide:

- resilient hash functions
- resilient hash containers

For the latter another solution, rather than modifying the hash function,
would be to modify the hash container.

For example, one could initialize `std::unordered_set` (and co) with a
random seed and simply XOR this seed with the result of `h(k)`. Said seed
can even change each time the container is rehashed to prevent an observer
from analyzing the collisions and cause undue chaining.

And this would not require a salted hash so there would be no issue with
the standard.

-- Matthieu


On Sat, Aug 31, 2013 at 9:03 PM, Zhihao Yuan <zy at miator.net> wrote:

> On Sat, Aug 31, 2013 at 2:37 PM, Howard Hinnant <hhinnant at apple.com>
> wrote:
> > [hash.requirements]/ Table 26 says:
> >
> >> The value returned shall depend only on the argument k. [ Note: Thus
> all evaluations of the expression h(k) with the same value for k yield the
> same result. — end note ]
>
> I know.  But the wording here is not clear: does that mean two
> different standard library implementations have to share the
> same hash function?  Obviously not.
>
> > Now it isn't clear, at least to me, that if this is talking about all
> evaluation within the process, or across different invocations of the same
> process, or even across invocations of different processes.  Without
> guidance from the LWG, I think we need to assume the most conservative
> answer.
>
> Tend to agree.
>
> > I faintly recall this subject was brought up at the Portland meeting,
> Fall 2012.  I do not believe anything was definitively resolved at that
> time.  I do not know if this issue was discussed this Spring in Bristol.  I
> do not see an LWG issue on this subject.
>
> I guess it's inside
>
>   http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2012/n3333.html
>
> Thanks to the labor day, the deadline is extended.  Can I submit
> an issue like
>
> "The value returned shall depend only on the argument k<ins> for
> the duration of the program</ins>  [ Note: Thus all evaluations of the
> expression h(k) with the same value for k yield the same result
> <ins> for each execution of the program(, some guideline here?)</ins>.
> — end note ]"
>
> The hashing can't be per-process BTW.  First the standard knows
> nothing about OS process; second, practically that makes you unable
> to share an unordered container to a child process :(
>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130901/b0395b9a/attachment.html>