Mohammad Hassan Ameri

Mohammad Hassan Ameri, Jeremiah Blocki

We introduce the notion of a conditional encryption scheme as an extension of public key encryption. In addition to the standard public key algorithms ($\mathsf{KG}$, $\mathsf{Enc}$, $\mathsf{Dec}$) for key generation, encryption and decryption, a conditional encryption scheme for a binary predicate $P$ adds a new conditional encryption algorithm $\mathsf{CEnc}$. The conditional encryption algorithm $c=\mathsf{CEnc}_{pk}(c_1,m_2,m_3)$ takes as input the public encryption key $pk$, a ciphertext $c_1 = \mathsf{Enc}_{pk}(m_1)$ for an unknown message $m_1$, a control message $m_2$ and a payload message $m_3$ and outputs a conditional ciphertext $c$. Intuitively, if $P(m_1,m_2)=1$ then the conditional ciphertext $c$ should decrypt to the payload message $m_3$. On the other hand if $P(m_1,m_2) = 0$ then the ciphertext should not leak any information about the control message $m_2$ or the payload message $m_3$ even if the attacker already has the secret decryption key $sk$. We formalize the notion of conditional encryption secrecy and provide concretely efficient constructions for a set of predicates relevant to password typo correction. Our practical constructions utilize the Paillier partially homomorphic encryption scheme as well as Shamir Secret Sharing. We prove that our constructions are secure and demonstrate how to use conditional encryption to improve the security of personalized password typo correction systems such as TypTop. We implement a C++ library for our practically efficient conditional encryption schemes and evaluate the performance empirically. We also update the implementation of TypTop to utilize conditional encryption for enhanced security guarantees and evaluate the performance of the updated implementation.

Mohammad Hassan Ameri, Jeremiah Blocki, Samson Zhou

Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive key-derivation functions resistant to brute-force attacks. Broadly speaking, MHFs can be divided into two categories: data-dependent memory hard functions (dMHFs) and data-independent memory hard functions (iMHFs). iMHFs are resistant to certain side-channel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive input e.g., password. While dMHFs are potentially vulnerable to side-channel attacks (the induced memory access pattern might leak useful information to a brute-force attacker), they can achieve higher cumulative memory complexity (CMC) in comparison than an iMHF. In this paper, we introduce the notion of computationally data-independent memory hard functions (ciMHFs). Intuitively, we require that memory access pattern induced by the (randomized) ciMHF evaluation algorithm appears to be independent from the standpoint of a computationally bounded eavesdropping attacker --- even if the attacker selects the initial input. We then ask whether it is possible to circumvent known upper bound for iMHFs and build a ciMHF with CMC $Ω(N^2)$. Surprisingly, we answer the question in the affirmative when the ciMHF evaluation algorithm is executed on a two-tiered memory architecture (RAM/Cache). See paper for the full abstract.