臺灣博碩士論文加值系統

在植基於身份之加密系統之中，寄送者不僅能直接利用接收者的身份作為公鑰加密，減少儲存公鑰的成本之外，也可以免去儲存憑證的成本。為了更加符合現時使用狀況，許多個多接收者加密機制也已被提出。然而，這些植基於身份之多接收者加密機制的安全性大多植基於離散對數問題或是大整數分解問題。在未來量子電腦發展成熟後，將有被破解的風險。為了能夠預防量子電腦攻擊，許多學者已投入後量子密碼學領域研究；其中之一的晶格密碼學被認為能夠抵擋量子攻擊。因此，本研究提出了植基於晶格密碼學，並以身份為基礎之匿名多接收者簽密法。此研究所提出的機制能夠保護接收者的身份不會暴露給無論外部攻擊者或惡意接收者得知，也提供了在晶格密碼學下少見的解密完整性驗證。並在D-LWE難題下，證明了此機制之機密性及匿名性達到IND-CPA及ANON-CPA等級的安全性；且在SIS難題下，證明了簽章之不可偽造性在隨機預言機下達到了SU-CMA等級之安全性。

In identity-based cryptosystems, not only can public key infrastructure reduce the storage cost of public keys by directly using receivers’ identities as public keys, but it can exempt storing certificates as well. In order to realize the practical situation, multi-receiver schemes have been also proposed. However, most of the identity-based multi-receiver schemes are based on the discrete logarithm problem or the problem of large integer factorization, which may be insecure under quantum computers. Therefore, the thesis presents a lattice-based anonymous multi-receiver identity-based signcryption scheme. The proposed scheme can hide the receivers’ identities against external and internal attackers and secure the integrity of the plaintext.
Moreover, the proposed scheme achieves the IND-CPA and ANON-CPA security based on the D-LWE hard problem, and the SU-CMA security based on the SIS problem under the
random oracle model.

論文審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Acknowlegment . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

Chapter 1 Introduction 1
1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Chapter 2 Preliminaries 7
2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Computational Lattice Hard Problems . . . . . . 8
2.4 The Short Integer Solution (SIS) Problem . . . .9
2.5 Discrete Gaussian Distribution . . . . . . . . . . . . . 9
2.6 Learning With Errors (LWE) . . . . . . . . . . . . . . . . 10
2.7 Lattice Trapdoors . . . . . . . . . . . . . . . . . . . . . . . . 11
2.8 The Reconciliation Mechanism . . . . . . . . . . . . 13
2.9 LA-AMRIBS Scheme . . . . . . . . . . . . . . . . . . . . . . 15

Chapter 3 Related Works 16
3.1 Anonymous Multi-Receiver Identity-Based Signcryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
3.1.1 Pang et al.’s AMRIBS Scheme . . . . . . . . . . . . 16
3.1.2 Pang et al.’s Anonymous Certificateless Multi-Receiver Signcryption Scheme Without Bilinear Pairing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Zhang et al.’s Lattice-Based Multi-Receiver Identity-Based Signcryption Scheme . . . . . . . . .21

Chapter 4 The Proposed Scheme 24
4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Extract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Signcrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 De-Signcrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.5 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Chapter 5 Security Models and Proofs 29
5.1 Security Models . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1.2 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
5.1.3 Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . .31
5.2 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . . . . .32
5.2.2 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2.3 Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . .38

Chapter 6 Comparison 43
6.1 Property Comparison . . . . . . . . . . . . . . . . . . . . .43
6.2 Ciphertext Comparison . . . . . . . . . . . . . . . . . . . 43
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Chapter 7 Conclusion 46

Bibliography 48

[1] A. Shamir, “Identity-based cryptosystems and signature schemes,” in Workshop on the Theory and Application of Cryptographic Techniques, pp. 47–53, Springer, 1984.

[2] R. Sakai, K. Ohgishi, and M. Kasahara, “Cryptosystems based on pairings,” in Symposium
on Cryptography and Information Security, SCIS, 2000.

[3] D. Boneh and M. Franklin, “Identity-based encryption from the weil pairing,” in Annual
International Cryptology Conference, pp. 213–229, Springer, 2001.

[4] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and
public-key cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978.

[5] B. Libert and J.-J. Quisquater, “A new identity based signcryption scheme from pairings,” in Proceedings 2003 IEEE Information Theory Workshop (Cat. No. 03EX674), pp. 155–158, IEEE, 2003.

[6] S. S. Chow, S.-M. Yiu, L. C. Hui, and K. Chow, “Efficient forward and provably secure idbased
signcryption scheme with public verifiability and public ciphertext authenticity,” in International Conference on Information Security and Cryptology, pp. 352–369, Springer, 2003.

[7] X. Boyen, “Multipurpose identity-based signcryption,” in Annual International Cryptology
Conference, pp. 383–399, Springer, 2003.

[8] J. Baek, R. Safavi-Naini, and W. Susilo, “Efficient multi-receiver identity-based encryption and its application to broadcast encryption,” in International Workshop on Public Key Cryptography, pp. 380–397, Springer, 2005.

[9] S. S. D. Selvi, S. S. Vivek, D. Shukla, and P. R. Chandrasekaran, “Efficient and provably secure certificateless multi-receiver signcryption,” in International Conference on Provable Security, pp. 52–67, Springer, 2008.

[10] L. Pang, L. Gao, H. Li, and Y. Wang, “Anonymous multi-receiver id-based signcryption
scheme,” IET Information Security, vol. 9, no. 3, pp. 194–201, 2015.

[11] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134,
IEEE, 1994.

[12] M. Ajtai, “Generating hard instances of lattice problems,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 99–108, ACM, 1996.

[13] M. Ajtai and C. Dwork, “A public-key cryptosystem with worst-case/average-case equivalence,” in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 284–293, 1997.

[14] O. Goldreich, S. Goldwasser, and S. Halevi, “Public-key cryptosystems from lattice reduction problems,” in Annual International Cryptology Conference, pp. 112–131, Springer, 1997.

[15] J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A ring-based public key cryptosystem,”
in International Algorithmic Number Theory Symposium, pp. 267–288, Springer, 1998.

[16] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” Journal of the ACM (JACM), vol. 56, no. 6, pp. 1–40, 2009.

[17] M. Ajtai, “The shortest vector problem in l2 is np-hard for randomized reductions,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 10–19, 1998.

[18] L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, “Lattice signatures and bimodal gaussians,” in Annual Cryptology Conference, pp. 40–56, Springer, 2013.

[19] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in ACM Symposium on Theory of Computing, p. 84–93, Association for Computing Machinery, 2005.

[20] D. Micciancio and C. Peikert, “Trapdoors for lattices: Simpler, tighter, faster, smaller,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 700–718, Springer, 2012.

[21] N. Genise and D. Micciancio, “Faster gaussian sampling for trapdoor lattices with arbitrary
modulus,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 174–203, Springer, 2018.

[22] C. Peikert, “Lattice cryptography for the internet,” in international Workshop on Post-
Quantum Cryptography, pp. 197–219, Springer, 2014.

[23] L. Pang and H. Li, “nmibas: a novel multi-receiver id-based anonymous signcryption with
decryption fairness,” Computing and Informatics, vol. 32, no. 3, pp. 441–460, 2013.

[24] L. Pang, M. Kou, M. Wei, and H. Li, “Efficient anonymous certificateless multi-receiver
signcryption scheme without bilinear pairings,” IEEE Access, vol. 6, pp. 78123–78135,
2018.

[25] X. Zhang, C. Xu, and J. Xue, “Efficient multi-receiver identity-based signcryption from
lattice assumption,” in International Journal of Electronic Security and Digital Forensics,
vol. 10, pp. 20–38, Inderscience Publishers (IEL), 2018.

[26] J. Alwen and C. Peikert, “Generating shorter bases for hard random lattices,” in Theory
of Computing Systems, vol. 48, pp. 535–553, Springer, 2011.