Accelerating the Distributed Multiplication Protocol with Applications to the Distributed Miller-Rabin Primality Test

P. Lory ()
Additional contact information
P. Lory: Universität Regensburg, Institut für Wirtschaftsinformatik

A chapter in From Nano to Space, 2008, pp 245-257 from Springer

Abstract: Abstract In the light of information security it is highly desirable to avoid a “single point of failure” because this would be an attractive target for attackers. Cryptographic protocols for distributed computations are important techniques in pursuing this goal. An essential module in this context is the secure multiparty multiplication of two polynomially shared values over ℤq with a public prime number q. The multiplication protocol of Gennaro, Rabin and Rabin (1998) is considered as the best protocol for this purpose. It requires a complexity of O(n 2 k log n+nk 2) bit operations per player, where k is the bit size of the prime q and n is the number of players. The present paper reduces this complexity to O(n 2 k +nk 2) with unaltered communication and round complexities. This improvement is possible by a loan from the field of numerical analysis, namely by the use of Newton’s classical interpolation formula. The distributed version of the famous probabilistic primality test of Miller and Rabin is built of several modules, which depend on distributed multiplications. Applications of the new method to these modules is studied and its importance for distributed signatures is outlined.

Keywords: Signature Scheme; Shared Secret; Random Oracle; Lagrange Interpolation; Secret Sharing Scheme (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-74238-8_18

Ordering information: This item can be ordered from
http://www.springer.com/9783540742388

DOI: 10.1007/978-3-540-74238-8_18

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().