Abstract
Aggregate signature schemes enable us to aggregate multiple signatures into a single short signature. One of its typical applications is sensor networks, where a large number of users and devices measure their environments, create signatures to ensure the integrity of the measurements, and transmit their signed data. However, if an invalid signature is mixed into aggregation, the aggregate signature becomes invalid, thus if an aggregate signature is invalid, it is necessary to identify the invalid signature. Furthermore, we need to deal with a situation where an invalid sensor generates invalid signatures probabilistically. In this paper, we introduce a model of aggregate signature schemes with interactive tracing functionality that captures such a situation, and define its functional and security requirements and propose aggregate signature schemes that can identify all rogue sensors. More concretely, based on the idea of Dynamic Traitor Tracing, we can trace rogue sensors dynamically and incrementally, and eventually identify all rogue sensors of generating invalid signatures even if the rogue sensors adaptively collude. In addition, the efficiency of our proposed method is also sufficiently practical.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In general, aggregate signature schemes can aggregate multiple signatures even if they are generated under the same key, but for simplicity, we do not introduce such version in this paper.
- 2.
The mechanism for watermarking contents is detached from the syntax and beyond the scope of this primitive, which is the same treatment as in [FT99].
References
Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: CCS 2010, pp. 473–484. ACM (2010)
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). https://doi.org/10.1007/3-540-39200-9_26
Fiat, A., Tassa, T.: Dynamic traitor tracing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 354–371. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_23
Gerbush, M., Lewko, A., O’Neill, A., Waters, B.: Dual form signatures: an approach for proving security from static assumptions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 25–42. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_4
Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_17
Hartung, G., Kaidel, B., Koch, A., Koch, J., Rupp, A.: Fault-tolerant aggregate signatures. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 331–356. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_13
Hohenberger, S., Sahai, A., Waters, B.: Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 494–512. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_27
Lee, K., Lee, D.H., Yung, M.: Sequential aggregate signatures with short public keys without random oracles. Theor. Comput. Sci. 579, 100–125 (2015)
Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_5
Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_28
Makarov, A.: A survey of aggregate signature applications. In: Misyurin, S.Y., Arakelian, V., Avetisyan, A.I. (eds.) Advanced Technologies in Robotics and Intelligent Systems. MMS, vol. 80, pp. 309–317. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-33491-8_37
Neven, G.: Efficient sequential aggregate signed data. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 52–69. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_4
Sato, S., Shikata, J.: Interactive aggregate message authentication scheme with detecting functionality. In: Barolli, L., Takizawa, M., Xhafa, F., Enokido, T. (eds.) AINA 2019. AISC, vol. 926, pp. 1316–1328. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-15032-7_110
Sato, S., Shikata, J.: Interactive aggregate message authentication equipped with detecting functionality from adaptive group testing. IACR Cryptology ePrint Archive: Report 2020/1218 (2020)
Sato, S., Shikata, J., Matsumoto, T.: Aggregate signature with detecting functionality from group testing. IACR Cryptology ePrint Archive: Report 2020/1219 (2020)
Acknowledgement
This paper is based on results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO). The third author was supported by JSPS KAKENHI Grant Number JP18K18055.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A \(\mathsf {multi\hbox {-}HKK}^+\)
A \(\mathsf {multi\hbox {-}HKK}^+\)
Here, we give the description of \(\mathsf {multi\hbox {-}HKK}^+\) that is constructed based on an ordinary aggregate signature scheme \(\varSigma _{\mathrm {AS}}\) and a cover free family. Recall that a d-cover free family (d-CFF) \(\mathcal {F}=(\mathcal {S},\mathcal {B})\) consists of a set \(\mathcal {S}\) of m elements and a set \(\mathcal {B}\) of n subsets of \(\mathcal {S}\), where \(d< m < n\), such that for any d subsets \(B_{i_1}, \ldots , B_{i_d} \in \mathcal {B}\) and for all distinct \(B \in \mathcal {B} \setminus \{B_{i_1}, \ldots , B_{i_d}\}\), it holds that \(B \notin \bigcup _{j \in [d]} B_{i_j}\).
Let d be an integer such that there exists a prime \(q=2d+1\). Let \(\mathcal {F}=(\mathcal {S},\mathcal {B})\) be a d-CFF based on quadratic polynomials where \(\mathcal {S}\) and \(\mathcal {B}\) are defined as follows:
Figure 4 describes \(\mathsf {multi\hbox {-}HKK}^+\) where \(T_i=\{j\in \{0,\ldots ,q^{k+1}-1\} \mid f_j(x_i)=y_i\}\) (\(i=0,\ldots ,q^2-1\)).
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Ishii, R. et al. (2021). Aggregate Signature with Traceability of Devices Dynamically Generating Invalid Signatures. In: Zhou, J., et al. Applied Cryptography and Network Security Workshops. ACNS 2021. Lecture Notes in Computer Science(), vol 12809. Springer, Cham. https://doi.org/10.1007/978-3-030-81645-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-81645-2_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-81644-5
Online ISBN: 978-3-030-81645-2
eBook Packages: Computer ScienceComputer Science (R0)