• Breaking News

    Saturday, February 3, 2018

    Home Unlabelled Cryptography Proving that an element is in a list to a party that only knows h(l)

    Cryptography Proving that an element is in a list to a party that only knows h(l)

    February 03, 2018

    Cryptography Proving that an element is in a list to a party that only knows h(l)

    Proving that an element is in a list to a party that only knows h(l)

    Posted: 02 Feb 2018 05:07 PM PST

    If there is a list l with multiple entries, does there exist a function h(l) where someone can prove that a certain entry exists in the list to a party that only knows h(l) without sending the entire contents of l?

    Example: Alice is at a convention giving away keychains to everyone who was already a member of her mailing list. The only problem is that she has a 10tb mailing list l. Instead of checking every email against the list, she calculates h(l). Each member of the mailing list knows their email and a verification tag v which can be used to prove they are on the list. What function h(l) can we use to minimize both the authentication time and v.

    One thought is to use a Merkle tree and only store the top. The tag would be the other branches on each layer of the tree.

    For example if I was proving entry 0 I would have to reveal all the colored boxes and if I was proving entry 9 I would reveal all the colored boxes. This makes the size of the tag 256log_2(n) where n is the length of the list. The time complexity of verification is in O(log(n)).

    Is there any better way to do this?

    EDIT: the hash function that would be used in the merkle tree would first sort the two inputs so it is independent of the order. This way, the tag does not have to include whether the included branch is on the left or the right.

    submitted by /u/stealth9799
    [link] [comments]

    Libsodium authenticated encryption is inexplicably fast

    Posted: 02 Feb 2018 03:04 AM PST

    While benchmarking Monocypher, I've noticed strange (yet consistent) timings from libsodium (on my core i5 skylake laptop):

    Chacha20 : 1925 megabytes per second Poly1305 : 1191 megabytes per second Auth'd encryption: 1016 megabytes per second

    The benchmark uses crypto_stream_chacha20_xor(), crypto_onetimeauth(), and crypto_aead_xchacha20poly1305_ietf_encrypt_detached() respectively.

    I've looked ath their AEAD function, and it looks like a straightforward implementation that just uses their chacha20 and poly1305 algorithms. But if they did that, I would expect authenticated encryption to have a throughput of only 736 megabytes per second (1/ (1/1925 + 1/1191)). Monocypher, on the same benchmark, follow this rule (chacha20 is much slower, but the timings make sense).

    So there's an unexplained 300 megabytes per second here, and I have no idea where it might come from. Surely libsodium doesn't use faster core algorithms for authenticated encryption? I though it would combine them in clever ways, but it doesn't look like it does. Any idea what might be going on here?

    (For reference, here's the benchmark's source code, in case someone finds a flaw.)

    submitted by /u/loup-vaillant
    [link] [comments]

    Messenger Secret Conversations

    Posted: 02 Feb 2018 07:24 AM PST
    Read more
    at

    No comments:

    Post a Comment