拉丁方陣與密碼 摘要：應用拉丁方陣來建構密碼 交大應數系 傅恆霖.

Presentation on theme: "拉丁方陣與密碼 摘要：應用拉丁方陣來建構密碼 交大應數系 傅恆霖."— Presentation transcript:

1 拉丁方陣與密碼 摘要：應用拉丁方陣來建構密碼 交大應數系 傅恆霖

2 A Latin square of order n is an n×n array based on an n-set S such that each element of S occurs exactly once in each row and each column. We can take A latin square of order 3

3 A latin square of order n defines a quasigroup on 3 elements.
<S,*> is a quasigroup if <S,*>is a groupoid and have unique solution

4 Two latin squares and of order n are orthogonal if 。
Two orthogonal latin squares of order 4

5 are mutually orthogonal latin squares of order n (MOLS(n)), if for 。
Theorem Let n be a prime power and n≠2 . Then there exists n-1 latin squares (best possible!) of order n which is a collection of mutually orthogonal latin squares.

6 Orthogonal Latin Square Graph
　　我們可以把拉丁方陣當做點，“互相垂直“，當成關係來定義一個圖 OLSG。 V：一些拉丁方陣所成的集合。 E：兩個點相連若且唯若對應的拉丁方陣互相垂直。 例：令　　　 為k個互相垂直的拉丁方陣，則以 定義出來的OLSG為 。

7 利用L⊥M我們可定義函數f，f為 的一個Permutation，或者說f為由 對映至 的1-1, onto 函數。

8 (＊) 令α為的一個排列，β也是排列， 則 ， 其中 。 　　由上述的結果，我們可以發現當L⊥M時，與L垂直的n階拉丁方陣至少有n！個。所以，要判斷key是由哪兩個方陣所形成並不容易！

9 Cryptosystem from MOLS(n)
Theorem [Lindner et al,(1979)JGT] 令G為任意圖，則必存在P=|V(G)|個n階拉丁方陣，n夠大，使得由這p 個拉丁方陣所定義出來的OLSG，H，　　　。 Cryptosystem from MOLS(n) 使用n階拉丁方陣。 有 個 Messages (Plaintexts)。 以n階拉丁方陣建構一個圖(OLSG)，G，則有 |E(G)| 個keys。 (最早使用k個MOLS(n)，則有 個keys.)

10 討論： 1.當n相當大時，MOLS(n)的個數也會很大。 2.如果只考慮MOLS(n)，key space較小。 3.Orthogonal mate。不容易找！(全部找出來！)

11 　　我們可以選 n 為Prime Power, 如此N(n)，互相垂直的n階拉丁方陣數(max)，自然是最大N(m)=n-1。
更明確地說 [T. Beth, Abh. Math. Sem. Hamburg 53(1983)] 所以，有足夠多的MOLS(n)！

12 分散模式解 (Sharing Scheme)
　　在近代有很多重大的決定，為了確保決策過程沒有暇疵，通常會採用由多個人都同意的情況下才執行；例如開金庫，發射核彈…。所以，建立一個系統使得較小的人數無法開啟是有它的必要性。

13 A critical set C in a latin square 　　 is a set
(partial latin square) with the following two properties： 1. L is the only latin square of order n which has symbol k in (i,j)-cell for each ；and 2. no proper subset of c has property (1). A critical set

14 例 　　上面圈出的三個位置，任兩個都會形成一個臨界集(Critical Set)。少了，或多了都不是臨界；然而多了(3個)也可以繼續填成唯一的拉丁方陣。

15 Fact 1 A critical set C of a latin square L provides minimal infos from which L can be reconstructed. Fact 2 Deciding whether a partial latin square is a critical set is NP-complete. (From completion point of view.) Fact 3 Denote the minimum size of a critical set of order n by M(n) [D. Curran & G.H.J.van Rees, Cong. Numer. 1979]

16 Critical sets, n=5

17 Conjecture 。 Theorem (高, Fu, C.A. Rodger, JSPI 1997) For n>20, 。
M*(n)：Maxmim size of a critical set of order n. Theorem (D.R.Stison, G.H.J. van Rees, Cong. Numer 1980) For ， 。 Theorem (高, Fu, 廖, Cong, Numer, 1995) For ，

18 分散模式解 1.Key → L (拉丁方陣) n public 2.選一個集合它是L中多個臨界集的聯集：S。
3.把其中 t’≦|S|。(可以容許高階者持有多一些(i,j ; k), 甚至一個Critical Set！) 4.足夠多的人即可得到“Key“。

19 A (s,t)-secret sharing scheme is a system where k 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.

20 臨界集的選擇有很多！ ↑ 對於臨集的了解不多。 ↓ 增加破解難度

21