Về mã hóa thông tin quảng bá
Mã hóa thông tin quảng bá, hay còn gọi là mã hóa quảng bá (broadcast encryption) là bài toán gửi thông báo được mã hóa tới một tập lớn những người dùng sao cho chỉ những người thuộc một tập con đặc quyền (có thể thay đổi động) mới có thể giải mã được. Nó bao gồm một tập các thuật toán: thuật toán cài đặt, thuật toán quảng bá và thuật toán giải mã.
Điển hình là trường hợp có một Trung tâm quảng bá và tập hợp những người sử dụng. Trung tâm cung cấp khoá cho người sử dụng khi họ gia nhập hệ thống. Tại một thời điểm nào đó, Trung tâm muốn quảng bá một thông báo (chẳng hạn đó là một khoá để giải mã) tới tập con những người sử dụng (tập này được quyền thay đổi theo thời gian và sẽ được gọi là lớp đặc quyền) theo một cách sao cho những thành viên không thuộc lớp này không thể hiểu được nội dung thông báo.
Ta có thể trình bày cụ thể hơn như sau. Giả sử U là tập tất cả những người sử dụng (với n là số thành viên của U) và T thuộc U là tập những người thuộc lớp đặc quyền. Trung tâm có thể quảng bá các thông báo tới toàn bộ người sử dụng. Song chỉ những người thuộc lớp có đặc quyền mới được thông báo, vì vậy tất cả các thành viên của T phải có khoá chung.
Trong pha chuẩn bị, thuật toán cài đặt nhận người sử dụng và cung cấp các thông tin riêng cho họ. Thuật toán quảng bá nhận danh sách những người sử dụng không thuộc tập đặc quyền và khóa phiên rồi tạo ra thông báo quảng bá. Thuật toán giải mã nhận đầu vào là thông báo quảng bá, nhận dạng người sử dụng và các thông tin riêng của họ rồi tạo ra khóa phiên. Đôi khi ta gọi tập này là lược đồ quảng bá.
Một lời giải hiển nhiên là đưa cho mỗi người một khoá riêng và truyền riêng lẻ thông báo đã được mã tới mỗi thành viên của lớp đặc quyền. Giải pháp này yêu cầu số lượng truyền thông tin lớn (dung lượng truyền = số thành viên trong lớp đặc quyền x độ dài thông báo).
Một cách đơn giản khác là cung cấp một khoá chung cho mỗi tập con những người sử dụng, nghĩa là cung cấp cho mỗi người sử dụng các khoá tương ứng với mỗi tập con mà họ tham gia. Giải pháp này yêu cầu mỗi người sử dụng lưu giữ một lượng lớn khoá.
Người ta quan tâm đến hiệu quả của mã hóa quảng bá theo hai độ đo: dung lượng truyền và lượng khóa lưu giữ ở người sử dụng cuối. Một tham số nữa được quan tâm là số người sử dụng phải liên kết để có thể phá vỡ hệ thống, vì như trên đã nói, những người không thuộc lớp đặc quyền cũng có thể tìm cách để biết nội dung thông báo được quảng bá.
Cụ thể hơn, lược đồ quảng bá được gọi là bền vững đối với tập S nếu với mỗi tập con T, không giao nhau với S, không kẻ trộm nào, dù có tất cả các bí mật liên quan với các thành viên của S, có thể thu nhận được bí mật chung của T.
Lược đồ quảng bá được gọi là k- bền vững nếu nó bền vững đối với tập bất kỳ S thuộc U có cỡ là k.
Lược đồ được coi là bị phá vỡ nếu một người sử dụng không thuộc lớp đặc quyền có thể đọc được thông báo truyền đi.
Với tham số k cho trước, cần xây dựng lược đồ bền vững đối với tập bất kỳ gồm k người sử dụng liên kết và tập con bất kỳ người sử dụng đặc quyền.
Một tham số khác được quan tâm là số lượng trung bình người sử dụng được chọn theo phân phối ngẫu nhiên đều phải liên kết với nhau để phá vỡ hệ thống. Tham số này được gọi là độ bền vững ngẫu nhiên của lược đồ mã quảng bá. Trong nhiều ứng dụng người ta chỉ quan tâm đến độ bền vững ngẫu nhiên. Chẳng hạn, nếu các công cụ giải mã bị chặn bắt một cách ngẫu nhiên bởi những người sử dụng (hoặc được gán một cách ngẫu nhiên cho người sử dụng) thì độ bền vững ngẫu nhiên là số lượng “công cụ giải mã” bị chặn bắt cần thiết để phá vỡ lược đồ.
Mục tiêu cuối cùng của lược đồ mã quảng bá là phải truyền an toàn một thông báo tới tất cả các thành viên của tập con đặc quyền.
Điều chúng ta muốn tối ưu hoá là số các khoá mà mỗi người sử dụng phải lưu giữ, lượng thông tin được truyền bởi trung tâm và chi phí tính toán của các thành viên thuộc lớp đặc quyền để tìm khoá chung.
Trong nhiều ngữ cảnh, tập đặc quyền có thể được nhận dạng bằng cách gửi đi một thông báo tương đối ngắn. Chẳng hạn, nếu bằng cách nào đó tập đặc quyền có thể được tính từ tập đặc quyền cũ hoặc biểu diễn của tập này có thể được nén. Nhưng việc truyền nhận dạng tập này là khác với việc truyền mã quảng bá. Mục đích ở đây là nghiên cứu việc truyền mã quảng bá và những yêu cầu của chúng. Nói chung, trung tâm sẽ nhận dạng mỗi người sử dụng với một số nhận dạng duy nhất và như vậy biểu diễn tập có thể là một véc tơ bit.
Người ta còn phân biệt các lược đồ không–thông báo với các lược đồ tổng quát hơn. Lược đồ không–thông báo có tính chất là việc biết tập con đặc quyền T đủ cho tất cả người sử dụng thuộc T tính khoá chung với trung tâm mà không cần sự truyền nào. Khoá này sẽ được dùng để mã dữ liệu cần truyền.
Các lược đồ tổng quát hơn có thể yêu cầu trung tâm truyền nhiều thông báo. Tiếp cận chung để kiến thiết các lược đồ là sử dụng tiếp cận 2 giai đoạn. Đầu tiên, ta thiết lập các lược đồ không thông báo bền vững ở mức thấp, sau đó sử dụng chúng để xây dựng những lược đồ bền vững ở mức cao hơn. Lược đồ cuối cùng không phải là lược đồ không- thông báo.
