The lattices have been studied by cryptographers for last decades, both in the field of cryptanalysis and as a source of hard problems on which to build encryption schemes. Interestingly, though, research about building secure and efficient signature schemes using the theory of lattices is extremely sparse in the cryptographic literature. An early scheme is due to Goldreich, Goldwasser and Halevi [7], who proposed that one could sign a message by demonstrating the ability to solve the approximate closest vector problem reasonably well for a point in space (hereafter referred to as the message digest point) generated from a hash of the message, and verify by checking that the 'close lattice point' returned was indeed a lattice point and that it was close enough to the message digest point to make forgeries impractical. However, this idea was not analyzed in detail by its authors.
Another public-key cryptosystem, NTRU encryption scheme, was proposed at almost the same time by Hoffstein, Pipher, and Silverman. After that they introduced a new type of authentication and digital signature scheme called NTRUSign at CT-RSA'03 [11]. NTRUSign features reasonably short, easily created keys, high speed, and low memory requirements like NTRU encryption scheme. Its security is also based on the hard problem of solving the approximate shortest(or closest) vectors in a certain lattice, called NTRU lattice. In this scheme, the signer uses secret knowledge to find a point in the NTRU lattice close to the given point. He/She then exploits this approximate solution to the closest vector problem as his signature.
There are two reasons for seeking this alternative hard problems (like GGH or NTRU) on which cryptography may be based. First, it is prudent to hedge against the risk of potential breakthroughs in factoring and computing discrete logarithms. A second and more significant reason is efficiency. NTRU-based algorithms, for example, run hundreds of times faster while providing the same security as competing algorithms. The drawback in using alternative hard problem is that they may not be well understood. Although lattice theory has been studied for over 100 years, the algorithmic nature of hard lattice problems such the shortest vector problem(SVP) was not really studied intensively until Lenstra, Lenstra and Lova´sz discovered a polynomial-time lattice basis reduction algorithm in 1982. Moreover, NTRU-based schemes use specific types of lattices based on an underlying polynomial ring, and these lattices generate specific types of lattice problems that may be easier to solve than general lattice problems. Since these specific lattice problems have been studied intensively only since NTRUEncrypt's introduction in 1996, we can expect plenty of new results.
In this thesis, first we propose an attack method of NTRUSign signature scheme. Our proposed attack will allow a passive adversary who observes only a valid message-signature pair to generate another signature. Thus NTRUSign signature scheme is not secure in the sense of malleability. From this property, we can derive a second signature of the message from any message-signature pair. In this case, one cannot distinguish the second one from the original one generated by who knows the secret key, which can be in practice regarded as a forgery. Although such a weakness does not allow the attacker to change the message string, this forgery shows that the signature scheme cannot be used for all kinds of applications. For example, if one would like to apply it to electronic cash, finding a second valid signature for a bill should be impossible. Also, an entity receiving the message-signature pairs (m,s) and (m,s´) such that s≠s´ at the same time, neither s nor s´ will be accepted as a valid signature for the message m by him. In this scenario if a legitimate signer wants to assert s as his/her own signature for the message m, then he/she should exhibit his/her private key.
Finally, we provide a simple technique to avoid this weakness in NTRUSign scheme. Although our modification does not degenerate the security of the original NTRUSign scheme, we are not sure whether or not the repaired version of NTRUSign is non-malleable. We believe, however, that it is computationally infeasible to find another shortest vector in repaired NTRUSign because all lattice-based signature schemes use a lattice vector sufficiently close to the vector derived from a message as its signature.
래티스 개념은 암호 분석 및 어려운 문제를 찾는 분야에 있어서 많은 암호학자들에 의하여 오랜 동안 연구 되어 왔다. 그럼에도 불구하고 래티스 이론에 기반한 안전하고 효율적인 전자 서명 기법들의 제안은 매우 드물었다. 초기의 Goldreich, Goldwasser, 그리고 Halevi에 의하여 제안된 기법에서 서명자는 주어진 메시지의 해쉬값 으로부터 얻어진 임의의 점에 대하여 대략적인 가장 가까운 벡터 찾는 문제를 풀 수 있음을 증명함으로서 서명하게 된다. 또한 검증자의 경우에는 서명 값으로 받은 벡터가 실제로 래티스 상에 있는 점이며 메시지 해쉬값과 충분히 가까움을 확인함으로서 서명 값을 증명하게 된다. 그러나 이러한 아이디어가 그 저자들에 의하여 상세하게 분석되지 않았었다.
같은 시기에 또 다른 공개키 암호시스템인 NTRU 암호 알고리즘이 Hoffstein, Pipher, 그리고 Silverman에 의하여 제안되었다. 그 후 그들은 CT-RSA'03 에서 NTRUSign이라 불리는 새로운 형태의 인증 및 전자 서명 기법을 소개하였다. NTRU 공개키 암호 알고리즘과 마찬가지로, NTRUSign 서명 기법은 짧고 쉽게 생성되는 키들, 매우 빠른 속도, 그리고 적은 메모리양을 요구하는 장점을 가지고 있다. 그것의 안전성 또한 NTRU 래티스라 불리는 임의의 래티스 상에서의 대략적 가장 짧은 벡터 찾는 문제에 기반하고 있다. 이 NTRUSign기법에서, 서명자는 임의의 점에 가까운 래티스 상의 점을 구하기 위하여 그의 비밀 정보를 사용한다. 이때, 가장 가까운 벡터문제의 대략적 해가 그의 서명 값이 된다.
이렇게 GGH 그리고 NTRU 에서 처럼 기존의 어려운 문제들(예를 들면, 인수분해 문제 그리고 이산대수 문제)과 다른 문제들을 찾고자 하는 데에는 크게 두 가지의 이유가 있다. 첫째, 인수분해 문제 및 이산대수 문제들에 관하여 해결하고자하는 많은 연구들이 진행 되고 있다. 두 번째 더욱 중요한 이유는 효율성에 있다. 예를 들어, NTRU 기반의 알고리즘들은 다른 암호알고리즘들과 비교하여 같은 안정성을 제공하면서 그들보다 수백 배 이상이 빠르다고 알려져 있다. 그러나 이러한 어려운 문제에 기반 하는 알고리즘들의 결점은 아직까지 그 안전성에 관하여 잘 연구되어지지 않았다는데 에 있다. 비록 래티스 이론이 100년 이상동안 연구 되어온 것은 사실이지만, 가장 짧은 벡터 문제와 같은 어려운 래티스 문제들의 특성들은 Lenstra, Lenstra, 과 Lova´sz 들이 1982년에 다항식 시간 래티스 기저 축소 알고리즘(polynomial-time lattice basis reduction algorithm)을 발견한 후에야 비로소 집중적으로 연구되었다. 더욱이, NTRU-기반의 기법들은 다항식 환에 기반 하는 특정 형태의 래티스들을 사용하고 있으며, 이러한 래티스들은 일반적인 래티스 문제들보다 해결하기에 더 쉬울지도 모르는 특정 형태의 래티스 문제들을 만들어 낸다. 이러한 특정 형태의 래티스 문제들은 단지 1996년 NTRU암호알고리즘의 소개 이후부터 활발한 연구가 되어왔기 때문에, 우리는 매우 유용한 새로운 결과들을 기대할 수 있다.
본 논문에서, 첫째 우리는 NTRUSign 서명 알고리즘에 대한 공격 방법을 제안한다. 우리가 제안하는 공격 기법을 통하여 타당한 메시지-서명 쌍 만을 관찰하는 수동적 공격자로 하여금 비밀 키를 모르고도 또 다른 서명 값을 만들어 내는 것을 가능하게 한다. 그러므로 NTRUSign 서명 알고리즘은 유연성(malleability) 성질을 가지고 있다는 점에서 안전한 서명 알고리즘이 아니다. 이 유연성의 성질로부터, 우리는 임의의 메시지-서명 쌍 을 가지고 그 메시지에 대한 제 2의 서명값을 유도해 낼 수 있다. 이 경우, 우리는 두 번째의 서명 값과 비밀 키를 알고 있는 사용자에 의하여 생성된 원래의 서명을 구분 할 수 없다. 비록 이러한 취약점이 공격자로 하여금 메시지 스트링을 바꾸는 것을 허락하지는 않지만, 이러한 종류의 위조는 그 서명 알고리즘이 모든 응용서비스에서 사용되어질 수 있는 것은 아니다. 예를 들어, 전자화폐의 경우에 있어서, 화폐에 대한 두 번째 타당한 서명 값을 찾아내는 것은 불가능 해야만 한다. 또한, 임의의 사용자가 s≠s´을 만족하는 메시지-서명 쌍들 (m,s) 과 (m, s´)을 동시에 받았을 경우, s 뿐만 아니라 s´ 도 메시지 m에 대한 타당한 서명 값으로서 결코 받아들여지지 않을 것이다. 만약 합법적인 서명자가 메시지 m에 대한 서명 s는 그의 서명 값이라는 것을 주장하고 싶을 경우, 그는 그의 비밀 키를 드러내야만 한다.
다음으로, 우리는 NTRUSign 서명 알고리즘이 가지고 있는 이런 취약점을 피하기 위한 기법을 제공한다. 비록, 수정된 NTRUSign은 앞에서 제안한 공격으로부터 안전하지만, 그것이 유연하지 않다는 사실을 아직 증명하지 못하였다. 실제로, 제안한 수정 NTRUSign이 유연성을 회피하는 서명 알고리즘이라는 것을 증명하는 것은 앞으로 우리가 해결해야하는 하나의 과제로서 남아있다.
