-
Caulk : Lookup Arguments in Sublinear Time
논문은 https://eprint.iacr.org/2022/621 입니다. 선행지식 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf https://www.secmem.org/blog/2022/05/15/KZG-ASVC/ 정확히는, Powers of Tau 및 KZG Commitment 계열 이론, ZK 계열 이론 기초 Membership Proofs in Zero Knowledge 우리의 목표는 집합 $S$가 있을 때, 어떤 $v$가 $v \in S$를 만족한다는 사실을 영지식으로 증명하는 겁니다. 이를 위해서 사용된 대표적인 방법이 두 가지가 있는데, 하나는 Tornado Cash에서 사용하고 있는 것과 같은 Merkle Tree + zkSNARKS입니다. 적당한 hash function을 기반으로 한 Merkle Tree를 만들고, 자신이 갖고 있는 원소가 leaf 중 하나임을 Merkle...
-
Congestion Balancing
Congestion Balancing 일반적인 그래프에서 효율적으로 해결할 수 있는 문제들을, 간선이 추가되고 제거되는 등의 업데이트가 가해질 때도 효율적으로 해결할 수 있는지를 연구하는 분야를 Dynamic Graph Algorithm이라고 부른다. 이 분야에 대해서는 최근 많은 연구가 진행되고 있으며, 여러 차례의 멤버십 글로도 이 분야의 다양한 최신 기술과 테크닉을 소개한 바 있다. 이 글에서 소개할 주제는 Decremental Graph Algorithm을 얻을 수 있는 프레임워크 중 하나인 Congestion Balancing 이다. 어떠한 알고리즘이 decremental하다는 것은, 간선 추가 쿼리는 처리할 수 없으나 제거 쿼리는...
-
Large S-box의 암호학적 성질 및 대수적 공격
1. Introduction 대칭키 암호화 시스템은 선형 연산과 비선형 연산을 반복적으로 적용해 키와 암호문 혹은 평문과 암호문의 관계를 가립니다. 이 때 S-box는 비선형 성질을 제공하는 중요한 역할을 합니다. DES에서는 6비트의 입력을 받아 4비트를 출력하는 S-box가 사용되었고 AES에서는 8비트의 입력을 받아 8비트를 출력하는 S-box가 사용되었습니다. 암호가 안전하기 위해서는 S-box가 편향되지 않고 잘 정의되어야 합니다. 예를 들어 S-box의 차분 성질이나 선형 성질의 편향이 클 경우 이를 이용한 차분 공격 혹은 선형 공격이 가능할 수 있습니다. 직관적으로 생각했을 때...
-
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를 참고하시기 바랍니다. 서론...