-
Optimal Ate Pairings, BLS12-381, BN254 알아보기
이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q) = f_{r, P}(Q)^{(q^k - 1) / r}\] 를 얻을 수 있었습니다. 이제 이를 최적화하는 Ate Pairing을 알아봅시다. Lemma \[f_{ab, Q} = f_{a, Q}^b \cdot f_{b, [a]Q}\] 증명: 단순 계산. 어렵지 않습니다. 그러면 특히 $[r]Q = \mathcal{O}$인 경우에는 \[f_{mr, Q} = f_{r, Q}^m\] 가...
-
Segment Tree Beats와 Kinetic Segment Tree
Segment Tree Beats와 Kinetic Segment Tree 이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수...
-
ICPC World Finals 2021 풀이
11월에 ICPC World Finals 2021에 참가했습니다. 이후 11월 말까지 한 문제를 제외한 나머지를 모두 풀었고, 이 글에서 모든 문제의 풀이를 정리합니다. 최근 3년과 달리 상대적으로 쉬운 (플래티넘 하급 이하) 문제가 좀 더 많이 나왔는데, 그것들을 푸느라 더 어려운 문제에 쓸 시간이 부족했습니다. A: Crystal Crosswind 바람의 방향이 $(w_x, w_y)$, 가장자리의 집합이 $S$라고 하면 다음과 같은 정보를 얻습니다. (1) $(x, y) \in S$일 경우, $(x, y)$은 분자고, $(x - w_x, y - w_y)$는 빈칸입니다. (2) $(x,...
-
Local Differential Privacy
들어가며 지난번에는 어느 한 데이터셋에서 하나의 데이터가 가지는 영향력에 대해서 공부해 보았습니다. 어떤 데이터셋에서 한 데이터를 제외한 나머지 정보를 다 알고 있을 때, 나머지 한 개의 데이터를 유출할 수 있는지에 대한 것이었습니다. Differential Privacy는 이를 수식을 활용해 표현한 것으로, $\epsilon$의 값으로 데이터의 안정성을 확인할 수 있었습니다. 이번에는 Differential Privacy와는 조금 다르지만 개인의 프라이버시를 보호할 수 있는 개념을 소개하려고 합니다. 개인이 신뢰하지 않는 서버에 데이터를 제공했을 때의 프라이버시를 보호하기 위한 개념인 Local Differential Privacy에 대해 소개하려고...
-
Homomorphic Encryption에 대한 소개
Introduction 올 한해 크립토랩이라는 스타트업에서 근무할 기회가 있었습니다. 크립토랩은 Homomorphic Encryption, 즉 동형암호 scheme 중 CKKS를 바탕으로 창업한 스타트업입니다. (CKKS scheme을 제안하신 천정희 교수님이 대표입니다.) 회사에서 근무하며 그동안 잘 몰랐던 동형암호에 대해서 배울 기회가 있었습니다. 현재 국내에는 동형암호에 대해 서술하는 자료가 그리 많지 않은 것으로 보여, 동형암호에 대한 소개글을 작성하기로 했습니다. What is Homomophic Encryption? 먼저 동형암호가 무엇인지 간단하게 설명하도록 하겠습니다. 우선 보통의 암호 scheme의 경우 평문(plaintext)와 암호문(ciphertext)의 관계를 최대한 random하게 만드려고 합니다. 평문과 암호문...