拉丁方阵与密码-交通大学应数系傅恒霖老师网页.PPT

Critical sets, n=5 A critical set C of a Latin square L provides minimal infos from which L can be reconstructed. Deciding whether a partial Latin square is a critical set is NP-complete. (From completion point of view.) Denote the minimum size of a critical set of order n by M(n). Then M(n) is at least [n2/4]. [D. Curran G.H.J.van Rees, Cong. Numer. 1979] (Conjecture!) Applications in Cryptography An (s,t)-secret sharing scheme is a system where s pieces of information called shares or shadows of a secret key K are distributed so that each participant has a share such that: 1. the key K can be reconstructed from knowledge of any t or more shares; and 2. the key K can not be reconstructed from knowledge of fewer than t shares. A sharing scheme Key: A Latin square L From L we design a critical set C for the time being. (This critical set can be changed.) The shares are partial Latin squares which are contained in C. 分散模式解 (Sharing Scheme) 　　 　　在近代有很多重大的決定，為了確保決策過程沒有暇疵，通常會採用由多個人都同意的情況下才執行；例如開金庫，發射核彈…。所以，建立一個系統使得較小的人數無法開啟是有它的必要性。 臨界集的選擇有很多！ ↑ 對於臨集的了解不多。 ↓ 增加破解難度 Latin square changes my life It is a story now! I went to Auburn University (1977) with a teaching assistantship to learn Topology which I felt very interesting when I was an undergraduate student (as a 學弟 of 薛老師). Auburn was a power house of General Topology in 70’s. (Not Football) Fortunate or unfortunate They did not have enough students to open the class of Topology that year, they need at least three. I was informed to take another class besides Algebra (I) and Analysis (I) which I have chosen already. I did have many courses to choose. So, it comes “Combinatorics”. The first subject I learned The first subject I learned from Prof. C. C. Lindner was “Latin square”. He claims that Latin square is the most important combinatorial configuration in combinatorics. It took more than one month to complete his lectures on Latin square at that year. From C. C. Lindner Do whatever you enjoy