低資源装置向き暗号方式の安全性解析と設計

摘要

Recent tremendous increase on applications of lightweight devices such as smart cards, RFIDtags, etc., has led a high demand for secure cryptographic schemes on these devices. However,since theoretically a certain amount of memory and computation is necessary for guaranteeingsecurity, designing a theoretically provable secure cryptographic scheme in such constrainedenvironment has been a challenging task. Moreover, due to the limited resources,countermeasures towards side-channel attacks (kind of physical attacks) are very limited,and it makes such devices to be a frequent target for such attacks. Therefore, here, not onlytheoretical security, but practical security needs sufficient analysis as well. We propose amethod to analyze a cryptographic scheme for lightweight devices and a method to constructsecure identification schemes for lightweight devices.In the first part, we show a number theoretic analysis on multi-prime RSA, a cryptographicscheme suitable for lightweight devices. In RSA, the most widely used factoring basedcryptographic scheme, a composite integer N = p1p2 is set as the public key. To reducethe cost of computations, a variant called multi-prime RSA, where N = p1p2 ￠ ￠ ￠ pk has beenproposed. However, a side-channel attack has indicated that one can get several bits of thesecret factors of N in RSA. The main concern is how severe such attack will affect multiprimeRSA if it is extensible to multi-prime RSA. In this work, we use a new lattice theorybased algorithm to find how many bits of each factor of N are sufficient to factorize N. Ouranalysis shows that when each factor of N has the same bit length, for k = 3, 3/5 part fromeach factor are sufficient to factorize N. Since this is smaller than the previous results where2/3 part of each factor were necessary, our result makes such attack become more dangerous.In the second part, we concentrate on the new design of a secure identification schemefor lightweight devices with fast online authentication. We focus on the implementation onRFID tags, where both the memory and the power consumption are very small. The previousscheme GPS has a fast online authentication, but it requires large memory since it needs alarge size of randomness to guarantee the security. In this work, we propose two new schemes,GPS+ and GPS++ and prove their security. Although we have to use a slightly strongernumber theoretic assumption than GPS, both of them have fast online authentication andbetter storage requirements compared to GPS. GPS+ achieves a faster online authenticationcompared to GPS by limiting the number of use and allowing authentication errors, whileGPS++ applies some additional computation to online authentication to reduce the memoryrequirement for guaranteeing security.