-
rkm0959's profile image
rkm0959
November 22, 2022
Pairing 제대로 알아보기
자료: Pairings For Beginners Introduction 이 글에서는 여러 암호학의 분야에서 자주 등장하는 Elliptic Curve Pairing에 대해서 자세하게 알아보겠습니다. 독자 대상은 현대대수학 기본 Elliptic Curve 연산에 대한 기초지식 Elliptic Curve를 기반으로 한 Cryptography에 대한 기초지식 Pairing을 기반으로 한 Cryptography에 대한 기초지식 이 있는 분들입니다. 즉, 이 글에서는 Pairing이 왜 쓸모있는지, 어떻게 사용되는지는 다루지 않고, Pairing이란 무엇이며 어떻게 효율적으로 계산되는지 다룹니다. 최대한 증명을 포함하려고 하나, 지나치게 증명이 어려운 경우에는 따로 알아두면 좋은 사실로 빼겠습니다. A Look at...
-
rkm0959's profile image
rkm0959
October 19, 2022
Sum-Check Protocol and Applications
Introduction 최근 개인적인 사정으로 공부를 제대로 못하다가 정신을 차리고 Thaler의 책을 읽고 있습니다. 그 내용 중 일부분인 Sum-Check Protocol과 이를 활용한 application들에 대해서 짚고 넘어가고자 합니다. 이번 글에서는 다루지 않으나, 최근 등장한 HyperPLONK도 역시 Sum-Check Protocol에 기반하고 있으니, 이를 공부하기 위해서라도 Sum-Check에 대해서 제대로 공부해놓는 것이 좋아보입니다. The Sum-Check Protocol $v$-variate polynomial $g$가 유한체 $\mathbb{F}$ 위에서 정의되었다고 합시다. 목표는 \[H = \sum_{(b_1, \cdots, b_v) \in \{0,1\}^v} g(b_1, \cdots , b_v)\] 가 성립함을 증명하는 것인데, 특히...
-
rkm0959's profile image
rkm0959
September 12, 2022
Polynomial Commitment Scheme from DARK
논문: https://eprint.iacr.org/2019/1229.pdf Introduction 수많은 zkSNARK 체계들은 하나의 커다란 연산 과정을 간단한 게이트들로 구성된 Arithmetic Circuit으로 변환하고, 이에 대한 증명을 다항식들에 대한 항등식을 증명하는 것으로 전환합니다. 결과적으로 다루는 대상들이 다항식이므로, 자연스럽게 Polynomial Commitment라는 암호학 기술이 사용되게 됩니다. 보통 Commitment라고 하면, 값 $x$에 대한 commitment $C$를 계산하는 commit 함수가 있고, 다시 $C$를 알때 이것이 $x$의 commitment임을 증명하는 open 과정이 있습니다. $C$를 다른 값 $y$의 commitment로 open 하지 못하도록 하는 특성을 binding이라 하고, $C$만 봐서는 이것이 $x$의 commitment임을...
-
rkm0959's profile image
rkm0959
August 19, 2022
Isochronous Gaussian Sampling of [HPRR20]
논문은 https://eprint.iacr.org/2019/1411.pdf 입니다. Post Quantum Cryptography and Lattices 지금 사용되고 있는 많은 암호화 체계, 예를 들면 블록체인에서 많이 사용되고 있는 ECDSA/EDDSA나 공개키 암호화를 위해 사용되는 RSA 등은 전부 충분히 강력한 양자컴퓨터가 나오면 더 이상 안전하지 않게 됩니다. 양자컴퓨터가 나오는 미래에 대비하기 위해 NIST는 2010년대 후반부터 양자컴퓨터가 나오더라도 안전한, Post Quantum Cryptography에 (이하 PQC) 대한 표준을 정하기 위한 과정을 밟기 시작했습니다. 여러 과정을 거쳐서 매우 최근 Round 4 발표 및 첫 표준이 등장하게 되었는데, PQC 암호체계를...
-
rkm0959's profile image
rkm0959
July 1, 2022
On the insecurity of ROS
논문은 https://eprint.iacr.org/2020/945.pdf 입니다. 이번 논문을 읽기 위해서는 사전지식이 거의 필요하지 않습니다. What is ROS? ROS란, 다음의 약자를 따서 만든 이름입니다. Random inhomogeneities in a Overdetermined Solvable system of linear equations ROS는 다음과 같이 정의되는 문제입니다. 소수 $p$와 임의의 input을 $\mathbb{F_p}$로 보내는 random oracle $H_{ros}$가 있다고 합시다. 이때, dimension $l$의 ROS 문제는 서로 다른 $\hat{\rho}_i \in \mathbb{F}_p^l$을 각 $1 \le i \le l+1$에 대하여 찾되, $c \in \mathbb{F}_p^l$이 존재하여 \[H_{ros}(\hat{\rho}_i) = \langle \hat{\rho}_i, c \rangle\] 이...
-
rkm0959's profile image
rkm0959
June 13, 2022
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...
-
rkm0959's profile image
rkm0959
May 15, 2022
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를 참고하시기 바랍니다. 서론...
-
rkm0959's profile image
rkm0959
March 17, 2022
Zero Knowledge and Groth16 Protocol
서론 최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다. 이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다. 세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다. Zero Knowledge Proof (ZKP) Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다. 예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의...
-
rkm0959's profile image
rkm0959
February 17, 2022
Recents Large Attacks on Decentralized Applications
서론 이 글에서는 rekt.news에 등재된 블록체인 해킹 사건 중 가장 규모가 큰 10개를 아주 간략하게 돌아봅니다. 각각의 기초적인 원리를 살펴보고, 이 10가지의 사건을 통해서 제가 블록체인 보안에 대해서 느낀 점을 정리했습니다. Lineup https://rekt.news/leaderboard/ 에 있습니다. 여기에도 옮기면, Poly Network : $611M Wormhole : $326M BitMart : $196M Compound : $147M Vulcan Forged : $140M Cream Finance : $130M Badger : $120M Qubit Finance : $80M Ascendex : $77M EasyFi : $59M 합치면 대략 2조 3천억...
-
rkm0959's profile image
rkm0959
January 17, 2022
Terra Smart Contracts
서론 이 글에서는 Terra Blockchain에서 Smart Contract를 어떻게 구현하는지 대해서 간단하게 다루어보려고 합니다. Terra 블록체인의 가장 대표적인 native 코인은 LUNA인데, 이는 coinmarketcap에서 1월 16일 현재 시가총액 9위 (약 $30B) 입니다. Terra Blockchain에서도 Ethereum과 마찬가지로 Smart Contract들을 올릴 수 있는데, 그 언어와 구조가 Ethereum의 Smart Contract들과 많이 다릅니다. 이 글에서는 Terra 블록체인 위에서의 금융적 흐름보다는 Smart Contract 구조와 구현에 대해서 더 집중하겠습니다. 글은 기본적으로 Terra Documentation에서 많이 가져왔으나, 조금 더 이해하기 쉽고 찾아볼 reference가 충분하도록 부가설명을...
-
rkm0959's profile image
rkm0959
November 20, 2021
Smart Contract Vulnerabilities
서론 최근 스마트 컨트랙트 보안에 대해 공부하게 되었습니다. 블록체인 위에 있는 여러 스마트 컨트랙트들은 대부분 NFT나 ERC20 토큰, 또는 ETH, AVAX 등 블록체인 위의 기초 화폐를 다루는 만큼 그 보안이 매우 중요하게 여겨지고 있습니다. DeFi (Decentralized Finance, 탈중앙화 금융) 서비스를 개발하는 회사들은 여러 보안 전문 회사에 Security Audit을 받으면서 보안성을 강화하려고 하지만, 모든 실수를 완벽하게 막을 수는 없기 때문에 여러 해킹사건이 발생하고는 합니다. 이 글에서는 스마트 컨트랙트 위에서 발생하는 공격들에 몇 가지에 대해서 간략하게 알아보도록...
-
rkm0959's profile image
rkm0959
August 15, 2021
An Automatic System to Detect Equivalence Between Iterative Algorithms
논문 링크 : https://arxiv.org/abs/2105.04684 논문 저자 : Shipu Zhao, Laurent Lessard, Madeleine Udell Introduction : Optimization Algorithms and Their Equivalence 수학적 최적화에는 문제를 해결하기 위한 다양한 알고리즘이 있습니다. 각 알고리즘은 그 형태를 통해서 우리에게 최적화에 대한 직관을 주기도 하고 훌륭한 성능으로 우리가 최적화 문제를 어떻게 해결할 수 있는지 알려줍니다. 이는 이미 작성했던 여러 글에서도 강조했던 내용입니다. 예를 들어, 단순히 smooth differentiable convex function $f$를 최소화하는 문제에는 여러 알고리즘이 있고, 특히 Accelerated Gradient Method를 기반으로 하는...
-
rkm0959's profile image
rkm0959
July 15, 2021
The Attacks on GEA-1 and GEA-2
Introduction 최근 한 논문이 암호학계에서 크게 주목을 받고 있습니다. 최고의 컨퍼런스 중 하나인 EUROCRYPT 2021에 수록된 논문인 “Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2”라는 논문입니다. 이 내용은 GEA-1, GEA-2라는 암호체계를 공격하는 알고리즘을 제시하는 논문입니다. 암호를 공격하는 논문은 많은데, 왜 하필 이 논문은 이렇게 주목을 많이 받고 있는 걸까요? 그 이유는 공격 과정에서 GEA-1에 백도어가 있다는 것이 사실상 확정적으로 밝혀졌기 때문입니다. 암호학적 백도어가 무엇인지는 barkingdong님의 http://www.secmem.org/blog/2020/09/20/Cryptographic-Backdoor/ 라는 글을 참고하시길 바랍니다. 이번 글에서는 GEA-1, GEA-2...
-
rkm0959's profile image
rkm0959
June 15, 2021
SCLI Framework and its Applications on Minimax Problems
Introduction Machine Learning, Artificial Intelligence의 가장 기본적인 구조는 주어진 데이터에 대한 loss function을 만들고, 이를 최소화하는 것입니다. loss function $f$를 design 했다면, 이 $f$를 최소화하는 것은 최적화 알고리즘의 영역에 들어오게 됩니다. 특히, ML/AI 분야에서는 $f$를 최소화하기 위하여 그 gradient $\nabla f$를 사용하는 gradient-based optimization을 주로 사용합니다. 이러한 환경에서, 최적화 알고리즘을 연구하는 사람들이 자연스럽게 최적화 알고리즘에 대하여 주로 관심을 가지게 되는 정보는 크게 다음과 같습니다. $f$에 대한 특정 조건이 주어졌을 때, 주어진 알고리즘이 얼마나 빠르게 최적해로...
-
rkm0959's profile image
rkm0959
May 4, 2021
Variance Reduction Algorithms and Catalyst Acceleration
서론 본 글에서는 단순히 convex function $f$를 최소화 하는 것이 아니라, 이들의 합인 $F = \frac{1}{n} \sum_{i=1}^n f_i(x)$ 를 최소화하는 알고리즘에 대해서 알아보고, 이에 Catalyst를 적용해보겠습니다. 이와 같은 형식의 함수 $F$는 Logistic Regression 등 Machine Learning에서 등장합니다. 원래는 $F$에 추가적인 “proximal function”이 있어, $F = \frac{1}{n} \sum_{i=1}^n f_i(x) + \psi(x)$ 형태를 가지나 (예를 들어 $l_1$ regularization) 여기서는 편의상 $\psi$에 대한 논의를 생략하겠습니다. 글의 순서는 대략적으로 다음과 같습니다. $F$를 최소화하는 알고리즘이 발전한 과정의 큰 흐름에 대해서...
-
rkm0959's profile image
rkm0959
April 15, 2021
Catalyst Acceleration
서론 Convex Optimization의 주요 목적 중 하나는, convex function $f$가 있을 때 최적화 문제 $ f_{*} = \min_{x \in \mathbb{R}^d} f(x) $ 를 효율적으로 해결하는 것입니다. 특히, $f$가 수학적으로 좋은 조건을 만족하는, 즉 convex, closed, proper function인 경우를 (CCP function) 주로 다룹니다. Gradient Descent와 같은 first-order algorithm들은 이 목표를 달성하기 위해서 Gradient 또는 Subgradient를 이용합니다. 이제부터 다룰 대상은 Gradient를 사용하여 최적화를 하는 대신, Proximal Operator $ prox_{\lambda f}(x) = \text{argmin}_y \left( f(y) + \frac{1}{2\lambda} ...
-
rkm0959's profile image
rkm0959
March 15, 2021
Inequality Solving with CVP
서론 이 글은 제가 CTF 대회에서 자주 사용하는 toolkit인 github.com/rkm0959/Inequality_Solving_with_CVP의 설명서입니다. 이미 README에 많은 설명이 있지만, 설명서라기에는 부실한 점이 많아 이를 보강합니다. 제가 이 글을 작성하는 목적은 이 repository의 존재를 더 많은 사람들에게 홍보하기 위해서 이 repository의 기본적인 아이디어를 CTF를 하지 않는 사람들에게도 알리기 위해서 이 repository가 더 많은 사람들에게 사용되기를 바라기 때문 이 repository의 부족한 점을 보충하기 위해서 입니다. 이 점을 참고하시고 글을 읽어주시면 감사하겠습니다. 이 글에서 모든 나눗셈은 floor function을 거친 결과로 생각하시기...