CryptoDB
Adam O'Neill
Publications
Year
Venue
Title
2021
PKC
On Selective-Opening Security of Deterministic Primitives
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.
2011
CRYPTO
2008
CRYPTO
2008
CRYPTO
Program Committees
- PKC 2021
- Crypto 2020
- PKC 2017
- Eurocrypt 2016
- PKC 2015
- Eurocrypt 2014
- PKC 2012
Coauthors
- Mihir Bellare (2)
- Allison Bishop (1)
- Alexandra Boldyreva (4)
- Angelo De Caro (2)
- Nathan Chenette (2)
- Dana Dachman-Soled (2)
- Serge Fehr (1)
- Marc Fischlin (1)
- Georg Fuchsbauer (1)
- Benjamin Fuller (2)
- Michael Gerbush (1)
- S. Dov Gordon (1)
- Vipul Goyal (2)
- Viet Tung Hoang (1)
- Vincenzo Iovino (2)
- Abhishek Jain (1)
- Aayush Jain (1)
- Jonathan Katz (1)
- Eike Kiltz (3)
- Younho Lee (1)
- Mark Lewko (1)
- Feng-Hao Liu (1)
- Payman Mohassel (2)
- Omer Paneth (1)
- Chris Peikert (1)
- Giuseppe Persiano (1)
- Vanishree Rao (1)
- Leonid Reyzin (2)
- Thomas Ristenpart (1)
- Adam Smith (3)
- Brent Waters (2)
- Mohammad Zaheri (2)
- Hong-Sheng Zhou (1)