-
IND-CCA2 Encryption schemes and Fujisaki-Okamoto transform
Introduction 암호의 안전성 암호는 수천년 전에 로마나 고대 그리스에서 사용하던 고전암호로부터 시작해 20세기 초에는 상당히 발전되어 전쟁에서 사용되기도 했으며, 그 후 현재까지 쓰이고 있는 대칭키 암호(symmetric key cryptography) 및 공개키 암호(public key cryptography)가 개발되었습니다. 현재는 그 외에도 Lattice-based cryptography 등의 여러 암호가 활발하게 연구되고 있습니다. 초창기의 암호 중 몇몇은 하나의 문자가 하나의 문자에 대응되는 형식을 띠고 있습니다. 이러한 암호의 경우 문자마다 실제 단어에 사용되는 빈도가 달라 암호문이 충분히 주어진다면 그 빈도를 파악하여 대응되는 문자를 파악하여...
-
Treewidth를 사용한 PS 문제 해결
알고리즘에서 다루는 많은 문제들은 그래프 문제로 환원할 수 있는데, 일반적인 그래프에서 어떤 문제들은 효율적으로 해결이 불가능한 경우가 있다. 이러한 비효율성의 대표적인 예시는 NP-hard로, 어떠한 문제가 NP-hard일 경우 다항 시간으로 푸는 것이 아예 불가능할 가능성이 높다. 그 외에도, 최단 경로 문제와 같이 다양한 쿼리에 대해서 빠른 시간 안에 해결하는 것이 어려운 경우 등, 비효율성의 예시는 NP-hard에 한정되지 않는다. 이러한 비효율성에 당착했을 때 자주 취하는 전략은 환원한 그래프의 특수성에 의존하는 것이다. 예를 들어, NP-hard 문제들이라 하더라도 그래프가...
-
Optuna: hyperparameter optimization
Introduction 딥러닝 모델을 구현함에 있어서 hyperparameter를 결정하는 것은 어려운 문제입니다. 일반적으로 hyperparameter를 결정하기 위해서는 hyperparameter에 대한 여러 번의 실험을 진행합니다. 실험을 진행하는 가장 간단한 방법은 실험을 할 때마다 코드의 hyperparameter들을 직접 변경하는 방법이 있습니다. 이 방법을 사용할 경우 새로운 실험을 진행할 때마다 코드가 변경되기 때문에 버전 관리도 쉽지 않고, 매번 코드를 수정하는 것이 번거롭다는 단점이 있습니다. 이보다 약간 개선된 방법은 command line argument로 hyperparameter를 설정하는 방법이 있습니다. 이 방법을 사용할 경우에는 새로운 실험을 진행할 때마다...
-
다익스트라에 제출한 SPFA 저격 데이터
다익스트라 알고리즘은 모든 간선이 음이 아닌 가중치를 가질 때 사용할 수 있는 최단거리 알고리즘으로, 새로 확인할 정점을 고를 때 매번 모든 정점의 알려진 최단거리를 비교하는 방식으로는 $O(V^2)$에, 우선순위 큐를 사용하면 $O(E \log E)$에 구현할 수 있습니다. 한편 벨만-포드 알고리즘의 변형이라고 볼 수 있는 SPFA 알고리즘은 간선의 가중치가 음수인 경우에도 사용할 수 있으며, 최악의 경우의 시간복잡도는 $O(VE)$이지만, $O(E \log E)$ 다익스트라 알고리즘이 정해인 문제에서도 저격 데이터가 없는 경우 통과하는 경우도 있습니다. 이 글에서는 SPFA 알고리즘의 기본적인...
-
Simple Copy-Paste is a Strong Data Augmentation Method for Instance Segmentation
Simple Copy-Paste is a Strong Data Augmentation Method for Instance Segmentation (2021) Instance Segmentation Computer Vision에서 Data Augmentation 기법은 항상 같이 붙어다닐 수밖에 없는 분야입니다. 모델의 성능이 아무리 좋아지더라도, 그것을 학습시키기 위한 충분한 데이터가 없다면 제대로 성능이 나오지 않기 때문입니다. 요새에는 굉장히 많은 양의 데이터들이 쏟아지고, 이를 수집하면서 기업들은 최대한 양질의 많은 데이터를 얻으려고 노력합니다. 하지만 그럼에도 불구하고 데이터를 얻어내는 것이 어려운 분야들이 있죠. 의료나 혹은 수집 동안 굉장히 오랜 시간이 걸리는 분야들은 그 자체로...