k-threshold system of deciphering N

k-threshold system of deciphering N


Updated 23 Sep 2004

No License

This programme is an application of the Chinese Remainder Theorem for Integers - for obtaining a solution to the "k-threshold system for sharing a secret". The concept is explained in the book "A course in Number Theory and Cryptography by Neal Koblitz" in Ch 1, Prob 24 / P27 and it's solution in P205.

Let me explain the problem with some specific numbers.

Let N = 4333621567 be a secret number known completely ONLY to the Commanding General for unlocking a missile system. Let there be 9 Lt Gens under him who are each given some partial info related to N. If the General is incapacitated, we want that ANY "k" Lt Gens (k >= 3) (out of the total of 9 Lt Gens) should be able to decipher N by processing their combined partial infos. Also, information available with just (k-1) Lt Gens should not be able to decipher N.

Now the problem to be solved is :

a) if k = 3, ie, if ANY 3 Lt Gens should be able to make the decision, what is partial info that should be given to each of the 9 Lt Gens
so that they (ANY 3) can combine to decipher N?

b) if k = 5, ie, if ANY 5 Lt Gens should be able to make the decision, what is partial info that should be given to each of the 9 Lt Gens
so that they (ANY 5) can combine to decipher N ?

I developed this programme to answer exactly these 2 questions.

In this programme, the variable k_thrsh represents the "threshold k". Refer to Usage Eg Case 6 for k (k_thrsh) = 3 and Usage Eg Case 5 for k_thrsh = 5.

This programme calls my code Ch_Rem_Thr_Int.m for solving the k number of simultaneous congruence equations. Since Matlab has a Precision limit of 16 digits, we will not get correct results whenever this limit is crossed in the intermediate calculations.

A "Mathematical Proof" linking N to (different) mk and ck sets is what I am looking for. I will be glad if someone can mail me the Proof or links to the Proof. See Q N4 below.

Q N4 : How is it that mk set formed of ANY k_thrsh primes within the band of sqrt(N) and N^(1/k_thrsh) (and it's corresponding residue ck with mod N) results in the correct deciphering of N?

I understand that once mk and ck are given, the Chinese Remainder Theorem will calculate the correct solution c_soln.

But what I would like to have is a "Mathematical Proof" for :

a) Why should mk set of coprimes fall within the above band ?

b) How ANY set of k_thrsh primes in the above band gives the correct solution ?

Cite As

Sundar Krishnan (2023). k-threshold system of deciphering N (https://www.mathworks.com/matlabcentral/fileexchange/5895-k-threshold-system-of-deciphering-n), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

Added Ch_Rem_Thr_Int.m in the ZIP-file, even though it is available in my earlier submissions elsewhere.