RFID (Radio Frequency Identification) technology has been used on a large scale in various applications such as payments, supply chain management, medical devices, and electronic passports. However, the emergence of this technology has also raised kinds of security and privacy issues. This thesis focuses on cryptographic tools to deal with the most prevalent security and privacy concerns in RFID systems. The first part of this dissertation discusses distance bounding protocols, a special kind of authentication protocols which can be applied to determine an upper bound on the physical distance between two parties. These protocols play a crucial role for the security of proximity identification systems such as RFID systems. Among the RFID distance bounding protocols in the literature, besides defending against various attacks such as impersonation, distance fraud, Mafia attack, terrorist attack, and distance hijacking, some also support mutual authentication and tag privacy protection. Due to the requirements of being lightweight, low-cost, and efficient, it is the common objective to design new RFID distance bounding protocols which require fewer message ows and less complex cryptographic operations, while maintaining or enhancing the security and privacy of the protocols. We propose three new RFID distance bounding protocols, among which the firrst protocol achieves mutual authentication, supports the untraceability of RFID tags, and resists all the attacks above except for terrorist frauds by having only one slow transmission phase. The second and the third protocols prevent all the above attacks, provide mutual authentication, and provide tags' privacy. In addition, in the second and the third protocols, we consider pre-computation by using a large capacitor to store the DC voltage that can be used to power the tag in order to make the computation in slow phase offline. This means that there is no significant cryptographic calculation online, which shortens the execution time and decreases the period that the reader needs to transmit an RF carrier to power the tag. We put forward a brand new kind of response function in the third protocol, which lows the success probability of all the attacks to a near-optimal value. To the best of our knowledge, this is the first protocol which can achieve this with high efficiency. Then, we explore how to extend one-hop distance-bounding to twohop case. To do this, we present a general model. Furthermore, we provide a detailed security analysis for two-hop distance-bounding protocols and we make simulations to verify the correctness of our theoretical analysis. The second part of the thesis is dedicated to the privacy of RFID authentication protocols. Ind-privacy and unp-privacy, later refined to unp*-privacy, are two main classes of models for formalizing the privacy of RFID authentication protocols. These models capture many practical attacks related to the privacy aspect of RFID authentication protocols such as anonymity and untraceability. However, there is a class of attacks that are practical but yet to be captured. Through sidechannel attacks, we show that it is feasible and very practical for an adversary to observe the responses of RFID tags and readers which are running some RFID authentication protocols. This adversarial capability can be used to compromise the privacy of some RFID authentication protocols, which have been proven secure in the existing privacy models. We extend the unp*-privacy model to a new variant called unpτ-privacy which captures this attack. We further propose a concrete and efficient RFID authentication protocol and prove its security in this new unpτ-privacy model. Furthermore, we extend our privacy model to support forward privacy which requires the previous transactions of a tag remain untraceable even after it is corrupted. We call the new unpredictability-based forward privacy model unpfτ-privacy. Similarly, we present an RFID authentication protocol and prove that it supports forward privacy under the unpfτ-privacy model.