# Tore's current projects and ideas
I will here try to outline the current, recently finished and potential research projects, which I believe might be of interest to Protocol Labs.

---

## Cross-chain privacy preserving smart contracts
*Finished project with potential for extension*
Two main challenges of web3 is the inherent lack of decentralized cross-chain communication and privacy on smart contracts. Many companies and works have tried to handle these issues in different ways.
For cross-chain communication, Chainlink might be one of the biggest contenders in the space, through the use of somewhat trusted oracles, that relays information from one chain onto the other.
For privacy many works and systems try to achieve this by adding zero knowledge proofs. Unfortunately, this inherently only allows privacy in showing statements about private data, but does not directly facility computation on private data.

One specific case where the need for both cross-chain communication and the need for private computation comes up, is when trying to do order matching or auctions of digital goods, residing on distinct chains. This generalises to the problem of exchanging different tokens on different chains, in a way that prevents front-running.

In our work (in collaboration with Carsten Baum, Bernardo David and James Hsin-yu Chiang) we try to tackle both the blockchain issues at the same time through the use of MPC, by leveragning a small set of servers. The servers can act maliciously, but are financially incentivised (through ante on a smart contract) to be available and behaving honestly. Security of the entire system is fulfilled as long as not *all* servers maliciously collude.

In our [first paper](https://eprint.iacr.org/2021/283.pdf), P2DEX, we construct such a system by having all the servers create and hold threshold keys for burner addresses. Concretely the servers create a burner address on each blockchain for each client wish to give input/tokens to. The clients then transfers their tokens to their burner address and give auxiliary, private input to all the servers through an ["outsourced MPC" protocol](https://eprint.iacr.org/2016/037.pdf).
The servers then execute the desired MPC protocol. This could for example be a limit order matching, on tokens which a client wishes to exchange on chain A, to tokens on another chain B.
Based on the output of the MPC computation the servers threshold sign transfers out of the burner addresses to the appropriate clients and post these transactions to the relevant blockchains.
By doing the order matching in MPC, it means that neither the servers, nor miners are able to front-run the exchange, since they only learn about the clearing price once the order have been matched.

In a [follow-up work called Eagle](https://eprint.iacr.org/2022/1435), currently in submission, we enhance the above solution by adding support for computation on hidden token amounts, besides just hidden auxiliary input.
We achieve this by adding a second layer for confidential transfers, on top of any Turing complete smart contracting language. This approach uses Pedersen commitments to hidden token amounts. These commitments can be minted or burned by a holding smart contract.
Clients can thus exchange native tokens for their hidden counterparts using this contract. The hidden tokens can then be used as input to an MPC computation. As part of the MPC computation, the servers compute new hidden token amounts, and ask the holding smart contract to mint these and transfer them to the appropriate clients.
The servers can administrate the holding smart contract using a threshold signing key.
The protocol involves a bit more cumbersome techniques, such as Schnorr and range proofs which are described in the paper.

We tried to implement a minimal integration of this, but did not manage to finalise it due to limited funding. So when it comes to future work, it would be very interesting to do a full proof-of-concept implementation along with researching additional optimisations in relation to storing commitment opening information in a user-friendly manner and optimise the needed ZKPs.

## More efficient distributed RSA key generation
*Work in progress with Claudio Orlandi, Ivan Damgård, Jakob Burkhardt and Satrajit Ghosh*
The generation of RSA moduli, for which no single party knows the factorisation has many useful applications. The most straight-forward application is decentralised key management, which can be used to realise systems such as HSM-in-the-cloud as done by Unbound (recently purchased by Coinbase) or [Sepior](https://sepior.com) (recently purchased by Blochdaemon).
However, other stand-alone applications exist, such as [Verifiable Delay Functions](https://eprint.iacr.org/2018/623.pdf).

While the problem can be solved using generic multiparty computation, this unfortunately leads to huge runtimes. The reason is that it is hard to pick random large prime numbers. Thus many random candidates must be picked and then validated to be prime. This requires big-integer arithmetic to be performed in MPC, including exponentiations and modulo operations to perform Fermat's primality test.
Since this is so inefficient, much research has been carried out in finding protocols for sampling random RSA moduli in a distributed manner.
These protocols consist of multiple phases, rejecting more and more potential prime numbers, and finally ending in a test where a given N is validated to be the product of 2 primes. This can be validated in a relatively efficient manner when p and q are distributed into additive shares and N=p\*q.
Performing this check turns out to be the bottle neck in computing distributed RSA moduli.
However, even the fastest protocols still leave a lot to be desired in efficiency.

We have tried to optimise this phase by revisiting an old distributed RSA prime generation protocol by [Mikkelsen and Damgård](https://link.springer.com/content/pdf/10.1007/978-3-642-11799-2_12.pdf).
This protocol only requires O(n) exponentiations, where n is the amount of parties participating. This is generally less than the the most efficient alternative presented by [Boneh and Franklin.](https://link.springer.com/content/pdf/10.1007/BFb0052253.pdf) which requires O(s) exponentiations for statistical security s, *and* requires a general secure computation over big-integers.

Unfortunately the protocol by Damgård and Mikkelsen only works in the honest majority setting and only for 3 parties.
In this work we explore multiple ideas to generalise this to work in the generic dishonest majority setting for any amount of parties. To do so we develop multiple tricks, while avoiding the need to emulate big-integer arithmetic in MPC. Instead we only rely on O(n) calls to a generic multiplication protocol on secret shares, which can be realised using either oblivious transfer or additive homomorphic encryption.
Our work achieves security in the semi-honest model, although we note that since there is no private input to RSA modulus generation, this can trivially be compiled to a covert secure protocol.
We particularly believe the advantage of our approach is its simplicity and lack of needing to emulate generic big-integer computation in MPC.

We are still writing down the work, although we already have the essential proofs sketched. However, we still lack an implementation and benchmarks showing superiority over the alternatives in this model.
Furthermore, it would be interesting to do more research in investigating if this could be done in a maliciously secure model or in a more efficient covert manner.

## Succinct distributed set-membership
*Research idea*
Set-membership and set-non-membership are two essential operations that comes up a lot, both on the internet and in web3. For example the need to validate that a certificate/public key has not been revoked or that a user hold a credential on an approve-list. Such operations are easy to do in plain in a compact manner e.g. through a Merkle-tree or simply a hash map.
However, in many situations we might wish to be able to do this in a privacy preserving manner. For example if someone wants to prove to a smart contract that they are part of an approved set, without leaking which entry on the approved set they fulfil.

A few years ago Sophia Yakoubov and I looked at how achieve this through the use of a secret shared algebraic accumulator. While we generally succeeded in achieving anonymity, we could not succeed in avoiding client interaction if the set got updated.
While not all use-cases require set updates, it greatly impacts the usability of set-membership if the set can never change.
However [a paper](https://eprint.iacr.org/2020/724.pdf) came out some time ago leading to some new inspiration on how to distribute an accumulator in an efficient manner. While their contributions do not trivially allow for efficient updates using the ideas of Sophia and myself, another recent paper of mine and some other colleagues lead to a possible solution:
1. Secret share the trapdoor of an MPC friendly accumulator.
2. Let all users receive an information theoretic MAC on their ID and membership data, constructed in a distributed manner by the servers.
3. Later the users can reuse their MAC to prove to the servers that they have been authenticated and have the servers collaboratively, and blindly construct shares of an accumulator witness to the user's element.
4. The user reconstruct the actual witness and can now use this to succinctly prove membership/non-membership.

In the solution above the computation of the witness is outsourced to the servers, who are already aware of the elements in the set. The crucial part of this construction is that the client is authenticated towards the servers in a way they can validate blindly and that the value they have authenticated towards the client can be piped into the construction of an accumulator witness. This is crucial as the private key of an algebraic accumulator could be used to construct a incorrect witness.

A concrete and interesting application of this could be a whistle blowing solution where the whistle blower can be validated to be from a specific organisation or department, without a risk of leaking who they actually are.

## Exploding commitments
*Project idea, partially started by colleagues*
Money laundering is a big issue in the world! Currently banks and other financial institutions do very little to prevent this as doing more would require sharing personal information about account holders and account traffic with other banks.
However, in many situations money laundering through mixing and smurfing can be detected by keeping track of a "suspiciousness" score and flagging accounts or transfers, if the score gets too high.
Such a suspiciousness score could be computed in MPC between two banks whenever a transfer happens.
Unfortunately with the quantity of transfers this would be very inefficient. It would also have the downside that a single malicious bank could input malicious information to try to extract information about the recipient based on whether the transfer gets flagged or not.

In this project we propose another way of carrying out such operations, which we believe might be interesting in other settings as well.
Constructing commitments to data in a limited, and special homomorphic manner, can allow scores to be incremented in a verifiable manner. A creative construction can also ensure that comparing the score in a commitment to a limit can only be done in a threshold manner; thus preventing a single malicious party from trying to modify a commitment and checking the threshold, and extracting information this way.

## Other ongoing projects
I have a few other projects I am part of which I don't think are as relevant to PL as the other, but I am listing them here for completeness.

### Efficient truncation in MPC
In the setting of secure computation with decimal numbers, which for example occurs in the ML settings, fix-point numbers are usually used. This means that a truncation is needed after every multiplication. Unfortunately truncations are very inefficient and requires many multiplications. In collaboration with Jonas Lindstrøm, Anne Dorte Spangsberg and Mikkel Madsen we have an idea of doing MPC using residue number systems, which allows for certain efficient truncations which can be modified for general truncations efficiently.

### Reusable garbled circuits
An approach to efficient reusable garbled circuits in the semi-honest client-server model was [recently introduced](https://eprint.iacr.org/2022/751.pdf). While being able to be build on standard assumptions such as the discrete log problem, it is quite inefficient and for example requires 256 group elements and exponentiations for each cipher-text.
We have ideas to get this down to a constant amount of group elements, using a construction that can afford efficient zero-knowledge proofs, thus opening the option for constructing such client-server garbled circuits in a maliciously secure manner.