Ideal Objects: Is there such a thing as an Ideal Functionality with persistent memory?

de flag

In general, proofs of security for secure Multiparty Computation are based on Ideal Functionalities. For instance, see Definition 4.1 of this Simulator tutorial.

However, in a regular program in an object-oriented programming language, one deals not only with functions but with objects. Objects have functions, but also have some persistent memory.

It is possible to implement MPC objects. For instance this paper implements oblivious (i.e. MPC) arrays, dictionaries and priority queues. In these memory is persisted in a secret-shared manner which is accessed for future queries.

However, it seems that formalism for these objects is lacking. Intuitively, an MPC object should not reveal any more information than calls to some Ideal Object, which returns only (secret-shares of) the results to (secret-shared) queries on the object. Describing an Ideal Object as a sequences of calls to Ideal Functionalities does not work, because in-between the parties get correlated shares of data-structures, and so the functionalities have to be defined in reference to whatever data structure is used, rather than just in terms of the desired properties of the object.

Is there any formalism in the literature for how to prove security of MPC objects?

us flag

The term you're looking for is called reactive. A reactive functionality receives inputs and gives outputs over many rounds. In between rounds, it maintains a private internal state. The usual MPC frameworks like UC already support reactive functionalities, so there is nothing special you need to do to use them.


  • The commitment functionality is a standard primitive, and often called a "cryptographic locked box." In the commit phase, the sender provides a secret value to the functionality; in a later reveal phase, the sender allows the receiver to learn that secret value. Between these phases the functionality stores the secret value in its private state.

  • The arithmetic black box (ABB) was introduced here. It is a useful abstraction for defining many MPC protocols. The ABB functionality allows parties to initialize variables and then blindly perform operations on them. The functionality is usually achieved by using some kind of secret sharing protocol, but the functionality's specification only talks about an ideal collection of variables and operations on them.


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.