How to design a secret sharing scheme where when participants are positioned as a matrix, the minimum group people who can reconstruct the secret are the ones that are in same row or in same column?

  • 2
    $\begingroup$ Could you please provide some motivation for the question? Currently it looks like an assignment. Please check our FAQ particularly the section tips about writing better questions. $\endgroup$
    – Kaveh
    Nov 6, 2012 at 3:34

1 Answer 1


For an m x n matrix, you can simply create m+n independent sharings (using any n-out-of-n or m-out-of-m secret sharing scheme, such as the XOR scheme), one for each row and for each column.

Each participant will get tow shares, one for his row and one for his column. His total share size is 2s, where s is the length of the secret. Since you can't get share size less than s, this simple scheme is within a factor of 2 of the optimum.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.