Skip to content

Remove small statistical bias in PRF output #10

@b-wagn

Description

@b-wagn

The current PRF implementation (shake to field) takes 64 bit chunks and maps each of those to one 31-bit field element.
This introduces a small statistical bias (per field element!), even if the PRF outputs were truly uniform.

We should consider ways of solving that. For instance:

  • take, say 256 bits and map them to one field element. At that point, the bias is certainly statistically negligible.
  • split the PRF output into chunks of 16 bits and use one chunk per field element, realizing an injective mapping F_2^{256} to F_p^{16}, then apply one Poseidon to get the actual chain start (suggested by @khovratovich).

The advantage of the first is that we don't need to call Poseidon in the PRF.
The advantage of the second is that we don't need to think about bias, but on the other hand we need to think about which security property of Poseidon is used here, and whether we need tweaks and the parameter for this application.

Note: the reason this did not show up in the papers is that they did not use a PRF there.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions