Rational secret sharing and multiparty computation: extended abstract

We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. We show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. However, we show that both are possible using randomized mechanisms with constant expected running time.

• Publication year

  2004

• Venue

  Symposium on the Theory of Computing

• Publication date

  2004-06-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1007352.1007447arXiv cs/0609035
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Non-cooperative computation: Boolean functions with correctness and exclusivity

  2005cited by this paper
• Foundations of Cryptography: Volume 2, Basic Applications

  2004cited by this paper
• Towards a general theory of non-cooperative computation

  2003cited by this paper
• Distributed algorithmic mechanism design: recent results and future directions

  2002cited by this paper
• Epistemic conditions for iterated admissibility

  2001cited by this paper
• Timed Commitments

  2000cited by this paper
• Studies in secure multiparty computation and applications

  1995cited by this paper
• Reasoning about knowledge

  1995cited by this paper
• A Course in Game Theory

  1995cited by this paper
• Practical and provably secure release of a secret and exchange of signatures

  1994cited by this paper
• Controlled Gradual Disclosure Schemes for Random Bits and Their Applications

  1989cited by this paper
• Completeness theorems for non-cryptographic fault-tolerant distributed computation

  1988cited by this paper
• Multiparty unconditionally secure protocols

  1988cited by this paper
• How to play ANY mental game

  1987influential reference
• A randomized protocol for signing contracts

  1985cited by this paper
• How to exchange (secret) keys

  1983cited by this paper
• How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin

  1983cited by this paper
• Protocols for Secure Computations (Extended Abstract)

  1982cited by this paper
• How to share a secret

  1979cited by this paper

• Non-Delegatable Commitments

  2025cites this paper
• Distributed MIS Algorithms for Rational Agents using Games

  2025cites this paper
• Bandwidth Efficient Partial Authorized PSI

  2025cites this paper
• Breaking Omertà: On Threshold Cryptography, Smart Collusion, and Whistleblowing

  2025cites this paper
• Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

  2025cites this paper
• Cryptanalysis and improvement of fair quantum secret sharing based on symmetric bivariate polynomial

  2025cites this paper
• Blockchain-Based Secure Multiple Computation Scheme (Bsmpcs) for Preserving and Extraction of Health Care Data

  2025cites this paper
• SCS-RDL: A Smart Contract Scheme for Rational Delegation Learning

  2025cites this paper
• Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game

  2025influential citation
• Rational Secret Sharing with Competition

  2025influential citation
• Game-Theoretically Fair Distributed Coin Tossing With Private Preferences

  2025cites this paper
• A Verifiable Multi-Secret Sharing Scheme for Hierarchical Access Structure

  2024cites this paper
• Secure and Efficient Video Inferences with Compressed 3-Dimensional Deep Neural Networks

  2024cites this paper
• FPGA Accelerated Implementation of 3D Mesh Secret Sharing Based on Symmetric Similarity of Model

  2024cites this paper
• Revisiting the Primitives of Transaction Fee Mechanism Design

  2024cites this paper
• A rational hierarchical (t,n)-threshold quantum secret sharing scheme

  2024cites this paper
• Secure Vickrey Auctions with Rational Parties

  2024cites this paper
• Game Theory-Based Rational Secret Sharing Scheme with Quantum Resistant

  2024cites this paper
• Game-Theoretically Fair Distributed Sampling

  2024cites this paper
• Collaboration Encouraging Quantum Secret Sharing Scheme with Seal Property

  2024cites this paper
• A rational and reliable model for outsourcing polynomial two-party computation

  2024cites this paper
• Collusion-Resilience in Transaction Fee Mechanism Design

  2024cites this paper
• Consortium blockchain private key protection scheme based on rational secret sharing and blockchain

  2024cites this paper
• Secret Sharing with Snitching

  2024cites this paper
• Rational Broadcast Protocols against Timid Adversaries

  2023cites this paper
• Collusion-Deterrent Threshold Information Escrow

  2023cites this paper
• ROMSS: a rational optional multi-secret sharing scheme based on reputation mechanism

  2023cites this paper
• Rational quantum secret sharing scheme based on GHZ state

  2023cites this paper
• Chex-Mix: Combining Homomorphic Encryption with Trusted Execution Environments for Oblivious Inference in the Cloud

  2023cites this paper
• An Introduction to Secret Sharing: A Systematic Overview and Guide for Protocol Selection

  2023cites this paper
• Maximizing Miner Revenue in Transaction Fee Mechanism Design

  2023influential citation
• FPGA acceleration of secret sharing for 3D data cubes

  2023cites this paper
• Long-term Data Sharing under Exclusivity Attacks

  2022cites this paper
• Rational Uniform Consensus with General Omission Failures

  2022cites this paper
• On the impossibility of surviving (iterated) deletion of weakly dominated strategies in rational MPC

  2022influential citation
• Quantum Advantage of Threshold Changeable Secret Sharing Scheme

  2022cites this paper
• The optimal attack-defense scheme for secret sharing

  2022cites this paper
• Practical Undeniable Multiparty Drawing-Straw Protocol in Asynchronous Networks for Resource-Constrained Information Systems

  2022cites this paper
• Secure Auctions in the Presence of Rational Adversaries

  2022cites this paper
• Adversarial Level Agreements for Two-Party Protocols

  2022cites this paper
• Information-theoretic secure rational secret sharing in asynchronous networks for untrusted cloud environments

  2022cites this paper
• Research on the fair (t,r,n) threshold secret sharing scheme

  2022cites this paper
• log ∗ -Round Game-Theoretically-Fair Leader Election (cid:63)

  2022cites this paper
• DE‐RSTC: A rational secure two‐party computation protocol based on direction entropy

  2021cites this paper
• CHEX-MIX: Combining Homomorphic Encryption with Trusted Execution Environments for Two-party Oblivious Inference in the Cloud

  2021cites this paper
• A Permissioned Blockchain System for Secure Multiparty Computation

  2021cites this paper
• Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

  2021cites this paper
• Deposit schemes for incentivizing behavior in finite games of perfect information

  2021cites this paper
• Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader Election

  2021cites this paper
• A new entropic criterion model in rational secure two-party computation

  2021cites this paper
• A Complete Characterization of Game-Theoretically Fair, Multi-Party Coin Toss

  2021cites this paper
• Truthful Information Dissemination in General Asynchronous Networks

  2021cites this paper
• An incentive-compatible rational secret sharing scheme using blockchain and smart contract

  2021influential citation
• JUBILEE: Secure Debt Relief and Forgiveness

  2021cites this paper
• ABDKS: attribute-based encryption with dynamic keyword search in fog computing

  2021cites this paper
• Towards reducing delegation overhead in replication-based verification: An incentive-compatible rational delegation computing scheme

  2021cites this paper
• Payment Schemes from Limited Information with Applications in Distributed Computing

  2021cites this paper
• Verification of multi-agent systems with public actions against strategy logic

  2020cites this paper
• Belief and fairness: A secure two-party protocol toward the view of entropy for IoT devices

  2020cites this paper
• Multi-player Equilibria Verification for Concurrent Stochastic Games

  2020cites this paper
• Coded Computing

  2020cites this paper
• Economically Viable Randomness

  2020cites this paper
• Almost Public Quantum Coins

  2020cites this paper
• Cooperate Delegation of Computation for Rational Party Using Zero-Determinant Strategy Approach

  2020cites this paper
• Generic Superlight Client for Permissionless Blockchains

  2020influential citation
• Extremal Set Theory and LWE Based Access Structure Hiding Verifiable Secret Sharing with Malicious Majority and Free Verification

  2020cites this paper
• Game-Theoretically Fair Leader Election in O(log log n) Rounds under Majority Coalitions

  2020cites this paper
• A secret sharing scheme based on game theory and BP neural network*

  2020cites this paper
• A game-theoretic security framework for quantum cryptography: Performance analysis and application

  2020cites this paper
• Verifiable Secret Sharing Based On Micali-Rabin's Random Vector Representations Technique

  2020cites this paper
• Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles

  2020cites this paper
• Financial Cryptography and Data Security: FC 2020 International Workshops, AsiaUSEC, CoDeFi, VOTING, and WTSC, Kota Kinabalu, Malaysia, February 14, 2020, Revised Selected Papers

  2020cites this paper
• Perfectly Secure Message Transmission Against Rational Adversaries

  2020cites this paper
• Vote Selling Resistant Voting

  2020cites this paper
• Survey on quantum information security

  2019cites this paper
• Secure Voting Protocols with Perfect Ballot Secrecy

  2019cites this paper
• Private Shotgun DNA Sequencing: A Structured Approach

  2019cites this paper
• Reverse Outsource: Reduce the Cloud's Workload in Outsourced Attribute-Based Encryption Scheme

  2019cites this paper
• Perfectly Secure Message Transmission Against Independent Rational Adversaries

  2019cites this paper
• When Is a Semi-honest Secure Multiparty Computation Valuable?

  2019cites this paper
• Game theoretic security of quantum bit commitment

  2019cites this paper
• Rational Threshold Cryptosystems

  2019cites this paper
• Efficient Publicly Verifiable 2PC over a Blockchain with Applications to Financially-Secure Computations

  2019cites this paper
• Realistic versus Rational Secret Sharing

  2019cites this paper
• Title Ideal Secret Sharing Schemes with Share Selectability

  2019cites this paper
• Fair and private rewarding in a coalitional game of cybersecurity information sharing

  2019cites this paper
• SoK: Tools for Game Theoretic Models of Security for Cryptocurrencies

  2019cites this paper
• BFR-MPC: A Blockchain-Based Fair and Robust Multi-Party Computation Scheme

  2019cites this paper
• Secure computation protocols under asymmetric scenarios in enterprise information system

  2019cites this paper
• Consensus in Equilibrium: Can One Against All Decide Fairly?

  2019cites this paper
• Improved Signature Schemes for Secure Multi-party Computation with Certified Inputs

  2018cites this paper
• Rational protocol of quantum secure multi-party computation

  2018cites this paper
• Sharing Information with Competitors

  2018cites this paper
• Rational quantum secret sharing

  2018cites this paper
• Self-stabilization Through the Lens of Game Theory

  2018cites this paper
• Outsourcing secret sharing scheme based on homomorphism encryption

  2018cites this paper
• A Rational Exchange Protocol under Asymmetric Information in Wireless Sensor Networks

  2018cites this paper
• Perfectly Secure Message Transmission Against Rational Timid Adversaries

  2018cites this paper
• Doctor of philosophy

  2018cites this paper
• Rational adversary with flexible utility in secure two-party computation

  2018influential citation