-
Operations on Set Power Series
Table Of Contents Introduction Set Power Series Addition Or Convolution Subset Convolution Composition of Set Power Series Exponential General Case Example: ARC105 F Introduction 안녕하세요, Aeren입니다! 이번 글에서는 set power series와 그와 관련된 연산들을 소개하고, combinatorial problem에서 어떻게 활용될 수 있는지 간단하게 소개하겠습니다. Set Power Series 어떤 set $G = \lbrace g _ 0,g _ 1,\cdots ,g _ {N-1} \rbrace$와 commutative ring $R$이 주어질 때, 함수 $p:\mathcal{P}(G) \rightarrow R$를 set power series라고 부릅니다. 그리고 일반적인...
-
Attacking a Variant of the RSA Cryptosystem
서론 이번 글은 저번 달의 글에 이어서 pbctf 2021를 출제하면서 사용한 논문 하나를 리뷰하려고 합니다. 이 논문은 Yet Another RSA라는 문제로 작성하게 되었습니다. 해당 논문의 제목은 Classical Attacks on a Variant of the RSA Cryptosystem인데요, RSA의 변종에 대해 $d$가 작을 경우의 공격법을 다루는 논문입니다. 본론 RSA Variant 이 논문에서 소개하는 RSA의 변종은 정수가 아닌 group 위에서 정의됩니다. 해당 그룹에 대해서 정의하자면 다음과 같습니다. Field $(\mathbb{F}, +, \cdot)$에 대해서 non-cubic integer $r \in \mathbb{F}$를 하나 뽑읍시다....
-
Linear Suffix Array Construction
제가 최근에 작업을 하면서 큰 문자열에서 다른 작은 문자열을 많이 찾을 필요가 있었습니다. 정확히는, 이런 일을 해야 할 필요가 있었습니다. 문자열 $T$가 주어집니다. 문자열 $S_{1}$, $S_{2}$, $\cdots$, $S_{K}$가 $T$에서 등장하는 횟수를 구해야 합니다. 모든 정수 $1 \leq i < K$에 대해, $S_{1}$, $S_{2}$, $\cdots$, $S_{i}$에 대한 답을 구한 이후에야 $S_{i+1}$을 알 수 있습니다. 이 조건은 실제 문제 상황보다는 조금 빡빡한 제한이지만, 이렇게 가정해도 큰 무리는 없습니다. 이 상황이 다른 일반적인 상황과 크게 다른 점은 이렇습니다....
-
Cryptanalytic Extraction of Neural Network Models
1. Introduction 이번 글에서는 암호학 분야에서 탑 티어 컨퍼런스 중 하나인 CRYPTO 2020에 통과된 Cryptanalytic Extraction of Neural Network Models 논문에 대해 알아보고자 합니다. 보통 암호학에서 인공지능을 활용할 때나 반대로 인공지능에서 암호학을 활용할 때에는 해당 기술을 마치 블랙박스와 같이 두고 결과를 가져다 쓰는 방식으로 진행되기 마련인데 이 논문에서는 그게 아니고 Neural Network Model의 Extraction을 하는 상황이 곧 암호학에서 아주 유명한 공격인 차분 공격을 하는 상황과 유사하다는 것을 이용해 Neural Network Model에 대한 Extraction을 기존의 방법들보다...
-
알고리즘 문제 접근 과정 5
알고리즘 문제 접근 과정 5 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 두 배열의 합 - KOI 2001 고등부 1번 관찰 우리가 생각해볼 수 있는 가장 쉬운 방법은 무엇이 있을까요? 아마 문제에서 나온 방법을 그대로 사용하는 것이 가장 편한 방법일 것입니다. 우리가 만들 수 있는...