Article

Free access

Multi-party protocols

Authors:

Ashok K. Chandra,

Merrick L. Furst,

Richard J. LiptonAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 94 - 99

https://doi.org/10.1145/800061.808737

Published: 01 December 1983 Publication History

PDF eReader

Abstract

Many different types of inter-process communication have been examined from a complexity point of view [SP, Y]. We study a new model, in which a collection of processes

P₀, ..., P_k−1

that share information about a set of integers

{a₀, ...,a_k−1},

communicate to determine a 0-1 predicate of the numbers.

In this new model, tremendous sharing of information is allowed, while no single party is given enough information to determine the predicate on its own. Formally, each P_i has access to every a_j except for a_i. For simplicity, we only allow the parties to communicate as follows.

References

[1]

A. Borodin, M. Fischer, D. Kirkpatrick, N. Lynch, M. Tompa, "A time-space tradeoff for sorting and related non-oblivious computations." Toronto, Dept. of Computer Science, Technical Report 79-01-01, 1979.

Google Scholar

[2]

A. Borodin, D. Dolev, F. Fich, W. Paul, "Bounds for width-2 branching programs." These proceedings.

Google Scholar

[3]

P. Erdös and R. Graham, Old and New Problems and Results in Combinatorial Number Theory. L'Enseignement Mathématique, Université de Genève, 1980.

Google Scholar

[4]

M. Furst, J. Saxe, M. Sipser, "Parity, circuits and the polynomial-time hierarchy." 22ndSymposium on the Foundations of Computer Science, 1981, pp. 260-270; To appear in Mathematical Systems Theory.

Digital Library

Google Scholar

[5]

R. Graham, Rudiments of Ramsey theory. Regional Conference Series in Mathematics, number 45, 1981.

Google Scholar

[6]

R. Graham, B. Rothschild, J. Spencer, Ramsey Theory. Wiley-Interscience, 1980, p. 38.

Google Scholar

[7]

N. Pippenger, "A time-space trade-off." Journal of the ACM, 25, 1978, pp. 509-515.

Digital Library

Google Scholar

[8]

K. Roth, "On certain sets of integers." J. London Math. Soc., 29, 1954, pp. 20-26.

Crossref

Google Scholar

[9]

M. Sipser, C. Papadimitriou, "Communication complexity." 14thAnnual ACM Symposium on Theory of Computing, 1982, pp. 196-200.

Digital Library

Google Scholar

[10]

M. Tompa, "Time-space tradeoffs for computing functions, using connectivity properties of their circuits." 10thAnnual ACM Symposium on Theory of Computing, 1978, pp. 196-204.

Digital Library

Google Scholar

[11]

A. Yao, "Some complexity questions related to distributed computing." 11thAnnual ACM Symposium on Theory of Computing, 1979, pp. 209-213.

Digital Library

Google Scholar

Cited By

View all

Kelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)Explicit Separations between Randomized and Deterministic Number-on-Forehead CommunicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649721(1299-1310)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649721
Derksen HLee CViola E(2024)Boosting Uniformity in Quasirandom Groups: Fast and Simple2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00091(1425-1430)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00091
Alman JBłasiok J(2023)Matrix Multiplication and Number on the Forehead CommunicationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.16(1-23)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.16
Show More Cited By

Index Terms

Multi-party protocols
1. Networks
  1. Network protocols
2. Theory of computation
  1. Logic
    1. Finite Model Theory
  2. Randomness, geometry and discrete structures

Recommendations

Collusive attacks to "circle-type" multi-party quantum key agreement protocols

We find that existing multi-party quantum key agreement (MQKA) protocols designed for fairness of the key are, in fact, unfair. Our analysis shows that these protocols are sensitive to collusive attacks; that is, dishonest participants can collaborate ...
Quantum protocols for secure multi-party summation

Quantum secure multi-party summation is a kind of privacy-preserving summation whereby multiple mutually distrustful parties can securely compute the summation of their secret data, which can be utilized to execute many tasks of quantum secure multi-...
Formal Analysis Of Multi-party Non-repudiation Protocols Without TTP
ICCIIS '10: Proceedings of the 2010 International Conference on Communications and Intelligence Information Security

Non-repudiation service is crucial to electronic commerce. Now multi-party non-repudiation is a new focus of research. This paper presents a multi-party non-repudiation protocol, based on a group encryption scheme. A multi-party non-repudiation problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

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: 01 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

151
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)11

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)Explicit Separations between Randomized and Deterministic Number-on-Forehead CommunicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649721(1299-1310)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649721
Derksen HLee CViola E(2024)Boosting Uniformity in Quasirandom Groups: Fast and Simple2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00091(1425-1430)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00091
Alman JBłasiok J(2023)Matrix Multiplication and Number on the Forehead CommunicationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.16(1-23)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.16
Meir O(2023)Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00064(1056-1081)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00064
Kelley ZMeka R(2023)Strong Bounds for 3-Progressions2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00059(933-973)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00059
Sherstov ALeonardi SGupta A(2022)The approximate degree of DNF and CNF formulasProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520000(1194-1207)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520000
Abboud ABringmann KHermelin DShabtay D(2022)SETH-based Lower Bounds for Subset Sum and Bicriteria PathACM Transactions on Algorithms10.1145/345052418:1(1-22)Online publication date: 23-Jan-2022
https://dl.acm.org/doi/10.1145/3450524
Brian GFaonio AObremski MRibeiro JSimkin MSkorski MVenturi D(2022)The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for FreeIEEE Transactions on Information Theory10.1109/TIT.2022.319384868:12(8197-8227)Online publication date: Dec-2022
https://doi.org/10.1109/TIT.2022.3193848
Bukh BKarthik CNarayanan B(2022)Applications of Random Algebraic Constructions to Hardness of Approximation2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00032(237-244)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00032
Linial NShraibman A(2021)An improved protocol for the exactly-N problem*Proceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.2Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Collusive attacks to "circle-type" multi-party quantum key agreement protocols

Quantum protocols for secure multi-party summation

Formal Analysis Of Multi-party Non-repudiation Protocols Without TTP

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations