This doctoral dissertation presents contributions advancing the state-of-the-art of secure two-party computation (S2PC) — a cryptographic primitive that allows two mutually distrustful parties, with respective private inputs, to evaluate a function of their combined input, while ensuring privacy of inputs and outputs and integrity of the computation, externally indistinguishable from an interaction mediated by a trusted party. The dissertation shows that S2PC can be made more practical by means of innovative cryptographic techniques, namely by engineered use of commitment schemes with special properties, enabling more efficient protocols, with provable security and applicable to make systems more dependable. This is one further step toward establishing S2PC as a practical tool for privacy-preserving applications. The main technical contribution is a new protocol for S2PC of Boolean circuits, based on an innovative technique called forge-and-lose.1 Building on top of a traditional cut-and-choose of garbled circuits (cryptographic versions of Boolean circuits), the protocol improves efficiency by reducing by a factor of approximately 3 the needed number of garbled circuits. This significantly reduces a major communication component of S2PC with malicious parties, for circuits of practical size. The protocol achieves simulatable S2PC-with-commitments, producing random commitments of the circuit input and output bits of both parties. The commitments also enable direct linkage of several S2PCs in a malicious adversarial setting. As second result, the dissertation describes an improvement to the efficiency of one of the needed sub-protocols: simulatable two-party coin-flipping.1 The sub-protocol is based on a new universally composable commitment scheme that for bit-strings of increasing size can achieve an asymptotic communication-complexity rate arbitrarily close to 1. The dissertation then discusses how S2PC-with-commitments can enable in brokered identification systems a difficult-to-achieve privacy property — a kind of unlinkability.1 This mitigates a vector of potential mass surveillance by an online central entity (a hub), which is otherwise empowered in systems being developed at nation scale for authentication of citizens. When the hub mediates between identity providers and service providers the authentication of users, an adequate S2PC (e.g., of a block-cipher) can prevent the hub from learning user pseudonyms that would allow linking transactions of the same user across different services providers. 1 Parts of these contributions were previously presented at ASIACRYPT 2013, PETS 2015 and PKC 2016.

<div>Multiparty computation refers to a scenario in which multiple distinct yet connected parties aim to jointly compute a functionality. Over recent decades, with the rapid spread of the internet and digital technologies, multiparty computation has become an increasingly important topic. In addition to the integrity of computation in such scenarios, it is essential to ensure that the privacy of sensitive information is not violated. Thus, secure multiparty computation aims to provide sound approaches for the joint computation of desired functionalities in a secure manner: Not only must the integrity of computation be guaranteed, but also each party must not learn anything about the other parties' private data. In other words, each party learns no more than what can be inferred from its own input and its prescribed output.</div><div><br></div><div> This thesis considers secure two-party computation over arithmetic circuits based on additive secret sharing. In particular, we focus on efficient and secure solutions for fundamental functionalities that depend on the equality of private comparands. The first direction we take is providing efficient protocols for two major problems of interest. Specifically, we give novel and efficient solutions for <i>private equality testing</i> and multiple variants of <i>secure wildcard pattern matching</i> over any arbitrary finite alphabet. These problems are of vital importance: Private equality testing is a basic building block in many secure multiparty protocols; and, secure pattern matching is frequently used in various data-sensitive domains, including (but not limited to) private information retrieval and healthcare-related data analysis. The second direction we take towards a performance improvement in equality-based secure two-party computation is via introducing a generic functionality-independent secure preprocessing that results in an overall computation and communication cost reduction for any subsequent protocol. We achieve this by providing the first precise functionality formulation and secure protocols for replacing original inputs with much smaller inputs such that this replacement neither changes the outcome of subsequent computations nor violates the privacy of sensitive inputs. Moreover, our input-size reduction opens the door to a new approach for efficiently solving Private Set Intersection. The protocols we give in this thesis are typically secure in the semi-honest adversarial threat model.</div>