-
rkm0959's profile image
rkm0959
July 26, 2024
STIR: Reed-Solomon Proximity Testing with Fewer Queries
소개 이 글은 https://eprint.iacr.org/2024/390.pdf에 대해서 설명합니다. STIR의 목표는, Reed-Solomon Code와의 Proximity Testing을 최소한의 query로 하는 것입니다. 동일한 문제를 푸는 알고리즘 중 가장 잘 알려진 FRI는, degree $d$ 문제를 $\lambda$-bit security를 갖게 해결하기 위하여 query를 $\mathcal{O}(\lambda \log d)$개 사용합니다. STIR는, 그에 비해 $\mathcal{O}(\log d + \lambda \cdot \log \log d)$만큼의 query를 사용하여, 더 적은 query를 사용하게 됩니다. query의 개수는 STARK proof의 크기와 연결되어 있기 때문에, FRI를 STIR로 대체하여 STARK의 proof size 및 verifier time을 줄일 수...
-
rkm0959's profile image
rkm0959
June 11, 2024
Anatomy of a zkVM: Looking at SP1
소개 최근 Succinct Labs의 zkVM인 SP1을 자세히 볼 기회가 생겼습니다. zkVM은 ZKP를 통해서 하나의 프로그램 자체의 execution을 통째로 증명하는 것을 목표로 하고 있습니다. SP1의 경우에서는 RISC-V 프로그램을 대상으로 하고 있어, Rust을 구현한 후 컴파일하면 SP1이 바로 증명을 할 수 있게 됩니다. 이를 통해서, 복잡한 ZKP 서킷을 직접 작성하는 대신 Rust로 코드를 짜고, 이를 SP1으로 덮어서 ZKP를 사용할 수 있게 됩니다. 즉, zkEVM을 구현하기 위해서 EVM의 Rust 구현체를 가져다 쓰기만 하면 됩니다. 이 글에서는 SP1의 구조에...
-
rkm0959's profile image
rkm0959
May 26, 2024
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을 하고 싶다면...
-
rkm0959's profile image
rkm0959
April 25, 2024
Insights from and on Taxonomy of ZKP Vulnerabilities
올해 4월 초, ZKP 관련 최대 컨퍼런스 중 하나인 zkSummit11에서 ZKP 보안과 관련된 발표를 진행할 수 있었습니다. 이번 글에서는 발표 내용에 대한 간략한 설명을 합니다. ZKP 보안에 대한 업계의 이해도는 2022년부터 꾸준히 증가해왔지만, 아직도 ZKP 보안 판에는 여러 문제가 있습니다. 가장 큰 문제 중 하나는 사람이 부족하다는 것인데, 이에 대한 해답으로는 크게 두 가지를 생각할 수 있습니다. 암호를 잘 하는 사람에게 보안의 컨텍스트를 가르쳐 ZKP 보안을 소개하는 것 블록체인 보안을 하는 사람에게 암호의 컨텍스트를 가르쳐...
-
rkm0959's profile image
rkm0959
March 25, 2024
PIOP Improvements for ZeroCheck
Circle STARK Part 2를 하기 이전에, 최근 읽은 논문 중 간단하면서도 강력한 게 하나 있어서 이를 공유합니다. 이번 글에서는 https://eprint.iacr.org/2024/108 의 내용을 정리합니다. Zero Check Multivariate Polynomial을 기반으로 한 proof system들은, 일반적으로 boolean hypercube $H_n$ 위에서 어떤 함수 $C(x)$가 전부 0으로 계산됨을 증명하는 것으로 문제를 환원시킵니다. 결국 최종적으로 \[C(x) = 0 \quad \forall x \in H_n\] 를 보여야 하는데, 이를 위해서 verifier는 랜덤한 $\alpha$를 정한다음 \[\sum_{x \in H_n} \tilde{eq}(x, \alpha) \cdot C(x) = 0\] 을...
-
rkm0959's profile image
rkm0959
February 26, 2024
Circle STARK Part 1: Circle FFT
ZKP를 위한 Underlying Field $\mathbb{F}_p$ ZKP의 패러다임을 다루거나, ZKP를 본격적으로 분류를 하게 되면 그에 대한 가능한 기준으로는 여러가지가 있습니다. 하지만 요즘 대부분이 생각하는 방식은 (수학적으로 엄밀하거나 완전하지는 않아도) $\mathbb{F}_p$ 위에서 ZKP가 작동을 할 때 $p$가 어떤 값을 가지냐를 가지고 많이 논의를 합니다. $p$가 256 bit 정도를 가지는 경우 $p$가 64 bit 정도거나 32 bit 정도로 작은 경우 $p$가 소수가 아니라 256 bit 정도의 2의 거듭제곱인 경우 여기에 추가적으로 $p$가 NTT를 지원한다던가, 타원곡선의 크기여야 한다던가 하는...
-
rkm0959's profile image
rkm0959
January 28, 2024
Proximity Testing with Logarithmic Randomness
Code-Based PCS의 복습 Linear code $V$에 대하여, 벡터 $x$와 $V$의 거리를 \[d(x, V) = \lVert x - V \rVert_0 = \min_{y \in V} (\lVert x - y \rVert_0)\] 또, 행렬 $X$와 $V$의 거리를 각 column이 전부 $V$의 원소인 행렬 $Y$에 대하여, $X - Y$가 갖는 non-zero row의 최소 개수라고 정의한다. 이 거리의 정의를 기반으로, $q$-close와 $q$-far를 정의할 수 있다. 이때, code-based PCS의 안정성을 증명하는 가장 핵심적인 결과는 \[\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le...
-
rkm0959's profile image
rkm0959
December 25, 2023
Folding Part 2: HyperNova
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Verifiable Computation은 Generator $\mathcal{G}(1^\lambda) \rightarrow pp$: security parameter $\lambda$를 받고 public parameter $pp$를 만든다 Encoder $\mathcal{K}(pp, F) \rightarrow (pk, vk)$: public parameter $pp$와 반복할 함수 $F$를 받고, prover key 및 verifier key $pk, vk$를 만든다 Prover $\mathcal{P}(pk, (i, z_0, z_i), \omega_i, \Pi_i) \rightarrow \Pi_{i+1}$은 결과 $z_i$와 이에 대한 IVC proof $\Pi_i$를 받고, $z_{i+1} =...
-
rkm0959's profile image
rkm0959
November 26, 2023
Folding Part 1: ProtoStar
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 ProtoStar에 대해서 다룹니다. https://eprint.iacr.org/2023/620.pdf Folding이란 무엇이며, ProtoStar의 목표는 무엇인가 Folding은, input 자체만 제외하면 증명하고자 하는 연산의 형태는 동일한 두 ZKP instance를 하나의 instance로 fold 하는 테크닉으로, 올해 초부터 더욱 본격적인 관심을 받게된 테크닉입니다. 기존에 IVC를 (Incrementally Verifiable Computation) 얻으려면 recursive SNARKs, 즉 이전 SNARK의 verification 과정을 다시 SNARK로 올려 계산하는 방식으로 구현했다면, 이제는 SNARK를 accumulate 하여 접어가면서 쌓아올린 후 최종 accumulator를 가지고 전체...
-
rkm0959's profile image
rkm0959
October 22, 2023
Multilinear PCS from Univariate PCS
저번 포스팅에서는 Multilinear Polynomial에 대한 linear-time commitment 중 하나인 Brakedown에 대해서 알아보았습니다. Sumcheck 관련 기법들이 떠오르면서, Multilinear Polynomial의 commitment에 대한 기법들이 더욱 중요해졌습니다. 그 방법에는 Brakedown 및 이를 강화하는 Orion, Orion+ 뿐만 아니라 Dory, Hyrax 등 다른 기법도 존재합니다. 특히, Univariate Polynomial에 대한 Commitment를 기반으로 Multilinear Polynomial에 대한 Commitment 기법을 유도하는 기법들도 여러 가지 존재합니다. 여기서는 그 방법인 Gemini와 Zeromorph에 대해서 알아보도록 하겠습니다. 이 포스팅에 대응되는 논문은 아래와 같습니다. https://eprint.iacr.org/2022/420.pdf Section 5 https://eprint.iacr.org/2023/917 KZG +...
-
rkm0959's profile image
rkm0959
September 16, 2023
Brakedown Overview
이 내용은 https://eprint.iacr.org/2021/1043 의 요약입니다. 이 논문의 목표는 Linear Code를 기반으로 한 Linear-Time PCS를 준비하고 이를 Spartan에 적용하여 Linear-Time Field-Agnostic SNARK를 얻는 것입니다. Spartan 계열 테크닉이 주목을 받는 시점에서 읽기 좋은 논문이라고 생각됩니다. 다만, 길이의 문제로 각종 증명들은 생략하도록 하겠습니다. Linear Time Polynomial Commitment Multilinear polynomial을 기준으로 생각하면, $g$의 Lagrange basis에서 coefficient를 $u$라고 했을 때 \[g(r) = \sum_i u_i \cdot \left(\prod_{k} (r_k i_k + (1 - r_k)(1 - i_k)) \right)\] 라고 쓸 수 있고, 대괄호...
-
rkm0959's profile image
rkm0959
July 14, 2023
Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
이 내용은 https://eprint.iacr.org/2023/1025.pdf 의 요약입니다. ZK Friendly Hash Function의 필요성 해시함수는 굉장히 많은 곳에서 사용되고 있습니다. 그런만큼 ZKP 상에서도 해시함수의 계산에 대한 증명을 하게 될 필요가 상당히 많습니다. 그런데 일반적인 해시함수는 일반적인 컴퓨팅 환경에서 빠르게 작동하는 것을 목표로 하기 때문에, 비트 연산 등을 많이 활용합니다. 이는 비트 연산을 다루는 비용이 큰 ZKP 상에서는 큰 문제로 작용합니다. 이에 따라, ZKP 상에서 비용이 적은, 즉 적은 constraint로 증명을 할 수 있는 해시함수를 만드는 것이 필요해졌습니다. 또한, ZKP...
-
rkm0959's profile image
rkm0959
March 19, 2023
ZKP and Block Hash Oracles
이 내용은 ZK-School에서 멘토링한 자료에 기반합니다. ZKP의 목표 영지식 증명, Zero Knowledge Proof는 기본적으로 일련의 계산이 제대로 되었음을 간단하게 증명하는 것을 목표로 하고 있습니다. Zero Knowledge라는 부분도 중요하지만, 가장 핵심은 보통 Proof에 있습니다. 일단 Proof가 되어야지 Zero Knowledge를 이야기를 하겠죠? 그래서 대강 압축을 하자면, Alice가 $f(x)$라는 값을 알고 싶은데 이를 직접 계산하기에는 컴퓨팅 파워가 부족하다면, 그 컴퓨팅 파워가 있는 Bob이 $f(x)$를 직접 계산해서 $y = f(x)$라는 사실을 알아내고, Alice에게 단순히 $y$의 값을 넘기는 것이 아니라,...
-
rkm0959's profile image
rkm0959
December 5, 2022
Optimal Ate Pairings, BLS12-381, BN254 알아보기
이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q) = f_{r, P}(Q)^{(q^k - 1) / r}\] 를 얻을 수 있었습니다. 이제 이를 최적화하는 Ate Pairing을 알아봅시다. Lemma \[f_{ab, Q} = f_{a, Q}^b \cdot f_{b, [a]Q}\] 증명: 단순 계산. 어렵지 않습니다. 그러면 특히 $[r]Q = \mathcal{O}$인 경우에는 \[f_{mr, Q} = f_{r, Q}^m\] 가...
-
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을 거친 결과로 생각하시기...