CryptoDB
On Selective-Opening Security of Deterministic Primitives
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Classically, selective-opening attack (SOA) has been studied for \emph{randomized} primitives, like randomized encryption schemes and commitments. The study of SOA for deterministic primitives, which presents some unique challenges, was initiated by Bellare \emph{et al.} (PKC 2015), who showed negative results. Subsequently, Hoang \emph{et al.} (ASIACRYPT 2016) showed positive results in the non-programmable random oracle model. Here we show the first positive results for SOA security of deterministic primitives in the \emph{standard} (RO devoid) model. Our results are: \begin{itemize} \item Any $2t$-wise independent hash function is SOA secure for an unbounded number of ``$t$-correlated'' messages, meaning any group of up to $t$ messages are arbitrarily correlated. \item A construction of a deterministic encryption scheme with analogous security, combining a regular lossy trapdoor function with a $2t$-wise independent hash function. \item The one-more-RSA problem of Bellare \emph{et al.} (J.~Cryptology 2003), which can be seen as a form of SOA, is hard under the $\Phi$-Hiding Assumption with large enough encryption exponent. \end{itemize} Somewhat surprisingly, the last result yields the first proof of RSA-based Chaum's blind signature scheme (CRYPTO 1982) based on a ``standard'' computational assumption. Notably, it avoids the impossibility result of Pass (STOC 2011) because lossiness of RSA endows the scheme with non-unique signatures. |
BibTeX
@article{pkc-2021-31007,
title={On Selective-Opening Security of Deterministic Primitives},
booktitle={Public-Key Cryptography - PKC 2021},
publisher={Springer},
doi={10.1007/978-3-030-75248-4_6},
author={Adam O'Neill and Mohammad Zaheri},
year=2021
}