1. 과제의 중요성

전통적으로 수학의 과학, 공학, 산업에의 응용은 주로 해석학에 국한되어 발전하여 왔으며, 따라서 응용수학이라고 하면 편미분방정식, 수치해석 등이 그 주류를 이루고 있는 것으로 인식되어 왔다. 그러나 최근에는 수학의 응용이 해석학과 함께 대수학, 기하학 등 수학의 전 분야로 확산되고 있으며, 특히 대수학의 응용은 컴퓨터 발달에 힘입어 크게 각광을 받고 있다.

통신기술의 핵심인 코딩이론, 전자상거래에서 없어서는 안되는 보안기술인 암호이론 등에 대수학, 정수론, 조합수학 등이 핵심적인 역할을 담당하고 있음이 밝혀지면서부터 이러한 응용은 순수수학 중에서도 순수수학이라고 여겨지던 대수학에 대한 새로운 인식을 요구하고 있다. 소위 응용대수학이라는 이름으로 분류되기 시작한 이 분야는 전산수학, 코딩이론 및 암호이론 등에 학문적인 기초를 제공하던 단계를 넘어서서 첨단의 코딩기술 및 암호기술을 직접 개발하는 단계에 접어들고 있으며, 역으로 대수학이라는 학문의 폭을 넓혀주는 계기가 되고 있다. 외국에서는 이미 몇몇 수학자들에 의하여 이러한 코딩기술 및 암호기술을 특허로 보유하고 있는 회사들이 설립되고 있으며 상당한 로열티를 벌어들이고 있다.

그러나 이러한 현상은 이제 시작단계에 불과하며, 전자통신 및 전자상거래 시장의 규모가 앞으로 폭발적으로 성장할 것으로 예견되고 있는 이때, 가능한 한 빨리 코딩기술 및 암호기술을 선점하여 급증할 이 분야의 인력수요 및 기술수요에 대비하는 것이 바람직하다. 뿐만 아니라 코딩기술 및 암호기술의 개발과 관련된 대수학, 정수론, 조합수학 등의 분야가 비교적 새로운 분야이므로 노력하기에 따라서 가까운 장래에 선진 외국과의 격차를 좁히고 더 나아가 오히려 우위를 점할 수 있는 가능성도 매우 높은 것으로 판단된다.

이러한 맥락에서 BK-21 사업과 관련하여 시행될 구조조정과 교과과정의 개편에서, 학사과정부터 대학원과정까지 응용대수학 관련 교과목을 새로이 편성하여 교육하고, 자연스럽게 연구단계로 연계될 수 있도록 하여 코딩기술 및 암호기술의 개발에 필요한 고급인력을 양성하는 것이 절실히 요구되고 있다고 하겠다.

응용대수 및 암호이론 사업팀은 이러한 배경 하에, 정수론, 군론, 조합이론의 연구와 더불어 이러한 연구결과를 활용하여 코딩이론 및 암호이론을 발전시키고 유용한 첨단기술을 개발하고자 한다. 또한 전자통신, 전사상거래업계 등에서 필요로 하는 고급기술을 연구, 개발할 수 있는 고급인력을 배출하고자 한다. 이러한 인력은 산업계뿐만 아니라 국방분야에서도 절실히 요구되는 인력이 될 것으로 기대된다. 암호기술이 국방분야에서도 필수 불가결한 역할을 담당하고 있음을 새삼 강조할 필요는 없을 것이다.

2. 과제 관련 국내외 동향

(1) 산업수요측면

Shannon 이 1948년에 "커뮤니케이션의 수학적 이론"을 발표한 이후 코딩이론은 통신기술의 핵심이론으로 자리를 잡았고 채널코딩 문제, 샘플링 문제 등이 많은 수학자들에 의하여 연구되어 왔다. 특히, 오류자동정정 부호이론은 코딩이론 및 기술에서 가장 집중적으로 연구되고 있는 이론이다. 통신과정에서 반드시 발생할 수밖에 없는 오류를 자동적으로 정정해 주는 부호시스템은 Hamming 에 의하여 체계적으로 연구되기 시작한 이래 다양한 부호시스템이 개발되었다. 그러나 이상적인 오류자동정정 부호시스템의 개발은 아직 요원한 상태이며 본 사업팀의 인적구성을 감안할 때 선진외국과의 경쟁에서도 충분한 승산이 있다고 자부하고 있다. 새롭고 효율적인 오류자동정정 부호시스템을 개발할 경우, 기본의 부호시스템보다 우수한 것으로 판정되면 엄청난 로열티를 벌어들일 수 있다. 오류자동정정 부호시스템은 비단 전자통신에서만 쓰이는 것이 아니라, 콤팩트디스크의 제작, 스마트카드의 제작 등 그 용도가 다양하고 광범위하기 때문이다.

현재 개발되어 있는 이러한 부호시스템은 Hamming-코드, Golay-코드, Bose, Chaudhuri, Hocquenghem 의 BCH-코드, Reed 와 Solomon 의 RS-코드 및 Reed 와 Muller의 RM-코드, 그리고 Goppa-코드 및 기하학적 Goppa-코드 등이며 이러한 코드들의 실용성을 높이기 위한 연구가 치열한 경쟁 속에 진행되고 있다. 특기할 사항은 이러한 코드가 대부분 수학자들에 의하여 개발되고 있다는 점이다.

한편으로 인터넷을 이용한 전자상거래시장의 규모는 전세계적으로 10-20년내에 수조달러에 달할 것으로 예측되고 있으며, 궁극적으로 거의 모든 상거래를 대체할 미래의 상거래 패턴으로 간주되고 있다. 이에 따라 종래에는 군사용, 첩보용 또는 기업용 기밀의 송수신이나 은행간 또는 은행-기업간 금전거래 등에서나 사용되던 암호기술의 수요가 폭발적으로 증가할 것으로 보인다. 암호론은 1976년 Diffie와 Hellman이 공개키 암호시스템이라는 혁명적인 시스템을 제안한 것을 계기로 새로운 발전을 하게 된다. 특히 Rivest, Shamir, Adleman 이 RSA 공개키 암호시스템을 개발한 이후 암호이론은 수학의 영역으로 들어오게 되었으며 수 천년 동안 수학에서 다루어온 수많은 일방향함수들을 이용한 다양한 공개키 암호시스템이 개발, 제안되고 또 그러한 암호시스템들을 여러 가지 수학이론들을 동원하여 공격, 해독하는 방법들이 연구되고 있다.

현재까지는 이러한 암호시스템이 실용화되어 회사가 설립된 대표적인 경우는 위에서 언급한 RSA 와 타원곡선을 이용한 Vanstone, Menezes, Koblitz 의 Certicom, 그리고 다항식을 이용한 Hofstein, Silvermann 의 NTRU 와 수체를 이용한 Buchmann 의 NFC 등 얼마 되지 않으며, 아직은 시작단계라고 볼 수 있다. 이러한 암호시스템을 개발한 사람들 역시 대부분 수학자들이라는 사실은 암호시스템의 내용을 알고나면 당연한 일이다.

(2) 연구수행측면

코딩이론의 핵심은 정수론과 군론, 그리고 조합이론이다. 또한 최근에는 대수기하이론을 이용한 코딩이론도 개발되고 있다. Hamming-코드, Golay-코드, BCH-코드, RS-코드 및 RM-코드, Goppa-코드 및 기하학적 Goppa-코드 등은 모두가 이차형식이론, 보형형식이론, 유한군론, 그래프이론, 이산대수론 등에 대한 폭넓고 깊이 있는 기초연구를 바탕으로 개발되었음을 쉽게 알 수 있다. 대수학에서 다루는 다양하고 풍부한 대수적 구조들에 대한 완전한 이해와 깊이 있는 연구가 선행되지 않으면 새로운 코딩기술의 개발은 불가능하다. 또한 이러한 연구결과는 바로 코딩기술의 개발로 연결되고 있다. 코딩기술에서는 특히 격자이론에 대한 연구가 필수적이며, 최근에는 이 격자이론에 대한 연구가 집중적으로 이루어지고 있다.

전자상거래에서는 송신하고자 하는 메시지를 암호화하여 송신하고, 그 암호문을 수신하여 원래의 메시지를 복원하되 제삼자는 그 내용을 알 수 없도록 하는 전통적인 암호시스템의 기능 이외에 송신자확인 및 서명, 원문변조방지, 키 공유 및 교환, 비밀분산 등 다양한 기능들이 요구된다. 선진외국에서는 대대적인 투자를 통하여 이러한 기능들을 완벽하게 갖춘 공개키 암호시스템의 개발에 박차를 가하고 있다.

현재 가장 많이 사용되고 있으며 미국에서 표준화된 RSA 공개키 암호시스템은 앞에서 언급한바와 같이 Rivest, Shamir, Adleman 에 의하여 개발되었다. Fermat 와 Euler 의 정리를 이용하면 자연수를 법으로 하는 정수의 멱승계산을 손쉽게 할 수 있다는 사실을 이용하여 수자화된 메시지를 이미 공개된 자연수를 법으로 적당히 멱승한 암호문을 보내고 이 암호문을 다시 멱승하여 원래의 메시지를 복원하는 이 암호시스템은 소수의 성질을 이용한 것으로, 소수의 판정이 비교적 쉬운데 반하여 소인수분해는 매우 어렵다는데 착안하고 있다. 발표된 이래 20여간 수많은 공격에도 견디고 있는 실용화된 암호시스템이다.

이처럼 멱승한 숫자를 토대로 멱승되기 전의 수를 찾는 이산로그의 계산이 어렵다는 사실을 이용한 또 다른 공개키 암호시스템으로는 El Gamal 의 공개키 암호시스템이 있다. 이는 곱을 연산으로 가지는 유한군에서 원소의 멱승은 쉽고 이산로그는 매우 어렵다는 사실에 근거한 암호시스템이다. 최근에는 유한체상의 타원곡선이 유한군을 이룬다는 성질을 이용한 공개키 암호시스템이 개발되어 실용화되고 있다.

그 외에도 격자의 기저를 이용한 공개키 암호시스템과 그래프를 이용한 공개키 암호시스템, 특수선형행렬군의 자유생성자를 이용한 공개키 암호시스템, 그래프이론을 이용한 공개키 암호시스템 등이 제안되고 있으며 이에 대한 안정성 검증 연구가 진행되고 있다.

이러한 공개키 암호시스템들은 각각 장단점을 가지고 있으며 무엇보다도 안전성에 대한 완전한 검증이 이루어지기 전에는 실용화 될 수 없기 때문에 이러한 암호시스템의 안정성 검증과 관련된 알고리즘의 복잡성, 효율성 등을 연구하는 계산수학의 중요성이 대두되고 있다.

많은 자료의 안전한 저장, 정보위조 및 변조의 방지 등과 관련된 해쉬함수, 컴튜팅 파워의 향상을 위한 컴퓨터 로직, 알고리즘 개발, 모델이론 등 대수학의 응용범위는 정보과학 전반으로 계속 확장되고 있다.

3. 세부내용

(1) 코딩이론 연구 및 코딩기술 개발

격자이론을 중심으로 다양한 코딩의 장단점을 보다 심층적으로 분석하고 개선의 가능성을 연구하고자 한다. Hamming-코드와 Leech-격자를 이용한 Golay-코드, BCH-코드, RS-코드 및 RM-코드, Goppa-코드, QR-코드, 완전코드, 순환코드 등 기존의 코딩시스템을 개선하기 위하여 격자이론, 이차형식이론, 보형형식이론, 유한군론, 그래프이론, 이산대수론 등의 관련분야에 대한 폭넓고 깊이 있는 기초연구를 수행할 예정이며, 다시 이를 바탕으로 새롭고 실용적인 코딩기술을 개발하고자 한다.

(1)-1. 오류자동정정 부호시스템

우리 사업 팀은 오류자동정정 부호시스템을 집중적으로 연구할 예정이다. 좋은 오류자동정정 부호시스템의 조건은 코드워드의 길이에 비하여 상대적으로 많은 오류를 정정할 수 있어야 하고 실용성이 높아야한다. 오류정정 기능은 좋지만 시간과 경비 면에서 실용성이 떨어지는 부호시스템은 별로 쓸모가 없으며, 반대의 경우도 마찬가지이다. 오류정정 범위는 소위 부호시스템의 Hamming 거리(서로 다른 코드워드간의 거리의 최소치)의 1/2 정도임이 알려져 있으며, 이와 관련하여 각 코드워드의 Hamming 무게(코드워드의 영 아닌 좌표의 개수)와 주어진 Hamming 무게를 가지는 코드워드의 개수와 이를 계산해 주는 Hamming 무게다항식, 특히 최소 무게를 가지는 코드워드의 개수 등이 집중적인 연구의 대상이다.

이러한 것들은 격자이론에서 나타나는 격자점(혹은 벡터)간의 최소거리, 격자의 원점에서 주어진 거리만큼 떨어져 있는 벡터의 개수와 이를 계산해 주는 소위 theta-급수, 최소벡터의 개수 등에 대한 연구와 자연스럽게 연결된다. 뿐만 아니라, 이러한 연구는 다시 Kepler 의 packing 문제의 연구와 밀접하게 연결되는 등, 오류자동정정 부호시스템은 수학사적으로도 매우 뿌리 깊고 오래된 신비스러운 연구주제와 직결되어 있다. 예를 들어, 24차원 격자 중에서 가장 밀도 높은 packing 을 가능하게 하는 격자가 바로 Leech-격자이며(24차원 짝유니모듈라-격자 24개 중 최소벡터의 길이가 4로서 가장 큰 격자), 이 Leech-격자로부터 Golay-코드를 제작하게 되는데, Golay-코드는 코드워드에서 3개 이내의 오류가 발생할 경우 이를 자동으로 정정해 주는 놀라운 오류정정 기능을 가지고 있다.

(1)-2. 극격자코드, 순환코드, 비선형코드

짝유니모듈라-격자의 차원은 8의 배수로 나타나게 되는데, Leech-격자처럼 최소벡터의 길이가 가장 큰 것을 극격자라고 부르며, 이러한 극격자로부터 오류정정 기능이 뛰어난 부호시스템을 제작할 수 있음이 알려져 있다. 그러나 이러한 극격자를 찾는 일은 매우 어려운 문제로서 우리는 이에 대한 연구에 많은 노력을 기울이고자 한다.

유한체의 구조를 이용한 BCH-코드와 이를 차원이 큰 경우에 보완한 Justesen-코드, 그리고 RS-코드 및 RM-코드 등의 순환코드에 대한 연구와 비선형코드의 개발연구도 수행하고자 한다.

(2) 암호이론 연구 및 암호기술 개발

정수론, 군론, 조합이론 등을 기반으로 공개키 암호시스템과 해쉬함수, 무지식 대화 증명, 그리고 비밀 분산시스템 등을 연구하고자 한다. 여기서, 암호시스템이란 평문을 암호문으로 대응시키는 함수라고 볼 수 있다. 대수적인 알고리즘을 사용하여 암호를 만든 역사는 로마 시대까지 거슬러 갈 수 있다. 그러나 20세기가 될 때까지는 대부분 기초적인 대수와 정수의 성질만이 암호에 이용되었다. 1970년대까지의 암호시스템이란 비밀키에 의해 암호문을 작성하는 비밀키 암호시스템이었다. 이 경우, 암호를 주고받으려는 양측은 먼저 비밀 키들을 안전하게 주고받아야 했다.

1976년 이후, 암호론은 Diffie와 Hellman이 제안한 공개키 암호시스템이라는 혁명적인 시스템을 계기로 새로운 발전을 하게 된다. 공개키 암호시스템이란 암호를 받으려는 사람이 암호 메시지를 보내려는 사람들에게 암호를 만드는데 사용하는 키들을 공개적으로 알려주는 시스템이다. 이 때, 암호를 보내려는 사람은 이미 공개되어 있는 키를 사용하여 암호를 만들어 보내고, 암호를 받은 사람은 자기만이 갖고 있는 비밀키를 사용하여 암호를 해독하는 것이다.

공개키 암호시스템의 기본 개념은 암호를 만드는 일방향 함수이다. 간략히 말하면, 집합 X 에서 Y 로 가는 일대일 함수 f 가 일방향 함수라는 것은 X 의 원소 x 에 대해 함수값 f(x) 를 계산하는 것은 쉽지만 반대로 f(x) 의 값을 만드는 x 를 거꾸로 계산하는 것은 어렵다는 것이다. 암호에 쓰일 수 있는 일방향 함수는 특별한 함수로, 비밀키가 알려지지 않은 경우에는 안전한 일방향 함수이지만 비밀키를 사용하면 거꾸로 계산을 쉽게 할 수 있는 함수들이다. 이러한 함수를 함정함수라고 하는 이유가 여기에 있다.

공개키 암호시스템의 발견은 암호학에 정수론, 군론, 조합이론 등의 수학이 핵심적인 역할을 담당하게 되는 결정적인 계기가 되었다. 가장 중요한 이유는 이러한 분야들이 일방향 함수들로 가득한 보물 창고이기 때문이다. 맨 처음 발견된 공개키 암호시스템인 RSA 시스템은 정수론을 사용한다. 비슷한 시기에 발견된 Knapsack 문제에 기반을 둔 공개키 암호시스템은 불안전함이 밝혀졌다. 그러나 NP-complete 문제들을 이용하여 다양한 일방향 함수를 만들 수 있기 때문에 RSA와 함께 Knapsack 문제와 같은 NP-complete 문제를 이용하여 공개키 암호시스템을 구성하는 일방향 함수를 만들려는 조합론적인 시도도 계속되고 있다.

NP 라는 것은 다항식 시간 내에, 비결정적 알고리즘에 의해 풀 수 있는 문제들의 집합이고, P 라는 것은 다항식 시간 내에 결정적 알고리즘에 의해 풀 수 있는 문제들의 집합이다. 이때 P 에 속하는 모든 문제가 NP 에 속하는 것은 당연하지만, NP 에 속하는 문제들이 P 에 속하는지에 대하여는 아직 밝혀지지 않고 있다.

그런데 P≠NP 라는 주장에 설득력 있는 증거가 되는 부가적인 특성을 지닌 문제들이 발견되었다. 즉, 어떤 문제가 결정적 기계에서 다항식 시간 내에 풀릴 수 있다면 NP 에 속하는 모든 문제가 그렇게 풀릴 수 있다(즉, P = NP)라는 것을 함의하게 되는 문제들이 발견된 것이다. 그러한 문제들을 NP-complete 라고 하는데, 최초로 발견된 NP-complete 문제는 1971년에 Cook 이 제기한 '만족성 문제'라고 불리는 것으로 그는 만족성 문제가 NP-complete 라는 직접적인 증명을 제시하였다. 즉, 만족성 문제에 대한 다항식 시간 알고리즘이 존재한다면 NP 에 속하는 모든 문제가 다항식 시간 안에 풀릴 수 있다는 것을 밝힌 것이다. 그 후, 다양한 문제들이 NP-complete 라는 것이 밝혀졌다. 그래프이론의 '떠돌이 장사꾼 문제', '해밀턴 사이클 문제', 그리고 '최장거리 경로 문제'들이 모두 NP-complete 이다. 또한 무지식에 쓰일 수 있는 그래프 동형 문제도 NP-complete 이다.

(2)-1. 공개키 암호시스템

우리 사업 팀은 정수론과 군론 등을 이용한 기존의 다양한 공개키 암호시스템의 장단점을 분석하고 공격방법을 검토하고 개선의 가능성을 연구하고자 한다. 소수판정의 용이함과 소인수분해의 난해함(NP-complete 여부가 아직 밝혀지지 않고 있음)에 기반을 둔 RSA 공개키 암호시스템, 유한순환군에서 이산로그의 계산이 어렵다는 사실을 이용한 El Gamal 의 공개키 암호시스템, 유한체상의 타원곡선이 이루는 유한군의 연산구조의 난해함을 기반으로 한 ECC 공개키 암호시스템 등의 원리를 심층적으로 연구하고 다양한 공격을 시도함으로써 이러한 시스템을 더욱 안전하고 실용적인 것으로 개선해 보고자 한다.

그 외에도 최근 개발되어 제안되고 있는 격자의 직교성이 큰 기저(비교적 직교기저에 가까운 기저)의 LLL-알고리즘과 관련된 특수한 성질을 이용한 격자축조 공개키 암호시스템, 2차 특수선형행렬군의 자유생성자를 이용한 SL(2,Z) 공개키 암호시스템, 수체의 이데알동류군에서의 이산로그의 난해함에 기반을 둔 NF 공개키 암호시스템, 유한체상에서 정의된 다항식환의 factor 환의 곱셈구조와 norm 의 관계를 이용한 NTRU 공개키 암호시스템 등의 안전성을 집중적으로 연구함으로써 이러한 시스템의 약점을 보완한 새로운 공개키 암호시스템을 개발하고자 한다.

이러한 공개키 암호시스템은 각각 장단점이 있으며 무엇보다도 안정에 대한 완전한 검증이 이루어지기 전에는 실용화 될 수 없기 때문에 이러한 암호시스템의 안정성 검증과 관련된 알고리즘의 복잡성, 효율성 등에 대한 연구를 병행할 것이다.

한편, 앞에서 밝힌 바와 같이 Knapsack 문제와 같은 NP-complete 문제를 이용한 공개키 암호시스템은 안전하지 않음이 Shamir 등에 의해 밝혀졌고, 이와 관련하여 Brassard 정리는 어떤 가정 아래에서 NP-complete 문제를 이용한 공개키 암호시스템이 안전하지 않은가를 규명하였다.

그런데 1990년대 초반에 Koblitz 와 Fellows 는 Brassard 정리의 가정을 만족시키지 않기 때문에 Brassard 정리에 의해 안전하지 않다고 말할 수 없는, NP 문제에 기반을 둔 공개키 암호시스템이 있음을 밝혔다. 이로 인하여 일반적인 NP-complete 문제를 기반으로 하는 공개키 암호시스템의 가능성이 다시 제시된 셈이며, 다양한 조합이론의 NP-문제를 기반으로 한 공개키 암호시스템이 활발히 연구되고 있다.

이러한 배경아래, 우리 사업 팀에서는 NP-complete 인 그래프 문제를 연구하고 그 결과를 공개키 암호시스템의 개발에 적용하고자 한다. 모든 꼭지점이 3개의 다른 꼭지점과 인접한 그래프를 cubic 그래프라고 하는데, 주어진 cubic 그래프에서 소위 PDS 를 구하는 문제는 NP-complete 라는 것이 알려져 있다. 일반적으로 그래프의 모든 꼭지점이 꼭 d(≥3)개의 꼭지점과 인접한 경우, 그 그래프의 PDS 를 구하는 것은 NP-complete 라는 것을 1991년 Kratochvil 이 증명하였다. 여기서 PDS 의 개념은 코딩이론에서의 완전코드의 개념과 유사하다.

Koblitz와 Fellows가 제안한 polly cracker 암호시스템을 바탕으로 PDS 와 같은 조합이론의 NP-complete 문제를 기반으로 암호시스템을 만들 수 있다. 예를 들어, cubic 그래프와 그것의 K4-커버링을 이용하여 PMDF 를 찾기 어려운 그래프를 만들 수 있으며, 이를 이용하여 polly cracker 암호시스템을 제안할 수 있다. 이와 같은 PDMF 문제와 관련된 polly cracker 암호시스템에서 가장 중요한 부분은 PMDF 를 찾기 힘든 그래프를 만드는 과정이다. 물론 실용성을 높이고 안전성을 강화하는 방법 등도 계속 연구되어야 할 과제들이다.

대부분의 정수론에 입각한 암호시스템은 결정론적인 시스템이다. 즉 보내려는 평문을 암호로 만들 때는 대응되는 암호문이 항상 일의적으로 결정된다. 그러기에 결정론적 암호시스템은 두 가지의 결점을 갖게 된다. 즉, '예' 또는 '아니오'라는 간단한 메시지에 대한 암호문은 상대방이 쉽게 해독할 수가 있다. 또한 일의적으로 암호화되기 때문에 그 시스템이 안전하다는 것을 주장하는데 어려움이 있다. 이러한 이유에서 1980년대부터 확률적인 암호시스템이 등장하게 되었다. 확률적인 암호시스템에서는 보내려는 메시지에 대응하는 암호문이 일의적이 아니다. 앞서 열거한 우리의 연구주제 중 하나인 NP-complete 문제와 polly cracker에 기반을 둔 공개키 암호시스템이 바로 이러한 확률적 암호시스템이다.

(2)-2. 암호시스템의 옵션 기능

앞으로의 암호시스템은 다양한 기능을 연구하고 개발하여 다양한 수요자의 욕구를 충족시킬 수 있도록 하는 것이 중요하다. 암호이론 및 기술의 개발을 위해 이미 많이 연구되고 있으며 우리 사업팀에서도 연구를 시도하고자 하는 중요한 기능들은 다음과 같다.

- 인증 기능
보내어진 메시지를 누가 보냈는지에 대한 사용자 인증 기능과 보내어진 메시지가 변조되지 않았다는 메시지 인증 기능 등 두 종류가 있다. 해쉬함수, 디지털 서명, 패스워드와 확인시스템(데이타나 시설에 접근할 수 있게 하거나 사용자를 확인할 수 있는 시스템), 그리고 증인시스템(디지탈 계약에서와 같이 어떤 일에 동의하고도 나중에 안했다는 말을 못하도록 하는 시스템) 등이 사용된다.

- 무지식 대화 증명
예를 들어, 내가 어떤 문제에 대한 답을 알고 있을 때, 상대방에게 답에 대한 어떤 정보도 흘리지 않고 내가 답을 알고 있음을 확신시킬 수 있는 기능이다.

- 비밀 분산스킴
예를 들어, 미사일을 발사하는 패스워드 등을 한 사람이 갖고 있으면 위험할 수 있다. 이 경우 미사일 패스워드에 관한 정보를 조각 내어 관계자들에게 나누어주되, 나누어 받은 사람 중 k 사람이 모이면 패스워드를 복구할 수 있지만 k 미만의 사람이 모여서는 알아낼 수 없도록 할 수 있게 하는 기능이다.

이러한 기능들은 여러 종류의 프로토콜을 사용하여 얻을 수 있다. 여기서 프로토콜이란 간단히 말하면 사용자가 정보를 보내는 순서라고 할 수 있다. 위에서 열거한 것처럼 쌍방이 통신망을 통해 정보 교환 시에 생길 수 있는 메시지 도청과 메시지의 수정, 송수신자의 위장, 그리고 정보 교환시 쌍방의 신분을 확인하는 문제와 쌍방이 주어진 정보에 동시에 서명하는 문제 등이 암호론의 중요한 문제들이다. 일반적으로 신분의 확인 및 인증은 안전한 공개키 암호시스템을 통해 해결하고 있다. 그러나 이러한 암호방식은 정보의 비밀성을 키에 의존하기 때문에 먼저 개인 식별 및 안전한 키분배방식이 전제되어야 한다. 또한 동시성에 대한 문제는 인증-서명과는 또 다른 암호화 프로토콜을 요구하고 있다.

인증-서명에 필요한 해쉬함수에 관한 연구는 RM-코드, 비선형코드 등의 코딩이론적 연구와 임의치환들에 대한 암호학적 연구가 결합된 수학적 문제이다. 따라서 이러한 연구는 여러 분야가 모여 협동연구를 하는 것이 바람직 하다. 또한 해쉬함수는 몇 개의 Bool-함수가 모인 것으로서 Bool-함수에 대한 암호학적 연구 및 수학적 연구가 해쉬함수의 연구에 필요하다. Bool-함수는 순수수학의 입장에서 RM-코드와 관계되어 연구가 활발한데, Bool-함수는 유한체 공간의 부분공간으로 볼 수 있기 때문에 유한기하와도 관계가 있으며, 또한 Bool-함수의 진리표는 2진-코딩과 연결된다. 한편 코드의 비선형성과 bent 함수 등의 성질은 코딩이론의 covering 반경 및 coset 과 밀접한 관계가 있다. 이러한 Bool-함수에 대한 암호학적 연구와 수학적 연구는 임의치환과 연계되어 바람직한 해쉬함수를 만드는데 응용될 수 있다. 그러나 해쉬함수를 통해 제안된 많은 인증-서명 시스템은 해쉬함수의 여러 약점으로 인해 아직도 많은 문제점을 갖고 있다. 우리 사업 팀은 이러한 문제점을 개선하여 실용적인 해쉬함수의 개발하기 위한 연구를 수행하고자 한다. 뿐만 아니라 최근 Zemor, Ajtai 등에 의하여 제안되고 있는 군의 구조를 이용한 해쉬함수, 격자이론을 이용한 해쉬함수 등에 대하여도 연구할 예정이다.

무지식 증명이란 어떤 정보를 알고 있을 때, 그 정보에 대한 어떤 사실도 상대방에게 공개하지 않으면서 상대방에게 자신이 그 정보를 알고 있다는 것을 납득시키는 방법을 말한다. 무지식 증명을 이용한 개인 식별 프로토콜의 예가 바로 Fiat 와 Shamir 의 개인 식별 프로토콜이다. 이들은 무지식 대화 증명과 ID 개념을 결합시킨 매우 안전한 개인 식별 프로토콜을 개발하였다. 이러한 무지식 대화증명이 가능한 공개키 암호시스템들도 있다. 예를 들면, 우리 사업 팀의 연구주제 중 하나인 그래프의 PMDF 와 polly cracker 를 이용한 공개키 암호시스템이 바로 그러한 암호시스템이다. 비밀 분산스킴은 키의 분배와 관련한 다중 프로토콜이다. 처음에는 비밀키를 분실할 경우에 대비하여 고안되었다. 그래서 비밀키의 backup copy 를 만들 필요가 생겼는데, backup copy 의 수가 많아질수록 안전성이 줄어드는 문제점이 발생하였다. 비밀 분산스킴은 간단히 말해서 어떤 비밀을 작은 조각으로 나누어 여러 사용자에게 나누어주되 필요시 사용자들이 작은 조각비밀들을 모아서 본래의 비밀을 재구성하는 프로토콜을 말한다. 비밀 분산스킴은 코딩이론, 정수론, 그래프이론, matroid 이론 등과 밀접하게 연결되어 있다. 우리 사업팀은 그래프이론과 디자인이론, 정수론 등의 연구를 통해 무지식 대화 증명과 비밀 분산시스템 등에 대한 프로토콜 연구를 수행할 예정이다.

우리 사업팀은 그 외에도 공개키 암호체계에 필요한 안전한 메시지 교환 기능, 각자의 비밀키를 비밀로 유지하면서 두 사람 이상이 공동키를 안전하게 만들어 공유하거나 교환 사용할 수 있도록 해 주는 키교환 기능, 디지털 상에서 게임을 할 때 순서를 정할 수 있도록 해 주는 동전 던지기 기능 등에 대한 연구를 병행하고자 한다.

(3) 정수론, 군론 및 표현론, 조합이론의 기초연구

위에서 밝힌 바와 같이 우리 사업팀은 코딩이론 및 기술과 암호이론 및 기술 등 크게 두 가지의 연구주제를 계획하고 있다. 그러나 응용대수학의 범위는 코딩과 암호를 넘어서서 정보과학의 근간을 이룬다. 이러한 내용은 결국은 관련된 정수론, 군론, 조합이론 등의 기초연구가 성공의 관건이다. 응용대수학의 특징은 이러한 기초연구의 결과가 바로 실용적인 기술로 개발 될 수 있다는 점이다.

우리 사업팀의 성패여부는 따라서 다음과 같은 기초이론에 대한 연구에 있다고 해도 과언이 아니다. 즉, 소수이론, 이차형식이론, 보형형식이론, 대수적수론, 격자이론, 유한군론, 군표현론, 그래프이론, 이산대수이론 등에 대한 연구를 병행할 예정이다.

(4) 산학연 협동 연구 및 교육

우리 사업팀은 응용대수학 과목을 기존의 대수학 및 정수론 과목과 함께 학사과정과 대학원과정에서 제공하여 대학원 2학년 수준이면 응용대수학 - 코딩이론, 암호이론, 조합수학 - 에 대한 연구를 시작할 수 있도록 유도할 예정이다. 그리고 정보보호센터, 전자통신연구소, 국방과학연구소, 혹은 은행이나 기업의 전자통신분야나 전자상거래분야 연구소, 컴퓨터나 전산관련 기업 등으로부터 위탁연구 또는 공동연구를 유치하여 대학원생 또는 관심 있는 학부생들을 연구에 참여시키고, 또 가능하다면 학생들을 파견하여 현장 연구 경험을 축적하여 이러한 분야의 고급인력으로 양성하고자 한다. 이렇게 함으로써 현장경험을 가진 고급연구인력이 양성될 것으로 믿고 있다.

우리 사업팀은 향후 도출될 연구성과를 SCI급 국제학술지에 게재함을 원칙으로 하며, 필요하다면 특허를 출원할 것이다. 또한 응용대수학 분야의 석사 및 박사를 다수 배출할 것이다.

정보과학 및 컴퓨터과학의 지식이 가장 중요한 가치로 군림하게될 21세기를 대비할 때, 암호이론과 코딩이론의 연구 및 개발은 국가적으로 더 이상 미룰 수 없는 과제이다. 우리의 연구결과 뿐만 아니라 우리가 배출할 암호이론 및 코딩이론의 고급인력은 다가올 정보화시대에 우리 나라에 꼭 필요한 자산이 될 것으로 자부한다.