-
Advanced SIMD Guide
Intro 최근에 SIMD 연산을 활용해서 최적화를 해 볼 기회가 있었습니다. 그 과정에서 겪었던 어려운 점들과 흥미로운 점들, 그리고 유용한 점들을 모아 공유하고자 합니다. 확인해보니, 암호학 분야를 깊게 보시는 blisstoner께서 기존에 SIMD에 관한 소개글을 포스팅하신 것이 있습니다. Link 이 글에서는 좀더 다양한 연산들, 주의해야 할 점들, 그리고 어떻게 쉽게 개발할 수 있을지를 집중적으로 설명해봅니다. 간단하게 다시 짚고 넘어가자면, SIMD (Single Instruction Multiple Data) 연산은 다수의 데이터에 동일한 연산을 한꺼번에 적용하고자 하는 목표를 가집니다. 여러 개의 데이터를...
-
New Updates on Proximity Testing with Logarithmic Randomness
소개 이전 글에서, “Proximity Testing with Logarithmic Randomness”라는 논문을 소개했습니다. 이 논문을 읽은 당시에 제가 논문에 있었던 증명의 작은 오류를 찾아 이를 수정하는데 기여하기도 했으며, 그 내용도 이전 글에 소개되어 있습니다. 1월 이후, 해당 논문과 관련된 여러 새로운 발견이 이루어졌습니다. 이 글에서는 1월 이후 Proximity Testing에 대한 추가적인 발전에 대해서 다룹니다. 복습 이전 논문에서 다룬 핵심적인 정리는 다음과 같습니다. For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots,...
-
PS에서 C++ 상속 활용하기
C++에는 클래스가 있고, 클래스에는 상속이 있다는 사실은 대부분 알고 계실 것입니다. 상속의 개념을 Animal, Dog, Cat의 관계로 설명하는 것을 한 번쯤은 보셨을 것입니다. 하지만 실제 PS를 할 때 C++의 상속 개념을 활용하는 경우는 그닥 많지 않습니다. 그러나 상속을 잘 활용하면, PS에서도 더 편하고 깔끔하게 코드를 짤 수 있게 됩니다. 이 글에서는 PS에서 실용적으로 상속을 활용할 수 있는 몇 가지 사례를 소개합니다. 모든 원소에 특정 값 더하기 아래의 쿼리를 해결하는 문제를 생각해봅시다. 배열에 $x$ 추가하기 배열에서...
-
Polymath: Groth16 is Not The Limit
소개 ZKP의 성능을 측정하는 요소에는 여러 가지가 있습니다. Prover와 Verifier의 입장에서 생각해보면, 가장 중요한 것은 아무래도 Prover가 proof를 생성하는데 걸리는 시간 및 리소스 Verifier가 proof를 검증하는데 걸리는 시간 및 리소스 입니다. 하지만, Recursive ZKP나 최종적으로 Verifier가 위치하는 곳이 어디인지 등을 생각해보면, 시간 및 리소스만큼이나 중요한 것이 바로 Proof의 크기, 즉 proof size임을 알 수 있습니다. Proof의 크기 자체가 크면 blockchain 위에 올리는 데 비용이 커지며, 동시에 Recursive ZKP를 하는 overhead도 커지기 때문입니다. 특히, blockchain 위에...
-
Moving Least Squares Projection
Point Based Graphics Point Based Graphics는 컴퓨터 그래픽스의 한 분야로, 기존의 다각형 기반으로 형상을 모델링하는 기법인 Polygon Based Graphics와 달리 점들을 사용하여 3D 객체의 표면을 표현하는 기법입니다. 각 점은 위치 뿐만 아니라 그 지점의 색상과 텍스쳐 등 다양한 속성도 가질 수 있습니다. 여기서 객체를 표현하는데 사용된 점들의 집합을 Point Cloud라고 합니다. 이 Point Cloud가 조밀할수록 더욱 세밀한 형태를 표현할 수 있습니다. Point Based Graphics는 복잡한 형상을 기존 기법보다 더 효율적이고 자세하게 표현할 수 있다는 장점이...