ICML 2026 Spotlight
사용자를 지키려면 사용자를 기억해야 한다
차분 프라이버시
한 줄 요약
사용자 단위 차분 프라이버시를 지키면서 스트림에 남아 있는 사용자 수를 세려면, 프라이버시가 없을 때처럼 로그 수준의 메모리로는 안 되고 스트림 길이 \(T\)의 세제곱근에 가까운 메모리가 든다. 프라이버시 때문에 메모리가 더 든다는 것을 암호 가정 없이 보인 첫 결과다.
무엇이 달라졌나
차분 프라이버시(differential privacy, DP)는 한 사람의 데이터를 빼도 출력의 분포가 거의 바뀌지 않게 하라는 조건이다. 이 논문은 그 가운데 강한 쪽으로, 한 사용자의 기록을 통째로 지워도 출력이 거의 같아야 하는 사용자 단위(user-level) DP를 다룬다(2절).
스트리밍(streaming) 모델에서는 데이터가 하나씩 흘러 들어오고, 알고리즘은 이를 다 저장하지 못한 채 작은 메모리로 갱신마다 답을 낸다. 대표 문제가 고유 개수 세기(CountDistinct)다. 사용자가 들어오고(\(+1\)) 나가는(\(-1\)) 갱신이 \(T\)번 오는 동안 지금 남은 사용자 수를 10% 곱셈 오차 안에서 맞힌다. 프라이버시가 없으면 스케치(sketch) 기법으로 \(\log T\)의 몇 제곱 정도 메모리면 된다(1장, 2절).
사용자 단위 DP에서 최선의 덧셈 오차는 \(T^{1/3}\) 수준이고, Cummings 외(2025)는 이 오차를 \(T^{1/3}\) 수준의 메모리로 냈다(2.1절). 메모리를 로그 수준으로 줄일 수 있느냐가 열린 문제였다.
답은 “줄일 수 없다”다. 갱신이 \(w\)번을 넘는 사용자가 많아야 \(k\)명이라고 약속된 스트림에서도, 덧셈 오차를 \(h\) 안으로 맞추는 DP 알고리즘은 로그 인자를 빼고 \(kw/h^2\)비트 이상을 써야 한다(정리 2.1). 매개변수를 맞추면, 오차를 \(T^{1/3-\alpha}\)보다 작게 하려면 \(T^{1/3-4\alpha}\)비트가 필요하다(\(0<\alpha<1/9\), 따름정리 2.2). 프라이버시가 없을 때보다 지수적으로 큰 값이고, Cummings 외의 알고리즘이 이 영역에서 거의 최적이라는 뜻이다. 가장 인기 있는 항목 고르기(MaxSelect)와 분위수(Quantile)에도 같은 하한이 나온다(정리 2.3).
프라이버시의 메모리 하한으로는 암호 가정 아래 일부러 만든 문제를 다룬 Dinur 외(2023)가 유일했다(1장). 이번 하한은 가정 없이 흔한 통계 문제에서 성립한다.
어떻게 보였나
실마리는 기여 상한(contribution capping)이다. 사용자 단위 DP 알고리즘은 흔히 갱신이 지나치게 많은 단골을 찾아내 그 뒤로는 무시하는데, 단골 명단을 적어 두는 데만 \(k\)에 비례하는 메모리가 든다(2.1절). 논문은 이 비용을 피할 길이 없음을 보인다.
어려운 스트림은 이렇게 짠다(2.3절). 단골 \(k\)명을 무작위로 뽑고, 뜨내기를 \(3h\)명씩 \(P\)묶음 고른다. \(i\)번째 구간에서는 단골과 \(i\)번째 묶음을 섞어 놓고, 무작위 확률로 일부를 넣은 뒤 개수를 묻고 다시 지우기를 \(w\)번 되풀이한다. 개수를 묻는 일은 곧 숨은 비트의 평균을 묻는 일이다. 뜨내기는 한 구간에만 나오지만 단골은 모든 구간에 나온다. 정확하면서 단골을 드러내지 않으려면 뜨내기만 세면 되지만(오차는 많아야 \(k\) 늘어난다), 그러려면 단골이 누구인지 알아야 한다.
(가) 어려운 스트림
(나) 통신 게임으로 옮기기
증명은 이 직관을 통신 게임으로 옮긴다(3.1절). 구간마다 플레이어가 한 명씩 있고, 각자 단골과 뜨내기가 섞인 집합만 본다. 앞 플레이어에게서 \(M\)비트를 받은 뒤 자기 집합에서 절반보다 \(\epsilon_1\)만큼 많은 사람을 골라 심판에게 낸다. 어느 단골도 \(P\)번 가운데 \(1/2+\epsilon_2\)를 넘는 비율로 뽑히면 안 된다. \(\epsilon_1\)이 \(\epsilon_2\)보다 크면 무작위로 골라서는 이길 수 없어서, \(M\)이 적어도 \(k(\epsilon_1-\epsilon_2)^2\)에 비례해야 한다(보조정리 3.1).
정확한 DP 알고리즘이 있으면 이 게임에서 이긴다(3.2절). 플레이어는 자기 구간의 스트림을 알고리즘에 넣고 그 메모리 상태를 다음 플레이어에게 넘긴다. 사용자마다 알고리즘의 답이 그 사람의 비트와 얼마나 같이 움직였는지를 점수로 매겨, 점수가 높을수록 잘 뽑히게 고른다. 지문 보조정리(fingerprinting lemma)에 따르면 정확한 평균 추정은 입력과 상관될 수밖에 없어서 고른 몫이 절반을 넘는다. 반대로 DP는 한 사람의 비트를 무관한 값으로 바꿔도 출력이 거의 같다는 조건이라, 단골 한 명의 누적 점수는 작게 묶인다. 여기서 \(\epsilon_1\approx\sqrt{w}/h\), \(\epsilon_2\approx 1/\sqrt{P}\)가 나오고, 보조정리 3.1에 넣으면 \(kw/h^2\)가 된다(3.3절). 플레이어의 계산과 작업 메모리는 제한하지 않으니, 하한은 구간 사이에 넘기는 기억의 양에서만 나온다(따름정리 3.3).
눈여겨볼 점
첫째, 하한이 알려진 상한과 맞는 곳은 따름정리 2.2의 영역 정도이고, 다른 \((w, k, h)\)에서는 틈이 남는다. 저자들도 이를 열린 문제로 적었다(2.2절). 또 갱신 횟수가 묶인 스트림에서만 성립하고, \(\epsilon=0.5\), \(\delta=1/T^2\)로 고정해 프라이버시 강도에 따른 변화는 다루지 않았다(2.2절 각주).
둘째, 사용자 단위라는 강한 조건에 기댄다. 한 리뷰어가 이를 짚었고, 저자들은 답변에서 갱신 하나만 보호하는 사건 단위(event-level)로 완화하면 일부 하한을 비켜 가는 결과(Aamand 외 2026)가 있다고 인정했다. 블로그의 해석으로는 이 논문의 메시지를 “프라이버시에는 메모리가 든다”보다 “사람마다 기여를 묶으려면 그 사람을 기억해야 한다”로 읽는 편이 정확하다.
열린 질문
- 사용자별 기여를 잘라 가며 흘러 들어오는 데이터로 학습하는 DP 학습에서도, 같은 통신 게임으로 메모리 하한을 보일 수 있을까.
이해 확인
증명에서 차분 프라이버시 조건이 맡는 역할은?
- 정확한 답이 입력 비트와 상관되게 만든다
- 단골 한 명이 모든 구간에 걸쳐 받는 누적 점수를 작게 묶는다
- 플레이어 사이에 넘기는 메시지를 \(M\)비트로 제한한다
- 뜨내기 사용자가 한 구간에만 나오게 만든다
DP 덕분에 단골 한 명의 누적 점수는 무관한 비트를 넣었을 때처럼 작게 머물고, 그래서 단골은 전체 구간의 절반 남짓만 뽑힌다(3.2.1절). 1번은 정확도와 지문 보조정리가 맡고, 3번은 알고리즘의 메모리 크기에서, 4번은 어려운 스트림을 짜는 방식에서 나온다.
논문 정보
- 제목: Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms
- 저자: Alessandro Epasto (Google Research), Xin Lyu (UC Berkeley), Pasin Manurangsi (Google Research)
- 학회: ICML 2026 스포트라이트(Spotlight)
- 링크: arXiv 2602.12209, OpenReview