Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
In this work, we extend the Constructive Cryptography (CC) framework introduced by Maurer in 2011 so as to handle interactive protocols. We design and construct a so-called {\em Interactive Server Memory Resource} (ISMR), that is an augmented version of the basic instantiation of a client-server protocol in CC, namely the Server Memory Resource. We then apply our ISMR construction to two types of interactive cryptographic protocols for remote storage : Updatable Encryption (UE) and Private Information Retrieval (PIR). Concerning UE, our results are a composable version of those protocols, clarifying the security guarantees achieved by {\em any} UE scheme. Namely, we give the relevant security notion to consider according to a given leakage context. Letting USMR denote our ISMR adapted to the UE application, we prove that
IND-UE-CPA security is sufficient for a secure construction of a confidential USMR that hides the age of ciphertexts; and
IND-(ENC+UPD)-CPA security is sufficient for a secure construction of a confidential USMR in case of unrestricted leakage. As a consequence, contrary to what was claimed before, the
IND-UE security notion is not always stronger than the
IND-(ENC+UPD) one. Concerning PIR, we also give a composable version of PIR protocols, yielding a unique model that unifies different notions of PIR : IT-PIR, C-PIR, one- or multi- server PIR. Using the flexibility of CC, we are also able to model PIR variants, such as SPIR.