Paper 2015/715

New Circular Security Counterexamples from Decision Linear and Learning with Errors

Allison Bishop, Susan Hohenberger, and Brent Waters

Abstract

We investigate new constructions of n-circular counterexamples with a focus on the case of n=2. We have a particular interest in what qualities a cryptosystem must have to be able to separate such circular security from IND-CPA or IND-CCA security. To start, we ask whether there is something special about the asymmetry in bilinear groups that is inherent in the works of ABBC10 and CGH12 or whether it is actually the bilinearity that matters. As a further question, we explore whether such counterexamples are derivable from other assumptions such as the Learning with Errors (LWE) problem. If it were difficult to find such counterexamples, this might bolster are confidence in using 2-circular encryption as a method of bootstrapping Fully Homomorphic Encryption systems that are based on lattice assumptions. The results of this paper broadly expand the class of assumptions under which we can build 2-circular counterexamples. We first show for any constant k >= 2 how to build counterexamples from a bilinear group under the decision k-linear assumption. Recall that the decision k-linear assumption becomes progressively weaker as k becomes larger. This means that we can instantiate counterexamples from symmetric bilinear groups and shows that asymmetric groups do not have any inherently special property needed for this problem. We then show how to create 2-circular counterexamples from the Learning with Errors problem. This extends the reach of these systems beyond bilinear groups and obfuscation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
circular securityencryptionDecision LinearLearning with Errors
Contact author(s)
susan @ cs jhu edu
History
2015-12-01: last of 2 revisions
2015-07-18: received
See all versions
Short URL
https://ia.cr/2015/715
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/715,
      author = {Allison Bishop and Susan Hohenberger and Brent Waters},
      title = {New Circular Security Counterexamples from Decision Linear and Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2015/715},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/715}},
      url = {https://eprint.iacr.org/2015/715}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.