Định nghĩa hàm băm XOR-Universal của Abidin[1]:
Một lớp học $H$ của các hàm băm từ $M$ đến $T$ là XOR-Phổ quát$_2$ ($XU_2$) nếu tồn tại nhiều nhất $|H|/|T|$ hàm băm $h$ $\in$ $H$ như vậy mà $(h(m_1) = h(m_2$) $\oplus t)$ cho hai phân biệt bất kỳ $m_1$, $m_2$ $\in$ $M$ và bất kỳ $t \in T$.
Nếu có nhiều nhất $\epsilon|H|$ thay vào đó, các hàm băm cho $\epsilon > 1/|T|$, lớp $H$ Là $\epsilon$-Hầu như-XOR-Phổ quát$_2$ ($\epsilon-AXU_2$).
$M$ là tập hợp chứa tất cả các thông báo (tất cả các chuỗi bit có độ dài m trong trường hợp này)
$T$ là tập hợp tất cả các thẻ có thể (tất cả các chuỗi bit có độ dài n trong trường hợp này)
$H$ là tập chứa tất cả các hàm băm có thể
$|H|$ đề cập đến số lượng hàm băm (Đối với $n$ x $m$ ma trận toeplitz $|H|$ = $2^{m + n-1}$).
$|T|$ đề cập đến kích thước của tập hợp $T$.
Toeplitz-Ma trận xác thực
Ma trận Toeplitz là ma trận nhị phân có đường chéo không đổi, sao cho chỉ hàng và cột đầu tiên là cần thiết để xác định bất kỳ ma trận nào như vậy (độ dài khóa của $m+n-1$ chút ít).
ví dụ.
$$
T_{3\times5}=
\left[{\begin{array}{ccccc}
0 & 1&0&0&1 \
1&0&1&0&0\
0& 1&0&1&0 \
\end{mảng} } \right]
$$
Để xác thực, mỗi thông báo được biểu diễn dưới dạng một vectơ cột nhị phân có độ dài m và được nhân với ma trận Toeplitz và với vectơ kết quả, thao tác XOR theo bit được áp dụng để nhận một vectơ nhị phân có độ dài n.
Nếu thao tác này là XOR-phổ quát, thì nó có thể được sử dụng trong sơ đồ xác thực an toàn vô điều kiện bằng cách thực hiện cả bước sau: Kết quả là XOR'ed với một chuỗi bit đồng nhất có độ dài n (mã hóa One-Time-Pad (OTP )) để kết thúc với thẻ. Bên thứ hai biết khóa để xác định ma trận Toeplitz và khóa của OTP. Để kiểm tra tính xác thực, cô ấy thực hiện các phép tính tương tự trên m và so sánh nó với thẻ nhận được
Câu hỏi
Tôi muốn chứng minh rằng ma trận Toeplitz là XOR-phổ quát trong sơ đồ được mô tả ở trên để tìm hiểu xem liệu chúng có thể được sử dụng trong sơ đồ xác thực Wegman-Carter One-Time-Pad như được mô tả trong [2]. Trong bài báo năm 94 của mình, Krawczyk [3]
đã chỉ ra rằng các ma trận Toeplitz được xây dựng bằng LFSR thực sự là XOR-phổ quát. Nhưng theo như tôi có thể nói, công trình của anh ấy chỉ mang lại một số ma trận Toeplitz bị hạn chế nhất định và bằng chứng của anh ấy không thể áp dụng cho trường hợp chung.
Bên cạnh đó, bất kỳ bài báo nào tôi đã tìm thấy cho đến nay đều trích dẫn Mansour [4] cho một bằng chứng như vậy, người không đề cập đến ma trận Toeplitz trong bài báo của mình. Do đó, câu hỏi của tôi là nếu ai đó biết bằng chứng cho thấy họ ma trận Toeplitz thực sự là XOR-Universal hoặc một bài báo có chứa bằng chứng như vậy.
[1]:http://liu.diva-portal.org/smash/record.jsf?pid=diva2%3A616704&dswid=3813
[2]:https://dl.acm.org/doi/10.1145/800105.803400
[3]:https://link.springer.com/chapter/10.1007/3-540-48658-5_15
[4]:https://www.sciencedirect.com/science/article/pii/030439759390257T?via%3Dihub
