Article

Signing a Linear Subspace: Signature Schemes for Network Coding

Authors:

Brent WatersAuthors Info & Claims

Irvine: Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC '09

Pages 68 - 87

https://doi.org/10.1007/978-3-642-00468-1_5

Published: 12 March 2009 Publication History

Abstract

Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. In contrast to traditional routing schemes, however, network coding requires intermediate nodes to modify data packets <em>en route</em> ; for this reason, standard signature schemes are inapplicable and it is a challenge to provide resilience to tampering by malicious nodes.

We propose two signature schemes that can be used in conjunction with network coding to prevent malicious modification of data. Our schemes can be viewed as signing linear subspaces in the sense that a signature <em>***</em> on a subspace <em>V</em> authenticates exactly those vectors in <em>V</em> . Our first scheme is (suitably) <em>homomorphic</em> and has <em>constant</em> public-key size and per-packet overhead. Our second scheme does not rely on random oracles and is based on weaker assumptions.

We also prove a lower bound on the length of signatures for linear subspaces showing that our schemes are essentially optimal in this regard.

References

[1]

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

Digital Library

[2]

Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography: The case of hashing and signing. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 216-233. Springer, Heidelberg (1994).

Digital Library

[3]

Boneh, D., Franklin, M.: An efficient public key traitor tracing scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 338-353. Springer, Heidelberg (1999).

Digital Library

[4]

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416-432. Springer, Heidelberg (2003).

Digital Library

[5]

Brands, S.: An efficient off-line electronic cash system based on the representation problem, CWI Technical Report CS-R9323 (1993).

Digital Library

[6]

Byers, J.W., Luby, M., Mitzenmacher, M., Rege, A.: A digital fountain approach to reliable distribution of bulk data. In: ACM SIGCOMM (1998).

Digital Library

[7]

Charles, D., Jain, K., Lauter, K.: Signatures for network coding. In: 40th Annual Conference on Information Sciences and Systems, CISS 2006 (2006).

[8]

Chou, P.A., Wu, Y., Jain, K.: Practical network coding. In: 41st Allerton Conference on Communication, Control, and Computing (2003).

[9]

Duquesne, S., Frey, G.: Background on pairings. In: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC Press, Boca Raton (2006).

[10]

Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/

[11]

Gkantsidis, C., Rodriguez, P.: Network coding for large scale content distribution. In: IEEE INFOCOM (2005).

[12]

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

[13]

Han, K., Ho, T., Koetter, R., Médard, M., Zhao, F.: On network coding for security. In: IEEE MILCOM (2007).

[14]

Ho, T., Koetter, R., Médard, M., Karger, D., Effros, M.: The benefits of coding over routing in a randomized setting. In: Proc. International Symposium on Information Theory (ISIT) (2003).

[15]

Ho, T., Leong, B., Koetter, R., Médard, M., Effros, M., Karger, D.: Byzantine modification detection in multicast networks using randomized network coding. In: Proc. Intl. Symposium on Information Theory (ISIT), pp. 144-152 (2004).

[16]

Ho, T., Médard, M., Koetter, R., Karger, D.R., Effros, M., Shi, J., Leong, B.: A random linear network coding approach to multicast. IEEE Trans. Inform. Theory 52(10), 4413-4430 (2006).

Digital Library

[17]

Jaggi, S.: Design and Analysis of Network Codes. PhD thesis, California Institute of Technology (2006).

Digital Library

[18]

Jaggi, S., Langberg, M., Katti, S., Ho, T., Katabi, D., Médard, M., Effros, M.: Resilient network coding in the presence of Byzantine adversaries. IEEE Trans. on Information Theory 54(6), 2596-2603 (2008).

Digital Library

[19]

Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244-262. Springer, Heidelberg (2002).

Digital Library

[20]

Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman & Hall/CRC Press, Boca Raton (2007).

Digital Library

[21]

Kim, M., Médard, M., Barros, J.: Counteracting Byzantine adversaries with network coding: An overhead analysis (2008), http://arxiv.org/abs/0806.4451

[22]

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).

[23]

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

Digital Library

[24]

Stanley, R.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (1997).

[25]

Zhao, F., Kalker, T., Médard, M., Han, K.: Signatures for content distribution with network coding. In: Proc. Intl. Symp. Info. Theory (ISIT) (2007).

Cited By

Tian YZhou TZhou XZhong WYang X(2024)Attribute-based linear homomorphic signature scheme based on key policy for mobile crowdsensingJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2024.10211436:6Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.jksuci.2024.102114
Pointcheval D(2024)Efficient Universally-Verifiable Electronic Voting with Everlasting PrivacySecurity and Cryptography for Networks10.1007/978-3-031-71070-4_15(323-344)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_15
Anthoine GBalbás DFiore D(2024)Fully-Succinct Multi-key Homomorphic Signatures from Standard AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_10(317-351)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_10
Show More Cited By

Recommendations

Delegation of signing rights using certificateless proxy signatures

A proxy signature scheme allows a proxy signer to sign messages on behalf of an original signer within a given context. It has lots of practical applications in distributed systems, grid computing, mobile agent applications, distributed shared object ...
Secure and Efficient Scheme for Delegation of Signing Rights
Information and Communications Security
Abstract
A proxy signature scheme enables a signer to transfer its signing rights to any other user, called the proxy signer, to produce a signature on its behalf. Multi-proxy signature is a proxy signature primitive which enables a user to transfer its ...
An Authenticated Encryption Scheme for Securely Signing a Signature with Message Linkages
ICICIC '07: Proceedings of the Second International Conference on Innovative Computing, Informatio and Control

Tseng et al. proposed a new signature scheme with message recovery by the concept of self-certified public keys in 2003. Their scheme provides two merits: one is that the signer's public key can simultaneously be authentic- cated in verifying the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Irvine: Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC '09

March 2009

520 pages

ISBN:9783642004674

Editors:
Stanisław Jarecki
Department of Computer Science, University of California, Irvine,
,
Gene Tsudik
Computer Science Department, University of California, Irvine,

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
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

Tian YZhou TZhou XZhong WYang X(2024)Attribute-based linear homomorphic signature scheme based on key policy for mobile crowdsensingJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2024.10211436:6Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.jksuci.2024.102114
Pointcheval D(2024)Efficient Universally-Verifiable Electronic Voting with Everlasting PrivacySecurity and Cryptography for Networks10.1007/978-3-031-71070-4_15(323-344)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_15
Anthoine GBalbás DFiore D(2024)Fully-Succinct Multi-key Homomorphic Signatures from Standard AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_10(317-351)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_10
Biryukov ALombard-Platet M(2023)PURED: A Unified Framework for Resource-Hard FunctionsProgress in Cryptology – INDOCRYPT 202310.1007/978-3-031-56235-8_7(126-149)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-56235-8_7
Ishizaka M(2023)Key-Range Attribute-Based Signatures for Range of Inner Product and Its ApplicationsProvable and Practical Security10.1007/978-3-031-45513-1_8(131-156)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45513-1_8
Hébant CPointcheval DSchädlich R(2023)Tracing a Linear Subspace: Application to Linearly-Homomorphic Group SignaturesPublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_12(312-341)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31368-4_12
Wang WSun YLi Y(2022)Security-Enhanced Certificate-Based Remote Data Integrity Batch Auditing for Cloud-IoTSecurity and Communication Networks10.1155/2022/78826622022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/7882662
Fiore DTucker IYin HStavrou ACremers CShi E(2022)Efficient Zero-Knowledge Proofs on Signed Data with Applications to Verifiable Computation on Data StreamsProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560630(1067-1080)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560630
Fischer AFuhry BKußmaul JJanneck JKerschbaum FBodden E(2022)Computation on Encrypted Data Using Dataflow AuthenticationACM Transactions on Privacy and Security10.1145/351300525:3(1-36)Online publication date: 19-May-2022
https://dl.acm.org/doi/10.1145/3513005
Lai JDeng RPang HWeng J(2022)Verifiable Computation on Outsourced Encrypted DataComputer Security - ESORICS 201410.1007/978-3-319-11203-9_16(273-291)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-11203-9_16
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