-
Probabilistic Method
그래프 이론과 확률. 왠지 어울리지 않을 것 같은 두 개념을 처음으로 엮은 것은 헝가리의 수학자 폴 에르되시 (Paul Erdős)였습니다. 그는 확률을 이용해서 그래프 이론과 조합론 분야의 정리를 증명하는 “확률론적 방법론” (Probabilistic Method)을 창안했습니다. 이번 글에서는 확률론적 방법론이 어떤 방식의 증명 방법인지 몇 가지 정리를 통해 알아봅시다. $ \renewcommand{\Pr}{\mathbf{Pr}} \newcommand{\Ex}{\mathbf{E}} $ Warm-Up: 2-Colorable Hypergraphs 다음을 증명해 봅시다. Problem. 집합 $S$가 있고, $S$의 부분집합 $m$개가 있다. 이 부분집합들은 모두 크기가 $k$ 이상이다. $m<2^{k-1}$일 때, $S$의 원소들을 빨강이나...
-
KZG Commitment, Aggregatable Subvector Commitments, Stateless Cryptocurrencies
들어가기 전에 논문 https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf (KZG Commitment, Asiacrypt 2010) https://eprint.iacr.org/2020/527.pdf (eprint) 이 논문의 저자에는 Vitalik Buterin도 있습니다. 선행지식 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 정확히는, Powers of Tau와 Pairing에 대한 기본적인 이해 다항식의 연산에 관한 알고리즘 (FFT 계열) 이 글에서 Security에 대한 부분은 생략하도록 하겠습니다. 필요한 가정과 실제 scheme의 security 증명 사이의 gap이 그렇게 크지 않고, 글에서 다루는 내용이 이미 많기 때문입니다. 이 부분에 대해 궁금한 점이 있는 독자들은 KZG Commitment 논문의 Section 2에 있는 Assumption들과 Appendix C를 참고하시기 바랍니다. 서론...
-
Haskell fix 함수
서론 하스켈에는 다음과 같은 함수가 있습니다. fix :: (a -> a) -> a fix f = let x = f x in x Data.Function 에 위치한 fix 함수는 자세하게 들여다 보면 신기한 특성을 가지고 있습니다. 함수를 조금씩 풀어봅시다. fix f -> let x = f x in x -> let x = f x in f x -> let x = f x in f (f x) -> let x = f x in f...
-
Densest Subgraph: Supermodularity, Iterative Peeling, Flow
Densest Subgraph: Supermodularity, Iterative Peeling, Flow 이 글에서는 SODA 2022 논문인 Densest Subgraph: Supermodularity, Iterative Peeling, Flow 를 요약한다. 위 논문은 Densest subgraph problem과, 이 문제의 supermodular set function 일반화 버전의 풀이를 다루는 논문이다. 본인은 최근 Densest subgraph problem에 대해서 최근에 다양한 접근 방법들을 정리하고 있는데, 이 글 역시 그러한 노력의 일환이라고 보면 좋다. Densest subgraph problem의 중요성에 대해서는 이 글을 참고하면 좋다. Densest subgraph problem에 대해서는 현재 크게 세 가지 접근 방법이 있다. Flow...
-
Image steganography based on deep learning
Introduction 최근 딥러닝을 사용하는 분야가 넓어짐에 따라, 보안에서는 딥러닝이 어떻게 사용되고 있는지 궁금해 관련 서베이 논문을 살펴보았습니다. 해당 논문에서는 아래와 같이 GAN이 적용되고 있는 여러 분야들을 제시하고 있습니다. 굉장히 다양한 분야가 있지만, 저는 이중에서도 Image steganography에 딥러닝이 어떻게 사용되는지에 대해 관심을 가지고 선행 연구들을 조사해보았는데, 이번 글에서는 Image steganography와 End-to-end Trained CNN Encode-Decoder Networks for Image Steganography에서 제안된 비교적 간단하지만 괜찮은 성능을 보이는 모델에 대해 살펴보려고 합니다. Image steganography Steganography는 임의의 데이터(cover)에 다른 데이터(payload)를 은폐하는...