def blake_encode_ngrams(ngrams,   # type: Iterable[str]
                        keys,     # type: Sequence[bytes]
                        ks,       # type: Sequence[int]
                        l,        # type: int
                        encoding  # type: str
                        ):
    # type: (...) -> bitarray.bitarray
    """ Computes the encoding of the ngrams using the BLAKE2 hash function.

        We deliberately do not use the double hashing scheme as proposed in [
        Schnell2011]_, because this
        would introduce an exploitable structure into the Bloom filter. For more
        details on the
        weakness, see [Kroll2015]_.

        In short, the double hashing scheme only allows for :math:`l^2`
        different encodings for any possible n-gram,
        whereas the use of :math:`k` different independent hash functions gives
        you :math:`\\sum_{j=1}^{k}{\\binom{l}{j}}`
        combinations.


        **Our construction**

        It is advantageous to construct Bloom filters using a family of hash
        functions with the property of
        `k-independence <https://en.wikipedia.org/wiki/K-independent_hashing>`_
        to compute the indices for an entry.
        This approach minimises the change of collisions.

        An informal definition of *k-independence* of a family of hash functions
        is, that if selecting a function at random
        from the family, it guarantees that the hash codes of any designated k
        keys are independent random variables.

        Our construction utilises the fact that the output bits of a
        cryptographic hash function are uniformly distributed,
        independent, binary random variables (well, at least as close to as
        possible. See [Kaminsky2011]_ for an analysis).
        Thus, slicing the output of a cryptographic hash function into k
        different slices gives you k independent random
        variables.

        We chose Blake2 as the cryptographic hash function mainly for two reasons:

        * it is fast.
        * in keyed hashing mode, Blake2 provides MACs with just one hash
          function call instead of the two calls in the HMAC construction used
          in the double hashing scheme.


        .. warning::
           Please be aware that, although this construction makes the attack of
           [Kroll2015]_ infeasible, it is most likely
           not enough to ensure security. Or in their own words:

             | However, we think that using independent hash functions alone
               will not be sufficient to ensure security,
               since in this case other approaches (maybe related to or at least
               inspired through work from the
               area of Frequent Itemset Mining) are promising to detect at least
               the most frequent atoms automatically.

        :param ngrams: list of n-grams to be encoded
        :param keys: secret key for blake2 as bytes
        :param ks: ks[i] is k value to use for ngram[i]
        :param l: length of the output bitarray (has to be a power of 2)
        :param encoding: the encoding to use when turning the ngrams to bytes

        :return: bitarray of length l with the bits set which correspond to the
                 encoding of the ngrams
    """
    key, = keys  # Unpack.

    log_l = int(math.log(l, 2))
    if not 2 ** log_l == l:
        raise ValueError(
            'parameter "l" has to be a power of two for the BLAKE2 encoding, '
            'but was: {}'.format(
                l))
    bf = bitarray(l)
    bf.setall(False)

    for m, k in zip(ngrams, ks):
        random_shorts = []  # type: List[int]
        num_macs = (k + 31) // 32
        for i in range(num_macs):
            hash_bytes = blake2b(m.encode(encoding=encoding), key=key,
                                 salt=str(i).encode()).digest()
            random_shorts.extend(struct.unpack('32H',
                                               hash_bytes))  # interpret
            # hash bytes as 32 unsigned shorts.
        for i in range(k):
            idx = random_shorts[i] % l
            bf[idx] = 1
    return bf
def blake_encode_ngrams ( ngrams , keys , ks , l , encoding ) : key , = keys log_l = int ( math . log ( l , 2 ) ) if not 2 ** log_l == l : raise ValueError ( 'parameter "l" has to be a power of two for the BLAKE2 encoding, ' 'but was: {}' . format ( l ) ) bf = bitarray ( l ) bf . setall ( False ) for m , k in zip ( ngrams , ks ) : random_shorts = [ ] num_macs = ( k + 31 ) // 32 for i in range ( num_macs ) : hash_bytes = blake2b ( m . encode ( encoding = encoding ) , key = key , salt = str ( i ) . encode ( ) ) . digest ( ) random_shorts . extend ( struct . unpack ( '32H' , hash_bytes ) ) for i in range ( k ) : idx = random_shorts [ i ] % l bf [ idx ] = 1 return bf
Computes the encoding of the ngrams using the BLAKE2 hash function.

        We deliberately do not use the double hashing scheme as proposed in [
        Schnell2011]_, because this
        would introduce an exploitable structure into the Bloom filter. For more
        details on the
        weakness, see [Kroll2015]_.

        In short, the double hashing scheme only allows for :math:`l^2`
        different encodings for any possible n-gram,
        whereas the use of :math:`k` different independent hash functions gives
        you :math:`\\sum_{j=1}^{k}{\\binom{l}{j}}`
        combinations.


        **Our construction**

        It is advantageous to construct Bloom filters using a family of hash
        functions with the property of
        `k-independence <https://en.wikipedia.org/wiki/K-independent_hashing>`_
        to compute the indices for an entry.
        This approach minimises the change of collisions.

        An informal definition of *k-independence* of a family of hash functions
        is, that if selecting a function at random
        from the family, it guarantees that the hash codes of any designated k
        keys are independent random variables.

        Our construction utilises the fact that the output bits of a
        cryptographic hash function are uniformly distributed,
        independent, binary random variables (well, at least as close to as
        possible. See [Kaminsky2011]_ for an analysis).
        Thus, slicing the output of a cryptographic hash function into k
        different slices gives you k independent random
        variables.

        We chose Blake2 as the cryptographic hash function mainly for two reasons:

        * it is fast.
        * in keyed hashing mode, Blake2 provides MACs with just one hash
          function call instead of the two calls in the HMAC construction used
          in the double hashing scheme.


        .. warning::
           Please be aware that, although this construction makes the attack of
           [Kroll2015]_ infeasible, it is most likely
           not enough to ensure security. Or in their own words:

             | However, we think that using independent hash functions alone
               will not be sufficient to ensure security,
               since in this case other approaches (maybe related to or at least
               inspired through work from the
               area of Frequent Itemset Mining) are promising to detect at least
               the most frequent atoms automatically.

        :param ngrams: list of n-grams to be encoded
        :param keys: secret key for blake2 as bytes
        :param ks: ks[i] is k value to use for ngram[i]
        :param l: length of the output bitarray (has to be a power of 2)
        :param encoding: the encoding to use when turning the ngrams to bytes

        :return: bitarray of length l with the bits set which correspond to the
                 encoding of the ngrams