유명한 암호화 알고리즘이 업그레이드되었습니다 | 콴타 매거진

점점 더 디지털화되는 삶에서 보안은 암호화에 달려 있습니다. 개인 메시지를 보내거나 온라인으로 청구서를 지불하면 데이터를 비밀로 유지하도록 설계된 알고리즘을 사용하게 됩니다. 당연히 일부 사람들은 이러한 비밀을 밝히고 싶어합니다. 따라서 연구자들은 이러한 시스템이 영리한 공격자의 손에 무너지지 않을지 확인하기 위해 이러한 시스템의 강도를 테스트하기 위해 노력하고 있습니다.

이 연구에서 중요한 도구 중 하나는 LLL 알고리즘으로, 연구자의 이름을 따서 명명되었습니다. 출판했다 1982년 — Arjen Lenstra, Hendrik Lenstra Jr., László Lovász. 많은 하위 항목과 함께 LLL은 경우에 따라 암호화 체계를 깨뜨릴 수 있습니다. 그들이 어떻게 행동하는지 연구하는 것은 연구자들이 공격에 덜 취약한 시스템을 설계하는 데 도움이 됩니다. 그리고 알고리즘의 재능은 암호화를 넘어 확장됩니다. 또한 계산 수 이론과 같은 고급 수학 분야에서도 유용한 도구입니다.

수년에 걸쳐 연구자들은 접근 방식을 보다 실용적으로 만들기 위해 LLL의 변형을 연마해 왔지만 어느 정도까지만 가능합니다. 이제 한 쌍의 암호학자가 효율성을 크게 향상시킨 새로운 LLL 스타일 알고리즘을 구축했습니다. 우승을 차지한 신기술 최우수 논문상 에 2023년 국제 암호학 컨퍼런스, 컴퓨터 과학자와 수학자들이 LLL과 유사한 접근 방식을 실현 가능하게 사용할 수 있는 시나리오의 범위를 넓힙니다.

“정말 흥미로웠다”고 말했다 크리스 페이커트, 논문에 참여하지 않은 미시간 대학의 암호학자입니다. 그는 이 도구가 수십 년 동안 연구의 초점이 되어 왔다고 말했습니다. "오랫동안 연구해온 목표가 아직 발견되지 않은 놀라움이 있다는 것을 보여주는 것은 언제나 좋은 일입니다."

LLL 유형 알고리즘은 규칙적으로 간격을 둔 점의 무한한 집합인 격자의 세계에서 작동합니다. 이를 시각화하는 한 가지 방법으로 바닥 타일을 깔고 있다고 상상해 보세요. 정사각형 타일로 덮으면 타일의 모서리가 하나의 격자를 구성하게 됩니다. 또는 다른 타일 모양(예: 긴 평행사변형)을 선택하여 다른 격자를 만들 수도 있습니다.

격자는 "기초"를 사용하여 설명할 수 있습니다. 이는 격자의 모든 점을 얻기 위해 다양한 방법으로 결합할 수 있는 벡터 세트(기본적으로 숫자 목록)입니다. [3, 2]와 [1, 4]라는 두 벡터로 구성된 기저를 가진 격자를 상상해 봅시다. 격자는 해당 벡터의 복사본을 더하고 빼서 도달할 수 있는 모든 지점입니다.

그 벡터 쌍은 격자의 유일한 기초가 아닙니다. 최소 XNUMX차원을 가진 모든 격자에는 무한히 많은 기반이 있습니다. 그러나 모든 기반이 동일하게 만들어지는 것은 아닙니다. 벡터가 더 짧고 서로 직각에 가까운 기저가 일반적으로 작업하기 쉽고 일부 계산 문제를 해결하는 데 더 유용하므로 연구자들은 이러한 기저를 "좋음"이라고 부릅니다. 이에 대한 예는 아래 그림의 파란색 벡터 쌍입니다. 빨간색 벡터와 같이 더 길고 덜 직교하는 벡터로 구성된 베이스는 "나쁜" 것으로 간주될 수 있습니다.

이것은 LLL의 임무입니다. LLL(또는 그 형제)에게 다차원 격자의 기초를 제공하면 더 나은 격자가 나올 것입니다. 이 프로세스는 격자 기반 감소로 알려져 있습니다.

이 모든 것이 암호화와 어떤 관련이 있나요? 어떤 경우에는 암호화 시스템을 깨는 작업이 또 다른 문제로 재구성될 수 있다는 것이 밝혀졌습니다. 격자에서 상대적으로 짧은 벡터를 찾는 것입니다. 그리고 때로는 LLL 스타일 알고리즘에 의해 생성된 축소된 기저에서 해당 벡터를 추출할 수도 있습니다. 이 전략은 연구자들이 표면적으로는 격자와 거의 관련이 없는 것처럼 보이는 시스템을 무너뜨리는 데 도움이 되었습니다.

이론적 의미에서 원래 LLL 알고리즘은 빠르게 실행됩니다. 실행하는 데 걸리는 시간은 입력 크기, 즉 격자의 차원과 숫자의 크기(비트 단위)에 따라 기하급수적으로 확장되지 않습니다. 기본 벡터. 그러나 그것은 다항식 함수로 증가하며 "실제로 그렇게 하고 싶다면 다항식 시간이 항상 실현 가능한 것은 아닙니다"라고 말했습니다. 레오 뒤카스, 네덜란드 국립연구소 CWI의 암호해독자.

실제로 이는 원래 LLL 알고리즘이 너무 큰 입력을 처리할 수 없음을 의미합니다. “수학자와 암호학자들은 더 많은 일을 할 수 있는 능력을 원했습니다.”라고 말했습니다. 키건 라이언, 캘리포니아 대학교 샌디에고 캠퍼스의 박사 과정 학생입니다. 연구원들은 더 큰 입력을 수용하고 종종 좋은 성능을 달성하기 위해 LLL 스타일 알고리즘을 최적화하기 위해 노력했습니다. 그럼에도 불구하고 일부 작업은 계속해서 도달할 수 없는 상태로 남아 있습니다.

Ryan과 그의 고문이 작성한 새 논문은 나디아 헤닝거는 LLL 스타일 알고리즘의 효율성을 향상시키기 위해 여러 전략을 결합합니다. 우선, 이 기술은 작업을 더 작은 덩어리로 나누는 재귀적 구조를 사용합니다. 또 다른 경우, 알고리즘은 관련된 숫자의 정밀도를 신중하게 관리하여 속도와 올바른 결과 사이의 균형을 찾습니다. 새로운 연구를 통해 연구자들은 수천 차원의 격자 기반을 줄이는 것이 가능해졌습니다.

과거 연구에서도 비슷한 접근 방식을 따랐습니다. 2021 용지 또한 재귀와 정밀 관리를 결합하여 대규모 격자를 빠르게 작업할 수 있지만 암호화에서 중요한 모든 격자가 아니라 특정 종류의 격자에만 작동했습니다. 새로운 알고리즘은 훨씬 더 넓은 범위에서 잘 작동합니다. “누군가가 해냈다니 정말 기쁘네요.” 토마스 에스피타우, PQShield 회사의 암호화 연구원이자 2021 버전의 저자입니다. 그의 팀의 작업은 "개념 증명"을 제공했다고 그는 말했습니다. 새로운 결과는 "건전한 방식으로 매우 빠른 격자 감소를 수행할 수 있다"는 것을 보여줍니다.

새로운 기술은 이미 유용하다는 것이 입증되기 시작했습니다. 오렐 페이지프랑스 국립 연구소 인리아(Inria)의 수학자인 는 그와 그의 팀이 일부 계산 정수론 작업을 수행하기 위해 알고리즘을 적용했다고 말했습니다.

LLL 스타일 알고리즘은 다음을 위해 설계된 격자 기반 암호화 시스템과 관련된 연구에서도 역할을 할 수 있습니다. 보안 유지 강력한 양자 컴퓨터가 있는 미래에도 말이죠. 이러한 시스템을 무너뜨리려면 이러한 알고리즘이 달성할 수 있는 것보다 더 짧은 벡터를 찾아야 하기 때문에 이러한 시스템에는 위협이 되지 않습니다. 그러나 연구원들이 알고 있는 최고의 공격은 LLL 스타일 알고리즘을 "기본 빌딩 블록"으로 사용한다고 말했습니다. 베셀 반 워르덴, 보르도 대학의 암호학자. 이러한 공격을 연구하기 위한 실제 실험에서 해당 구성 요소는 모든 것을 느리게 할 수 있습니다. 새로운 도구를 사용하면 연구원들은 공격 알고리즘에 대해 실행할 수 있는 실험 범위를 확장하여 공격 알고리즘의 수행 방식에 대한 보다 명확한 그림을 제공할 수 있습니다.

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 컴퓨터 과학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 상품.