Paper 2017/146

Toward Fine-Grained Blackbox Separations Between Semantic and Circular-Security Notions

Mohammad Hajiabadi and Bruce M. Kapron

Abstract

We address the problems of whether t-circular-secure encryption can be based on (t-1)-circular-secure encryption or on semantic (CPA) security, if t = 1. While for t = 1 a folklore construction, based on CPA-secure encryption, can be used to build a 1-circular-secure encryption with the same secret-key and message space, no such constructions are known for the bit-encryption case, which is of particular importance in fully-homomorphic encryption. Also, for $t \geq 2$, all constructions of t-circular-secure encryption (bitwise or otherwise) are based on specific assumptions. We make progress toward these problems by ruling out all fully-blackbox constructions of -- 1-seed circular-secure public-key bit encryption from CPA-secure public-key encryption; -- t-seed circular-secure public-key encryption from (t-1)-seed circular-secure public-key encryption, for any $t \geq 2$. Informally, seed-circular security is a variant of the circular security notion in which the seed of the key-generation algorithm, instead of the secret key, is encrypted. We also show how to extend our first result to rule out a large and non-trivial class of constructions of 1-circular-secure bit encryption, which we dub key-isolating constructions. Our separation model follows that of Gertner, Malkin and Reingold (FOCS’01), which is a weaker separation model than that of Impagliazzo and Rudich.

Note: Fixed some typos.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
Black-box separationscircular security
Contact author(s)
m hajiabadi @ ucl ac uk
History
2017-03-09: last of 2 revisions
2017-02-20: received
See all versions
Short URL
https://ia.cr/2017/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/146,
      author = {Mohammad Hajiabadi and Bruce M.  Kapron},
      title = {Toward Fine-Grained Blackbox Separations Between Semantic and Circular-Security Notions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/146},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/146}},
      url = {https://eprint.iacr.org/2017/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.