bank teller has a vault that must be opened every day. The bank employs
three senior tellers, but they do not want to trust any individual with
the key combination. Hence, they would like a system whereby any two of
the three senior tellers can gain access to the vault.'' (example by Gopalakrishnan
and Stinson, "Applications of designs to cryptography", The CRC Handbook
of Combinatorial Designs, 1996).
In general, partial information (shadows) should be shared among w participants, so that any t participants together can compute a key to a secret information, but no group with t-1 participants can. A (t,w,v)-threshold scheme is a way of distributing v shadows in this way, and the threshold scheme is perfect if it has the additional property that no group of t-1 participants can conspire to determine any partial information regarding the key. The bank teller example requires a (2,3,v)-threshold scheme for suitable v (the larger the number of possible shadows, the larger the number of possible keys). We will look at the construction of a perfect (3,3,v)-threshold scheme for arbitrarily large v. This threshold scheme has v possible shadows and v-2 keys; as described above, the 3 people can put their shadows together to discover the key, but if 2 people put their shadows together, any of the v-2 keys are equally likely to be the secret key.
In this project, you are going to study threshold schemes in general and implement a particular one, namely a (3,3,v)-threshold scheme based on a combinatorial construction by Wilson (see: Stinson and Vanstone, "A combinatorial approach to threshold schemes", SIAM J. Disc. Math. 1 (1988)). You are going to write two main tools. The first one will produce a complete (3,3,v)-threshold scheme, given a suitable v. The second tool will efficiently calculate the key, given 3 shadows and suitable v, in average time O(1). The construction uses arithmetic module p (for p a prime number), so you will have to implement basic arithmetic in a finite field of prime order.
Number of students required: 1 or 2
Additional information: You will need some basic algebra knowledge in order to implement arithmetic over a finite field of order p (F_p) and understand Wilson's construction. You will write a C++ class for handling basic operations over F_p. Operations should be carefully implemented in order to guarantee the O(1) average time for key calculation. Extense bibliography on the topic can be found online . We will provide background reading. Regular meetings with supervisor will be scheduled.
disk array architecture organizes many independent small disks into one
large logical disk. Suppose each part (some bits) of a piece of information
is stored in each of the physical disks. In order to tolerate disk failures,
redundancy must be incorporated. Thus, some extra disks are added to store
redundant information so that lost information can be quickly retrieved
and the contents of the erased disks can be reconstructed. This forms the
so-called RAIDs (redundant arrays of inexpensive disks). Error-correcting
codes could be used but erasure-resilient codes provide better solutions
for this problem (there is a tradeoff between reliability and check-disk
overhead/update penalty). It has been shown that certain combinatorial
designs can be used to construct the matrix defining optimal erasure-resilient
In this project, you will design and experiment with algorithms for generating certain triple systems (you will learn what these animals are!) for the construction of erasure-resilient codes for RAIDs. The general construction method to be used is called hill-climbing, which is a general randomized search algorithm. Care should be taken in the use of efficient data structures for this particular problem. Different heuristics should be tried and compared through experiments.
You will spend some time understanding the disk array application and the use of codes and combinatorial designs in this application. Then you will learn the general framework of the hill-climbing algorithm, and work on a careful implementation of this algorithm. A lot of time will be devoted to the design of this algorithm, its implementation and experimenting with variations.
Number of students required: 1 or 2
Additional information: Basic linear algebra knowledge is required for understanding linear codes. Good grasp of data structures and practice in programming is required for the design and implementation of the algorithm. We will provide background reading. Regular meetings with supervisor will be scheduled.
must design a bunch of tests for a program, so as to catch most errors
while keeping the number of tests not too high. Suppose the program
has 4 input parameters and each parameter can be assigned one of 2 possible
values. For example, a program computes life insurance premiums based
on the following parameters: gender (M/F), smoker (Y/N), age (young/old)
and serious disease among ancestors (Y/N). There is experimental evidence
that in many applications most errors occur from the interaction between
two parameters (for example, there is an error in the program when calculating
premiums for non-smoker males regardless of the other parameter values).
Therefore, our objective is to generate the minimum number of tests,
while guaranteeing pairwise coverage of parameter values.
Example: In the example above, testing all possible parameter combinations would require 2^4 = 16 tests. But we can achieve pairwise coverage with only 5 tests:
|test 1||test 2||test 3||test 4||test 5|
In this project, you are going to write a tool
for generating a set of tests guaranteeing some desired coverage while
minimizing the number of tests. The input parameters for your program will
be the number of parameters and the number of values for each parameter;
the user will also specify the desired coverage (complete pairwise coverage
or coverage of specified pairs). We are going to experiment with 2 types
of algorithms: one is based on an integer programming (IP) formulation
for this problem (your program will create an integer programming model
which will be fed into a package for its solution) and the second will
be a greedy heuristic (GH) implemented by you. The IP algorithm will give
the minimum number of tests but it is expected to take a long time, while
the GH will be quick but may generate too many tests. The idea is to compare
both methods in terms of running time spent in the generation and quality
of solution (how big is the test set generated). If two students are involved
in this project, the experimental comparison can be done more professionally.
Number of students required: 1 or 2
Additional information: Experience with programming and algorithms is required. You will need C or C++ in order to communicate with the Integer Programming solver (Cplex). Note that the problem of designing an efficient test generator is a hard research problem!!! The objective of this project is to play with two possible solution methods and see how far each method can go. In order to do a reasonable comparison between the methods, the test problems should be carefully chosen. So, we could have a much nicer project with 2 participants sharing the programming tasks. I strongly encourage that the pair of students know each other well and have previous experience working or studying together. We will provide background reading. Regular meetings with supervisor will be scheduled.