Article

Constructing fair-exchange protocols for E-commerce via distributed computation of RSA signatures

Authors:

Jung Min Park,

Edwin K. P. Chong,

Howard Jay SiegelAuthors Info & Claims

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Pages 172 - 181

https://doi.org/10.1145/872035.872060

Published: 13 July 2003 Publication History

Get Access

Abstract

Applications such as e-commerce payment protocols, electronic contract signing, and certified e-mail delivery require that fair exchange be assured. A fair-exchange protocol allows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. We describe a novel method of constructing very efficient fair-exchange protocols by distributing the computation of RSA signatures. Specifically, we employ multisignatures based on the RSA-signature scheme. To date, the vast majority of fair-exchange protocols require the use of zero-knowledge proofs, which is the most computationally intensive part of the exchange protocol. Using the intrinsic features of our multisignature model, we construct protocols that require no zero-knowledge proofs in the exchange protocol. Use of zero-knowledge proofs is needed only in the protocol setup phase--this is a one-time cost. Furthermore, our scheme uses multisignatures that are compatible with the underlying standard (single-signer) signature scheme, which makes it possible to readily integrate the fair-exchange feature with existing e-commerce systems.

References

[1]

M. Abadi, N. Glew, B. Home, and B. Pinkas. Certified email with a light on-line trusted third party: design and implementation. In International World Wide Web Conference Proceedings, pages 387--395, May 1991.]]

Digital Library

Google Scholar

[2]

N. Asokan. Fairness in Electronic Commerce. Department of Computer Science, University of Waterloo, 1998.]]

Digital Library

Google Scholar

[3]

N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. In Advances in Cryptology---EUROCRYPT '98, pages 591--606, 1998.]]

Crossref

Google Scholar

[4]

N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communications, 18(4):593--610, 2000.]]

Digital Library

Google Scholar

[5]

G. Ateniese. Efficient verifiable encryption (and fair exchange) of digital signatures. In Proceedings of ACM Conference on Computer and Communications Security, pages 138--146, November 1999.]]

Digital Library

Google Scholar

[6]

G. Ateniese and C. Nita-Rotaru. Stateless-recipient certified e-mail system based on verifiable encryption. In Proceedings of RSA 2002, February 2002.]]

Digital Library

Google Scholar

[7]

A. Bahreman and J. D. Tygar. Certified electronic mail. In Proceedings of Symposium on Network and Distributed Systems Security, pages 3--19, February 1994.]]

Google Scholar

[8]

F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with off-line TTP. In Proceedings of IEEE Symposium on Security and Privacy, pages 77--85, May 1998.]]

Google Scholar

[9]

M. Bellare and R. Sandhu. The security of practical two-party RSA signature schemes, unpublished manuscript, 2001, available at http://www.cs.ucsd.edu/users/mihir/papers/splitkey.html.]]

Google Scholar

[10]

M. Blum. How to exchange (secret) keys. ACM Transactions on Computer Systems, 1(2):175--193, 1983.]]

Digital Library

Google Scholar

[11]

J. Boyar, D. Chaum, and I. Damgard. Convertible undeniable signatures. In Advances in Cryptology---CRYPTO'90, pages 189--205, 1990.]]

Digital Library

Google Scholar

[12]

C. Boyd. Digital multisignatures. Cryptography and Coding, pages 241--246, 1989.]]

Google Scholar

[13]

C. Boyd and E. Foo. Off-line fair payment protocols using convertible signatures. In Advances in Cryptology---ASIA CRYPT'98, 1998.]]

Digital Library

Google Scholar

[14]

J. Camenisch and I. Damgard. Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In Advances in Cryptology---ASIACRYPT'00, pages 331--345, 2000.]]

Digital Library

Google Scholar

[15]

J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes. In Advances in Cryptology---EUROCRYPT'99, pages 106--121, 2000.]]

Google Scholar

[16]

D. Chaum, J. H. Evertse, and J. van der Graaf. An improved protocol for demonstrating possession of a discrete logarithm and some generalizations. In Advances in Cryptology---EUROCRYPT '87, pages 127--141, 1987.]]

Google Scholar

[17]

L. Chen. Efficient fair exchange with verifiable confirmation of signatures. In Advances in Cryptology---ASIACRYPT '98, pages 286--299, 1998.]]

Digital Library

Google Scholar

[18]

B. Cox, J. D. Tygar, and M. Sirbu. Netbill security and transaction protocol. In Proceedings of 1st USENIX Workshop on Electronic Commerce, pages 77--88, July 1995.]]

Digital Library

Google Scholar

[19]

I. Damgard and T. Pedersen. New convertible undeniable signature schemes. In Advances in Cryptology--EUROCRYPT '96, pages 372--386, 1996.]]

Crossref

Google Scholar

[20]

T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469--472, 1985.]]

Digital Library

Google Scholar

[21]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637--647, 1985.]]

Digital Library

Google Scholar

[22]

R. Gennaro, H. Krawczyk, and T. Rabin. RSA-based undeniable signatures. In Advances in Cryptology---CRYPTO'97, pages 132--149, 1997.]]

Digital Library

Google Scholar

[23]

L. Harn. Group-oriented (t, n) threshold digital signature scheme and digital multisignature. IEE Proceedings---Computers and Digital Techniques, 141(5):307--313, 1994.]]

Crossref

Google Scholar

[24]

N. Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag, New York, New York, 1987.]]

Digital Library

Google Scholar

[25]

P. MacKenzie and M. K. Reiter. Networked cryptographic devices resilient to capture. In Proceedings of IEEE Symposium on Security and Privacy, pages 12--25, May 2001.]]

Digital Library

Google Scholar

[26]

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, Boca Raton, Florida, 1996.]]

Digital Library

Google Scholar

[27]

S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures. In Proceedings of ACM Conference on Computer and Communications Security, pages 245--254, November 2001.]]

Digital Library

Google Scholar

[28]

M. Michels and M. Stadler. Efficient convertible undeniable signature schemes. In Proceedings of Annual Workshop on Selected Areas in Cryptography (SAC '97), pages 231--243, August 1997.]]

Google Scholar

[29]

I. Ray and I. Ray. Fair exchange in e-commerce. ACM SIGecom Exchange, 3(2):9--17, May 2002.]]

Digital Library

Google Scholar

[30]

R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21(2):120--126, 1978.]]

Digital Library

Google Scholar

[31]

J. Zhou and D. Gollmann. A fair non-repudiation protocol. In Proceedings of IEEE Symposium on Security and Privacy, pages 55--61, May 1996.]]

Digital Library

Google Scholar

Cited By

View all

Papaioannou TMantzonis DRitas V(2024)Towards a Blockchain-Enabled Trustworthy Market Framework2024 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain62396.2024.00096(656-662)Online publication date: 19-Aug-2024
https://doi.org/10.1109/Blockchain62396.2024.00096
Shiriaev EKucherov NBabenko MNazarov A(2023)Fast Operation of Determining the Sign of a Number in RNS Using the Akushsky Core FunctionComputation10.3390/computation1107012411:7(124)Online publication date: 28-Jun-2023
https://doi.org/10.3390/computation11070124
Chen JXiao HHu MChen C(2023)A blockchain-based signature exchange protocol for metaverseFuture Generation Computer Systems10.1016/j.future.2022.12.031142(237-247)Online publication date: May-2023
https://doi.org/10.1016/j.future.2022.12.031
Show More Cited By

Index Terms

Constructing fair-exchange protocols for E-commerce via distributed computation of RSA signatures

Recommendations

Breaking and repairing optimistic fair exchange from PODC 2003
DRM '03: Proceedings of the 3rd ACM workshop on Digital rights management

In PODC 2003, Park, Chong, Siegel and Ray [22] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is totally breakable already in the registration phase: the honest-but-curious arbitrator can easily ...
Optimistic Fair-exchange Protocols Based on DSA Signatures
SCC '04: Proceedings of the 2004 IEEE International Conference on Services Computing

The problem of fair exchange is one of the fundamental problems in secure electronic transactions and digital rights management. Recently, Park etc [Constructing fair exchange protocols for E-commerce via distributed computation of RSA signatures] ...
Fair Exchange of Signatures with Multiple Signers

Chen et al. introduced a new notion of a concurrent signature scheme for a fair exchange of signatures with two parties. Chen et al. also proposed a concrete scheme and proved its security under the assumption of discrete logarithm problem. Recently, ...

Reviews

Reviewer: David L. Mills

In a fair exchange protocol, players Alice and Bob exchange digitally encoded gifts verified by digital signatures. The exchange succeeds if both signatures are verified, in which case both gifts are accepted. The exchange fails if either signature is not verified, in which case both gifts are rejected. The common case is when Alice pays for an MP3 album with a digital credit card, and Bob confirms with a digital receipt. Fair exchange protocols are typically costly in computation and communication resources, and require cumbersome zero-knowledge proofs. The authors present a protocol to address this, based on RSA signatures commonly used in Internet commerce. The heart of their protocol is a key splitting scheme, using trusted third party Carol to act as a referee. In a registration subprotocol with zero-knowledge proofs, Alice and Carol exchange cryptographic values to be used later by Carol; this expensive protocol needs to be done only once. As a result, Carol can referee a fair exchange between Alice and Bob, should a signature be lost or fail to verify, but Carol cannot generate a valid signature herself. What makes this paper unique is the way in which the keys are split. The authors show that a prior scheme, involving the product of two partial keys, is vulnerable to attack, while showing that their scheme, involving the sum of two partial keys, resists attack. A particularly important aspect of their work is that the number of expensive cryptographic calculations required is much fewer than that required by other proposed methods, and that the calculations can be done using standard cryptographic libraries. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

July 2003

380 pages

ISBN:1581137087

DOI:10.1145/872035

General Chair:
Elizabeth Borowsky
Boston Coll.
,
Program Chair:
Sergio Rajsbaum
UNAM

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC03

Sponsor:

PODC03: Twenty-Second Annual ACM Symposium on Principles of Distributed Computing

July 13 - 16, 2003

Massachusetts, Boston

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
1,391
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Papaioannou TMantzonis DRitas V(2024)Towards a Blockchain-Enabled Trustworthy Market Framework2024 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain62396.2024.00096(656-662)Online publication date: 19-Aug-2024
https://doi.org/10.1109/Blockchain62396.2024.00096
Shiriaev EKucherov NBabenko MNazarov A(2023)Fast Operation of Determining the Sign of a Number in RNS Using the Akushsky Core FunctionComputation10.3390/computation1107012411:7(124)Online publication date: 28-Jun-2023
https://doi.org/10.3390/computation11070124
Chen JXiao HHu MChen C(2023)A blockchain-based signature exchange protocol for metaverseFuture Generation Computer Systems10.1016/j.future.2022.12.031142(237-247)Online publication date: May-2023
https://doi.org/10.1016/j.future.2022.12.031
Chen YTian XWang QJiang JLi MZhang Q(2022)SAFE: A General Secure and Fair Auction Framework for Wireless Markets With Privacy PreservationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2020.304544919:3(2038-2053)Online publication date: 1-May-2022
https://doi.org/10.1109/TDSC.2020.3045449
Du YXu CZhang Y(2021)A Blockchain-based Online Transaction System for Physical Products Trading with Fairness, Privacy Preservation, and Auditability2021 IEEE 9th International Conference on Smart City and Informatization (iSCI)10.1109/iSCI53438.2021.00012(15-22)Online publication date: Oct-2021
https://doi.org/10.1109/iSCI53438.2021.00012
.M S.M D(2020)Implementation of Multifactor Authentication Using Optimistic Fair ExchangeJournal of Ubiquitous Computing and Communication Technologies10.36548/jucct.2020.2.0022:2(70-78)Online publication date: 26-May-2020
https://doi.org/10.36548/jucct.2020.2.002
Atmaja IAstawa IWisswani NNugroho ISunu PWiratama I(2020)Document Encryption Through Asymmetric RSA Cryptography2020 International Conference on Applied Science and Technology (iCAST)10.1109/iCAST51016.2020.9557723(46-49)Online publication date: 24-Oct-2020
https://doi.org/10.1109/iCAST51016.2020.9557723
Yang XLau WYe QAu MLiu JCheng J(2020)Practical Escrow Protocol for BitcoinIEEE Transactions on Information Forensics and Security10.1109/TIFS.2020.297660715(3023-3034)Online publication date: 2020
https://doi.org/10.1109/TIFS.2020.2976607
Janin SQin KMamageishvili AGervais A(2020)FileBounty: Fair Data Exchange2020 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)10.1109/EuroSPW51379.2020.00056(357-366)Online publication date: Sep-2020
https://doi.org/10.1109/EuroSPW51379.2020.00056
Goni NAhmed SIbrahim A(2020)A P2P Optimistic Fair-Exchange (OFE) Scheme for Personal Health Records Using Blockchain Technology3rd International Conference on Wireless, Intelligent and Distributed Environment for Communication10.1007/978-3-030-44372-6_1(1-21)Online publication date: 24-Jun-2020
https://doi.org/10.1007/978-3-030-44372-6_1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Breaking and repairing optimistic fair exchange from PODC 2003

Optimistic Fair-exchange Protocols Based on DSA Signatures

Fair Exchange of Signatures with Multiple Signers

Reviews

Access critical reviews of Computing literature here