GT 2: Phân Ly và Phân Cách

NQH | 15/12/2009 |

2. Ma trận phân ly và ma trận phân cách

Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay cáng đáng tủ sách S.O.S. (dù các bản dịch Popper, Hayek hơi trúc trắc, cố gắng này thực sự là đáng nể phục và rất quan trọng), anh còn là nguyên viện trưởng viện IDS vừa tuyên bố giải thể để phản đối quyết định 97 của chính phủ, là một trong số rất hiếm những tiếng nói phản biện xã hội có nội lực ở Việt Nam hiện nay. Tôi cũng không biết tường tận tiểu sử TS Nguyễn Quang A, nhưng tôi biết anh có một bài báo chuyên ngành chất lượng liên quan đến vấn đề thử nhóm. Để mô tả kết quả trong bài báo này và các kết quả khác, chúng ta cần một khái niệm mới gọi là ma trận ${d}$ -phân cách.

Hãy quay lại với bài toán thử nhóm bất ứng biến. Giả sử ta có ${N}$ mẫu máu, trong đó ta biết trước rằng có nhiều nhất là ${d}$ mẫu dương tính. Cách thiết lập bài toán như thế này gọi là “thử nhóm tổ hợp” (combinatorial group testing), thích hợp với một số ứng dụng nhất định. Trong một số ứng dụng khác thì chúng ta không biết chặn trên ${d}$ này, và có thể phải giả sử hoăc học một phân bố xác suất của các mẫu máu dương tính. Đó là thiết lập bài toán “thử nhóm xác suất” (probabilistic group testing), nhánh nghiên cứu còn rất mở và chúng ta không có nhiều kết quả tốt, đúng như anh Xuân Long đã bình luận sắc bén trong bài trước.

Xét bài toán thử nhóm bất ứng biến tổ hợp. Giả sử ta thiết kế tổng cộng ${t}$ phép thử. Xây dựng một ma trận ${{\bf M} = (m_{ij})}$ có ${t}$ hàng và ${N}$ cột như sau: ${m_{ij} = 1}$ nếu và chỉ nếu mẫu máu ${j}$ nằm trong nhóm của phép thử thứ ${i}$ , ngoài ra thì ${m_{ij} = 0}$ . Ma trận này phải thỏa tính chất gì thì ta mới có thể chỉ ra nhiều nhất ${d}$ mẫu dương tính sau khi quan sát kết quả của ${t}$ phép thử? Bộ kết quả của ${t}$ phép thử có thể xem là một vector kết quả gồm ${t}$ thành phần, mỗi thành phần là ${0}$ hoặc ${1}$ — trong đó ${1}$ là phép thử dương tính, và ${0}$ là phép thử âm tính.

Giả sử ${S}$ là tập các mẫu dương tính. Vector kết quả chính là hội của các cột của ${{\bf M}}$ tương ứng với ${S}$ . Hội của hai vector nhị phân ${{\bf u}}$ và ${{\bf v}}$ là một vector nhị phân ${{\bf w}}$ trong đó ${w_i = u_i \vee v_i}$ , với mọi ${i}$ . Có thể mô tả cách khác như sau. Mỗi cột của ${{\bf M}}$ là vector đặc trưng của một tập con của tập ${[t] = \{1, \dots, t\}}$ , và vì thế có thể đánh đồng mỗi cột của ${{\bf M}}$ với tập con tương ứng. Vector kết quả chính là hội của các tập con tương ứng với ${S}$ .

Định nghĩa 1 Một ma trận nhị phân ${{\bf M}}$ với ${t}$ hàng và ${N}$ cột được gọi là ma trận ${d}$ -phân-ly ( ${d}$ -separable) nếu và chỉ nếu các hội của nhiều nhất ${d}$ cột của ${{\bf M}}$ là hoàn toàn khác nhau. Cụ thể hơn, lấy $d_1$ cột $C_1, \dots, C_{d_1}$ và $d_2$ cột khác $C'_1, \dots, C'_{d_2}$ của ma trận — trong đó $d_1 \leq d$ và $d_2\leq d$ — thì ta có

$C_1 \cup \cdots \cup C_{d_1} \neq C'_1 \cup \cdots \cup C'_{d_2}$

Như vậy, ta có kết quả cơ bản sau

Định lý 2 Chúng ta có thể tìm ra chính xác (nhiều nhất ${d}$ ) mẫu máu dương tính nếu và chỉ nếu ma trận thử nhóm ${{\bf M}}$ là ma trận ${d}$ -phân-ly.

Quan sát đơn giản trên cũng giúp ta thiết lập một chặn dưới cho tổng số phép thử cần thiết. Có tối đa ${2^t}$ các vector kết quả, do đó một điều kiện cần để ${{\bf M}}$ là ma trận ${d}$ -phân cách là

$\displaystyle 2^t \geq \sum_{i=0}^d \binom{N}{i} > \binom N d \geq \left(\frac N d\right)^d.$

Trong ngữ cảnh này thì thường ${d \ll N}$ , do đó cái chặn dưới ở trên không quá tệ. Từ đó ta có

$\displaystyle t = \Omega\left( d\log(N/d) \right).$

Dĩ nhiên đây không phải là chặn dưới tốt nhất chúng ta biết, nhưng nó cho ta một trực quan nhất định về tổng số phép thử cần thiết. Điều thú vị là tổng số phép thử cần thiết cũng không nhiều hơn cái chặn thô thiển này lắm.

Giả sử ta có một ma trận ${d}$ -phân-ly, cho một vector kết quả, làm thế nào để tìm đám mẫu dương tính? Cách thô thiển là làm sẵn một bảng tìm kiếm, ánh xạ các vector kết quả vào các tập con của ${[N]}$ . Như vậy vừa tốn thời gian, vừa tốn không gian một cách khủng khiếp. Điều ta cần là các ma trận ${d}$ -phân-ly “có cấu trúc”, để có thể dùng các tính chất đặc biệt nào đó của cấu trúc nọ cho việc tiết kiệm không/thời gian.

Định nghĩa 3 Một ma trận nhị phân ${{\bf M}}$ với ${t}$ hàng và ${N}$ cột được gọi là ma trận ${d}$ -phân-cách ( ${d}$ -disjunct) nếu và chỉ nếu hội của ${d}$ cột tùy ý của ${{\bf M}}$ không chứa bất kỳ cột nào khác. Cụ thể hơn, bất kỳ ${d+1}$ cột ${C_0, C_1, \dots, C_d}$ nào của ${{\bf M}}$ cũng thỏa điều kiện
$\displaystyle C_0 \not\subseteq C_1 \cup \cdots \cup C_d.$

Một ma trận ${d}$ -phân cách có ba tính chất quan trọng, trong đó tính chất 3 là động cơ ta định nghĩa ma trận phân cách. (Đại khái, định nghĩa vậy là để cho một thuật toán giải mã ngây thơ cũng tìm được các mẫu dương tính; xem thêm phía dưới.)

Nếu ${{\bf M}}$ là ${d}$ -phân-cách thì nó cũng là ${d}$ -phân-ly
Nếu ${{\bf M}}$ là ${d}$ -phân-ly thì nó là ${(d-1)}$ -phân-cách
Quan trọng hơn, cho một ma trận ${t \times N}$ ${d}$ -phân-cách bất kỳ, và một vector kết quả ${{\bf r} \in \{0,1\}^t}$ , chúng ta có thể chỉ ra các mẫu dương tính trong thời gian ${O(tN)}$ . Ngoài bản thân ma trận này ra, chúng ta không còn cần thêm cấu trúc dữ liệu ngoài nào khác (như cái bảng tìm kiếm ở trên).

Bài tập Chứng minh tính chất 1 và 2.

Thuộc tính 3 là một trong các lý do mà từ giờ trở đi chúng ta sẽ chỉ quan tâm đến các ma trận phân-cách. Tính chất 1 và 2 cho thấy hai loại ma trận này không khác nhau quá nhiều. Chúng ta cần xác định ${\bar t(d,N)}$ : số hàng nhỏ nhất có thể có của một ma trận ${d}$ -phân-ly, vì đó cũng là số phép thử ít nhất có thể đạt tới. Gọi ${t(d,N)}$ là số hàng nhỏ nhất của một ma trận ${d}$ -phân-cách, thì các thuộc tính trên cho thấy

$\displaystyle \bar t(d,N) \leq t(d,N) \leq \bar t(d+1, N).$

Lý do thứ hai mà chúng ta quan tâm đến các ma trận phân cách là vì chúng hoàn toàn tương đương với các mã chồng (superimposed codes). Câu hỏi tự nhiên là xác định ${t(d,N)}$ , và xây dựng các ma trận phân cách với số hàng càng gần tối ưu càng tốt.

Khi muốn chứng minh một cấu trúc mang tính tổ hợp nào đó tồn tại, như các ma trận phân cách, thì điều đầu tiên chúng ta nên thử là dùng phương pháp xác suất. Xây dựng một ma trận nhị phân ${{\bf M} = (m_{ij})}$ với ${t}$ hàng và ${N}$ cột một cách ngẫu nhiên như sau: gán ${m_{ij} = 1}$ với xác suất ${p \in [0,1]}$ , và gán ${m_{ij} = 0}$ với xác suất ${1-p}$ ; trong đó ${p}$ là tham số sẽ xác định sau, thì xác suất mà ${{\bf M}}$ không phải ma trận ${d}$ -phân-cách là

$\displaystyle (d+1)\binom{N}{d+1}\left[1-p(1-p)^d\right]^t \leq (d+1)\binom{N}{d+1}\left[1-\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\right]^t$

và đẳng thức đạt được khi ta đặt ${p = 1/(d+1)}$ . Do đó, sẽ tồn tại ma trận ${d}$ -phân-cách với ${t}$ hàng và ${N}$ cột nếu vế phải ở trên bé hơn hẳn ${1}$ . Dễ thấy rằng ${t \geq 3(d+1)\ln \left[ (d+1)\binom{n}{d+1} \right]}$ sẽ làm vế phải bé hơn hẳn ${1}$ , do đó

$\displaystyle t(d,N) = O(d^2 \log N).$

Có thể phản-ngẫu-nhiên-hóa (derandomize) chứng minh trên một cách dễ dàng, dẫn đến một thuật toán chạy trong thời gian ${\Theta(N^d)}$ bằng cách đặt lại bài toán theo một dạng khác và dùng kết quả hồi 2006 của Alon-Moshkovitz-Safra.

Năm ngoái ở hội nghị ICALP 2008 thì Porat và Rothschild tìm được một cách xây dựng hiệu quả hơn, cũng xây dựng được một ma trận với ${O(d^2\log N)}$ phép thử trong thời gian ${O(Nt)}$ . Phương pháp của Porat-Rothschild cũng là một phương pháp phản-ngẫu-nhiên-hóa, tuy nhiên thuật toán ngẫu nhiên hóa của họ khác với cách thô sơ trên; họ dùng mã đúng như trong cách của Kautz-Singleton, nhưng thay vì dùng một mã MDS đã sẵn thì họ xây dựng mã ngẫu nhiên để đạt đến ngưỡng của chặn Gilbert-Varshamov. Bài của anh Quang A và đồng tác giả Zeisel hồi 1988 cũng xây dựng được ma trận ${d}$ -phân-cách với ${t \leq 1.5d^2\log N}$ hàng trong thời gian khá nhanh (dù tệ hơn kết quả ${O(Nt)}$ gần đây). Bài đó cũng dựa trên ý tưởng dùng mã của Kautz-Singleton, nhưng dùng thẳng mã Reed-Solomon. Ngoài ra, các phép xây dựng dùng mã theo kiểu của Kautz-Singleton thường cho ra các ma trận mà tất cả các cột đều có cùng “cân nặng” (số số ${1}$ trong cột). Thuộc tính này một số ứng dụng cũng cần.

Như vậy ta đã biết rằng các ma trận ${d}$ -phân-cách với ${O(d^2 \log N)}$ hàng là tồn tại và có thể xây dựng được một cách tương đối nhanh. Nếu chỉ quan tâm đến việc tối thiểu hóa tổng số hàng (nghĩa là tổng số phép thử) thôi thì như vậy là rất tốt vì D’yachkov và Rykov (và sau đó Ruszinko, và Furedi) chứng minh được rằng

$\displaystyle t(d,N) = \Omega\left( \frac{d^2}{\log d} \log N \right).$

Trên thực tế thì thời gian “giải mã”, nghĩa là thời gian chỉ ra các mẫu dương tính cũng là một tham số quan trọng. Các phép xây dựng trên không cho ta biết cách giải mã như thế nào, ngoại trừ cách giải mã “ngây thơ” trong tính chất số 3 của ma trận ${d}$ -phân-cách.

Thuật toán giải mã ngây thơ:

Cho một vector kết quả ${{\bf r} = (r_i) \in \{0,1\}^t}$ , nếu mẫu máu ${j}$ nằm trong nhóm thử âm tính ${i}$ (nghĩa là ${r_i=0}$ còn ${m_{ij}=1}$ ) thì ${j}$ là âm tính. Sau khi loại hết các mẫu âm tính kiểu này thì chúng ta chỉ còn lại các mẫu dương tính mà thôi.

Bài tập: Chứng minh rằng thuật toán trên giải mã đúng.

Tuy đơn giản, thuật toán ngây thơ có thời gian chạy ${\Theta(Nt)}$ , quá lớn trong một số ứng dụng. Ví dụ, nếu ${d}$ là một hằng số thì ${Nt}$ là hàm mũ của ${t}$ . Trong một bài tới, chúng ta sẽ chỉ ra một thuật toán khác, xây dựng ma trận kiểu khác, để cho thời gian giải mã chỉ còn poly ${(t)}$ thôi.

Chủ đề : Combinatorics, Thuật Toán, Xác suất & thống kê. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

31 Comments

pandarbear

Posted 20/12/2009 at 11:26 pm | Permalink

Bác Hưng có thể phân biệt giúp PB về sự khác nhau giữa phép hội với phép cộng đại số không?

Như những gì đọc từ bài viết trên của bác thì PB giả sử hiểu phép hội ở đây ứng với phép modulo 2 thì phải ? Nhưng nếu vậy thì kết quả quan sát là r = M.x = tổng của d cột bất kỳ. Với cách hiểu là công modulo 2 thì sẽ không rút ra được kết luận như thuật giải ngây thơ. Vì giả sử trong cùng một nhóm thử i có hai mẫu thử j và (j + 1) xuất hiện dương tính thì cộng modulo 2 nó bằng 0 ở kết quả. Ngược lại nếu hiểu phép hội là phép Or logic, cụ thể là 1 + 0/1 = 1 thì PB lại không hiểu tập đại số này làm sao có thể liên kết nó với tập đại số thực bao gồm phép nhân và cộng và các giá trị là bây giờ là thực thay vì chỉ là các giá trị nhị phân ?

Reply
Ngô Quang Hưng

Posted 21/12/2009 at 6:03 am | Permalink

Hi PB, phép hội ở đây là Logical OR. Liên kết logical OR với đại số số thực quả là khó.

Reply
pandarbear

Posted 22/12/2009 at 8:29 am | Permalink

1.Bác Hưng cho PB hỏi định nghĩa 1 nhé, theo định nghĩa này thì ta rút ra khẳng định sau:

Giả sử nếu ta lấy ra 2d vecto cột bất kỳ thì nó phải thỏa mãn rằng hội của bất kỳ d vecto này sẽ khác với hội của d vecto còn lại trong 2d vecto đó,cụ nếu lấy 2 d cột $\displaystyle C_0,C_1,\cdots,C_{2d-1}$ thì :

$C_0 \cup C_1 \cup \cdots \cup C_{d-1} \neq C_{d} \cup C_{d+1} \cup \cdots \cup C_{2d-1}$

PB hiểu đúng không ?

Nếu đúng thì định nghĩa này tương tự như một ma trận của đại số tuyến tính dùng trong Compressed Sensing. Có một định lý phát biểu rằng, nếu vector tín hiệu cần đo là K-sparse thì số hàng ma trận đo M tối thiểu cần là 2K, khi đó các vecto cột của M cần thỏa mãn là bất kỳ 2K vecto cột trong N cột của M là độc lập tuyến tính. Điều này có thể đơn giản suy ra từ khái niệm ánh xạ, nếu hai vector $x_1,x_2 \in R^N, K-sparse, x_1 \neq x_2$ thì $M(x_1-x_2) \neq 0$ .

Nếu với số phép đo này thì một cách khôi phục đơn giản là phải chọn 2K cột rồi tìm lại $x = M^{-1}r$ . Nếu x là K-sparse thì nó là giá trị cần tìm. Tuy nhiên cách làm này không phù hợp với tín hiệu thực trong điều kiện chịu tác động bởi nhiễu. Trong khi như cách mô tả lý thuyết tổ hợp ở trên của bác Hưng thì lại có một thuận lợi là không gian tín hiệu lại chỉ là 0 với 1 nên khoảng cách giữa hai vecto tối thiểu cách nhau một đơn vi 1.

2. Ngoài ra, trong định nghĩa 1 và 3, hiểu hoàn toàn khác và chứa nhau có phải như:

Chẳng hạn nếu cho 2 vector $C_0 = (1,0)$ , $C_1 = (0,1)$ và $C_2 = (1,1)$ thì $C_0 \subseteq C_2$ nhưng $C_0$ không hoàn toàn khác $C_2$ , chỉ hoàn toàn khác với $C_1 = (0,1)$ .

PB hiểu như vậy có đúng không ?

Reply
Ngô Quang Hưng

Posted 22/12/2009 at 1:36 pm | Permalink

1. PB hiểu đúng rồi. Nhưng định nghĩa đó mạnh hơn điều PB phát biểu. Nói chính xác phải là: cho $d_1$ cột $C_1, \dots, C_{d_1}$ và $d_2$ cột khác $C'_1, \dots, C'_{d_2}$ — trong đó $d_1 \leq d$ và $d_2\leq d$ thì ta có

$C_1 \cup \cdots \cup C_{d_1} \neq C'_1 \cup \cdots \cup C'_{d_2}$

PB đã có quan sát sắc bén về sự tương tự và khác biệt giữa group testing và sparse signal recovery. Tôi sẽ viết thêm về mối liên quan này (chắc là phải đến bài GT 6 mới bắt đầu, vì GT 4 viết về chặn dưới, GT 5 về chặn trên và thuật toán giải mã nhanh). À cái thuận lợi của “tổ hợp” thì cũng có thể là một điều bất lợi vì mình không tận dụng được tính liên tục để làm việc trên một không gian thực nào đó. Như kiểu quy hoạch nguyên thì khó hơn quy hoạch tuyến tính.

2. $C_0 \subseteq C_2$ và $C_0$ khác cả $C_1$ lẫn $C_2$ . Xin lỗi, có lẽ chữ “hoàn toàn” gây hiểu lầm. “Hoàn toàn khác” chỉ có nghĩa là các vectors đó khác nhau, thế thôi.

Reply
Bùi Văn

Posted 04/10/2010 at 11:59 am | Permalink

Theo GS thì thời gian giải mã tối đa là dN (trường hợp tốt thì chỉ bằng d) có nhanh hơn kết quả poly(t) không?

Reply
- Ngô Quang Hưng
  
  Posted 04/10/2010 at 1:10 pm | Permalink
  
  @Bùi Văn, thuật toán ngây thơ không thể chạy trong thời gian $d$ được. Luôn là $\Theta(Nt)$ (ít nhất là $Nk$ với $k$ là “cân nặng” của cột, và khi $N$ là hàm mũ của $t$ thì tệ hơn poly $(t)$ là chắc chắn.
  
  Reply
RongChoi

Posted 27/11/2010 at 8:09 pm | Permalink

Hi anh Hưng,
Ma trận d-phân cách và d-cover-free family có gì khác nhau không ạ? RC thấy rất giống nhau.

Ngoài ra, RC có một vấn đề thế này, không biết đã có cụ nào xem xét chưa:

Giả sử ta có ma trận d-phân cách, ta có thể coi mỗi cột như một tập con của [t]. Do hội của d cột bất kỳ không chứa bất kỳ cột nào còn lại, xét $u_S$ là hội của một tập S gồm d cột thì mỗi cột còn lại trong $([N]-S)$ sẽ có ít nhất 1 phần tử thuộc $[t]-u_S$ .

Câu hỏi là liệu ta có thể phân hoạch tập $[t]-u_S$ thành $k_d$ tập con sao cho mỗi cột trong $([N]-S)$ sẽ chứa ít nhất 1 tập con trong phân hoạch này.

Với $k_d = t-|u_S|$ (phân hoạch tầm thường thành các tập con chứa 1 phần tử) thì hiển nhiên được. Vấn đề là làm sao cho $k_d$ là nhỏ nhất có thể (số tập con trong phân hoạch $[t]-U_S$ là ít nhất có thể). (Hàm “nhỏ” có thể được định nghĩa một cách nào đó theo t,d). Hay nói cách khác, xây dựng ma trận giữ tính chất d-phân cách để có thể có $k_d$ là nhỏ.

Reply
- Ngô Quang Hưng
  
  Posted 28/11/2010 at 4:22 pm | Permalink
  
  Hi RC,
  
  1. $d$ -phân cách và $d$ -cover-free family là tương đương nhau.
  
  2. Ma trận đơn vị là ma trận phân cách. Trong trường hợp này cái phân hoạch tầm thường là phân hoạch duy nhất thỏa điều kiện RC cần. Do đó, chắc RC phải thay đổi bài toán một chút, không thể xét một ma trận phân cách bất kỳ được.
  
  À, nhưng câu cuối cùng của RC đã phát biểu bài toán như vậy. Câu hỏi hay đó! RC có ứng dụng gì cụ thể không? Cần giải mã nhanh không? Cần xây dựng nhanh không?
  
  Reply
RongChoi

Posted 28/11/2010 at 5:15 pm | Permalink

Hi anh Hưng,

Khi hỏi quả là RC có nghĩ đến ứng dụng sau đây:
- Tập khóa $T$ gồm $t$ khóa.
- Mỗi người có một tập khóa là tập con của $T$ , được xác định tương ứng bởi 1 cột trong ma trận. Như vậy có tổng cộng $N$ người.
- Giả sử có $d$ người bị phát hiện gian lận, chẳng hạn như tiết lộ thông tin bí mật của nhóm (lập thành tập $S$ ) và hệ thống muốn loại bỏ họ. Khi đó sẽ loại bỏ các khóa tương ứng với hội của $d$ người này, tức các khóa trong $u_S$ .
- Nếu mă với từng khóa riêng lẻ trong $[t] - u_S$ thì đạt được mục đích những ai trong $S$ không giải mã được và những ai trong $([N]-S)$ giải được, nhưng khá lâu và do đó không hiểu quả. Giả sử ta phân hoạch $[t] - u_S$ được thành các $k_d$ tập con sao cho mỗi cột trong $([N]-S)$ sẽ chứa ít nhất 1 tập con trong phân hoạch này. Khi đó, nếu coi mỗi tâp con là 1 khóa mới thì vẫn thỏa mãn tính chất là mỗi người trong $([N]-S)$ sẽ giải mã được (mỗi người vẫn chứa ít nhất 1 khóa mới).
- Thực ra điều kiện trên có thể được giảm bớt đáng kể, chỉ cần: phân hoạch một tập con bất kỳ nào đó của tập $[t]-u_S$ thành $k_d$ tập con sao cho mỗi cột trong $([N]-S)$ sẽ chứa ít nhất 1 tập con trong phân hoạch này. Khi đó những ai trong $S$ vẫn không giải mã được và những ai trong $([N]-S)$ vẫn giải được.

Ngoài ra tập khóa cần phải được giữ không quá lớn. Chẳng hạn như cách xây dựng $t = O(d^2 \log(N))$ là thỏa mãn. Những trường hợp như ma trận đơn vị, kể cả nếu có dẫn tới cho ta $k_d$ nhỏ, thì vẫn sẽ bị loại từ vòng gửi xe vì $t= N$ là quá lớn.

Tất nhiên nếu xây dựng cái phân hoạch được nhanh thì quá tốt. Giải mã nhanh chắc chắn cũng sẽ rất cần thiết, nhưng trong ứng dụng trên ta có thể tạm bỏ qua.
Ngay trong trường hợp $d = 1$ thì RC cũng chưa thấy ngay cách xây dựng nào tốt. Ta có thể xét trường hợp riêng này trước?

Reply
- Ngô Quang Hưng
  
  Posted 29/11/2010 at 5:14 pm | Permalink
  
  Hi RC,
  
  Bài toán rất hay! Có hai tham số: tổng số khóa $t$ , và $k_d$ . Ta muốn cả hai đều nhỏ so với $N$ (và $d$ ). Nhưng hai chú này chắc là trade-off của nhau.
  
  Ví dụ $d=1$ trước. Với $N$ cố định thì $t$ nhỏ nhất là $t$ thỏa mãn $\binom{t}{t/2} \geq N$ . Cách thiết kế ma trận là gán mỗi cột là một tập con kích thước $t/2$ của $[t]$ . Thế nhưng, khi đó dễ thấy rằng $k_d = t/2 = t-u_S \approx \Theta(\log N)$ .
  
  Nhưng $k_d \approx \log N$ cũng được đấy chứ nhỉ, cho $d=1$ ?
  
  Reply
RongChoi

Posted 29/11/2010 at 6:54 pm | Permalink

Hi anh Hưng,
Hình như cách xây dựng này không hơn cách xây dựng tổng quát (hoặc chênh nhau 1 hằng số nhỏ). Trong cách tổng quát thì $t=O(d^2 \log(N))$ và với cách chọn tầm thường thì $k_d = t - | u_S|$ . Khi thay $d = 1$ thì cho ta kết quả tương tự?
Nhưng có lẽ với trường hợp $d = 1$ thì cũng không hơn được.

Không biết trong trường hợp tổng quát liệu ta có thể đặt được $t=O(d^2 \log^{c_1}(N))$ và $k_d=O(d^{c_2} \log(N))$ , cho phép $c_1 >1$ nhưng buộc $c_2 < 1$ . Tức là cho phép buông lỏng $t =O(d^ 2,poly(\log(N))$ để có $k_d= O(sublinear(d),\log(N))$ .

Reply
- Ngô Quang Hưng
  
  Posted 30/11/2010 at 5:38 pm | Permalink
  
  Hi RC,
  
  Có chiến lược này có thể … gần được: chia bộ $t$ hàng thành $n$ nhóm, mỗi nhóm $q$ hàng. Như vậy, $t =nq$ . Xét nhóm hàng thứ $i$ . Mỗi cột $c$ chỉ có một số $1$ trong nhóm hàng thứ $i$ mà thôi. Chọn số $1$ này một cách ngẫu nhiên trong nhóm. Có thể nghĩ về $q$ hàng trong nhóm thứ $i$ này như $q$ cái rọ, và ta “ném” các cột (hay bi) một cách ngẫu nhiên vào các rọ. Ta làm vậy với tất cả các nhóm hàng/rọ. Theo cách này thì mỗi cột sẽ có $n$ số $1$ .
  
  Ta có thể chứng minh được, với xác suất rất cao (gần đến 1), và với $n \approx q \approx d \log N$ thì ma trận xây dựng như trên là một ma trận $d$ -phân cách
  
  Chúng ta cần biết giá trị $k_d$ là bao nhiêu. Nói cách khác, ta cần tìm một tập $k_d$ các rọ (ở bất kỳ nhóm hàng nào) mà sao cho hội của các rọ này chứa tất cả các hàng “tốt” và *không* chứa bất kỳ một trong $d$ hàng xấu nào.
  
  (Lưu ý rằng formulation này hơi khác với cái phân hoạch của RC: chúng ta không cần phân hoạch các rọ, miễn là tìm một bộ rọ không chứa “bi” xấu mà lại “cover” tất cả các bi tốt là được.)
  
  Hãy xét nhóm hàng thứ nhất: có nhiều nhất là $d$ rọ không dùng được, tất cả các rọ còn lại đều dùng được để “cover” nhóm bi tốt. Sau khi dùng các rọ này thì ta cần “cover” khoảng chừng (tính trị kỳ vọng) $dN/q \approx N/\log N$ hàng chưa được “covered” (những hàng bị nhét vào chung rọ với bọn $d$ hàng xấu).
  
  Để “cover” tập $S$ gồm khoảng $N/\log N$ hàng này thì ta xét đến nhóm hàng thứ hai. Có lẽ (RC chứng minh thử nhé!) ta sẽ chứng minh được rằng một tỉ lệ nhất định các hàng trong $S$ (một nửa chẳng hạn) có thể được “covered” bằng các rọ trong nhóm rọ thứ $2$ .
  
  Nếu tỉ lệ này không đổi, thì sau khoảng $\log$ bước, chúng ta sẽ cover hết tất cả các rọ của $S$ .
  
  Tổng cộng số rọ $k_d$ cần dùng sẽ vào khoảng $d \text{poly}(\log)$
  
  Reply
  - RongChoi
    
    Posted 01/12/2010 at 8:51 am | Permalink
    
    Hi anh Hưng,
    Có chỗ trong lập luận của anh RC chưa rõ : Nếu cả $d$ hàng xấu đều không thuộc nhóm thứ nhất thì anh sẽ lấy hợp của cả $q$ rọ trong nhóm thứ nhất? Cái hợp này sẽ cho ta tập $[N]$ và bao luôn tất cả hàng xấu lẫn hàng tốt?
    
    Ngoài ra cái Reformulation của anh không áp dụng được vào ứng dụng của RC. Tuy nhiên RC đang suy nghĩ, rất có thể cái Reformulation này sẽ cho một ứng dụng đẹp nào đó. Ta có thể phát biểu lại:
    
    Prob2: Tìm một tập $T$ con của $[N]$ sao cho mọi hàng xấu đều không phải tập con của $T$ và mọi hàng tốt đều là con của $T$ .
    
    Giờ RC giải thích rõ hơn tại sao ứng dụng của RC cần formulation khác.
    
    Prob 1: Tìm một họ các tập $T_1,\dots, T_{k_d}$ sao cho mọi $T_i$ đều không là tập con của hợp các hàng xấu VÀ với mọi hàng tốt đều tồn tại một tập $T_i$ là con của nó.
    
    Prob 1′(giảm nhẹ): Tìm một họ các tập $T_1,\dots, T_{k_d}$ sao cho mọi $T_i$ đều không là tập con của mỗi hàng xấu và với mọi hàng tốt đều tồn tại một tập $T_i$ là con của nó.
    
    Ví dụ với N= 6, t=5:
    
    1 0 0 1 0 1 0
    1 0 1 1 1 0 1
    0 1 0 1 0 1 0
    1 0 1 1 0 0 1
    0 1 0 0 1 1 0
    
    Giả sử cần loại hàng 1 và 3. Hội của chúng cho ta 1 1 0 1 0 0
    
    Trường hợp tầm thường, lấy $T_1 = \{3\}, T_2 = \{5\}, , T_3 = \{6\}$ thì thỏa mãn nhưng $k_d = 3$ lớn.
    
    Ta có thể làm tốt hơn bằng cách lấy $T_1 = \{3,6\}, T_2 = \{5\}$ . Khi đó $T_1$ là con của hàng 2,4 và $T_2$ là con của hàng 5. Và $k_d=2$ tốt hơn trường hợp trên.
    Nếu coi mỗi cột là một khóa. Ta có thể khóa bản rõ M của ta với $K_3 + K_6$ (tương ứng $T_1$ ) và với $K_5$ (tương ứng $T_2$ ). Khi đó ta thấy được chỉ người 2,4,5 giải được, còn người 1, 3 không giải được dù hợp lực với nhau.
    
    Nếu đạt $k_d = d poly(\log N)$ thì RC nghĩ cũng là một kết quả không tồi. Để đạt $k_d = sublinear(d) poly(\log N)$ như RC mong có thể hơn quá tham vọng.
    
    Reply
    - Ngô Quang Hưng
      
      Posted 01/12/2010 at 10:15 am | Permalink
      
      Hi RC,
      
      Có chỗ trong lập luận của anh RC chưa rõ : Nếu cả hàng xấu đều không thuộc nhóm thứ nhất thì anh sẽ lấy hợp của cả rọ trong nhóm thứ nhất? Cái hợp này sẽ cho ta tập và bao luôn tất cả hàng xấu lẫn hàng tốt?
      
      Tại vì khi ném bi vào rọ, mỗi bi phải thuộc một rọ nào đó (thuộc nhóm thứ i), cho nên mỗi hàng xấu phải thuộc vào một rọ nào đó của nhóm. Nếu lấy toàn bộ q rọ trong nhóm thì cover tất cả các hàng.
      
      Ngoài ra cái Reformulation của anh không áp dụng được vào ứng dụng của RC. Tuy nhiên RC đang suy nghĩ, rất có thể cái Reformulation này sẽ cho một ứng dụng đẹp nào đó.
      
      Tôi không hiểu tại sao không áp dụng được cho ứng dụng của RC. À, trong reply trước tôi viết sai. Đáng lẽ phải là cột xấu/tốt chứ không phải hàng xấu tốt. Không biết cái này có làm RC hiểu lầm không.
      
      Cột = bi (= người dùng/account)
      
      Hàng = rọ (= khóa)
      
      Bi xấu = compromised accounts/users
      
      Có nhiều nhất là d bi xấu. Chúng ta cần lấy ra một bộ $k_d$ khóa (i.e. rọ) sao cho các rọ này chứa tất cả các bi tốt và không chứa bi xấu nào. Khi đó, mỗi account tốt sẽ có ít nhất một khóa mà không account xấu nào có. Tôi tưởng đây là (một biến thể tương tự của) bài toán mà RC đang nghĩ tới?
    - RongChoi
      
      Posted 01/12/2010 at 10:29 am | Permalink
      
      Hi anh Hưng,
      Đúng là RC khi đọc “hàng xấu” đã lẫn mỗi người là 1 hàng, do vậy mới có chuyện nhóm đầu không chứa người xấu nào.
      Ví dụ trên của RC cũng lẫn cho người là hàng.
      RC sẽ xem lại kỹ hơn phương án của anh.
RongChoi

Posted 01/12/2010 at 11:32 am | Permalink

Hi anh Hưng,

RC sẽ xem kỹ hơn nhưng có vẻ đó là một phương án rất thú vị.

Nếu ở bước thứ $i$ ta còn $s_i$ người chưa được covered. Chỉ tính riêng nhóm thứ $i+1$ , số người không được cover nhiều nhất là $N/\log N$ .

Số người sau bước thứ $i+1$ không được covered là những người trong $s_i$ người chưa được covered ở bước $i$ , và sau đó cũng không được covered ở bước $i+1$ .

Mặt khác, xác suất 1 người không được covered ở bước $i+1$ là $1/ \log N$ . Do vậy số người sau bước thứ $i+1$ không được covered là $s_{i+1} = s_i/\log N$ .

Từ đó suy ra số bước để cover tất cả là $\log N/(\log (\log N))$ .

Reply
RongChoi

Posted 01/12/2010 at 5:48 pm | Permalink

Hi anh Hưng,

RC nghĩ hiện tại chúng ta có:
- Cho tối đa $d$ kẻ ăn gian cần loại bỏ
- Muốn loại bỏ cần sử dụng ma trận cỡ $t \times N$ với $t = d^2\log^2N$ . Yếu hơn đôi chút so với lời giải tối ưu $t = O(d^2\log N)$ .
- Số khóa cần sử dụng $d\log^2N/(\log(\log N))$ . Tốt hơn đáng kể so với lời giải tầm thường $(d^2\log N)$ khi $d>\log N$ .

Để cải thiện, RC nghĩ chúng ta có thể giảm nhẹ mục đích bài toán như sau:
- Yêu cầu của bài toán gốc phía trên là có nhiều nhất $d$ kẻ ăn gian (hợp thành tập $S$ ), và ta cần truyền thông điệp cho toàn bộ $N-d$ người còn lại.
- Tuy nhiên, trong thực tế, ta không phải lúc nào cũng cần truyền cho tất cả những người còn lại mà chỉ cần gửi cho một tập con $P$ (gồm $p$ người nào đó) trong số $N-d$ người còn lại.

- Ví dụ về một ứng dụng cho bài toán mới này như sau. Ta thiết lập một danh sách tất cả những người quen để gửi email. Sau một thời gian ta thấy cần loại bỏ một tập $S$ người và không bao giờ muốn họ giải mã mail của ta. Tuy nhiên với 1 cái mail có nội dung cụ thể, ta chỉ cần gửi cho 1 nhóm con trong danh sách còn lại sau khi loại bỏ những người trong $S$ chứ không cần gửi cho tất cả. Chẳng hạn, nếu mail về Tin thì cho nhóm bạn Tin, về Toán cho nhóm bạn Toán.

- Yêu cầu của ta khi gửi là: Những người trong $S$ không thể giải được, những người trong $T$ chắc chắn giải được, những người còn lại ta không quan tâm (1 bạn Toán thích tò mò giải được một cái mail về Tin cũng không sao).
- Với yêu cầu trên, liệu ta có thể giảm được đáng kể số khóa cần dùng không?

Một số nhận xét:
- Khi $P = [N]-S$ , trở lại bài toán gốc
- Lời giải của bài toán gốc cũng là một lời giải cho bài toán mới. Do vậy số khóa tối đa là $d\log^2N/(\log(\log N))$ .
- Trong bài toán mới, sau khi loại bỏ các khóa trong hội của $S$ , với mỗi thành viên trong $P$ ta chọn sử dụng 1 khóa của người đó mà không trong $S$ (đảm bảo sự tồn tại, từ tính chất $d-$ phân cách). Đây cũng là một lời giải tầm thường và cho số khóa cần dùng là $p$ .

Do đó, mục đích là làm sao số khóa sử dụng tốt hơn hẳn $\min(p, d\log^2N/(\log(\log N)))$ .

Reply
- Ngô Quang Hưng
  
  Posted 02/12/2010 at 10:07 am | Permalink
  
  @RC, nếu mà chiến lược trên là đúng thì mình chỉ cần khoảng $O((d\log N) \cdot (\log |P|))$ rọ để “cover” $P$ , phải không nhỉ.
  
  Reply
  - RongChoi
    
    Posted 03/12/2010 at 10:36 am | Permalink
    
    Theo RC thì đúng vậy, và như thế chứng tỏ việc đưa vào $P$ có tiềm năng dẫn đến sự thay đổi tốt
    Tuy nhiên chiến lược này không cần thông tin về P và độ cải thiện là $\log N/ \log p$ cũng không phải tốt lắm, dù có ý nghĩa lý thuyết . Nếu tận dụng thông tin về $P$ , chẳng hạn hội của $P$ thì có lẽ ta sẽ có kết quả tốt hơn, chí ít không cần dùng các hàng không nằm trong hội của $P$ .
    Ngoài ra thì độ phức tạp của việc giải mã đối với ma trận trên là bao nhiêu ạ, hình như không nhanh lắm? RC sẽ trình bày vì sao sự giải mã có vai trò cũng quan trọng, nhưng 2 hôm nay bị ốm nên đánh khất để sau.
    
    Reply
  - RongChoi
    
    Posted 07/12/2010 at 7:07 pm | Permalink
    
    Hi anh Hưng,
    RC tiếp tục về ứng dụng của ma trận phía trên.
    Hiện tại thì chúng ta đã có thể loại bỏ $d$ người trong hệ thống, bằng cách sử dụng $d\log^2 N$ khóa.
    
    Bây giờ ta hình dung đến trường hợp sau đây: Có kẻ xấu Pirate mua chuộc được $c$ người ( $c \leq d$ ), và do đó thu thập được tất cả các khóa của $c$ người này. Nó ghi toàn bộ các khóa này vào 1 đầu đọc và che dấu rất kỹ thuật để từ cái đầu đọc này ta không thấy được các khóa ẩn trong đó. Bây giờ khi ta gửi bản mã cho mọi người, chỉ cần 1 người trong số những người Pirate mua chuộc được giả được mã là cái đầu đọc của Pirate cũng giải được mã. Vô hình chung cái đầu đọc của Pirate tượng trưng cho sức mạnh giải mã tổng hợp của $c$ người nó mua chuộc được. Pirate sau đó nhân rộng cái đầu đọc thành hàng trăm nghìn bản và bán đầy rẫy ở chợ trời, ai mua cũng được.
    
    Vấn đề của ta bây giờ là ta sẽ ra chợ trời mua 1 cái đầu đọc. Mục đích hay bài toán của ta sẽ là truy ra chính xác $c$ người đã tiếp tay cho Pirate. Trừng trị nghiêm khắc $c$ người này sẽ là cách hữu hiệu ngăn chặn việc sản xuất đầu đọc giả (không ai tiếp tay cho kẻ xấu nữa).
    
    Và tính chất $d-$ -cover free giúp ta giải quyết bài toán trên một cách hiệu quả.
    
    Với cái đầu đọc trong tay, ta có thể làm gì?
    - Ta đầu tiên gửi tín hiệu được mã bằng khóa thứ nhất, tức là tương ứng hàng thứ nhất. Nếu đầu đọc giải được mã có nghĩa là hội của $c$ người ẩn trong đầu đọc có khóa thứ nhất.
    - Làm tương tự lần lượt với tất cả các hàng.
    - Cuối cùng kết quả thu được chính là hội của $c$ người ẩn trong đầu đọc.
    - Với tính chất giải mã được từ véc tơ hội, ta tìm lại được chính xác $c$ thủ phạm!
    
    Cách bên trên hoàn toàn trùng khớp với thử nhóm để tìm ra các mẫu máu dương tính.
    
    Tuy nhiên, ta chỉ làm được như trên với một Pirate không thông minh lắm.
    Lý do là bởi, ở phía trên, khi mã hóa, ta luôn dùng tới $d \log^2 N$ hàng. Vậy mà bây giờ ta lại chỉ dùng có 1 hàng, Pirate phát hiện ra sự bất bình thường và đầu đọc không giải mã. Và đó là sự khác biệt với thử nhóm.
    
    Câu hỏi trở thành: mỗi lần ta phải sử dụng cùng 1 lúc $O(d \log^2 N)$ hàng chứ không phải 1 hàng (có như vậy Pirate mói không phát hiện ra sự bất thường) và Pirate chỉ cần có 1 trong các khóa tươg ứng các hàng này là giải được. Làm sao để vẫn có thể tìm được véc tơ hội của $c$ véc tơ mà Pirate sở hữu?
    
    (RC có một số ý tưởng, đưa vào các dummy rows nhưng không cơ bản, tối ưu nhất là vẫn giữ nguyên ma trận trên mà vẫn tìm được véc tơ hội)
    
    Reply
    - Ngô Quang Hưng
      
      Posted 08/12/2010 at 5:20 pm | Permalink
      
      Hi RC,
      
      Biến thể này tôi không hiểu lắm. Có phải là:
      
      1. Mỗi phép thử là một tập gồm $K$ hàng ( $K = O(d\log^2N)$ chẳng hạn)
      2. Kết quả là YES/NO. YES nều một trong $c$ cột bí mật có phần giao với một trong $K$ hàng, và NO nếu không cột nào có số 1 nào trong K hàng.
      
      Tìm cách thiết kế ma trận với số hàng tối thiểu để có thể chỉ ra c cột bí mật?
    - RongChoi
      
      Posted 08/12/2010 at 6:12 pm | Permalink
      
      Hi anh Hưng,
      Chính xác là như vậy.
      
      Ma trận $n$ blocks, mỗi blocks $q$ hàng phía trên cho phép ta gửi thông điêp cho tất cả mọi người, trừ $d$ kẻ gian. Muốn vậy, mỗi thông điêp cần dùng $K$ hàng đồng thời. Do vậy một valid ciphertext phải sử dụng $K$ hàng. Do đó đầu đọc của Pirate cũng chỉ chấp nhận những phép thử cho valid ciphertext, tức phép thử tương ứng với $K$ hàng.
      
      Một cách tổng quát, tìm cách thiết kế ma trận:
      -P1: khi loại bỏ $d$ người thì cần sử dụng $K$ hàng. Mục tiều là tối thiểu hóa $K$ (tức là tối thiểu hóa ciphertext size). Phía trên ta đã có được ma trận thỏa mãn tính chất này với $K= d\log^2 N$ . Chú ý là ta không cần tối thiểu hóa số hàng của ma trận, lớn không sao miễn là poly(d,\log N). Ma trận phía trên rất tốt, số hàng là $d^2 \log^2N$ . (Lý do không cần tối thiểu hóa số hàng sẽ cần giải thích kỹ hơn nhưng một cách đại khái là vì số hàng tương ứng private key size, nhưng bằng cách áp dụng 1 kỹ thuật ghép dựa trên RSA, ta có thể compact cái private key size này về cỡ hằng số ).
      - P2: bằng cách sử dụng các phép thử đồng thời $K$ hàng ( $K$ xác định bởi P1), tìm véc tơ hội của $c$ kẻ gian (ẩn trong đầu đọc giả). Từ véc tơ hội này tìm lại $c$ kẻ gian. Mục tiêu là tối thiểu hóa số phép thử và tối thiểu hóa thời gian giải mã (từ véc tơ hội về $c$ kẻ gian). Tuy nhiên, trước mắt chưa cần hiệu quả mà chỉ cần chứng tỏ có thể đạt được P2 đối với các ma trận có tính chất P1 là đã rất đep.
      
      Một tính chất khác nếu có được thì rất tốt, đó là các hàng trông “giống nhau” để ngăn một số chiến thuật thông minh của kẻ tấn công. Nhưng ma trận phía trên anh đưa ra đã đạt tính chất này. Do vậy, RC rất kết ma trận $n$ blocks, mỗi blocks $q$ hàng phía trên . Điều nó còn thiếu là tính chất P2.
    - Ngô Quang Hưng
      
      Posted 09/12/2010 at 11:20 am | Permalink
      
      Hi RC, bỏ qua tốc độ giải mã, một cách brute-force có thể làm là
      
      1. Tìm một tập $S$ gồm $K$ hàng mà sao cho $c$ cột bí mật không giao, nghĩa là đầu đọc không giải mã được. Ta có thể tìm $K$ hàng này một cách brute-force. Tổng số hàng mà hội của $c\leq d$ cột bí mật chiếm giữ là $d^2\log N$ , do đó có ít nhất $d^2\log^2N - d^2\log N > K$ hàng mà đám cột bí mật không chiếm đóng.
      
      2. Sau đó, lấy một hàng $h$ ra khỏi $S$ và thay nó bằng một trong các hàng $h'$ còn lại. Cứ như vậy từng hàng một, cho $h'$ duyệt qua tất cả các hàng còn lại. Mỗi lần thử thì dùng $S-h+h'$ . Và, mỗi lần thử có thể dùng một $h$ khác trong $S$ .
      
      Cách này có vẻ không hay vì 2 lý do: một là tìm ra $S$ tốn thời gian quá; hai là các bộ $K$ hàng dùng để thử có phần chung hơi lớn quá.
      
      Nếu cần “diversify” các phép thử hơn nữa cũng có lẽ được; phải nghĩ thêm. Có vẻ như đây là một bài thử nhóm “bên trong” một bài thử nhóm khác. Ta có thể nghĩ như sau. Giả sử $t$ là tổng số hàng của ma trận đã xây dựng. Chúng ta cần tìm $C$ , vector hội của các “cột xấu”. Vector hội này có nhiều nhất là $D = d^2\log N$ số 1. Và dimension của nó là $t = d^2\log^2N$ . Chúng ta cần dùng các phép thử kích thước $K = d\log^2N$ để chỉ ra vị trí của các số 1 trong vector hội.
      
      Hãy xét một ma trận $D$ -disjunct gồm $t'$ hàng và $t$ cột sao cho mỗi hàng có cân nặng chính xác là $K$ . Ta sẽ dùng ma trận này để thiết kế các phép thử. Nếu ma trận này có ít hàng thì số phép thử ít. Nếu nó giải mã nhanh được thì ta cũng giải mã nhanh được. Trong bài toán của RC có vẻ như một adaptive strategy là đủ, không cần non-adaptive.
    - RongChoi
      
      Posted 09/12/2010 at 11:57 am | Permalink
      
      Hi anh Hưng,
      RC trên kia có nói đến cách đưa vào dummy rows, nó cũng khá giống cách anh nói. Ta đưa vào $d \log^2 N$ hàng toàn 0 (không ai có khóa), nhét ngẫu nhiên xen kẽ với các hàng thât. Sau đó trong phép thử thì dùng $K-1$ dummy rows và 1 hàng thật.
      Cách này và cách của anh sẽ loại bỏ được các chú Pirate khá thông minh nhưng chưa thông minh lắm. Tuy nhiên đó cũng là một bước tiến tới đích. Cách của RC có nhược điểm là các hàng không còn giống nhau nữa(nhưng Pirate vẫn không phân biệt được 1 dummy row với 1 hàng thật ở đó nó không có khóa: giới hạn trên $c$ cột nó sở hữu thì cả 2 loại đều chứa toàn 0), có ưu điểm là không cần dùng brute-force để tìm.
      
      Còn một loại Pirate có thể coi là rất thông minh thì chúng nó có thể so sánh số khóa ở hữu. Bình thường nếu ta dùng $K$ hàng và nếu $c$ cột nó sở hữu không bị loại bỏ, trung bình nó sẽ sở hữu khoảng $c(1-( q-1/q)^K)$ tức là rất nhiều khóa. Do vậy nếu trong phép thử nó thấy nó chỉ có duy nhất 1 khóa nó có thể sẽ từ chối, xác suất nó từ chối nhầm có thể rất rất bé. Tuy nhiên, chống lại loại Pirate này có lẽ hơi khó, phải luôn gửi $K$ hàng gần như là ngẫu nhiên.
      
      Nhưng có thể giảm bới yêu cầu bằng cách xét các threshold-Pirate: nếu nó có từ $t$ khóa trở lên nó sẽ giải mã, dưới thì nhất định không. Đối với loại này RC định đưa các dummy rows toàn 1 vào, mỗi lần gửi $t-1$ dummy rows loại này+ 1 hàng thât. Tuy nhiên ở đây, kha’c với dummy rows toàn 0, Pirate có thể phân biệt dummy rows toàn 1 và normal row vì giao của $c$ cột với dummy rows toàn 1 cho ra toàn 1, quá bất bình thường.
      
      Đúng như anh nói, adaptive strategy là đủ, và càng “diversify” các phép thử càng làm ta xử lý được các Pirate thông minh hơn.
    - Ngô Quang Hưng
      
      Posted 09/12/2010 at 12:08 pm | Permalink
      
      Hi RC,
      
      Như vậy cách tốt nhất để formalize bài toán và lời giải là dùng cái chiến lược “thử nhóm bên trong thử nhóm” ở trên. Việc xây dựng một ma trận (hoặc chiến lược thử nhóm adaptive) với $D$ mẫu máu dương tính, mỗi phép thử có $K$ mẫu, cũng không khó lắm.
      
      Một trong các cách xây dựng rất đơn giản là chọn các hàng của ma trận này ngẫu nhiên. Ta có thể chứng minh bằng pp xác suất là nếu chọn đủ hàng thì ma trận sẽ là $D$ -disjunct. Lợi điểm của phương pháp này là các hàng trông sẽ rất giống nhau, chú pirate không có cách gì phân biệt được. Cái dở có lẽ là cần hơi nhiều hàng.
      
      Cái threshold-pirate cũng rất thú vị. Nhưng như thế mình phải giả sử $t \leq c \leq d$ nhỉ.
    - RongChoi
      
      Posted 09/12/2010 at 12:27 pm | Permalink
      
      Hi anh Hưng,
      Số hàng nhiều không thành vấn đề ạ, miễn là $K$ đừng lớn quá theo đó. Nếu $K$ không lớn quá thì số hàng là tiêu chí chúng ta có thể hy sinh không thương tiếc để đạt các mục đích khác quan trọng hơn.
      Đúng là cần giả thiết $t \leq c \leq d$ .
    - RongChoi
      
      Posted 09/12/2010 at 6:31 pm | Permalink
      
      RC giải thích 1 chút tại sao số hàng nhiều không thành vấn đề.
      Số hàng liên quan đến độ dài khóa bí mật, vì mỗi hàng tương ứng 1 khóa. Chẳng hạn nếu anh Hưng là một người trong hệ thống, tương ứng với cột 011001 thì có nghĩa khóa bí mật của anh Hưng gồm 3 khóa $k_2,k_3,k_6$ . Rõ ràng khi số hàng lớn thì số khóa của mỗi người cũng có thể lớn.
      Tuy vậy ta có cách gộp các khóa này lại với nhau bằng cách sử dụng RSA: cho cùng 1 modulus N, định nghĩa khóa $k_i = x ^{1/e_i}$ với $(e_i,d_i)$ là một cặp khóa công khai/bí mật RSA và $x$ là một giá trị cố định không cần bí mật.
      Khi đó, thay vì đưa cho anh Hưng 3 khóa $k_2,k_3,k_6$ , ta chỉ cần cho anh Hưng 1 giá trị $x ^{1/(e_2e_3e_6)}$ . Từ các khóa công khai anh Hưng sẽ tự tính được $k_2,k_3,k_6$ (tất cả các phép tính theo modulo N).
      Như vậy dù có nhiều hàng thì khóa cho mỗi người vẫn có thể đưa về 1 giá trị. Chính thế mà số hàng lớn không thành vấn đề (tuy rằng việc chứng minh tính bảo mật sẽ không phải là dễ).
      
      RC vẫn chưa thấy cách xây dựng ma trận ngẫu nhiên cho phép giải quyết vấn đề, đạt 2 mục tiêu:
      - Giữ mục tiêu loại bỏ một nhóm không cho phép giải mã, bằng cách gửi $K$ hàng mỗi lần
      - Đạt mục tiêu tìm lại được véc tơ hội của một tập $c$ cột, cũng bằng các phếp thử $K$ mẫu.
      Anh Hưng có thể nói rõ hơn không? RC nghĩ vẫn nên giữ ý tưởng xây ma trận trên các blocks con?
    - Ngô Quang Hưng
      
      Posted 09/12/2010 at 7:59 pm | Permalink
      
      Hi RC, về phần xây dựng ngẫu nhiên, để mình viết rõ hơn.
      
      Có *hai* ma trận, chắc là confusion đến từ chỗ này.
      
      1. Ma trận $M$ có tính $d$ -disjunct mình vẫn xây dựng như đã mô tả, chia thành $n$ nhóm, mỗi nhóm $q$ rọ. Giả sử ma trận $M$ có kích thước $t \times N$ .
      
      2. Ma trận $M$ thỏa tính chất P1 như RC đã viết. Bây giờ ta chứng minh $M$ cũng thỏa tính chất P2. Tính chất này nói là, chúng ta phải dùng nhiều phép thử, mỗi phép thử là một tập $S$ gồm đúng $K$ hàng của $M$ . Phép thử trả về YES nếu ít nhất một trong $c$ cột “xấu” có giao với $S$ , và trả về NO nếu không cột xấu nào giao với $S$ .
      
      Câu hỏi là, ta phải chọn các phép thử $S$ như thế nào để có thể xác định được vector hội $C$ của $c$ cột xấu? Từ vector hội $C$ chúng ta sẽ giải mã ra được các cột xấu.
      
      Vector hội $C$ là vector nhị phân có số chiều là $t$ . Tổng số số 1 của $C$ nhiều nhất là $D = d^2\log N$ , tại vì mỗi cột xấu của $M$ có $n = d\log N$ số 1. Do đó, bài toán trở thành bài toán chỉ ra vị trí của $D$ số 1 trong một vector $t$ -chiều.
      
      Bài toán này chính là bài toán … thử nhóm! Và do đó ta sẽ dùng một ma trận $D$ -disjunct thứ hai, gọi nó là ma trận $A$ , có $t'$ hàng và $t$ cột. Mỗi hàng của $A$ có cân nặng bằng $K$ , tương ứng với một tập con $S$ kích thước $K$ của $[t]$ .
      
      Nếu ma trận $A$ có tính $D$ -disjunct là xong! Và ta có thể xây dựng $A$ bằng cách chọn các hàng của $A$ một cách ngẫu nhiên. Nói chung có nhiều cách xây dựng $A$ sao cho $A$ là $D$ -disjunct và mỗi hàng của $A$ có cân nặng là $K$ . Điều RC muốn là các hàng của $A$ trông “uniform”. Ta có thể lấy $A$ là tập tất cả các hàng với cân nặng $K$ .
RongChoi

Posted 10/12/2010 at 12:50 pm | Permalink

Hi anh Hưng,
A ha, ma trận $A$ là ma trận “ảo”, tức là nó không phục thuộc gì vào $M$ . lúc đầu RC tưởng anh định làm như kiểu mã trong mã ngoài (mỗi cột của $M$ tương ứng một ma trận $A$ ) nhưng ko phải.
Tức là xây dựng ma trận $A$ độc lập có tính chất D-disjunct, mỗi hàng trong số $K$ , nếu các bít 1 của nó là $i_1, \dots, i_K$ thì thực chất trong phép thử ma trận $M$ ta sẽ chọn các hàng $i_1, \dots, i_K$ : nếu các hàng này giao $C$ thì nó đồng thời có nghĩa phép thử tương ứng trong $A$ chứa máu dương tính. Tìm được vị trí các mẫu dương tính trong $A$ tương ứng cho ta véc tơ hội $C$ .

Cách xây dựng rất thú vị! Nếu ma trận $A$ được chọn ngẫu nhiên thì đúng là coi như mỗi lần chọn ngẫu nhiên $K$ hàng trong ma trận $M$ .

Vấn đề theo RC gần như giải quyết trọn vẹn . Tuy nhiên, ma trận $A$ có hơi ngẫu nhiên quá đến mức Pirate phát hiện ra không? Lý do là khi ta mã thì ta lại không chọn các hàng một cách ngẫu nhiên.

Khi mã, ta chọn block thứ nhất, loại các hàng chứa khóa của tập ta muốn loại, và sử dụng toàn bộ các hàng còn lại. Ta tiếp tục như vậy với block thứ 2, 3… cho đến khi cover toàn bộ tập các users cần gửi. Như vậy cách chọn các hàng không hoàn toàn ngẫu nhiên.

Nhưng có lẽ vấn đề cũng dễ giải quyết: thay vì chọn như trên thì ta chọn các hàng ngẫu nhiên không theo block, việc phân tích số hàng cần thiết có thể hơi khác đôi chủt. Cách thứ hai là vẫn sử dụng y như nguyên cách trên kia, chỉ có điều ta đưa vào thêm một hoán vị ngẫu nhiên các hàng $P$ (kỹ thuật Boneh-Shaw), thay vì sử dụng ma trận $M$ , ta sử dụng ma trận $M' = P(M)$ . Khi đó, dù chọn các hàng theo block thì nếu không biết hoán vị $P$ , nó tương tự như chọn các hàng ngẫu nhiên.

Reply
- Ngô Quang Hưng
  
  Posted 10/12/2010 at 1:49 pm | Permalink
  
  Hi RC, vậy bây giờ đến bước viết các chứng minh ra cụ thể xem có ước lượng sai chỗ nào không. Hôm nay tôi bận mấy cái proposals, mai mốt sẽ viết thử xem có giảm ciphertext size xuống còn $O(d\log N)$ được không; tôi nghĩ là có thể được.
  
  Reply
  - RongChoi
    
    Posted 10/12/2010 at 3:51 pm | Permalink
    
    Hi anh Hưng,
    Theo RC là khó có thể giảm được xuống $O(d \log N)$ . Mỗi hàng có trọng số cỡ $N/q$ nên để cover $N$ users thì cần ít nhất đã là $q = d \log N$ hàng. Đó là khi các hàng không giao nhau và không có ai bị loại. Thêm yếu tố bị loai và thêm điều kiện các hàng được chọn ngẫu nhiên theo từng block thì việc mất thêm $\log N$ cũng là tốt rồi ạ:) Mà trên kia ta tính là $O(d \log^2 N/ \log\log N)$ , dưới $O(d \log^2 N)$ một chút.
    
    Nếu khi nào rảnh anh Hưng viết tường minh được chứng minh của ma trận bên trên thỏa mãn hai tính chất P1, P2 theo ngôn ngữ tổ hợp thì tốt quá (anh Hưng viết tiếng Anh luôn được ko ạ?). RC sẽ viết generic transformation từ loại ma trận này về sơ đồ mật mã và chứng minh tính an toàn.
    
    À, còn 1 điểm nữa. Việc xây dựng ma trận của ta (số hàng, mật độ số 1) dựa trên giả thuyết biết trước số người bị loại là $d$ , đây có lẽ là 1 nhược điểm (một số phương pháp khác không cần) nhưng có lẽ không sao lắm. Điểm lợi thế của ta là ngoài khả năng loại bỏ lại cho phép truy lùng kẻ gian RC thấy có triển vọng là 1 kết quả tốt
    
    Reply