article

Discrete logarithm based additively homomorphic encryption and secure data aggregation

Authors:

Yixian YangAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 181, Issue 16

Pages 3308 - 3322

https://doi.org/10.1016/j.ins.2011.04.002

Published: 01 August 2011 Publication History

Abstract

At PKC 2006, Chevallier-Mames, Paillier, and Pointcheval proposed discrete logarithm based encryption schemes that are partially homomorphic, either additively or multiplicatively and announced an open problem: finding a discrete logarithm based cryptosystem that would help realize fully additive or multiplicative homomorphism. In this study, we achieve this goal by enclosing two opposite settings on the discrete logarithm problems (DLP) simultaneously: the first setting is that DLP over Z"p"""0 (where p"0-1 is smooth) is used to encode messages, while the second setting is that DLP over Z"p (where p-1 is non-smooth, i.e., containing large prime factors) is used to encrypt plaintexts. Then, based on the proposed scheme, novel protocols for secure data aggregation in wireless sensor networks are presented. Finally, taking Paillier's factoring-based additively homomorphic encryption schemes as the reference framework, we present detailed performance comparisons and further enhancement.

References

[1]

Agrawal, S. and Boneh, D., Homomorphic MACs: MAC-based integrity for network coding. In: Lecture Notes in Computer Science, Vol. 5536. Springer. pp. 292-305.

[2]

Bellare, M., Desai, A., Pointcheval, D. and Rogaway, P., Relations among notions of security for public-key encryption schemes. In: Lecture Notes in Computer Science, Vol. 1462. Springer. pp. 26-45.

Digital Library

[3]

Benaloh, J., Dense probabilistic encryption. In: Proceedings of the Workshop on Selected Areas of Cryptography, Kingston. pp. 120-128.

[4]

Castagnos, G. and Chevallier-Mames, B., Towards a DL-based additively homomorphic encryption scheme, in Information Security. In: Lecture Notes in Computer Science, 4779. Springer. pp. 362-375.

[5]

Castelluccia, C., Mykletun, E. and Tsudik, G., Efficient aggregation of encrypted data in wireless sensor networks. In: Second International ICST Conference on Mobile and Ubiquitous Systems (MobiQuitous), IEEE Computer Society. pp. 109-117.

Digital Library

[6]

Chevallier-Mames, B., Paillier, P. and Pointcheval, D., Encoding-free elgamal encryption without random oracles. In: Lecture Notes in Computer Science, Vol. 3958. Springer. pp. 91-104.

Digital Library

[7]

Damgård, I., Geisler, M. and Krøigaard, M., Homomorphic encryption and secure comparison. IJACT. v1 i1. 22-31.

[8]

Diffie, W. and Hellman, M.E., New directions in cryptography. IEEE Transactions on Information Theory. v22 i5. 644-654.

[9]

Dijk, M., Gentry, C., Halevi, S. and Vaikuntanathan, V., Fully homomorphic encryption over the integers. In: LNCS 2020, Springer.

[10]

Dolev, D., Dwork, C. and Naor, M., Non-malleable cryptography. In: 23rd Annual ACM Symposium on the Theory of Computing (STOC), ACM Press. pp. 542-552.

[11]

ElGamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory. v31 i4. 469-472.

[12]

Ertaul, L. and Kedlaya, V., Computing aggregation function minimum/maximum using homomorphic encryption schemes in wireless sensor networks (WSNs). In: Proceedings of the 2007 International Conference on Wireless Networks, CSREA Press. pp. 186-192.

[13]

Gentry, C., On homomorphic encryption over circuits of arbitrary depth. In: 41st ACM Symposium on Theory of Computing (STOC), ACM Press. pp. 169-178.

[14]

Goldwasser, S. and Micali, S., Probabilistic encryption & how to play mental poker keeping secret all partial information. In: 14th ACMSymposium on Theory of Computing(STOC), ACM Press. pp. 365-377.

[15]

Goldwasser, S. and Micali, S., Probabilistic encryption. JCSS: Journal of Computer and System Sciences. v28 i2. 270-299.

[16]

Hoogh, S., Schoenmakers, B., Skoric, B. and Villegas, J., Verifiable rotation of homomorphic encryptions. In: Lecture Notes in Computer Science, Vol. 5443. Springer. pp. 393-410.

Digital Library

[17]

Kaya, K. and Selcuk, A.A., Threshold cryptography based on asmuth-bloom secret sharing. Inf. Sci. v177 i19. 4148-4160.

[18]

Kuribayashi, M. and Tanaka, H., Fingerprinting protocol for images based on additive homomorphic property. IEEE Trans. Image Process. v14 i12. 2129-2139.

[19]

Lin, X., Lu, R. and Shen, X., Mdpa: multidimensional privacy-preserving aggregation scheme for wireless sensor networks. Wireless Commun. Mobile Comput. (Wiley). v10 i6. 843-856.

[20]

Melchor, C.A., Gaborit, P.G. and Herranz, J., Additively Homomorphic Encryption with d-operand Multiplications. In: CRYPTO'10, Springer.

[21]

Naor, M. and Yung, M., Public-key cryptosystems provably secure against chosen cypher-text attack. In: Proceeding of 22nd Annuals ACM Symposium on Theory of Computing(STOC), ACM Press. pp. 427-437.

[22]

Ostrovsky, R. and Skeith, W., Private searching on streaming data. In: LNCS, 3621. Springer. pp. 223-240.

[23]

Paillier, P., Public-key cryptosystems based on composite degree residuosity classes. In: Lecture Notes in Computer Science, Vol. 1599. Springer. pp. 223-238.

Digital Library

[24]

K.G. Paterson, S. Srinivasan, On the relations between non-interactive key distribution, identity-based encryption and trapdoor discrete log groups Cryptography ePrint Archive: Report 2007/453.

[25]

Pohlig, S.C. and Hellman, M.E., An improved algorithm for computing logarithms over gf(p) and its cryptographic significance. IEEE Trans. Inf. Theory (IT). v24 i1. 106-110.

[26]

Pollard, J.M., A Monte Carlo method for factorization. BIT Numer. Math. v15 i3. 331-334.

[27]

Rackoff, C. and Simon, D.R., Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Lecture Notes in Computer Science, Vol. 576. Springer. pp. 433-444.

Digital Library

[28]

Shoup, V., A Computational Introduction to Number Theory and Algebra. 2005. Cambridge University Press.

[29]

O. Ugus, D. Westhoff, R. Laue, A. Shoufan, S.A. Huss, Optimized implementation of elliptic curve based additive homomorphic encryption for wireless sensor networks, 2009. Available from (CoRR, arXiv:org/abs/0903.3900).

[30]

Wang, L., Wang, L., Pan, Y., Zhang, Z. and Yang, Y., Discrete-log-based additively homomorphic encryption and secure WSN data aggregation. In: Lecture Notes in Computer Science, Vol. 5927. Springer. pp. 493-502.

[31]

Yacoub, H. and Sarkar, T.K., A homomorphic approach for through-wall sensing. IEEE Trans. Geosci. Remote Sens. v47 i5. 1318-1327.

[32]

Yokoo, M. and Suzuki, K., Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions. In: First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), ACM Press. pp. 112-119.

[33]

Zhao, B., Kou, W., Li, H., Dang, L. and Zhang, J., Effective watermarking scheme in the encrypted domain for buyer-seller watermarking protocol. Inf. Sci. v180 i23. 4672-4684.

Cited By

Saravanaselvan AParamasivan B(2019)Design and implementation of an efficient attack resilient computation algorithm in WSN nodesCluster Computing10.1007/s10586-018-2147-622:2(3301-3311)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10586-018-2147-6
Parmar KJinwala D(2016)Concealed data aggregation in wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.04.013103:C(207-227)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.04.013
Wang TYu JZhang PXie X(2014)Efficient Linear Homomorphic Encryption from LWE Over RingsWireless Personal Communications: An International Journal10.1007/s11277-013-1335-174:2(1005-1016)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1007/s11277-013-1335-1

Index Terms

Discrete logarithm based additively homomorphic encryption and secure data aggregation

Index terms have been assigned to the content through auto-classification.

Recommendations

Breaking an ID-based encryption based on discrete logarithm and factorization problems

We cryptanalyse the new ID-based encryption scheme proposed by Meshram.We find a method to factorize N, where N is the parameter proposed by Meshram.We also give a method to recover the secret master key of Meshram's ID-based encryption scheme.We also ...
Secure Data Aggregation in WSNs: A Two Level Framework
SIN '18: Proceedings of the 11th International Conference on Security of Information and Networks

Energy efficiency is an important issue in wireless sensor networks; clustering of nodes and sensor data aggregation are popular techniques to address the issue. Sensors generate sensitive data in many applications and thus methods to secure the data so ...
Discrete-Log-Based Additively Homomorphic Encryption and Secure WSN Data Aggregation
Information and Communications Security
Abstract
At PKC 2006, Chevallier-Mames, Paillier, and Pointcheval proposed encryption schemes that are partially homomorphic, either additively or multiplicatively and announced an open research problem: finding a discrete-log-based cryptosystem that would ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier Inc. © 2011.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 August 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saravanaselvan AParamasivan B(2019)Design and implementation of an efficient attack resilient computation algorithm in WSN nodesCluster Computing10.1007/s10586-018-2147-622:2(3301-3311)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10586-018-2147-6
Parmar KJinwala D(2016)Concealed data aggregation in wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.04.013103:C(207-227)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.04.013
Wang TYu JZhang PXie X(2014)Efficient Linear Homomorphic Encryption from LWE Over RingsWireless Personal Communications: An International Journal10.1007/s11277-013-1335-174:2(1005-1016)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1007/s11277-013-1335-1

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents