Cryptography allows us to do magical things ranging from private communication over a public channel to securely evaluating functions among distrusting parties. For the real-world implementation of these tasks, efficiency is usually one of the most desirable objectives. In this work, we advance our understanding of efficient cryptographic constructions on several fronts.<div><br></div><div>Non-malleable codes are a natural generalization of error-correcting codes. It provides a weaker yet meaningful security guarantee when the adversary may tamper with the codeword such that error-correcting is impossible. Intuitively, it guarantees that the tampered codeword either encodes the original message or an unrelated one. This line of research aims to construct non-malleable codes with a high rate against sophisticated tampering families. In this work, we present two results. The first one is an explicit rate1 construction against all tampering functions with a small locality. Second, we present a rate-1/3 construction for three-split-state tampering and two-lookahead tampering.</div><div><br></div><div>In multiparty computation, fair computation asks for the most robust security, namely, guaranteed output delivery. That is, either all parties receive the output of the protocol, or no party does. By relying on oblivious transfer, we know how to construct MPC protocols with optimal fairness. For a long time, however, we do not know if one can base optimal fair protocol on weaker assumptions such as one-way functions. Typically, symmetric-key primitives (e.g., one-way functions) are much faster than public-key primitives (e.g., oblivious transfer). Hence, understanding whether one-way functions enable optimal fair protocols has a significant impact on the efficiency of such protocols. This work shows that it is impossible to construct optimal fair protocols with only black-box uses one-way functions. We also rule out constructions based on public-key encryptions and f-hybrids, where f is any incomplete function.</div><div><br></div><div>Collective coin-tossing considers a coin-tossing protocol among n parties. A Byzantine adversary may adaptively corrupt parties to bias the output of the protocol. The security ε is defined as how much the adversary can change the expected output of the protocol. In this work, we consider the setting where an adversary corrupts at most one party. 10 Given a target security ε, we wish to understand the minimum number of parties n required to achieve ε-security. In this work, we prove a tight bound on the optimal security. In particular, we show that the insecurity of the well-known threshold protocol is at most two times the optimal achievable security. </div>

<p dir="ltr">This thesis presents an in depth study and evaluation of a class of secure multiparty protocols that enable execution of a confidential software program $\mathcal{P}$ owned by Alice, on confidential data $\mathcal{D}$ owned by Bob, without revealing anything about $\mathcal{P}$ or $\mathcal{D}$ in the process. Our initial adverserial model is an honest-but-curious adversary, which we later extend to a malicious adverarial setting. Depending on the requirements, our protocols can be set up such that the output $\mathcal{P(D)}$ may only be learned by Alice, Bob, both, or neither (in which case an agreed upon third party would learn it). Most of our protocols are run by only two online parties which can be Alice and Bob, or alternatively they could be two commodity cloud servers (in which case neither Alice nor Bob participate in the protocols' execution - they merely initialize the two cloud servers, then go offline). We implemented and evaluated some of these protocols as prototypes that we made available to the open source community via Github. We report our experimental findings that compare and contrast the viability of our various approaches and those that already exist. All our protocols achieve the said goals without revealing anything other than upper bounds on the sizes of program and data.</p><p><br></p>