### Advanced Cryptography Techniques and Blockchain Applications PhD Thesis Proposal :open_book: Lorenzo Gentile lorg@itu.dk Advisor: Bernardo David beda@itu.dk Note: 15-20 min https://intranet.itu.dk/the-phd-guide/step-by-step/midway-evalutation/on-the-day-of-the-midway-evaluation --- #### About me - PhD Student at ITU :male_elf: - / Cryptographic protocols / Secure multi-party computation (MPC) / Privacy preserving blockchain applications :mag:  --- #### Examples - How can different parties (e.g., tax authorities, hospitals, universities) ==combine their data== to ==extract something useful== while ==preserving privacy== (no third party involved)? :incoming_envelope: - What lies between ==MPC and blockchain==? :chains: --- ## Introduction :open_book: --- #### MPC intro: Yao's Millionaires' problem (1982) - Introduced by computer scientist Andrew Yao: two millionaires, Alice and Bob, are interested in knowing which of them is richer ==without revealing their actual wealth==. ``` a +--------+ Alice ---> | YAO | f(a,b) = 1 if a > b else 0 b | | ---> Bob ---> | | +--------+ ``` - Compute $f(a, b)$ while preserving the privacy of $a$ and $b$. --- ### Blokchain intro: Bitcoin (2008) ``` +----------------------+ +----------------------+ | +-------+ +-------+ | | +-------+ +-------+ | ----->| Prev. | | Nonce | |----->| Prev. | | Nonce | | | | Hash | | (PoW) | | | | Hash | | (PoW) | | | +-------+ +-------+ | | +-------+ +-------+ | | +----+ +----+ +----+ | | +----+ +----+ +----+ | | | Tx | | Tx | | ...| | | | Tx | | Tx | | ...| | | +----+ +----+ +----+ | | +----+ +----+ +----+ | +----------------------+ +----------------------+ ``` A distributed, decentralized and public transaction ledger. Note: Courtesy of Satoshi Nakamoto (2008) --- ### Blockchain intro: GKL model (2014) - Blockchain protocol properties in the GKL model: - Chain Growth - Chain Quality - Common Prefix - Assumption for proving security: the adversary ==can control $< 1/2$ of the computational power invested in solving the PoW puzzle==. Note: - Chain Growth: the chain will grow with at least constant speed (a constant number of new blocks is added to the chain after a constant number of rounds). - Chain Quality: given $k$ blocks in a blockchain, at least $c \cdot k$ blocks were generated by honest parties for a constant $c$ with overwhelming probability. - Common Prefix: the probability that two honest parties see different chains after removing the $k$ last blocks from a chain is negligible in $k$. --- ### Blockchain intro: smart contracts - Smart Contracts allow to describe ==arbitrarily complex conditions== under which transactions might take place among the parties. --- ### MPC and blockchain meeting point - Efficient MPC protocols for specific applications exist, but ==abort== and ==fairness== may be a problem $\rightarrow$ Adopt ==smart contracts== to financially punish cheating parties. - Find a ==tradeoff between privacy and accountability== in cryptocurrency and smart contract systems. --- ## Preliminary results :open_book: --- #### FAST protocol - Parties $P_i$ with $i \in {1,...,n}$. - Bid $b_i = b_{i1}|...|b_{il}$ with $b_{ir} \in \{0,1\}$. ``` b_1 +--------+ ---> | FAST | b_w = max(b_1,...,b_n) ... | | ---> b_n | | P_w sends b_w to the auctioneer ---> | | +--------+ ``` - Compute $max(b_1,...,b_n)$ while preserving the privacy of $b_1,...,b_n$. --- #### Secret deposits (novel technique) - Parties are required to send to a smart contract a ==deposit equal to their bid== plus the cost of running the protocol, thus it is guaranteed that ==funds are available== and ==cheating is not profitable== since it implies loosing the deposit. - The ==privacy of the bids has to be preserved==, thus the ==deposit is secret== (e.g., using ==confidential transactions==). --- #### Computing the winner - (idea) Use bit-by-bit anonymous veto protocol approach and modify input bits according to previous inputs and outputs. ``` b_1 = 1 1 0 1 0 b_2 = 1 1 0 0 1* b_3 = 1 0 1* 1* 1* -------------- v = 1 1 0 1 0 = max(b_1,b_2,b_3) v_r represents veto output in round r ``` - Using ==NIZK== parties have to prove that if $v_r = 1$ but $b_{ir} = 0$ then $b_{ik} = 0$ for $k = r+1,...,l$. --- #### Cheating detection - Parties are required to compute ==publicly verifiable== proofs to guarantee that each step of the protocol is executed correctly. - ==Only if== cheating is detected, a ==recovery stage== is executed with the help of a ==committee==. - The secret deposit is used to ==refund the other parties== or ==complete the payment==. --- #### Extension to second price auction - (idea) Execute again the protocol without the winning party $\mathcal{P}_w$. - (better idea) Once the winning party $\mathcal{P}_w$ is identified, conclude the execution to compute the second price without $\mathcal{P}_w$. - From a game theory perspective, bidding truthfully is a ==dominant strategy==. --- ## Ongoing and future work :open_book: --- #### Secret deposit: efficiency - Currently a trapdoor to spend the secret deposit of a cheating party is secret shared among the members of a committee. - (idea) Encrypt the trapdoor using ==witness encryption== (based on simplyfing assumption, *i.e.*, not for general NP statements) with witness equal to a ==proof that a majority of the members of the committee agree on decrypting the trapdoor==. --- #### Secret deposit: general purpose MPC - Extend the secret deposit technique to the case of ==general purpose MPC==, *i.e.*, computing any function on the private inputs, still with the ==secret deposit being a function of the private inputs==. --- #### PAPR: UC - PAPR (Publicly Auditable Privacy Revocation) is a credential scheme providing both ==conditional privacy of users== and ==public verifiability of correct behavior of a privacy revocation authority==. - Modify current protocol to achieve ==Universal Composability (UC)==. --- ### Time for questions! PhD Thesis Proposal :open_book: Lorenzo Gentile lorg@itu.dk Advisor: Bernardo David beda@itu.dk