-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 2
이 포스트에서는 이전 글인 Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1에 이어서, Suffix Automaton과 함께 사용할 수 있는 여러 테크닉들에 대해 설명합니다. Suffix Automaton이 무엇인지에 대해서는 제 이전 글을 참고하셔도 좋고, 아래 글을 읽어보셔도 좋습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html DAG + Small to Large Suffix Automaton의 DAG에서 DP를 진행할 수도 있지만, 관리해야 하는 것이 어떤 값이 아닌 목록인 경우 Small to Large 테크닉을 활용할 수 있습니다. DAG에서 Small to Large를 활용하게 되는 대표적인 경우는, $n$개의 문자열 $S_1,...
-
Minimizing Foreign Arithmetic in ZKP Circuits
https://eprint.iacr.org/2024/265.pdf 논문에 대해 다룹니다. 소개 ZKP를 사용하는 과정에서 가장 핵심적인 부분은 결국 $\mathbb{F}_p$ 위의 기본적인 연산들을 통해서 프로젝트 스펙에서 필요로 하는 constraint들을 표현하는 것에 있습니다. 하지만 $\mathbb{F}_p$ 위에서 모든 것을 표현하는 것이 쉽지만은 않습니다. 대표적인 사례는 바로 foreign field arithmetic인데, 이는 $\mathbb{F}_p$를 표현할 수 있는 ZKP system 위에서 $\mathbb{F}_q$의 연산을 증명하는 것을 의미합니다. 예를 들어, BN254 위의 PLONK를 하고 있다고 치면 BN254의 scalar field가 ZKP 상으로 native 하게 지원되지만, 여기서 SECP256K1 ECDSA verification을 하고 싶다면...
-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1
최근 공부 중에 Suffix Automaton이라는 자료 구조를 새로 알게 되어, Suffix Array 태그가 붙은 문제들을 전부 Suffix Automaton으로 풀어보려 시도했습니다. 그리고 꽤 많은 문제들이 Suffix Automaton을 사용할 때 훨씬 편리하게 풀린다는 것을 발견했습니다. 그 과정에서 알게 된 여러 테크닉들을 정리하고자 합니다. 이 글에서는 Suffix Automaton 자체에 대한 상세한 설명보다는 문제 풀이에 필요한 개념 위주로 간략하게 설명합니다. 아래에 Suffix Automaton에 대해 자세히 설명된 글이 있으니, 참고하시면 좋을 것 같습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html Suffix Automaton이란? Suffix Automaton을 간단히...
-
Insights from and on Taxonomy of ZKP Vulnerabilities
올해 4월 초, ZKP 관련 최대 컨퍼런스 중 하나인 zkSummit11에서 ZKP 보안과 관련된 발표를 진행할 수 있었습니다. 이번 글에서는 발표 내용에 대한 간략한 설명을 합니다. ZKP 보안에 대한 업계의 이해도는 2022년부터 꾸준히 증가해왔지만, 아직도 ZKP 보안 판에는 여러 문제가 있습니다. 가장 큰 문제 중 하나는 사람이 부족하다는 것인데, 이에 대한 해답으로는 크게 두 가지를 생각할 수 있습니다. 암호를 잘 하는 사람에게 보안의 컨텍스트를 가르쳐 ZKP 보안을 소개하는 것 블록체인 보안을 하는 사람에게 암호의 컨텍스트를 가르쳐...
-
IMO 조합 문제를 DP로 풀어보자
저번 글에 이어 이번에도 IMO(국제 수학 올림피아드)와 관련된 주제를 가져왔습니다. 오늘은 아마도 이 글을 읽는 분들이 가장 익숙하실 조합 문제들을 다뤄보려고 합니다. 최근 들어 PS에서 다루는 다양한 알고리즘적 사고를 요구하는 문제들이 수학 올림피아드에도 출제되고 있습니다. 특히 DP(점화식)를 이용하는 문제가 최근 2년 연속 IMO에 출제되며 큰 관심을 끌었습니다. 이번 글에서는 이 두 문제의 풀이를 간단히 소개해보려 합니다. IMO 2022 P6 양의 정수 $n$이 있다. 노르딕 사각형이란 $n\times n$ 모양의 판으로 각 칸에 $1$부터 $n^2$까지의 수가 하나씩...