Large smooth twins from short lattice vectors

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.격자의 최단벡터문제(SVP)를 풀어 B-smooth twin을 찾는 새 알고리즘 제안
2.기존 B≤100(증명)·B≤13(경험적) 한계를 넘어 B=751에서 196비트 twin 발견
3.격자를 변형해 B=997 조건의 213비트 twin까지 확장, 이번 연구 중 최대 크기
4.짧은 구간 내 smooth number 분포 휴리스틱으로 주어진 B에서 최대 twin 크기를 추정

왜 중요한가?

B-smooth twin 탐색은 암호학적 소수 생성·격자 기반 공격 분석과 연결되는 계산 난제로, SVP 격자 기법을 통해 탐색 가능한 B값을 기존 대비 크게 확장한 것은 관련 암호 파라미터의 안전성 평가에 참고자료가 된다.

본문 미리보기

Finding the largest pair of consecutive $B$-smooth integers for a fixed value of $B$, also called a $B$-smooth twin, is computationally challenging. It has only been provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기