A memory system, comprising: an interface configured to communicate over an unsecured communication link (LINK) with a host external to the memory system; a non-volatile memory pre-programmed with at least a device identifier (DEV-ID) and a corresponding initialization key (I-KEY), wherein the device identifier (DEV-ID) and the respective initialization key (I-KEY) are additionally stored in a database external to the memory system, the database is securely accessible by the host; and a controller configured to: send the device identifier (DEV-ID) to the host; receive from the host, via the interface, binding information (BINDING INFO) that was generated in the host; generate, using at least the received binding information (BINDING INFO) and the pre-programmed initialization key, a first binding key that matches a second binding key, wherein the second binding key is generated in the host based on the initialization key (I-KEY) securely obtained by the host from the database by querying the database using the device identifier (DEV-ID) received from the controller; and securely communicate with the host over the communication link (LINK) using the first binding key, wherein the controller is configured to receive a memory signature calculated over pre-programmed content of the non-volatile memory, to authenticate actual content of the non-volatile memory using the memory signature, and to use the first binding key for communicating with the host only if the memory signature was authenticated successfully, wherein the database stores the memory signature in association with the device identifier (DEV-ID), and wherein the controller is configured to receive, from the host, the memory signature that was retrieved by the host from the database using the device identifier (DEV-ID). an interface configured to communicate over an unsecured communication link (LINK) with a host external to the memory system; a non-volatile memory pre-programmed with at least a device identifier (DEV-ID) and a corresponding initialization key (I-KEY), wherein the device identifier (DEV-ID) and the respective initialization key (I-KEY) are additionally stored in a database external to the memory system, the database is securely accessible by the host; and a controller configured to: send the device identifier (DEV-ID) to the host; receive from the host, via the interface, binding information (BINDING INFO) that was generated in the host; generate, using at least the received binding information (BINDING INFO) and the pre-programmed initialization key, a first binding key that matches a second binding key, wherein the second binding key is generated in the host based on the initialization key (I-KEY) securely obtained by the host from the database by querying the database using the device identifier (DEV-ID) received from the controller; and securely communicate with the host over the communication link (LINK) using the first binding key, send the device identifier (DEV-ID) to the host; receive from the host, via the interface, binding information (BINDING INFO) that was generated in the host; generate, using at least the received binding information (BINDING INFO) and the pre-programmed initialization key, a first binding key that matches a second binding key, wherein the second binding key is generated in the host based on the initialization key (I-KEY) securely obtained by the host from the database by querying the database using the device identifier (DEV-ID) received from the controller; and securely communicate with the host over the communication link (LINK) using the first binding key, wherein the controller is configured to receive a memory signature calculated over pre-programmed content of the non-volatile memory, to authenticate actual content of the non-volatile memory using the memory signature, and to use the first binding key for communicating with the host only if the memory signature was authenticated successfully, wherein the database stores the memory signature in association with the device identifier (DEV-ID), and wherein the controller is configured to receive, from the host, the memory signature that was retrieved by the host from the database using the device identifier (DEV-ID).