Article

Efficient Pairing Functions - And Why You Should Care

Author:

Arnold L. RosenbergAuthors Info & Claims

IPDPS '02: Proceedings of the 16th International Parallel and Distributed Processing Symposium

Page 134

Published: 15 April 2002 Publication History

Abstract

This paper provides a short tour through the world of pairing functions--bijections between N N and N--as models for computational "situations." After a short discussion of the computationally simplest pairing functions-- the Cauchy-Cantor "diagonal" polynomials--we describe two specific computational situations in some detail: the use of pairing functions as storage mappings for rectangular arrays/tables that can expand and shrink dynamically; the use of pairing functions as the basis for a mechanism for instilling accountability into Web-computing projects.

References

[1]

G. Cantor (1878): Ein Beitrag zur Begrundung der transfiniter Mengenlehre. J. Reine Angew. Math. 84 , 242-258.

[2]

A.L. Cauchy (1821): Cours d'analyse de lÉcole Royale Polytechnique, 1ère partie: Analyse algébrique . l'Imprimerie Royale, Paris. Reprinted: Wissenschaftliche Buchgesellschaft, Darmstadt, 1968.

[3]

M. Davis (1958): Computability and Unsolvability . McGraw-Hill, N.Y.

[4]

R. Fueter and G. Pólya (1923): Rationale Abzählung der Gitterpunkte. Vierteljschr. Naturforsch. Ges. Zürich 58 , 380-386.

[5]

K. Gödel (1931): Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 , 173-198.

[6]

The Intel Philanthropic Peer-to-Peer program . <www.intel.com/cure>.

[7]

J.S. Lew and A.L. Rosenberg (1978): Polynomial indexing of integer lattices, I. J. Number Th. 10 , 192- 214.

[8]

J.S. Lew and A.L. Rosenberg (1978): Polynomial indexing of integer lattices, II. J. Number Th. 10 , 215- 243.

[9]

I. Niven and H.S. Zuckerman (1980): An Introduction to the Theory of Numbers . (4th Ed.) J. Wiley & Sons, New York.

[10]

The Olson Laboratory Fight AIDS@Home project . <www.fightaidsathome.org>.

[11]

A.L. Rosenberg (1974): Allocating storage for extendible arrays. J. ACM 21 , 652-670.

Digital Library

[12]

A.L. Rosenberg (1975): Managing storage for extendible arrays. SIAM J. Comput. 4 , 287-306.

Digital Library

[13]

A.L. Rosenberg (2002): Accountable Webcomputing. Submitetd for publication. See an extended abstract in IEEE Intl. Parallel and Distributed Processing Symp. (IPDPS'02) .

Digital Library

[14]

The RSA Factoring by Web Project . <http://www.npac.syr.edu/factoring> (with Foreword by A. Lenstra). Northeast Parallel Architecture Center.

[15]

A.M. Turing (1936): On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. (ser. 2, vol. 42) 230-265; Correction ibid . (vol. 43) 544-546.

Cited By

Moiseenko IOran DSchmidt TSeedorf J(2017)Path switching in content centric and named data networksProceedings of the 4th ACM Conference on Information-Centric Networking10.1145/3125719.3125721(66-76)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3125719.3125721
Barddal JGomes HEnembreck FBarthès J(2016)SNCStream+Information Systems10.1016/j.is.2016.06.00762:C(60-73)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.is.2016.06.007
Kuraj IKuncak VJackson D(2015)Programming with enumerable sets of structuresACM SIGPLAN Notices10.1145/2858965.281432350:10(37-56)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814323
Show More Cited By

Recommendations

Efficient revocation and threshold pairing based cryptosystems
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Boneh, Ding, Tsudik and Wong recently proposed a way for obtaining fast revocation of RSA keys. Their method consists in using security mediators that keep a piece of each user's private key in such a way that every decrytion or signature operation ...
Certificateless Proxy Re-Encryption Without Pairing: Revisited
SCC '15: Proceedings of the 3rd International Workshop on Security in Cloud Computing

Proxy Re-Encryption was introduced by Blaze, Bleumer and Strauss to efficiently solve the problem of delegation of decryption rights. In proxy re-encryption, a semi-honest proxy transforms a ciphertext intended for Alice to a ciphertext of the same ...
Efficient group signatures from bilinear pairing
CISC'05: Proceedings of the First SKLOIS conference on Information Security and Cryptology

This paper presents two types of group signature schemes from bilinear pairings: the mini type and the improved type. The size of the group public keys and the length of the signatures in both schemes are constant. An on-line third party is introduced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IPDPS '02: Proceedings of the 16th International Parallel and Distributed Processing Symposium

April 2002

ISBN:0769515738

Publisher

IEEE Computer Society

United States

Publication History

Published: 15 April 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moiseenko IOran DSchmidt TSeedorf J(2017)Path switching in content centric and named data networksProceedings of the 4th ACM Conference on Information-Centric Networking10.1145/3125719.3125721(66-76)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3125719.3125721
Barddal JGomes HEnembreck FBarthès J(2016)SNCStream+Information Systems10.1016/j.is.2016.06.00762:C(60-73)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.is.2016.06.007
Kuraj IKuncak VJackson D(2015)Programming with enumerable sets of structuresACM SIGPLAN Notices10.1145/2858965.281432350:10(37-56)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814323
Kuraj IKuncak VJackson DAldrich JEugster P(2015)Programming with enumerable sets of structuresProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814323(37-56)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814323
Rosenberg A(2003)Accountable Web-ComputingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2003.117887414:2(97-106)Online publication date: 1-Feb-2003
https://dl.acm.org/doi/10.1109/TPDS.2003.1178874

View Options

View options

Figures

Tables

Media

View Table of Conten