🤖 machine learning

Discovering Lattice Reduction Strategies via Self-Play

이 논문은 자기 대국(self-play)을 통해 학습되어 고전적인 LLL 알고리즘보다 더 적은 연산을 필요로 하는 우수한 격자 축소 전략을 발견하고, 더 높은 차원 및 보지 못한 모듈로에 대한 제로샷 일반화 성능을 입증하는 심층 강화 학습 에이전트인 DeltaStar를 소개한다.

원저자: Mohamed Malhou, Kristin Lauter, Ludovic Perret

게시일 2026-06-16

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mohamed Malhou, Kristin Lauter, Ludovic Perret

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 엉킨 실타래가 하나 있다고 상상해 보세요. 당신의 목표는 이 실타래를 풀어서 실들을 최대한 곧고 짧게 정렬하는 것입니다. 수학과 암호학의 세계에서 이 '실타래'는 **격자(lattice)**라고 불리며, '실'은 **벡터(vector)**라고 불립니다. 가장 짧고 곧은 배열을 찾아내는 것은 디지털 비밀을 안전하게 지키는 데 매우 중요하지만, 실타래가 거대해질수록 이를 손으로 직접 수행하기란 매우 어렵습니다.

수십 년 동안 이 실타래를 푸는 표준 도구는 LLL이라 불리는 알고리즘이었습니다. LLL을 아주 엄격한 규칙을 따르는 로봇이라고 생각해 보세요. 이 로봇에게는 두 가지 단순한 동작이 있습니다:

크기 축소(Size Reduction): 실의 느슨함을 제거하기 위해 실을 이전의 실들에 바짝 밀착시킵니다.
교환(Swapping): 만약 어떤 실이 순서에서 벗어나 보인다면, 그 실을 이웃한 실과 바꿉니다.

로봇은 이 교환을 언제 할지 결정하기 위해 "로바츠 조건(Lovász condition)"이라는 엄격하고 수기로 작성된 규칙을 따릅니다. 이 규칙은 로봇이 적절한 시간 내에 일을 끝낼 수 있도록 보장하지만, 항상 완벽하게 잘 풀린 결과를 만들어내는 것은 아닙니다. 이는 마치 지도를 따라 도시에 도착하긴 했지만, 불필요한 우회로를 몇 번 거친 것과 같습니다.

새로운 발견: "델타-스타(Delta-Star)"

이 논문의 저자들은 다음과 같은 간단한 질문을 던졌습니다: 만약 우리가 로봇에게 딱딱한 규칙 책을 주는 대신, 스스로 실을 푸는 게임을 하는 법을 가르친다면 어떻게 될까?

그들은 심층 강화 학습(Deep Reinforcement Learning) 기술을 사용하여 델타-스타라는 AI 에이전트를 구축했습니다. 여기서는 창의적인 비유를 사용하여 그 과정을 설명하겠습니다.

1. 훈련장 (작은 실타래)

그들은 AI를 거대하고 불가능한 매듭 속에 던져 넣지 않았습니다. 대신, 8차원의 작은 격자(생각해 보세요, 8개의 실이 있는 작은 실타래)에서 AI를 훈련시켰습니다.

게임: AI는 기존의 로봇과 똑같은 두 가지 동작(바짝 당기거나 교환하기)만 수행할 수 있는 1인용 게임을 합니다.
목표: AI는 실을 더 짧고 곧게 만들수록 점수를 얻습니다. 단계를 너무 많이 소모하면 점수를 잃습니다.
스승: AI는 자신과 수백만 번의 대국(Self-Play)을 하며 배웁니다. 어떤 동작을 시도하고, 그것이 도움이 되는지 확인하며, 도움이 되지 않는다면 다음번에는 그 동작을 잊어버립니다.

2. "수정구슬" 전략 (적응형 호라이즌 MCTS)

이 시스템의 가장 영리한 부분은 AI가 앞을 내다보는 방식입니다*

일반적인 사고: 보통의 AI는 한 단계 앞을 보고, 그다음 단계를 보고, 또 그다음을 봅니다. 이는 느리고 계산 비용이 많이 듭니다.
델타-스타의 사고: AI는 몇 단계 앞의 움직임을 한꺼번에 예측하는 "수정구슬"을 가지고 있습니다.
- 만약 수정구슬이 "다음 10단계의 움직임은 명확하고 자동적이다"라고 말하면, AI는 그 단계들을 즉시 건너뜁니다.
- 만 만약 수정구슬이 "와, 다음 단계는 선택지가 많고 까다로운 결정이다"라고 말하면, AI는 멈춰서 그 특정 순간에 대해 깊이 생각합니다.
비유: 자동차 운전을 상상해 보세요. 직선의 텅 빈 고속도로에서는 도로의 매 인치마다 생각할 필요 없이 그냥 주행하면 됩니다. 하지만 복잡한 교차로에 도달하면 속도를 줄이고 집중해야 합니다. 델타-스타는 자동으로 이 작업을 수행하여, 지루한 부분에서는 에너지를 아끼고 어려운 결정에는 집중합니다.

3. 마법 같은 기술: 제로샷 일반화(Zero-Shot Generalization)

이것은 가장 놀라운 결과입니다. AI는 오직 작은 8개 실의 실타래에 대해서만 훈련되었습니다. 훈련 중에 더 큰 실타래를 본 적이 없습니다.

테스트: 연구진들은 AI에게 한 번도 본 적 없는 거대한 32개 실의 실타래를 건네주었습니다.
결과: AI는 혼란에 빠지지 않았습니다. AI는 기존의 LLL 로봇보다 더 잘 실을 풀 수 있도록 즉각적으로 방법을 찾아냈습니다.
은유: 이것은 아이에게 아주 작은 아기 신발 끈을 묶는 법을 가르친 뒤, 성인용 부츠를 건네주는 것과 같습니다. 아이는 새로운 수업이 필요하지 않습니다. 그저 배운 논리를 적용하여, 수년간 신발 끈을 묶어온 성인보다 더 잘 해내는 것입니다.

이것이 왜 중요한가?

이 논문은 델타-스타가 고전적인 LLL 알고리즘보다 더 "깔끔하게" 정렬된 격자를 만들어낸다고 주장합니다.

더 나은 품질: 최종적인 실의 배열이 더 짧고 효율적입니다.
더 적은 단계: 목표에 도달하기 위해 더 적은 "당기기와 교환"을 수행합니다.
재학습 불필요: 본 적 없는 크기에서도 작동합니다.

한계점

논문은 한 가지 제한 사항에 대해 매우 명확하게 밝히고 있습니다: 바로 속도입니다.
델타-스타는 수학적 단계는 더 적게 사용하면서도 더 나은 해결책을 찾아내지만, AI 자체를 실행하는 속도는 현재의 기존 로봇보다 느립니다. 이는 AI가 매 동작을 결정할 때마다 복잡한 신경망(거대한 디지털 뇌)을 구동해야 하기 때문입니다. 기존의 로봇이 단순한 계산기라면, AI는 슈퍼컴퓨터입니다.

저자들은 이 AI가 오늘 당장 당신의 휴대폰에 있는 기존 로봇을 대체할 준비가 되었다고 말하는 것이 아닙니다. 대신 이렇게 말하고 있습니다: "우리는 실타래를 푸는 더 나은 방법을 찾아냈습니다. 이제, 이 AI가 발견한 규칙들을 기록하여, 동일한 일을 수행하는 더 단순하고 빠른 로봇을 만드는 방법을 찾아내야 합니다."

요약하자면, 그들은 슈퍼 스마트한 AI를 사용하여 수학 문제에 대한 더 나은 전략을 발견했으며, 그 전략은 AI가 명시적으로 배우지 않은 문제에 대해서도 작동한다는 것입니다.

기술 요약: 셀프 플레이를 통한 격자 축소 전략의 발견

문제 정의

격자 축소(Lattice reduction)는 계산 수학 및 암호학의 근간이 되는 문제로, 포스트 양자 암호 체계의 보안을 뒷받침합니다. 렌스트라-렌스트라-로바츠(LLL) 알고리즘은 다항 시간 내에 작동하는 표준적인 격자 기저 축소 방법입니다. 그러나 LLL은 특정 실행 시간과 벡터 길이의 상한을 보장하지만, 실제 적용 시 특히 격자 차원이 증가함에 따라 그 결과물이 최적이 아닌 경우가 많습니다. 이 알고리즘은 기저 벡터를 교체할지 결정하기 위해 수작업으로 설계된 휴리스틱인 로바츠 조건(Lovász condition)에 의존합니다. 이 조건은 잠재 함수(potential function)의 단조 감소를 보장하지만, 반드시 가장 강력한 축소를 달라는 최적의 조건은 아닙니다.

본 연구에서 다루는 핵심 과제는, 더 복잡한 오라클(예: 정확한 최단 벡터 문제(SVP) 해결사)을 포함하도록 액션 공간을 확장하지 않고도, 데이터 기반 접근 방식을 통해 LLL의 원시 연산(크기 축소 및 인접 스왑)에 대한 시퀀싱 정책을 발견하여 기존 알고리즘보다 엄격하게 우수한 축소 품질을 얻을 수 있는지 여부입니다.

방법론: 델타-스타(Delta-Star)

저자들은 격자 축소를 단일 플레이어 마르코프 결정 과정(MDP)으로 정식화하고, 몬테카를로 트리 탐색(MCTS)이 증강된 심층 강화 학습(RL) 프레임워크를 채택했습니다.

1. MDP 정식화

상태 공간(State Space): 상태는 현재 기저 행렬 $B$ , 그에 따른 그람-슈미트 직교화(GSO) 벡터 및 계수, 커서 위치 $k$ (현재 처리 중인 행을 나타냄), 그리고 남은 단계 수를 포함합니다.
액션 공간(Action Space): 공정한 비교를 위해 에이전트는 LLL 알고리즘의 정확한 원시 액션으로 제한됩니다:
- MOVEUP/MOVEDOWN: 커서 위치를 조정합니다.
- SWAP: 인접한 두 기저 행 $b_k$ 와 $b_{k-1}$ 을 교환합니다.
- SIZEREDUCE: 크기 축소 조건( $|\mu_{j,k}| \le 1/2$ )을 만족하도록 이전 행들의 정수 배를 뺍니다.
보상 함수(Reward Function): 품질 측정 지표인 직교 결함(Orthogonality Defect $\delta$ )과 LLL 잠재 함수( $\Phi$ )의 로그 메트릭에 대한 상대적 축소를 기반으로 정규화된 보상이 정의됩니다. 하이브리드 보상은 이 두 가지 목적을 보간합니다.

2. 적응형 호라이즌 MCTS (Adaptive-Horizon MCTS)

저자들은 탐색 효율을 높이기 위해 새로운 적응형 호라이즌 MCTS 메커니즘을 도입했습니다:

다단계 예측(Multi-Step Prediction): 신경망은 $H$ 개의 미래 단계에 대한 정책(policy)과 가치(value)를 동시에 예측합니다.
엔트로피 게이트 확장(Entropy-Gated Expansion): 트리를 한 번에 하나의 노드씩 확장하는 대신, 네트워크가 예측한 "탐욕적(greedy)" 경로를 따라 이동합니다. 각 단계 $k$ $k$ 에서 알고리즘은 예측된 정책의 샤논 엔트로피 $H[p(k)]$ $H [p (k)]$ 를 계산합니다.
- 엔트로피가 낮으면(확신이 높으면), 알고-리즘은 추론 비용을 분담하기 위해 브랜칭 없이 해당 단계를 자동으로 통과합니다.
- 엔트로피가 임계값 $\tau$ 를 초과하면(실제 결정 지점임을 나타냄), 확장이 중단되고 해당 노드에서 트리가 분기됩니다.
이 메커니즘을 통해 검색은 결정론적인 시퀀스를 건너뛰고 불확실한 결정 지점에 계산 자원을 집중할 수 있습니다.

3. 신경망 아키텍처

백본(Backbone): 시간적 이력을 포착하기 위한 룩백 윈도우(lookback window)를 갖춘 딥 레지듀얼 네트워크(ResNet)입니다.
관측 텐서(Observation Tensor): 기저, GSO, 계수, 남은 시간, 커서 위치를 5개 채널의 텐서로 인코딩합니다.
헤드(Heads): 네트워크는 정책 헤드( $H$ 단계에 대한 확률)와 가치 헤드( $H$ 단계에 대한 기대 수익)를 출력합니다.
학습: 모델은 알파제로(AlphaZero) 스타일의 셀프 플레이를 통해 학습되며, 예측된 정책과 MCTS 방문 횟수 사이의 교차 엔트로피, 그리고 예측된 가치와 에피소드 수익 사이의 평균 제곱 오차(MSE)를 최소화합니다.

4. 학습 설정

에이전트인 델타-스타는 기본 차원 $n=8$ 및 모듈러스 $q=251$ 인 작은 $q$ -ary 격체에서만 학습됩니다. 학습은 셀프 플레이 워커, 추론 서버, 중앙 학습기로 구성된 분산 파이프라인을 활용합니다.

주요 결과

1. 우수한 축소 품질

델타-스타는 다양한 차원에서 고전적인 LLL 알고리즘보다 현저히 더 나은 루트 헤르미트 인자(root Hermite factor, $\delta_0$ )와 직교 결함을 달성합니다.

학습 차원( $n=8$ )에서 델타-스타는 LLL($1.00660 $)보다 약간 낮은$ \delta_0 $($ \approx 1.00657$)로 수렴합니다.
결정적으로, 성능 격차는 차원이 증가함에 따라 넓어집니다. $n=32$ 에서 델타-스타는 $\delta_0 = 1.0149$ 를 달성하여 LLL($1.0171 $)을 능가하며,$ n=8$보다 큰 차원에서 학습되지 않았음에도 불구하고 BKZ- $\beta$ ($1.0125$)의 품질에 근접합니다.

2. 제로샷 일반화 (Zero-Shot Generalization)

모델은 강력한 제로샷 일반화 능력을 보여줍니다:

차원: 보지 못한 차원인 $n=32$ 까지 일반화됩니다.
모듈러스: $\sim 20$ 에서 $5000 $범위의 보지 못한 모듈러스$ q$에 대해서도 일반화됩니다.
이는 $q$ -정규화된 관측 텐서와 네트워크 아키텍처의 적응형 풀링(adaptive pooling)을 통해 달성됩니다.

3. 알고리즘 효율성

델타-스타는 동등하거나 더 나은 축소 품질에 도달하기 위해 LLL보다 더 적은 원시 행 연산을 필요로 합니다.

$n=8$ 에서 LLL이 요구하는 행 연산의 55%만을 사용합니다.
높은 차원( $n=26, 32$ )에서도 축소 과정 전반에 걸쳐 엄격하게 더 나은 궤적을 유지하며, 더 빠르게 수렴하고 더 나은 최종 상태에 도달합니다.
저자들은 신경망 추론이 고전적인 구현보다 실제 실행 시간(wall-clock time) 측면에서는 느리지만, 원시 연산 횟수의 감소가 더 효율적인 기저 전략을 나타낸다고 언급했습니다.

의의 및 주장

본 논문은 딥 강화 학습이 LLL의 원시 액션 공간과 상호작용함으로써 엄격하게 우수하고 일반화 가능한 축소 전략을 발견할 수 있음을 입증한다고 주장합니다.

수작업 휴리스틱을 넘어서: 본 연구는 경직된 로바츠 조건이 최적이 아니며, 학습된 정책이 상태 공간을 더 효과적으로 탐색할 수 있음을 보여줍니다.
확장성: 이 접근 방식은 격자 축소 전략이 반드시 다른 차원에 맞춰 재설계되어야 한다는 통념에 도전하며, 작은 인스턴스에서 학습된 모델이 훨씬 더 큰 미지의 차원으로 확장될 수 있음을 보여줍니다.
알고리즘 발견: 저자들은 이 작업을 알파텐서(AlphaTensor)나 알파데브(AlphaDev)와 같은 AI 기반 알고리즘 발견 패러다임 내에 위치시키며, 계산 수학의 근본적인 휴리스틱 기반 알고리즘을 RL을 통한 최적의 결정 경로 발견을 통해 최적화할 수 있음을 시사합니다.
향 향후 방향: 논문은 학습된 정책 가중치가 결정론적이고 효율적인 알고리즘을 인코딩하고 있다고 결론짓습니다. 주요 향후 목표는 이 신경망으로부터 고전적인 알고리즘을 추출하고 정식화하는 것입니다. 또한, 이 방법론을 BKZ와 같은 블록 기반 알고리즘을 개선하는 데 확장할 수 있습니다.

저자들은 현재 구현에 대해 겸손한 태도를 유지하며, 신경망이 연산당 고전적 코드보다 느리다는 점을 인정하고, 본 연구의 가치가 즉각적인 실행 성능보다는 더 효율적인 축소 전략의 구조를 규명하는 데 있음을 강조합니다.