Nhiều trong số này được giải quyết trong bài viết.Trong cài đặt này, "đối thủ" là một số thuật toán có thể đánh giá $f_n$ sử dụng ít tài nguyên hơn chúng ta mong đợi.
$S$ = độ phức tạp không gian/bộ nhớ của đối thủ. Trong dòng công việc này, $f_n$ là một chức năng thực hiện các cuộc gọi đến một số nhà tiên tri ngẫu nhiên $H : \{0,1\}^k \to \{0,1\}^k$, và $S$ là mức sử dụng không gian (trường hợp xấu nhất) của đối thủ, được đo bằng $k$-bit "khối."
$T$ = thời gian phức tạp của đối thủ. Thường được đo bằng số cuộc gọi đến $H$. Trong một số mô hình, kẻ thù được phép thực hiện các cuộc gọi song song tới $H$ miễn phí, vì vậy $T$ là số "vòng tuần tự" của các cuộc gọi đến $H$.
$n$ = tham số độ cứng có thể điều chỉnh của chức năng bộ nhớ cứng. lớn hơn $n$ tăng nỗ lực cần thiết để đánh giá chức năng $f_n$ (và lý tưởng nhất là nỗ lực quy mô bậc hai trong $n$). Các bên trung thực nên chọn lớn nhất $n$ sao cho họ sẵn sàng bỏ công sức để đánh giá $f_n$.
Định nghĩa này tốt như thế nào? ... Vì vậy, tôi đoán định nghĩa này không đủ chặt chẽ để cho chúng ta thấy KDF cứng bộ nhớ nào nhất thiết phải tốt hơn?
Đó là sự thật mà $n^2/1000$ khác rất nhiều so với $1000n^2$, nhưng định nghĩa này sẽ hài lòng với các hàm khó nhớ với một trong các mức độ khó này.
Tại thời điểm của bài báo này, hầu hết các ứng cử viên chức năng bộ nhớ cứng là tiệm cận tệ hơn nhiều so với $\Theta(n^2)$.
Vì vậy, định nghĩa này khá hiệu quả để loại trừ nhiều ứng cử viên xấu.
Một khi bạn có nhiều ứng viên đáp ứng điều này tiệm cận định nghĩa, thì bạn có thể bắt đầu lo lắng về các yếu tố không đổi.
Bất kỳ định nghĩa độ cứng bộ nhớ tốt hơn?
Có, định nghĩa này chỉ xem xét tồi tệ nhất trường hợp sử dụng không gian $S$.
Giả sử $f_n$ là một chức năng thực sự yêu cầu $n$ đơn vị bộ nhớ để đánh giá -- không có cách nào để đánh giá $f_n$ không giữ $n$ đơn vị bộ nhớ tại một số điểm.
Điều này không loại trừ khả năng $n$ đơn vị bộ nhớ chỉ được yêu cầu trong một cửa sổ thời gian rất ngắn.
Nói cách khác, có thể có một thuật toán cho $f_n$ biểu đồ sử dụng bộ nhớ theo thời gian trông như thế này:
(hình ảnh lấy từ Leo Reyzin của slide trên scrypt)
Nếu thuật toán này có tối đa sử dụng không gian $n$ và cũng sử dụng $n$ thời gian, độ phức tạp ST của nó là $\Omega(n^2)$.
Độ phức tạp ST giống như diện tích của hình chữ nhật hộp giới hạn màu xanh lam trong hình này.
Nhưng thước đo độ cứng của bộ nhớ này che khuất một số vấn đề.
Giả sử một đối thủ muốn đánh giá $f_n$ trên nhiều đầu vào khác nhau và nó khéo léo lên lịch cho những đánh giá đó như sau:
Chiến lược này có thể được sử dụng để đánh giá ví dụ $f_n$ trên $n$ đầu vào khác nhau chỉ sử dụng $O(n)$ thời gian và $O(n)$ tổng bộ nhớ!
Vậy tổng "ST-chi phí" để đánh giá hàm $n$ thời gian là $O(n^2)$, nghĩa là khấu hao chi phí cho mỗi phiên bản chỉ là $O(n)$.
Một cách tốt hơn để phân loại độ cứng bộ nhớ của một chức năng là đo khu vực dưới đường cong thay vì diện tích của hộp giới hạn.
Đây thực sự là những gì được đề xuất trong công việc tiếp theo, trong đó chỉ số độ cứng của bộ nhớ được gọi là "độ phức tạp của bộ nhớ tích lũy".
