Traditionally, cryptographic algorithms are designed under the so-called black-box model, which considers adversaries that receive black-box access to the hardware implementation. Although a "black-box" treatment covers a wide range of attacks, it fails to capture reality adequately, as real-world adversaries can exploit physical properties of the implementation, mounting attacks that enable unexpected, non-black-box access, to the components of the cryptographic system. This type of attacks is widely known as physical attacks, and has proven to be a significant threat to the real-world security of cryptographic systems. The present dissertation is (partially) dealing with the problem of protecting cryptographic memory against physical attacks, via the use of non-malleable codes, which is a notion introduced in a preceding work, aiming to provide privacy of the encoded data, in the presence of adversarial faults. In the present thesis we improve the current state-of-the-art on non-malleable codes and we provide practical solutions for protecting real-world cryptographic implementations against physical attacks. Our study is primarily focusing on the following adversarial models: (i) the extensively studied split-state model, which assumes that private memory splits into two parts, and the adversary tampers with each part, independently, and (ii) the model of partial functions, which is introduced by the current thesis, and models adversaries that access arbitrary subsets of codeword locations, with bounded cardinality. Our study is comprehensive, covering one-time and continuous, attacks, while for the case of partial functions, we manage to achieve a stronger notion of security, that we call non-malleability with manipulation detection, that in addition to privacy, it also guarantees integrity of the private data. It should be noted that, our techniques are also useful for the problem of establishing, private, keyless communication, over adversarial communication channels. Besides physical attacks, another important concern related to cryptographic hardware security, is that the hardware fabrication process is assumed to be trusted. In reality though, when aiming to minimize the production costs, or whenever access to leading-edge manufacturing facilities is required, the fabrication process requires the involvement of several, potentially malicious, facilities. Consequently, cryptographic hardware is susceptible to the so-called hardware Trojans, which are hardware components that are maliciously implanted to the original circuitry, having as a purpose to alter the device's functionality, while remaining undetected. Part of the present dissertation, deals with the problem of protecting cryptographic hardware against Trojan injection attacks, by (i) proposing a formal model for assessing the security of cryptographic hardware, whose production has been partially outsourced to a set of untrusted, and possibly malicious, manufacturers, and (ii) by proposing a compiler that transforms any cryptographic circuit, into another, that can be securely outsourced.

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>