Top

International Journal of Information Security

Published in:

22-03-2017 | Regular Contribution

Accumulable optimistic fair exchange from verifiably encrypted homomorphic signatures

Authors: Jae Hong Seo, Keita Emura, Keita Xagawa, Kazuki Yoneyama

Published in: International Journal of Information Security | Issue 2/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Let us consider a situation where a client (Alice) frequently buys a certain kind of product from a shop (Bob) (e.g., an online music service sells individual songs at the same price, and a client buys songs multiple times in a month). In this situation, Alice and Bob would like to aggregate the total transactions and pay once per month because individual payments are troublesome. Though optimistic fair exchange (OFE) has been considered in order to swap electronic items simultaneously, known OFE protocols cannot provide such aggregate function efficiently because various costs are bounded by the number of transactions in the period. In order to run this aggregation procedure efficiently, we introduce a new kind of OFE called accumulable OFE (AOFE) that allows clients to efficiently accumulate payments in each period. In AOFE, any memory costs, computational costs, and communication complexity of the payment round must be constant in terms of the number of transactions. Since a client usually has just a low power and poor memory device, these efficiencies are desirable in practice. Currently, known approaches (e.g., based on verifiably encrypted signature scheme) are not very successful for constructing AOFE. Thus, we consider a new approach based on a new cryptographic primitive called verifiably encrypted homomorphic signature scheme (VEHS). In this paper, we propose a generic construction of AOFE from VEHS and also present a concrete VEHS scheme over a composite-order bilinear group by using the dual-form signature techniques. This VEHS scheme is also of independent interest. Since we can prove the security of VEHS without random oracles, our AOFE protocol is also secure without random oracles. Finally, we implemented our AOFE protocol, and it is efficient enough for practical use.

previous article Dynamic reversed accumulator

next article A game-theoretic approach for integrity assurance in resource-bounded systems

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

We say an OFE protocol is setup-free if the client does not need to contact the adjudicator except when receiving and verifying the public key certificate of the adjudicator.

We say an OFE protocol is stand-alone if the full signature is an ordinary signature.

As an example, let us consider the Waters signature scheme [54] with public key $x = g^a$ and secret key $h^a$ and the corresponding VES scheme [48]. Let $\sigma = (\sigma _1, \sigma _2) = (h^a \cdot H(m)^r, g^r)$ for random r be an ordinary signature. Let $apk = y = g^\beta $ be the adjudicator?fs public key. Then, we define $\omega = (\omega _1, \omega _2, \omega _3) = (\sigma _1 \cdot y^t, \sigma _2, g^t)$ for random t. The verification of an encrypted signature checks if $e(\omega _1, g) = e(h, x) \cdot e(H(m), \omega _2) \cdot e(y, \omega _3)$ or not.

Correctly speaking, they constructed OFE from EUF-CMA secure signature, IND-CCA secure public-key encryption, and simulation-sound non-interactive zero-knowledge proof system, which yield a VES scheme.

$\mathsf {apk}$ is not always used. However, since the definition of $\mathsf {OFE.Sign}$ in OFE [30] contains $\mathsf {apk}$, we adopt the same formulation.

For example, session information contains the current period and identities of parties.

Consider the malicious adjudicator knowing the discrete logarithm of $h_i, \log _{g_1}(h_i)$.

Because key generation algorithms for a signer and the adjudicator are independent in VEHS, $\mathsf {AOFE_{basic}}$ is setup-free.

Then, Alice needs to store just one message and one ordinary signature in her memory during a transaction period.

Then, Bob also needs to store just one message and one partial signature in his memory during a transaction period.

Since the full signature is also an ordinary signature, our protocol is stand-alone.

In the original assumption $\mathbf {LW1}$ [47], given $g \leftarrow _{\$}\mathbb {G}_1$, $X_3 \leftarrow _{\$}\mathbb {G}_3$, and $T \in \mathbb {G}$, it is infeasible to decide if $T \leftarrow _{\$}\mathbb {G}_1$ or $T \leftarrow _{\$}\mathbb {G}_{1,2}$.

As a remark, a client Alice needs to compute $H_{\mathsf {hom}}$ for a vector $\mathbf {v}=(0,0,\ldots ,0,1,0,\ldots ,0)$ in the AOFE protocol based on our VEHS scheme. Therefore, no n-dependent computation is required for Alice in our AOFE protocol.

If, in an application protocol like AOFE, $\mathsf {Vrfy}$ will run after several $\mathsf {VesVrfy}$ with $\mathbf {v}$, then $H_{\mathsf {hom}}(\mathbf {v})$ can be accumulated and stored in order to reduce the computational costs of $\mathsf {Vrfy}$.

Agrawal, S., Boneh, D.: Homomorphic MACs: MAC-based integrity for network coding. In: ACNS 2009, pp. 292–305 (2009)

Agrawal, S., Boneh, D., Boyen, X., Freeman, D.M.: Preventing pollution attacks in multi-source network coding. In: PKC 2010, pp. 161–176 (2010)

Asokan, N., Schunter, M., Waidner, M.: Optimistic protocols for fair exchange. In: ACM CCS 1997, pp. 7–17 (1997)

Asokan, N., Shoup, V., Waidner, M.: Asynchronous Protocols for Optimistic Fair Exchange. In: IEEE Symposium on S&P 1998, pp. 86–99 (1998)

Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures (extended abstract). In: EUROCRYPT 1998, pp. 591–606 (1998)

Attrapadung, N., Libert, B.: Homomorphic network coding signatures in the standard model. In: PKC 2011, pp. 17–34 (2011)

Attrapadung, N., Libert, B., Peters, T.: Computing on authenticated data: New privacy definitions and constructions. In: ASIACRYPT 2012, pp. 367–385 (2012). http://hal.inria.fr/hal-00730665

Attrapadung, N., Libert, B., Peters, T.: Efficient completely context-hiding quotable and linearly homomorphic signatures. In: PKC 2013, pp. 386–404 (2013)

Bahreman, A., Tygar, J.D.: Certified electronic mail. In: NDSS 1994, pp. 3–19 (1994)

10.

Bao, F., Deng, R.H., Nguyen, K.Q., Varadharajan, V.: Multi-party fair exchange with an off-line trusted neutral party. In: DEXA Workshop 1999, pp. 858–863 (1999)

11.

Belenkiy, M., Chase, M., Erway, C.C., Jannotti, J., Küpçü, A., Lysyanskaya, A., Rachlin, E.: Making p2p accountable without losing privacy. In: WPES 2007, pp. 31–40 (2007)

12.

Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: ICALP 2007, pp. 411–422 (2007)

13.

Ben-Or, M., Goldreich, O., Micali, S., Rivest, R.L.: A fair protocol for signing contracts. IEEE Trans. IT 36(1), 40–46 (1990)MathSciNetCrossRef

14.

Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: EUROCRYPT 2004, pp. 223–238 (2004)

15.

Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: EUROCRYPT 2011, pp. 149–168 (2011)

16.

Boneh, D., Freeman, D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: PKC 2011, pp. 1–16 (2011)

17.

Boneh, D., Freeman, D.M., Katz, J., Waters, B.: Signing a linear subspace: signature schemes for network coding. In: PKC 2009, pp. 68–87 (2009)

18.

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: EUROCRYPT 2003, pp. 416–432 (2003)

19.

Boneh, D., Naor, M.: Timed commitments. In: CRYPTO 2000, pp. 236–254 (2000)

20.

Brands, S.A.: An efficient off-line electronic cash system based on the representation problem. Tech. Rep. CS-R9323, CWI, Amsterdam (1993). http://persistent-identifier.org/?identifier=urn:nbn:nl:ui:18-5303

21.

Calderon, T., Meiklejohn, S., Shacham, H., Waters, B.: Rethinking verifiably encrypted signatures: a gap in functionality and potential solutions. In: CT-RSA 2014, pp. 349–366 (2014)

22.

Camenisch, J., Damgård, I.: Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In: ASIACRYPT 2000, pp. 331–345 (2000)

23.

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)MathSciNetCrossRefMATH

24.

Catalano, D., Fiore, D., Warinschi, B.: Adaptive pseudo-free groups and applications. In: EUROCRYPT 2011, pp. 207–223 (2011)

25.

Catalano, D., Fiore, D., Warinschi, B.: Efficient network coding signatures in the standard model. In: PKC 2012, pp. 680–696 (2012)

26.

Coffey, T., Saidha, P.: Non-repudiation with mandatory proof of receipt. ACM SIGCOMM Comput. Commun. Rev. 26(1), 6–17 (1996)CrossRef

27.

Cox, B., Tygar, J.D., Sirbu, M.: NetBill security and transaction protocol. In: USENIX Workshop Electronic Commerce 1995, pp. 77–88 (1995)

28.

Deng, R.H., Gong, L., Lazar, A.A., Wang, W.: Practical protocols for certified electronic mail. J. Netw. Syst. Manag. 4(3), 279–297 (1996)CrossRef

29.

Desmedt, Y.: Computer security by redefining what a computer is. NSPW 1993, pp. 160–166 (1993)

30.

Dodis, Y., Lee, P.J., Yum, D.H.: Optimistic fair exchange in a multi-user setting. In: PKC 2007, pp. 118–133 (2007)

31.

Dodis, Y., Reyzin, L.: Breaking and repairing optimistic fair exchange from PODC 2003. In: Digital Rights Management Workshop 2003, pp. 47–54 (2003)

32.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRefMATH

33.

Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRefMATH

34.

Fischlin, M., Lehmann, A., Schröder, D.: History-free sequential aggregate signatures. In: SCN 2012, pp. 113–130 (2012)

35.

Freeman, D.M.: Improved security for linearly homomorphic signatures: a generic framework. In: PKC 2012, pp. 697–714 (2012)

36.

Garay, J.A., Jakobsson, M., MacKenzie, P.D.: Abuse-Free Optimistic Contract Signing. In: CRYPTO 1999, pp. 449–466 (1999)

37.

Gennaro, R., Katz, J., Krawczyk, H., Rabin, T.: Secure network coding over the integers. In: PKC 2010, pp. 142–160 (2010)

38.

Gerbush, M., Lewko, A.B., O’Neill, A., Waters, B.: Dual form signatures: an approach for proving security from static assumptions. In: ASIACRYPT 2012, pp. 25–42 (2012)

39.

Hohenberger, S., Sahai, A., Waters, B.: Replacing a Random Oracle: Full Domain Hash From Indistinguishability Obfuscation. In: Eurocrypt, 2014 (2014)

40.

Huang, Q., Yang, G., Wong, D.S., Susilo, W.: Ambiguous Optimistic Fair Exchange. In: ASIACRYPT 2008, pp. 74–89 (2008)

41.

Huang, X., Mu, Y., Susilo, W., Wu, W., Xiang, Y.: Further observations on optimistic fair exchange protocols in the multi-user setting. In: PKC 2010, pp. 124–141 (2010)

42.

Johnson, R., Molnar, D., Song, D.X., Wagner, D.: Homomorphic signature schemes. In: CT-RSA, 2002, pp. 244–262 (2002)

43.

Kilinç, H., Küpçü, A.: Optimally efficient multi-party fair exchange and fair secure multi-party computation. In: CT-RSA 2015, pp. 330–349 (2015)

44.

Küpçü, A., Lysyanskaya, A.: Usable optimistic fair exchange. Comput. Netw. 56(1), 50–63 (2012)CrossRef

45.

Lee, K., Lee, D.H., Yung, M.: Aggregating CL-signatures revisited: extended functionality and better efficiency. In: FC 2013, (2013)

46.

Lee, K., Lee, D.H., Yung, M.: Sequential aggregate signatures with short public Keys: design, analysis and implementation studies. In: PKC 2013, pp. 423–442 (2013)

47.

Lewko, A.B., Waters, B.: New techniques for dual system encryption and fully secure hibe with short ciphertexts. In: TCC 2010, pp. 455–479 (2010). http://eprint.iacr.org/2009/482

48.

Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: EUROCRYPT 2006, pp. 465–485 (2006)

49.

Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In: PODC, pp. 12–19 (2003)

50.

Nishimaki, R., Xagawa, K.: Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES. In: PKC 2013, pp. 405–422 (2013)

51.

PBC: The PBC (pairing-based cryptography) library (2013). http://crypto.stanford.edu/pbc/

52.

Rückert, M., Schröder, D.: Security of verifiably encrypted signatures and a construction without random oracles. In: Pairing 2009, pp. 17–34 (2009). http://eprint.iacr.org/2009/027

53.

Seo, J.H., Emura, K., Xagawa, K., Yoneyama, K.: Accumulable optimistic fair exchange from verifiably encrypted homomorphic signatures. In: ACNS 2015, pp. 192–214 (2015)

54.

Waters, B.: Efficient identity-based encryption without random oracles. In: EUROCRYPT 2005, pp. 114–127 (2005)

55.

Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: CRYPTO 2009, pp. 619–636 (2009)

56.

Zhou, J., Gollmann, D.: A Fair Non-repudiation Protocol. In: IEEE Symposium on S & P 1996, pp. 55–61 (1996)

57.

Zhu, H., Bao, F.: Stand-alone and setup-free verifiably committed signatures. CT-RSA 2006, 159–173 (2006)MathSciNetMATH

Title: Accumulable optimistic fair exchange from verifiably encrypted homomorphic signatures
Authors: Jae Hong Seo
Keita Emura
Keita Xagawa
Kazuki Yoneyama
Publication date: 22-03-2017
Publisher: Springer Berlin Heidelberg
Published in: International Journal of Information Security / Issue 2/2018
Print ISSN: 1615-5262
Electronic ISSN: 1615-5270
DOI: https://doi.org/10.1007/s10207-017-0367-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2018

A methodology to measure and monitor level of operational effectiveness of a CSOC

Structural analysis and detection of android botnets using machine learning techniques

A game-theoretic approach for integrity assurance in resource-bounded systems

HoneyCirculator: distributing credential honeytoken for introspection of web-based attack cycle

Using targeted Bayesian network learning for suspect identification in communication networks

Dynamic reversed accumulator

Premium Partner