nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Attribute-Based Signatures for Unbounded Languages from Standard Assumptions

verfasst von : Yusuke Sakai, Shuichi Katsumata, Nuttapong Attrapadung, Goichiro Hanaoka

Erschienen in: Advances in Cryptology – ASIACRYPT 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Attribute-based signature (ABS) schemes are advanced signature schemes that simultaneously provide fine-grained authentication while protecting privacy of the signer. Previously known expressive ABS schemes support either the class of deterministic finite automata and circuits from standard assumptions or Turing machines from the existence of indistinguishability obfuscations.

In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turing machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies.

Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Multi-key Homomorphic Signatures Unforgeable Under Insider Corruption

Nächstes Kapitel Learning Strikes Again: The Case of the DRS Signature Scheme

The other type is called signature-policy, where the roles of policies and attributes are swapped.

In terms of languages that machines accept, NFA is equivalent to a subclass of Turing machines called read-only right-moving Turing machines. Both accept the class of regular languages.

Here, one can think of the “snapshot" as the state the algorithm is in. For example, a snapshot of a Turing machine is whatever written in the working tape, the state it is in, and the position of the head. Furthermore, we use the term machine loosely to express some computational model such as Turing machines or automata.

In particular, it proves that the table includes an entry of the form \(\langle q, w, q' \rangle \) while hiding which entry it is. This can be accomplished by viewing the table as a matrix and using unit vectors to indicate the row to pick up.

Similar illustrations can be obtained for the case that the head stays and moves to the right with the same idea.

The other two cases \(\mathtt {right}\) and \(\mathtt {stay}\) are done similarly.

Since our definition of transition does not automatically expand the tape with blank symbols, we need to explicitly pad with blank symbols. The length can be bounded by the number of the steps until the machine halts.

This extra component of the messages is for resisting collusion attacks. Without this component, colluding signers may produce a forgery of the attribute-based signature scheme by mixing their certificates and forming a history of transitions that is not allowed to each of the signers.

See Fig. 1 and Eq. (2) for intuition. The five tuples in Eq. (2) are implemented in Eqs. (3)–(7) for the case that the head moves to left. The other two cases are implemented similarly.

We do not need \(\psi ^{(t)}_{i,j}\) for \(i = 0\), since these cases correspond to the initial configuration, which is public.

We do not need \(\psi ^{(\theta )}_{i,j}\) for \(i = \tilde{T}\), since these commitments are used to bind a configuration \(t_{i}\) and the next configuration \(t_{i+1}\), but \(t_{\tilde{T}}\) is the last configuration.

[AS16]

Ananth, P., Sahai, A.: Functional encryption for turing machines. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 125–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_6CrossRef

[BF14]

Bellare, M., Fuchsbauer, G.: Policy-based signatures. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 520–537. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_30CrossRef

[BGI14]

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_29CrossRef

[DDM17]

Datta, P., Dutta, R., Mukhopadhyay, S.: Attribute-based signatures for Turing machines. Cryptology ePrint Archive, Report 2017/801 (2017). http://eprint.iacr.org/2017/801

[GKP+13]

Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 536–553. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_30CrossRef

[GS12]

Groth, J., Sahai, A.: Efficient noninteractive proof systems for bilinear groups. SIAM J. Comput. 41(5), 1193–1232 (2012)MathSciNetCrossRef

[KPW15]

Kiltz, E., Pan, J., Wee, H.: Structure-preserving signatures from standard assumptions, revisited. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 275–295. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_14CrossRef

[MPR11]

Maji, H.K., Prabhakaran, M., Rosulek, M.: Attribute-based signatures. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 376–392. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_24CrossRef

[NP15]

Nandi, M., Pandit, T.: On the power of pair encodings: Frameworks for predicate cryptographic primitives. Cryptology ePrint Archive, Report 2015/955 (2015). http://eprint.iacr.org/

[OT11]

Okamoto, T., Takashima, K.: Efficient attribute-based signatures for non-monotone predicates in the standard model. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 35–52. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_3CrossRef

[SAH16]

Sakai, Y., Attrapadung, N., Hanaoka, G.: Attribute-based signatures for circuits from bilinear map. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 283–300. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_11CrossRef

[Sip96]

Sipser, M.: Introduction to the Theory of Computation, 1st edn. International Thomson Publishing, Stamford (1996)MATH

[SSN09]

Shahandashti, S.F., Safavi-Naini, R.: Threshold attribute-based signatures and their application to anonymous credential systems. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 198–216. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_13CrossRef

[TLL14]

Tang, F., Li, H., Liang, B.: Attribute-Based Signatures for Circuits from Multilinear Maps. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds.) ISC 2014. LNCS, vol. 8783, pp. 54–71. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13257-0_4CrossRef

Titel: Attribute-Based Signatures for Unbounded Languages from Standard Assumptions
verfasst von: Yusuke Sakai
Shuichi Katsumata
Nuttapong Attrapadung
Goichiro Hanaoka
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2018
Print ISBN: 978-3-030-03328-6

Electronic ISBN: 978-3-030-03329-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-03329-3_17

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"