Article

Homomorphic MACs: MAC-Based Integrity for Network Coding

Authors:

Shweta Agrawal,

Dan BonehAuthors Info & Claims

ACNS '09: Proceedings of the 7th International Conference on Applied Cryptography and Network Security

Pages 292 - 305

https://doi.org/10.1007/978-3-642-01957-9_18

Published: 16 May 2009 Publication History

Abstract

Network coding has been shown to improve the capacity and robustness in networks. However, since intermediate nodes modify packets en-route, integrity of data cannot be checked using traditional MACs and checksums. In addition, network coded systems are vulnerable to pollution attacks where a single malicious node can flood the network with bad packets and prevent the receiver from decoding the packets correctly. Signature schemes have been proposed to thwart such attacks, but they tend to be too slow for online per-packet integrity.

Here we propose a <em>homomorphic MAC</em> which allows checking the integrity of network coded data. Our homomorphic MAC is designed as a drop-in replacement for traditional MACs (such as HMAC) in systems using network coding.

References

[1]

Ahlswede, R., Cai, N., Li, S., Yeung, R.: Network information flow. IEEE Transactions on Information Theory 46(4), 1204-1216 (2000)

[2]

Koetter, R.: An algebraic approach to network coding. IEEE/ACM Transactions on Networking 11, 782-795 (2003)

[3]

Li, S.Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Trans. Inform. Theory 49(2), 371-381 (2003)

[4]

Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: Signature schemes for network coding. In: Proc. of PKC 2009 (2009)

[5]

Zhao, F., Kalker, T., Médard, M., Han, K.: Signatures for content distribution with network coding. In: Proc. of International Symposium on Information Theory (ISIT) (2007)

[6]

Han, K., Ho, T., Koetter, R., Medard, M., Zhao, F.: On network coding for security. In: Military Communications Conference (Milcom) (2007)

[7]

Charles, D., Jain, K., Lauter, K.: Signatures for network coding. In: CISS 2006 (2006); to appear in International Journal of Information and Coding Theory

[8]

Krohn, M., Freedman, M., Mazieres, D.: On the-fly verification of rateless erasure codes for efficient content distribution. In: Proc. of IEEE Symposium on Security and Privacy, pp. 226-240 (2004)

[9]

Gkantsidis, C., Rodriguez, P.: Network coding for large scale content distribution. In: Proc. of IEEE INFOCOM 2005, pp. 2235-2245 (2005)

[10]

Gkantsidis, C., Rodriguez, P.: Cooperative security for network coding file distribution. In: INFOCOM (2006)

[11]

Gkantsidis, C., Miller, J., Rodriguez, P.: Comprehensive view of a live network coding p2p system. In: Internet Measurement Conference, pp. 177-188 (2006)

[12]

Carter, L., Wegman, M.: Universal classes of hash functions. Journal of Computer and System Sciences 18(2), 143-154 (1979)

[13]

Canetti, R., Garay, J., Itkis, G., Micciancio, D., Naor, M., Pinkas, B.: Multicast security: A taxonomy and some efficient constructions. In: Proc. of INFOCOM 1999, vol. 2, pp. 708-716 (1999)

[14]

Perrig, A., Canetti, R., Tygar, D., Song, D.: Efficient authentication and signature of multicast streams over lossy channels. In: Proc. of 2000 IEEE Symposium on Security and Privacy (2000)

[15]

Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) Asiacrypt 2008. LNCS, vol. 5350, pp. 90-107. Springer, Heidelberg (2008)

[16]

Katz, J., Lindell, Y.: Introduction to Modern Cryptography: Principles and Protocols. CRC Press, Boca Raton (2007)

[17]

Kumar, R., Rajagopalan, S., Sahai, A.: Coding constructions for blacklisting problems without computational assumptions. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 609-623. Springer, Heidelberg (1999)

Cited By

Gay RUrsu B(2024)On Instantiating Unleveled Fully-Homomorphic Signatures from Falsifiable AssumptionsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57718-5_3(74-104)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57718-5_3
Yi ZWei LYang HWang XYuan WLi R(2022)An Improved Secure Public Cloud Auditing Scheme in Edge ComputingSecurity and Communication Networks10.1155/2022/15572332022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/1557233
Feng SXu SZhang LSuga YSakurai KDing XSako K(2022)Multi-Key Homomorphic MACs with Efficient Verification for Quadratic Arithmetic CircuitsProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3497770(17-27)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3497770
Show More Cited By

Recommendations

Generalized homomorphic MACs with efficient verification
ASIAPKC '14: Proceedings of the 2nd ACM workshop on ASIA public-key cryptography

Homomorphic MACs allow the holder of a secret key to construct authenticators for data blocks such that an untrusted server that computes a function of the data, can also compute an authenticator that can be verified by the key holder, guaranteeing ...
Privacy-Preserving Homomorphic MACs with Efficient Verification
Web Services – ICWS 2018
Abstract
Homomorphic Message Authentication Code (MAC) allows a user to outsource data to an untrusted server and verify that results of computation on the data returned by the server are correct. Recently, much effort has been independently focused on ...
On CCA-Secure somewhat homomorphic encryption
SAC'11: Proceedings of the 18th international conference on Selected Areas in Cryptography

It is well known that any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks. The question then arises as to what is the most stringent security definition which is achievable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ACNS '09: Proceedings of the 7th International Conference on Applied Cryptography and Network Security

May 2009

534 pages

ISBN:9783642019562

Editors:
Michel Abdalla
École Normale Supérieure, Paris Cedex 05, France 75230
,
David Pointcheval
École Normale Supérieure, Paris Cedex 05, France 75230
,
Pierre-Alain Fouque
École Normale Supérieure, Paris Cedex 05, France 75230
,
Damien Vergnaud
École Normale Supérieure, Paris Cedex 05, France 75230

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 May 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gay RUrsu B(2024)On Instantiating Unleveled Fully-Homomorphic Signatures from Falsifiable AssumptionsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57718-5_3(74-104)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57718-5_3
Yi ZWei LYang HWang XYuan WLi R(2022)An Improved Secure Public Cloud Auditing Scheme in Edge ComputingSecurity and Communication Networks10.1155/2022/15572332022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/1557233
Feng SXu SZhang LSuga YSakurai KDing XSako K(2022)Multi-Key Homomorphic MACs with Efficient Verification for Quadratic Arithmetic CircuitsProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3497770(17-27)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3497770
Burkhalter LHithnawi AViand AShafagh HRatnasamy SBhagwan RPorter G(2020)TimeCryptProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388302(835-850)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388302
Alghamdi WRezvani MWu HKanhere S(2019)Routing-Aware and Malicious Node Detection in a Concealed Data Aggregation for WSNsACM Transactions on Sensor Networks10.1145/329353715:2(1-20)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3293537
Li ZXu GChen XYang Y(2019)Secure quantum network coding based on quantum homomorphic message authenticationQuantum Information Processing10.1007/s11128-018-2127-z18:1(1-21)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11128-018-2127-z
Schabhüser LButin DBuchmann J(2019)Function-Dependent Commitments from Homomorphic AuthenticatorsInformation Security and Privacy10.1007/978-3-030-21548-4_22(399-418)Online publication date: 3-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-21548-4_22
Katsumata SNishimaki RYamada SYamakawa T(2019)Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman AssumptionsAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17656-3_22(622-651)Online publication date: 19-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17656-3_22
(2018)A publicly verifiable network coding scheme with null-space HMACInternational Journal of Intelligent Information and Database Systems10.5555/3271902.327190411:2-3(117-131)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3271902.3271904
Li JLi TRen JChao HAndersson K(2018)Enjoy the Benefit of Network CodingWireless Communications & Mobile Computing10.1155/2018/34739102018Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1155/2018/3473910
Show More Cited By

View Options

View options

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 Table of Contents