Re: [Ideas] Computing collisions

Padma Pillay-Esnault <padma.ietf@gmail.com> Sun, 11 December 2016 17:03 UTC

Return-Path: <padma.ietf@gmail.com>
X-Original-To: ideas@ietfa.amsl.com
Delivered-To: ideas@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 73B951293FF for <ideas@ietfa.amsl.com>; Sun, 11 Dec 2016 09:03:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id jxk5FLb3-qfH for <ideas@ietfa.amsl.com>; Sun, 11 Dec 2016 09:03:11 -0800 (PST)
Received: from mail-qt0-x234.google.com (mail-qt0-x234.google.com [IPv6:2607:f8b0:400d:c0d::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DA52C1293E8 for <ideas@ietf.org>; Sun, 11 Dec 2016 09:03:10 -0800 (PST)
Received: by mail-qt0-x234.google.com with SMTP id p16so57783731qta.0 for <ideas@ietf.org>; Sun, 11 Dec 2016 09:03:10 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=GdiDTu/MhlivKQqhkwfGszrzGy0IamYT2u6dTENuj1w=; b=lAl/CFeeHIHEIOWa2BKxbaQzdkiPVEK9JSJOOhecGdcahH8YUezMSoP9zNyxAMgKpv ca+Nok7epT1ZlXQ21qUy7xpr5W9M7EBYW8uT1BDGzzeFm1m/viZGX3+jTFwf0WJF99Rl JfF+ncXT+V5qVr6+6ZXuyUCmTcJyjeJRiZhJklBRtyNmGUJUcGFH5QbWwUJVWWupmibc 9K442J47tOp5m9vFU+PsV6vxENQcbZzVZ8abIHPa0gqnsbCIvXyCfSPe75kXmdEifK8P axd3YJaE4MRtNv0z+c9UOeJ4InX0hJoh8oHme7dhsK4Y+wzigg9nzTKgmMxnCmKJ+vXs 0n9Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=GdiDTu/MhlivKQqhkwfGszrzGy0IamYT2u6dTENuj1w=; b=mb6hxcQsnPxXa+RSEb3RfrmatqCjynbgKkcupQNpP5wxu2xQYcOb0uXtK+0W0TJ8uA m7KTP18zqA4XJpCK1F4KcMjsBckscDQYrVjcrALtjNwLxeo+b678ctgznJ74WquRVbqt REBuTXHMHPfYBK4QlX4jOkWEnPnXlIMOiPnY3rdDpUySATfEeLGzTa7UNcP7OxGEb5cG qF0WbAo6MuNuM8CaT9j9N3dz1mY9R6Di69L44HjJnFdWg/WynQdUz+qqwmgTIUb1hbu3 FRLTjA1/I1e61D7cM6KyJbJOaBFnY3juyMO7Y7wYqe7Rq2dkCjvSP8Uozu2/X7Sy157B YbWw==
X-Gm-Message-State: AKaTC00l78yDcWJDDDFpGU8ku8o49biGL+OLW+87UQK7t07PCyC64XioBkmCR5qF4RyzC5uMPvCgjbAybjfO3A==
X-Received: by 10.200.52.204 with SMTP id x12mr85471610qtb.193.1481475789960; Sun, 11 Dec 2016 09:03:09 -0800 (PST)
MIME-Version: 1.0
Received: by 10.200.41.198 with HTTP; Sun, 11 Dec 2016 09:03:09 -0800 (PST)
In-Reply-To: <fb888f85-22ed-5e87-bf84-2b6244d587e6@htt-consult.com>
References: <fb888f85-22ed-5e87-bf84-2b6244d587e6@htt-consult.com>
From: Padma Pillay-Esnault <padma.ietf@gmail.com>
Date: Sun, 11 Dec 2016 09:03:09 -0800
Message-ID: <CAG-CQxqds9osqTTAi_Gm-VCVKGo49pW5OVALxYiYCrqNQ2yvRA@mail.gmail.com>
To: Robert Moskowitz <rgm-ietf@htt-consult.com>
Content-Type: multipart/alternative; boundary="001a1137ba20343e31054364f609"
Archived-At: <https://mailarchive.ietf.org/arch/msg/ideas/4Jhv9mjU9eneFXVJHiDaK8lZ-dY>
Cc: ideas@ietf.org, Padma Pillay-Esnault <padma.ietf@gmail.com>
Subject: Re: [Ideas] Computing collisions
X-BeenThere: ideas@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "Discussions relating to the development, clarification, and implementation of control-plane infrastructures and functionalities in ID enabled networks." <ideas.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ideas>, <mailto:ideas-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ideas/>
List-Post: <mailto:ideas@ietf.org>
List-Help: <mailto:ideas-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ideas>, <mailto:ideas-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 11 Dec 2016 17:03:13 -0000

Hello Bob

Thanks for sending this formula.

If we assume that the population is not necessarily a flat space and that
it is in different separate instances, this could help reduce the collision.

Per the ideas problem statement draft, we have discussed about the
different types of devices and whether we could have some policy on what
they can do. Eg. a camera should not be shopping for clothes or access bank
accounts .... wouldn't it make sense to put them in different instances
with different access policies?

What are your thoughts on this?
Padma

On Thu, Nov 17, 2016 at 1:48 AM, Robert Moskowitz <rgm-ietf@htt-consult.com>
wrote:

> Here is the equation:
>
> probability of collision = 1 - e^{-k^2/(2n)}
>
> Where n is your max population size (e.g. 2^64)
>
> and k is your deployed population (e.g. 7B)
>
> Bob
>
> _______________________________________________
> Ideas mailing list
> Ideas@ietf.org
> https://www.ietf.org/mailman/listinfo/ideas
>