문자 메시지를 보내거나, CD를 재생하거나, 클라우드에 파일을 저장한 적이 있다면 오류 수정의 이점을 누릴 수 있습니다. 이 혁명적인 아이디어는 연구원들이 나중에 손상을 쉽게 되돌릴 수 있는 형식으로 메시지를 다시 작성할 수 있다는 것을 처음 깨달았던 1940년대로 거슬러 올라갑니다.

수년에 걸쳐 연구자들은 다양한 방식으로 데이터를 인코딩하고 다양한 절차를 사용하여 오류를 수정하는 오류 수정 코드라고 하는 많은 독창적인 체계를 개발했습니다. 그러나 이론적인 컴퓨터 과학자들에게는 소위 지역적으로 수정 가능한 코드만큼 매력적인 것은 거의 없습니다. 이러한 코드에는 거의 모순적으로 들리는 두 가지 동시 속성이 있습니다. 즉, 인코딩된 데이터를 몇 군데에서 읽어 오류를 수정할 수 있지만 공격자는 코드를 선택적으로 변조하여 이 수정 절차를 방해할 수 없습니다. 마치 책에서 찢어진 페이지를 다른 몇 페이지만 훑어보는 것만으로도 복구할 수 있는 것과 같습니다.

“정말 마법 같은 현상이에요.” 톰 구르, 캠브리지 대학의 컴퓨터 과학자. "선험적으로 그러한 수학적 객체가 전혀 존재할 수 있는지는 분명하지 않습니다."

하지만 이 마법에는 엄청난 대가가 따른다. 로컬에서 수정 가능한 코드의 유일한 알려진 예는 매우 비효율적입니다. 메시지를 인코딩하면 메시지가 기하급수적으로 길어집니다. 이런 식으로 인코딩된 전체 책은 너무 다루기 힘들 것입니다.

컴퓨터 과학자들은 더 나은 로컬 수정 가능 코드가 가능한지 오랫동안 궁금해해 왔습니다. 그들은 이러한 엄격한 제한으로 인해 이러한 코드를 더 쉽게 이해할 수 있기를 바라면서 오류를 수정하기 위해 세 가지 쿼리만 사용하는 코드에 특히 중점을 두었습니다. 하지만 이 간단한 사례조차도 20년 넘게 연구자들을 난처하게 만들었습니다.

이제 컴퓨터 과학자 프라베시 코타리 카네기 멜론 대학교와 그의 대학원생 피터 마노하르 마침내 증명 기하급수적인 비용을 피하는 로컬에서 수정 가능한 3개의 쿼리 코드를 작성하는 것은 불가능합니다. 부정적인 결과일 수도 있지만 오류 수정의 한계를 명확히 하는 것은 연구자들에게 흥미로운 일입니다. 특히 국지적으로 수정 가능한 코드의 수학은 통신에서 멀리 떨어진 영역에서 발생하기 때문입니다.

“이번 결과는 정말 놀랍습니다”라고 Shubhangi 사라프, 토론토 대학의 컴퓨터 과학자. “엄청난 발전이군요.”

숫자의 강점

오류 수정을 이해하려면 보호하려는 데이터를 비트 시퀀스, 즉 0과 1로 상상해 보세요. 이 모델에서 오류는 무작위 변동이나 고의적인 조작으로 인해 0이 1로 원치 않게 바뀌거나 그 반대로 바뀔 수 있습니다.

친구에게 메시지를 보내고 싶지만 오류로 인해 의미가 바뀔까 봐 걱정된다고 가정해 보겠습니다. 간단한 전략 중 하나는 메시지의 각 0을 000으로 바꾸고 각 1을 111로 바꾸는 것입니다. 친구가 세 개의 동일한 비트가 연속으로 포함되지 않은 메시지의 일부를 보면 오류가 발생했음을 알 수 있습니다. 그리고 오류가 무작위이고 상대적으로 드물다면 110의 문자열은 손상된 111보다 손상된 000일 가능성이 훨씬 더 높습니다. 각 삼중항 내의 단순 다수결은 대부분의 오류를 수정하는 데 충분합니다.

반복 코드라고 불리는 이 방식은 단순하다는 장점이 있지만 권장할 만한 것이 거의 없습니다. 우선, 비교적 드물게 발생하는 오류를 처리하기 위해 모든 메시지의 길이를 3배로 늘려야 하며, 두 개의 인접한 오류가 발생할 가능성이 있는 경우 훨씬 더 많은 중복이 필요합니다. 더 나쁜 것은 공격자가 적극적으로 코드를 방해하려고 시도하는 경우와 같이 오류가 무작위가 아닌 경우 빠르게 쓸모 없게 된다는 것입니다. 반복 코드에서는 특정 비트를 수정하는 데 필요한 모든 정보가 다른 몇 개의 비트에만 저장되므로 표적 공격에 취약해집니다.

다행히도 많은 오류 수정 코드가 더 나은 성능을 발휘합니다. 유명한 예 중 하나는 리드 솔로몬 코드, 메시지를 다항식(예: 다음과 같은 수학적 표현)으로 변환하여 작동합니다. x² + 3x + 서로 다른 용어가 함께 추가된 2개, 각각 변수가 있음(예: x) 다른 힘으로 상승했습니다. Reed-Solomon 코드를 사용하여 메시지를 인코딩하려면 메시지의 각 문자에 대해 하나의 용어로 다항식을 만든 다음 다항식을 그래프에 곡선으로 그리고 곡선 위에 있는 점의 좌표를 저장합니다(적어도 하나 더 사용). 문자 수보다 포인트). 오류로 인해 이러한 점 중 몇 개가 곡선 밖으로 밀려날 수 있지만 오류가 너무 많지 않으면 하나의 다항식 곡선만 대부분의 점을 통과합니다. 그 곡선은 거의 확실하게 실제 메시지와 일치합니다.

리드 솔로몬 코드는 매우 효율적입니다. 오류를 수정하려면 몇 개의 추가 포인트만 저장하면 되므로 인코딩된 메시지는 원본보다 약간 더 깁니다. 또한 어디에서나 오류를 수정하는 데 사용되는 정보가 전체 인코딩된 메시지에 분산되어 있기 때문에 반복 코드에 재앙을 초래할 수 있는 일종의 표적 중단에 덜 취약합니다.

전 세계적으로, 지역적으로 행동 생각

리드-솔로몬 코드의 강점은 상호 연결성에서 비롯됩니다. 그러나 이러한 상호 연결성 때문에 전체 내용을 읽지 않고는 인코딩된 메시지의 단일 오류를 수정할 방법이 없습니다. 의사소통 측면에서는 문제가 되지 않을 수도 있습니다. 메시지를 보내는 경우 수신자가 메시지를 모두 읽기를 원할 수도 있습니다. 그러나 이는 오류 수정의 또 다른 주요 응용 프로그램인 데이터 저장에 문제가 될 수 있습니다.

사용자의 이메일을 클라우드, 즉 광범위한 서버에 저장하는 회사를 생각해 보세요. 전체 이메일 모음을 하나의 긴 메시지로 생각할 수 있습니다. 이제 하나의 서버가 충돌한다고 가정해 보겠습니다. Reed-Solomon 코드를 사용하면 손실된 서버에서 이메일을 복구하기 위해 인코딩된 모든 데이터와 관련된 대규모 계산을 수행해야 합니다. “모든 것을 살펴봐야 할 것입니다.”라고 말했습니다. 지브 드비르, 프린스턴 대학의 컴퓨터 과학자. "이메일은 수십억 통에 달할 수 있습니다. 정말 오랜 시간이 걸릴 수 있습니다."

연구자들은 인코딩된 메시지의 일부만 사용하는 코드를 설명하기 위해 "로컬"이라는 용어를 사용합니다. 오류를 발견하다 또는 수정하십시오. 단순 반복 코드에는 이러한 로컬 특성이 있지만 바로 이것이 변조에 매우 취약한 이유입니다. 대조적으로, 로컬로 수정 가능한 코드는 두 가지 장점을 모두 활용합니다. 즉, Reed-Solomon 코드를 매우 탄력적으로 만드는 상호 연결성을 잃지 않고 단 몇 번의 쿼리만으로 오류를 수정할 수 있습니다.

Kothari는 "이것은 정말 엄격한 개념입니다."라고 말했습니다.

로컬에서 수정 가능한 코드의 가장 유명한 예는 1954년 수학자들이 발명한 유서 깊은 오류 수정 코드 버전입니다. 데이비드 뮬러 과 어빙 리드 (Reed-Solomon 코드 개발에도 도움을 준 사람) Reed-Solomon 코드와 마찬가지로 Reed-Muller 코드는 긴 메시지를 인코딩하기 위해 많은 용어를 추가한 다항식을 사용합니다.

리드 솔로몬 코드에 사용되는 다항식은 단일 변수를 포함합니다. x따라서 더 많은 항을 추가하는 유일한 방법은 더 높은 거듭제곱을 사용하는 것입니다. x. 그 결과 많은 점을 살펴보아야만 고정할 수 있는 흔들림이 많은 곡선이 생성됩니다. 대신 Reed-Muller 코드는 각 항에 함께 곱해진 여러 변수를 포함할 수 있는 다항식을 사용합니다. 더 많은 변수는 이들을 결합하는 더 많은 방법을 의미하며, 이는 개별 변수를 그렇게 높은 거듭제곱으로 올리지 않고도 다항식 항의 수를 늘릴 수 있는 방법을 제공합니다.

Reed-Muller 코드는 매우 유연합니다. 다항식에 나타나는 최고 검정력을 높이거나 변수 수를 늘리거나 두 방법을 모두 사용하여 더 긴 메시지를 인코딩할 수 있습니다. Reed-Muller 코드를 로컬에서 수정 가능하게 만들려면 각 변수의 최대 전력을 작은 상수 값으로 제한하고 변수 수만 늘려서 더 긴 메시지를 처리하면 됩니다.

특히 로컬에서 수정 가능한 2개 쿼리 코드의 경우 최대 전력은 XNUMX로 설정됩니다. 그런 다음 각 개별 변수에 관한 한 메시지를 인코딩하는 다항식은 간단한 포물선을 추적합니다. 포물선의 정확한 모양을 결정하려면 곡선의 세 점만 조사하면 됩니다. 더욱이, 많은 변수에는 이러한 포물선이 많이 있으며, 그 중 어떤 것이든 오류를 수정하는 데 사용할 수 있습니다. 이것이 Reed-Muller 코드의 탄력성을 높이는 이유입니다.

불행하게도 Reed-Muller 코드에는 심각한 단점이 있습니다. 즉, 메시지를 인코딩하는 데 필요한 비트 수가 변수 수에 따라 기하급수적으로 증가한다는 것입니다. 소수의 쿼리만으로 오류를 수정하는 고도로 지역적인 코드를 원한다면 긴 메시지에 많은 변수가 필요하며 Reed-Muller 코드는 실제로 빠르게 쓸모 없게 됩니다.

“이 경우 지수는 매우 나쁩니다.”라고 Dvir는 말했습니다. 하지만 불가피한 일인가요?

수정 가능합니까, 아니면 디코딩 가능합니까?

컴퓨터 과학자들은 보다 효율적인 로컬 수정 가능 코드를 찾으려고 노력했지만 실패하면서 그러한 코드가 전혀 불가능하다고 의심하기 시작했습니다. 2003년에는 두 명의 연구자가 증명 두 개의 쿼리만 사용하면 Reed-Muller 코드를 이길 수 있는 방법이 없습니다. 그러나 그것은 누구라도 얻을 수 있는 한입니다.

Kothari는 "일단 3단계로 가면 우리의 지식은 매우 개략적이 됩니다"라고 말했습니다.

다음 혁신은 문제를 더욱 복잡하게 만듭니다. 에 발표된 두 편의 논문에서 2008 과 2009, 컴퓨터 과학자인 Sergey Yekhanin과 Klim Efremenko는 Reed-Muller 코드보다 더 효율적인 3개의 쿼리 코드를 구성하는 방법을 보여 주었지만 이러한 코드는 로컬에서 수정이 불가능했습니다. 대신, 로컬 디코딩 가능성이라는 미묘하게 다른 속성을 가졌습니다.

차이점을 이해하기 위해 사용자의 데이터를 하나의 긴 메시지로 결합하고 오류 수정 코드를 사용하여 이를 보호하는 클라우드 저장소 공급자를 다시 상상해 보겠습니다. 로컬로 수정 가능한 코드와 로컬로 디코딩 가능한 코드 모두 몇 번의 쿼리만으로 원본 메시지의 모든 오류를 수정할 수 있습니다.

그러나 모든 오류 수정 코드에는 원본 메시지에 없는 추가 비트도 필요합니다. 이것이 바로 메시지를 인코딩하면 시간이 더 길어지는 이유입니다. 두 가지 유형의 코드는 이러한 추가 비트를 처리하는 방법이 다릅니다. 로컬로 디코딩 가능한 코드는 이러한 비트의 오류를 수정하는 데 필요한 쿼리 수에 대해 약속하지 않습니다. 그러나 부분적으로 수정 가능한 코드에서는 추가 비트의 오류가 원본 메시지의 모든 비트 오류와 동일한 방식으로 수정될 수 있습니다.

“사용자의 원본 데이터든 중복성 및 확인 정보든 저장하는 모든 것은 로컬에서 수정될 수 있습니다.”라고 말했습니다. 마두 수단, 하버드 대학의 컴퓨터 과학자.

원칙적으로는 다르지만 로컬 수정 가능성과 로컬 디코딩 가능성은 2008년 이전에는 실제로 항상 상호 교환 가능한 것처럼 보였습니다. 알려진 모든 로컬 디코딩 가능 코드도 로컬 수정 가능했습니다. 예카닌과 에프레멘코의 발견은 두 조건 사이에 근본적인 차이가 있을 가능성을 높였습니다. 아니면 Yekhanin과 Efremenko의 코드를 수정하여 로컬에서 수정 가능하도록 만드는 것이 가능했을 수도 있습니다. 이는 두 가지 조건을 다시 한 번 동등한 위치에 두게 되지만, 로컬에서 수정 가능한 XNUMX개의 쿼리 코드가 얼마나 효율적인지에 대해 연구자들이 착각했다는 의미이기도 합니다. 어느 쪽이든 기존의 통념은 바뀌어야 합니다.

논리 차용

Kothari와 Manohar는 마침내 컴퓨터 과학의 다른 영역인 소위 제약 조건 만족 문제에 대한 연구의 기술을 적용하여 이러한 긴장을 해결했습니다. 친구들과 함께 저녁 식사 계획을 조정하는 것은 일종의 제약 만족 문제입니다. 모든 사람에게는 받아들일 선택권과 거부할 선택권이 있습니다. 당신의 임무는 모두를 만족시키는 계획을 찾거나, 그러한 계획이 없다면 가능한 한 빨리 그것을 알아내는 것입니다.

두 가지 가능한 결과 사이에는 본질적인 비대칭성이 있습니다. 수용 가능한 솔루션을 찾는 것은 쉽지 않을 수 있지만, 일단 일단 확보하고 나면 그것이 효과가 있을 것이라고 다른 사람에게 설득하는 것은 쉽습니다. 하지만 문제가 실제로는 '불만족'하다는 것을 알더라도 증거를 제시하는 예가 없을 수도 있습니다.

2021년에 Kothari와 Manohar는 캘리포니아 대학교 버클리 캠퍼스의 Venkatesan Guruswami와 함께 주요 혁신 까다로운 불만족 사례를 식별하기 위한 새로운 이론적 기술을 사용하여 제약 조건 만족 문제를 연구합니다. 그들은 새로운 방법이 다른 문제를 해결하는 데에도 강력한 도구가 될 것이라고 의심했고 Guruswami의 대학원생 Omar Alrabiah는 로컬에서 디코딩할 수 있는 3개의 쿼리 코드를 살펴볼 것을 제안했습니다.

“이것은 말하자면 우리 손에 있는 망치가 달린 못이었습니다.”라고 Kothari는 말했습니다.

Yekhanin과 Efremenko의 놀라운 결과는 3개의 쿼리를 로컬로 디코딩할 수 있는 코드가 Reed-Muller 코드보다 더 효율적일 수 있음을 보여주었습니다. 그러나 그들의 코드는 가능한 최고의 코드였습니까? 아니면 로컬에서 3개의 쿼리로 디코딩 가능한 코드가 훨씬 더 효율적일 수 있었습니까? Kothari, Manohar, Guruswami 및 Alrabiah는 그들의 새로운 기술이 그러한 코드의 효율성에 대한 한계를 증명할 수 있다고 생각했습니다. 그들의 계획은 주어진 크기의 로컬로 디코딩 가능한 모든 가능한 3개 쿼리 코드의 구조를 포괄하는 논리 공식을 구축하고 그것이 만족스럽지 않다는 것을 증명함으로써 그러한 코드가 존재할 수 없음을 보여주는 것이었습니다.

네 명의 연구원은 2022년에 그 방향으로 첫 걸음을 내디뎠습니다. 새로운 한계 3개의 쿼리를 로컬로 디코딩할 수 있는 코드의 최대 효율성에 대해 알아봅니다. 결과는 연구자들이 다른 기술로 달성할 수 있었던 것보다 훨씬 뛰어났지만 Yekhanin과 Efremenko의 것보다 더 효율적인 모든 코드를 배제하지는 않았습니다.

Kothari와 Manohar는 그들이 더 나아갈 수 있다고 의심했습니다. 그러나 Manohar가 이 기술이 로컬에서 디코딩 가능한 코드보다 로컬에서 수정 가능한 코드에 더 잘 작동할 수 있음을 나타내는 간단한 계산을 기록할 때까지 진행이 중단되었습니다.

몇 달 후, 그들이 너무 낙관적이었다는 것을 두려워하게 만드는 더 많은 잘못된 시작 이후, 이 기술은 마침내 약속을 이행했습니다. Kothari와 Manohar는 연구원들이 예상한 대로 로컬에서 수정 가능한 3개 쿼리 코드가 Reed-Muller 코드보다 눈에 띄게 더 잘 작동하는 것은 불가능하다는 것을 증명했습니다. 이러한 지수 확장은 근본적인 한계입니다. 그들의 결과는 또한 로컬 수정 가능성과 로컬 디코딩 가능성이 표면적으로 유사하더라도 실제로는 근본적인 수준에서 다르다는 극적인 시연이었습니다. 후자는 전자보다 확실히 구현하기가 더 쉽습니다.

Kothari와 Manohar는 현재 알려진 바가 거의 없기 때문에 세 가지 이상의 쿼리를 만들 수 있는 코드를 연구하기 위해 기술을 확장하기를 희망하고 있습니다. 그리고 오류 수정 이론의 발전은 겉보기에 관련이 없어 보이는 다른 분야에도 영향을 미치는 경우가 많습니다. 특히, 부분적으로 수정 가능한 코드는 문제의 모든 곳에서 놀라운 모습을 보입니다. 개인 데이터베이스 검색 암호화에서 증명에 이르기까지 조합론의 정리. Kothari와 Manohar의 기술이 이러한 다양한 분야에 어떤 영향을 미칠지 말하기에는 너무 이르지만 연구자들은 낙관적입니다.

Dvir는 “여기 정말 아름다운 새로운 아이디어가 있습니다.”라고 말했습니다. “가능성이 많다고 생각해요.”