강의 계획 레슨 156개 중 133번째 · 차단 너머의 프라이버시 기술
차단 너머의 프라이버시 기술

필요한 수학

왜 중요한가 목록을 주고받지 않고 공유 고객을 찾거나, 각 사람을 지키는 통계를 발표하는 것 같은 이 모듈의 프라이버시 도구는 작은 수학 조각 셋에 기대요. 수학 학위는 필요 없어요. 시계 산수, 확률에 대한 감, 그리고 무작위 잡음이 큰 무리에서 상쇄된다는 생각이 필요해요. 이 레슨은 바로 그것들을, 해 볼 Python과 함께 줘요.

1. 시계 산수

22:00이에요. 5시간 뒤는 몇 시일까요? 27:00이 아니에요: 시계가 한 바퀴 돌아서 03:00이에요. 22 + 5 = 27을 하고 24로 나눈 나머지를 남겼어요.

모듈러 산술: 숫자가 정해진 크기, 모듈러스에 닿으면 한 바퀴 도는 산술. "27 mod 24"는 3, 27을 24로 나눈 나머지예요. Python에서 나머지 연산자는 %예요: 27 % 24는 3이에요.

한 바퀴 돌기는 아무리 더하거나 곱해도 숫자를 정해진 크기로 유지해서, 암호학에 쓸모 있어요. Python에는 "거듭제곱하고, 그다음 한 바퀴 돌기"를 위한 빠른 내장 함수도 있어요: pow(base, exponent, modulus).

print((22 + 5) % 24)       # 3
print(pow(3, 4, 7))        # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23))     # instant, even though 5 to the 200 is huge

2. 한쪽으로는 쉽고, 반대로는 어렵게

노란색과 파란색 물감을 섞어 초록색을 만드는 건 쉬워요. 초록색을 정확한 노란색과 파란색으로 되돌리는 건 사실상 불가능해요. 어떤 수학도 같은 방식으로 작동해요.

큰 소수 모듈러스 P와 숫자 h를 고르세요. 비밀 a에 대해 pow(h, a, P)를 계산하는 건 순식간이에요. 하지만 답만 주어졌을 때 a를 다시 찾는 건 숫자가 충분히 크면 너무 느려서 아무도 할 수 없어요. 이 한 방향 성질을 이산 로그 문제라고 해요.

사실 하나 더, 그리고 그게 다음 실습을 움직여요. a로 거듭제곱하고 그다음 b로 하면 b로 하고 그다음 a로 한 것과 같은 결과가 나와요. 둘 다 h의 a 곱하기 b 제곱과 같으니까요:

P = 1019                     # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P))    # True

상자 하나에 자물쇠 둘처럼, 다는 순서는 상관없어요. 두 사람이 각자 비밀을 더하고 비밀을 드러내지 않은 채 같은 곳에 닿을 수 있어요.

3. 한 문단으로 보는 확률

확률은 0(절대 아님)에서 1(언제나)까지의 숫자예요. 공정한 동전은 0.5의 확률로 앞면이 나와요. 두 일이 독립이면 둘 다의 확률은 곱이에요: 연달아 앞면 두 번은 0.5 × 0.5 = 0.25. 기댓값은 장기적인 평균이에요: 공정한 주사위를 여러 번 굴리면 평균이 3.5에 다가가요.

4. 잡음은 무리 속에서 상쇄돼요

잡음: 정확한 값을 숨기려고 참값에 일부러 더한 무작위한 양. 잡음이 위로든 아래로든 똑같이 일어나면, 많은 값에 걸쳐 평균이 0이 돼요.

여기 무작위 응답이라는 고전적인 설문 요령이 있어요. 몇 명이 부끄러운 무언가를 했는지 알고 싶어요. 각자 몰래 동전을 던져요. 앞면: 사실대로 답해요. 뒷면: 다시 던져서 앞면이면 "예", 뒷면이면 "아니요"라고 답해요. 어떤 "예" 하나도 그냥 동전일 수 있으니, 누구의 답도 그 사람에 대해 아무것도 증명하지 않아요.

그래도 무리의 합계는 여전히 쓸모 있어요. 참 비율이 p라면 기대하는 "예" 답의 비율은 0.5 x p + 0.25예요. 그래서 35%가 예라고 하면 p는 약 (0.35 - 0.25) / 0.5 = 0.2, 즉 20%예요. 무리가 클수록 추정이 가까워져요. 무리가 커질수록 무작위 잡음이 합계에 비해 줄어드니까요.

import random
rng = random.Random(1)               # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)]   # 20% really did it
answers = []
for did_it in truth:
    if rng.random() < 0.5:
        answers.append(did_it)             # heads: tell the truth
    else:
        answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3))       # close to 0.2

차분 프라이버시에 쓰는 잡음은 라플라스 잡음이라고 하는데, 같은 생각의 매끄러운 버전이에요: 보통 작고, 가끔 더 크고, 위아래로 똑같이 일어나요. 그 척도가 보통 얼마나 큰지 정해요.

다른 언어로

JavaScript의 %는 양수에 대해 같은 방식으로 작동하고, 큰 숫자는 BigInt(n을 붙여 써요)를 써요. 내장 모듈러 거듭제곱이 없으니, 표준 루프는 이래요:

function powMod(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}
console.log(powMod(3n, 4n, 7n));   // 4n

Go에서는 math/big의 new(big.Int).Exp(base, exp, mod)가 같은 일을 해요.

흔한 오해

"잡음을 더하면 데이터가 쓸모없어진다." 한 사람의 값에 대해서는 그래요. 그게 요점이에요. 큰 무리에 대해서는 잡음이 대체로 상쇄되니, 합계와 평균은 쓸모 있게 남아요. 프라이버시 기술은 그 틈에 살아요: 개인에게는 흐릿하게, 무리에게는 선명하게.

요약

  • 모듈러 산술은 숫자를 모듈러스 둘레로 돌려요. Python은 %와 pow(b, e, m)을 써요.
  • 비밀 제곱으로 거듭제곱하는 건 한쪽으로는 쉽고 되돌리기는 사실상 불가능하며, 두 비밀 제곱의 순서는 상관없어요.
  • 독립적인 확률은 곱해지고, 기댓값은 장기적인 평균이에요.
  • 무작위 잡음은 개인을 숨기지만 큰 무리에서는 상쇄되고, 그게 무작위 응답이 작동하는 방식이에요.

이 레슨에서 문제를 발견했나요? 알려 주세요 · 이 레슨에 대해 묻기

이 연습은 곧 열려요

앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.