password_distribution_3_of_k.md

How to Distribute Password Halves for Separation of Duty

Problem:

We have 5 passwords: a, b, c, d, e. It needs exactly two distinct passwords to open a safe. Each of the passwords is split into two halve - a prefix and a suffix. Let them be

    a1, a2; b1, b2; c1, c2; d1, d2; e1, e2

where a == a1||a2, etc.

We would like to distribute all password halves to N different people. What is the minimum N such that it requires at least three people to open the safe?

Answer

The minimum N is 4. A solution is as follows.

#!/usr/bin/env python3

'''
We have 5 passwords: a, b, c, d, e. It needs exactly two distinct passwords
to open a safe. Each of the passwords is split into two halve - a prefix and
a suffix. Let them be
    a1, a2; b1, b2; c1, c2; d1, d2; e1, e2
where a == a1||a2, etc.
We would like to distribute all password halves to N different people. What
is the minimum N such that it requires at least three people to open the
safe?
'''

import itertools


def partition_n(collection, n):
    '''Partition collection into n subsets
    '''
    if n < 1 or n > len(collection):
        print('len of set: {0}, num of parts: {1}'.format(len(collection), n))
        raise ValueError('No partition exists')

    if n == len(collection):
        yield [[c] for c in collection]
        return

    if n == 1 or len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    for smaller in partition_n(collection[1:], n-1):
        yield [ [first] ] + smaller

    for smaller in partition_n(collection[1:], n):
        for i, subset in enumerate(smaller):
            yield smaller[:i] + [[first] + subset] + smaller[i+1:]
    return


def can_construct_password(password_halves, password):
    '''Return True if the list of password_halves can construct password
    Example: password_halves [('a', 1), ('a', 2)] can construct password a
    '''
    count = 0
    for ph in password_halves:
        count += 1 if ph[0] == password else 0
    assert count <= 2
    return count == 2


def can_open_safe(password_halves, password_list):
    '''Return True if password_halves can construct at least 2 passwords in
    password_list
    '''
    count = 0
    for p in password_list:
        count += 1 if can_construct_password(password_halves, p) else 0

    return True if count >= 2 else False


def require_3_to_open(password_distribution, password_list):
    '''Return True if no two people on the password_distribution list can
       open the safe
       Example of password_distribution:
       [[('d', 2)], [('e', 1)], [('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2), ('d', 1), ('e', 2)]]
    '''
    combos = itertools.combinations(password_distribution, 2)
    for idx, combo in enumerate(combos):
        password_halves = combo[0] + combo[1]
        if can_open_safe(password_halves, password_list):
            return False
    print('require_3_to_open: ', password_distribution)
    return True


def is_atleast3_of_k(password_halves, password_list, k):
    '''Return True if there's a k-partition of password_halves that requires
       3 people to open the safe.
    '''
    partitions = partition_n(password_halves, k)
    for idx, password_distribution in enumerate(partitions):
        if require_3_to_open(password_distribution, password_list):
            return True;

    return False

if __name__ == '__main__':
    '''Check if the list of password halves can induce a 3-of-k situation.
    Password halves are of the form (password_string, i), where i=1, 2.
    '''
    password_halves = [('a', 1), ('a', 2),
                       ('b', 1), ('b', 2),
                       ('c', 1), ('c', 2),
                       ('d', 1), ('d', 2),
                       ('e', 1), ('e', 2)]
    password_list = [p[0] for p in password_halves[::2]]
    print('**********************')
    print('password halves: ', password_halves)
    print('**********************')
    for k in range(3, 11):
        if is_atleast3_of_k(password_halves, password_list, k):
            print('Found a 3-of-{} condition above.'.format(k))
        else:
            print('Cannot form a 3-of-{} condition.'.format(k))

Running the above code gives us

 $ python3 password_distrbution.py 
**********************
password halves:  [('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2), ('d', 1), ('d', 2), ('e', 1), ('e', 2)]
**********************
Cannot form a 3-of-3 condition.
require_3_to_open:  [[('a', 2), ('b', 1)], [('b', 2), ('c', 2), ('d', 1)], [('a', 1), ('d', 2), ('e', 1)], [('c', 1), ('e', 2)]]
Found a 3-of-4 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2), ('b', 1)], [('b', 2), ('c', 2), ('d', 1)], [('d', 2), ('e', 1)], [('c', 1), ('e', 2)]]
Found a 3-of-5 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2)], [('b', 1)], [('b', 2), ('c', 2), ('d', 1)], [('d', 2), ('e', 1)], [('c', 1), ('e', 2)]]
Found a 3-of-6 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2)], [('b', 1)], [('b', 2)], [('c', 2), ('d', 1)], [('d', 2), ('e', 1)], [('c', 1), ('e', 2)]]
Found a 3-of-7 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2)], [('b', 1)], [('b', 2)], [('c', 1)], [('c', 2), ('d', 1)], [('d', 2)], [('e', 1), ('e', 2)]]
Found a 3-of-8 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2)], [('b', 1)], [('b', 2)], [('c', 1)], [('c', 2)], [('d', 1)], [('d', 2)], [('e', 1), ('e', 2)]]
Found a 3-of-9 condition above.
require_3_to_open:  [[('a', 1)], [('a', 2)], [('b', 1)], [('b', 2)], [('c', 1)], [('c', 2)], [('d', 1)], [('d', 2)], [('e', 1)], [('e', 2)]]
Found a 3-of-10 condition above.