Individual Cryptography

We initiate a formal study of individual cryptography. Informally speaking, an algorithm $\mathsf{Alg}$ is "individual" if, in every implementation of $\mathsf{Alg}$, there always exists an individual user with full knowledge of the cryptographic data $S$ used by $\mathsf{Alg}$. In particular, it should be infeasible to design implementations of this algorithm that would hide $S$ by distributing it between a group of parties using an MPC protocol or outsourcing it to a trusted execution environment.

We define and construct two primitives in this model. The first one, called "proofs of individual knowledge", is a tool for proving that a given message is fully known to a single ("individual") machine on the Internet, i.e., it cannot be shared between a group of parties. The second one, dubbed "individual secret sharing", is a scheme for sharing a secret $S$ between a group of parties so that the parties have no knowledge of $S$ as long as they do not reconstruct it. The reconstruction ensures that if the shareholders attempt to collude, one of them will learn the secret entirely. Individual secret sharing has applications for preventing collusion in secret sharing. A central technique for constructing individual cryptographic primitives is the concept of MPC hardness. MPC hardness precludes an adversary from completing a cryptographic task in a distributed fashion within a specific time frame.