CRYPTOGRAPHY - Secure computation
The three main families of secure computation: MPC, FHE and FE.
Contents
See https://www.esat.kuleuven.be/cosic/blog/the-three-musketeers-of-secure-computation-mpc-fhe-and-fe/
MPC
Basics
Secure multi-party computation (also known as secure computation, multi-party computation (MPC), or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. The cryptography in this model protects participants' privacy from each other.
Related to Shamir's 'How to share a secret'.
Intro in 'A Pragmatic Introduction to Secure MPC' by Evans, Kolesnikov and Rosulek.
See also:
The first attempt to realize MPC was by Yao in 1982, who proposed a two-party computation (2PC) protocol based on Garbled Circuits in order to solve the Millionaires’ problem:
MPC can allow to solve problems such as:
- Private set intersection (PSI) of two (or more) parties lists
- Sign a message with a private key, without revealing the private key to any party (splitted among several parties)
- Compute a function on a private input, without revealing the input (shared on several parties)
- Match some orders from remote orderbooks, without revealing the orders (shared on several parties)
- Do survey results aggregation, without revealing the answers (shared on several parties)
- Vote on a secret ballot, without revealing the vote (shared on several parties)
Concepts
- securecomputation.org great intro
- Andrew Yao - Wikipedia
- Garbled circuit - Wikipedia
- Yao is credited for the idea.
- First written document about this technique was by Goldreich, Micali, and Wigderson in STOC'87.
- Yao's principle a way to prove lower bounds on the worst-case performance of randomized algorithms, by comparing them to deterministic (non-random) algorithms.
- Doleve-Yao model 'On the security of public key protocols'
- The adversary can overhear, intercept, and synthesize any message and is only limited by the constraints of the cryptographic methods used. In other words: "the attacker carries the message."
- Yao's millionaire problem Yao's protocol solving Yao's Millionaires' Problem was the beginning example of secure computation, yet it is not directly related to garbled circuits.
Implementations
- github.com - garbled circuits - set of repositories
- github.com - TinyGarble
- Two parts
- Circuit synthesis (output examples of this is stored in scd/netlist/v.tar.bz and will be unzipped and translated in bin/scd/netlist/ after make). Based on upon hardware synthesis and sequential circuit concept and outputs a netlist Verilog (.v) file (not included in this repository).
- Secure function evaluation - a GC framework implemented based on JustGarble project.
- TinyGarble general flow
- Write a Verilog file (.v) describing the function.
- Synthesis the Verilog file using TinyGarble's circuit synthesis to generate a netlist Verilog file (.v).
- Translate the netlist file (.v) to a simple circuit description file (SCD) using TinyGarble's V2SCD_Main and then provide both parties with the file. (We have done steps 1-3 for a number of functions, and you can find their scd files after compiling in bin/scd/netlists/.)
- Execute TinyGarble using --alice flag on one party and --bob flag on the other plus other appropriate arguments.
- github.com - JavaScript MPC RockEngine
- Secured N-parties (N>=2) multi-party computation - using garbled circuits - in golang. The input algorithms are in Javascript, making it easy to use in the browser, or in Node.js.
- Steps
- The function f is written as a JavaScript algorithm.
- One of the users compile the JavaScript file into a logical circuit. This circuit has the .re extension in rockengine.
- A uses this logical circuit to create a garbled circuit, which is equivalent but every input, operations and outputs are encrypted. We denote this garbled circuit as F.
- A sends F to B.
- A encrypts its input x, whose encrypted form we denote X. Hen he sends it to B.
- B encrypts its own input using oblivious transfer with A in order to get the right encrypted value without revealing anything about it. We denote by Y this encrypted input.
- B computes F(X,Y), i.e. he runs the garbled circuit on encrypted inputs. Thus he gets a encrypted output Z.
- A sends part of the decryption key d to B so that he can decrypt a certain part of Z. B sends to A the other part of Z which will also decrypt it. The two can share their information if they want.
Also
FHE - Fully Homomorphic encryption
Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext.
Algorithms such as ElGamal encryption have some homomorphic properties.
Nigel Smart's paper with Gentry and Halevi on performing the first large calculation using Fully Homomorphic Encryption won the IBM Pat Goldberg Best Paper Award for 2012.
Basics
Also
- OpenFHE DARPA involvement
- OpenFHE - github DARPA involvement
- FHE for arithmetic over integers (BFV - Brakerski-Fan-Vercauteren - ring learning with errors)
- FHE for arithmetic over integers (BGV)
- FHE for arithmetic over real numbers (CKKS) a.k.a. Homomorphic Encryption for Arithmetic of Approximate Numbers (HEAAN), was proposed to offer homomorphic computation on real numbers.
- FHE for Boolean circuits and larger plaintext spaces (FHEW/TFHE)
- Threshold FHE
Systems and schemes
- HE standard
- Paillier - Wikipedia
- Invented by and named after Pascal Paillier in 1999
- Is a probabilistic asymmetric algorithm for public key cryptography
- Based on the problem of computing n-th residue classes, i.e. the decisional composite residuosity assumption
- Is an additive homomorphic cryptosystem; this means that, given only the public key and the encryption
of m1 and m2 , one can compute the encryption of m1 + m2.
Applications
- Zama - building applications with FHE
- Inferati - building AI and ML applications with FHE
Nigel Smart et al.
Functional encryption
Functional encryption (FE) is a generalization of public-key encryption in which possessing a secret key allows one to learn a function of what the ciphertext is encrypting.
E-voting
Local info
Refer to crypto other applications for additional info.
E-voting basics
E-voting crypto
Methods include:
- Using blind signatures (Chaum, Okamoto-Fujisaki-Ohta)
- Cryptographic counters, as in additively homomorphic encryption e.g. (Paillier '97)
- Mix nets, e.g. Neff mix