Tập hợp các hàm băm $H=\{h:\{0,1\}^n \to \{0,1\}^m\}$ độc lập theo cặp nếu với mọi $x_1 \neq x_2 \in \{0,1\}^n$ và $y_1, y_2 \in \{0,1\}^m$:
$$ \Pr_{h \leftarrow H}[h(x_1)=y_1 \wedge h(x_2)=y_2]=\frac{1}{2^{2m}} $$
Cho một trường hữu hạn $\mathbb{F}$ kích thước $2^n$ Tôi đã có thể chứng minh cho tập hợp các hàm băm:
$\{h_{a,b}: \mathbb{F}\to \mathbb{F}\}_{a,b \in \mathbb{F}}$ ở đâu: $h_{a,b}=ax+b$
rằng nó độc lập theo cặp.
Bây giờ tôi được yêu cầu mở rộng điều này cho trường hợp miền và phạm vi không giống nhau - - trước đây có kích thước $2^n$ và cái sau $2^m$.
Tôi đã nghĩ phần sau là phần mở rộng, nhưng tôi không chắc liệu nó có hoạt động hay không: chọn $a,b \in \mathbb{F}_{2^m}$. Ý tưởng là tôi cần phải có một nghịch đảo trong lĩnh vực này để giải quyết duy nhất cho $a,b$ (ví dụ: cho $ax_1+b=y_1$ tôi muốn giải quyết cho $a,b$ duy nhất bằng cách tìm $a=(y_1-b)x_1^{-1}$ và tương tự cho $b$ (hệ hai phương trình mod $\mathbb{F}_{2^m}$) để tôi có được xác suất đã nói ở trên). Một hệ quả tất yếu có nghĩa là đảm bảo $x_1, x_2$ đang ở trong lĩnh vực này, tức là có $a$ và $b$ như vậy mà $x_1=(y_1-b)a^{-1}$. Từ $y_1 \in \mathbb{F}_{2^m}$ sau đó nó sẽ là đủ mà cũng $a,b \in \mathbb{F}_{2^m}$.
Tôi khá chắc chắn liệu điều này là chính xác. Bất kỳ lời khuyên sẽ được đánh giá rất cao.
