\documentclass[runningheads]{llncs}

\usepackage{amsmath} 
\usepackage{amssymb} 
\synctex=1 
\usepackage{multirow}
\usepackage{todonotes} 
%\usepackage{framed} 
%\usepackage{float}
 \usepackage[strings]{underscore}
 \usepackage{breakcites}

\renewcommand{\labelenumi}{\arabic{enumi}.}
\renewcommand{\labelenumii}{\labelenumi\arabic{enumii}.}
\renewcommand{\labelenumiii}{\labelenumii\arabic{enumiii}}

\usepackage[colorlinks=true, citecolor=blue]{hyperref}

\hyphenation{pri-mi-tive pri-mitive}
 
 
 

  
%To choose between versions simply uncoment the chosen one, and comment the rest 
%\def\eprintVersion{} 
%\def\IACRSubmission{}
\def\IACRSubmissionAlpha{}

\ifdefined\eprintVersion 
  \def\longAlphaBibliography{}
  \newcommand{\append}{Appendix}
\fi

\ifdefined\IACRSubmission
  \def\anonymous{}
  \def\shortLNCSBibliography{} 
  \newcommand{\append}{Supplementary Material}
\fi

\ifdefined\IACRSubmissionAlpha
 % \def\anonymous{}
  \def\longAlphaBibliography{} 
  \newcommand{\append}{(FULL)}
\fi

% Command to indicate whether we write Supplementary Material or Appendix 
 
 
  
\input{commands}

\title{Lockable Obfuscation from Circularly Insecure Fully Homomorphic Encryption}
\titlerunning{Lockable Obfuscation from Circularly Insecure FHE}


 
\ifdefined\anonymous
% No Author Given
\else 
 \author{Kamil Kluczniak\inst{1,2}}
 \institute{CISPA Helmholtz Center for Information Security \\
  \and  
  Stanford University \\
   \email{kamil.kluczniak@\{cispa.saarland,stanford.edu\}} \\ 
  }  
\fi
 
 

\begin{document}

\maketitle 
  
 
\begin{abstract}\label{sec:abstract}
\input{sections/abstract}
\end{abstract}

\section{Introduction}\label{sec:introduction}
\input{sections/introduction}

\subsection{Overview of our Techniques}
\input{sections/techniques}

\subsection{Related Work and Applications}
\input{sections/related-work} 


\section{Preliminaries}\label{sec:preliminaries}
\input{sections/preliminaries}
 
\section{Lockable Obfuscation from Circular Insecure FHE}\label{sec:lockable-obfuscation-from-fhe}
\input{sections/lockable-obfuscation-from-fhe}
 
\section{Extensions and Variants of the Lockable Obfuscation Scheme}\label{sec:extentions}
\input{sections/extending-the-lockable-obfuscation}

\subsection{Lock Ciphertext in the Plain}\label{sec:lock-ciphertexts-in-plain}
\input{sections/lock-ciphertext-in-the-plain}
 

\subsection{Extending to Multi-Bit Messages}\label{sec:multibit-messages}
\input{sections/extending-to-multibit-messages}

%\subsection{Weakening the Lock Distributions}\label{sec:weak-lock-distributions}
%\input{sections/weak-lock-distributions}
% 
%\section{New Counterexamples}
%
%\subsection{Counterexample for UCE-Security without Indistinguishability Obfuscation}
%
%\subsection{Separating CCA and Circular Security}

\section{Conclusions}
\input{sections/conclusions}


\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{CVW{\etalchar{+}}18a}

\bibitem[ABBC10]{EC:ABBC10}
Tolga Acar, Mira Belenkiy, Mihir Bellare, and David Cash.
\newblock Cryptographic agility and its relation to circular encryption.
\newblock In Henri Gilbert, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2010}, volume 6110 of {\em Lecture Notes in Computer Science},
  pages 403--422. Springer, Heidelberg, May~/~June 2010.

\bibitem[ADN{\etalchar{+}}10]{EC:ADNSWW10}
Jo{\"e}l Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and
  Daniel Wichs.
\newblock Public-key encryption in the bounded-retrieval model.
\newblock In Henri Gilbert, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2010}, volume 6110 of {\em Lecture Notes in Computer Science},
  pages 113--134. Springer, Heidelberg, May~/~June 2010.

\bibitem[Agr19]{EC:Agrawal19}
Shweta Agrawal.
\newblock Indistinguishability obfuscation without multilinear maps: New
  methods for bootstrapping and instantiation.
\newblock In Yuval Ishai and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2019, Part~I}, volume 11476 of {\em Lecture Notes
  in Computer Science}, pages 191--225. Springer, Heidelberg, May 2019.

\bibitem[AGV09]{TCC:AkaGolVai09}
Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan.
\newblock Simultaneous hardcore bits and cryptography against memory attacks.
\newblock In Omer Reingold, editor, {\em TCC~2009: 6th Theory of Cryptography
  Conference}, volume 5444 of {\em Lecture Notes in Computer Science}, pages
  474--495. Springer, Heidelberg, March 2009.

\bibitem[AJL{\etalchar{+}}19]{C:AJLMS19}
Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai.
\newblock Indistinguishability obfuscation without multilinear maps: New
  paradigms via low degree weak pseudorandomness and security amplification.
\newblock In Alexandra Boldyreva and Daniele Micciancio, editors, {\em Advances
  in Cryptology -- {CRYPTO}~2019, Part~III}, volume 11694 of {\em Lecture Notes
  in Computer Science}, pages 284--332. Springer, Heidelberg, August 2019.

\bibitem[AKPW13]{C:AKPW13}
Jo{\"e}l Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs.
\newblock Learning with rounding, revisited - new reduction, properties and
  applications.
\newblock In Ran Canetti and Juan~A. Garay, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2013, Part~I}, volume 8042 of {\em Lecture Notes in
  Computer Science}, pages 57--74. Springer, Heidelberg, August 2013.

\bibitem[AL20]{TCC:AnaLaP20}
Prabhanjan Ananth and Rolando~L. {La Placa}.
\newblock Secure quantum extraction protocols.
\newblock In Rafael Pass and Krzysztof Pietrzak, editors, {\em TCC~2020: 18th
  Theory of Cryptography Conference, Part~III}, volume 12552 of {\em Lecture
  Notes in Computer Science}, pages 123--152. Springer, Heidelberg, November
  2020.

\bibitem[AP16]{C:AlaPei16}
Navid Alamati and Chris Peikert.
\newblock Three's compromised too: Circular insecurity for any cycle length
  from (ring-){LWE}.
\newblock In Matthew Robshaw and Jonathan Katz, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2016, Part~II}, volume 9815 of {\em Lecture Notes in
  Computer Science}, pages 659--680. Springer, Heidelberg, August 2016.

\bibitem[BDGM20a]{EC:BDGM20}
Zvika Brakerski, Nico D{\"o}ttling, Sanjam Garg, and Giulio Malavolta.
\newblock Candidate {iO} from homomorphic encryption schemes.
\newblock In Anne Canteaut and Yuval Ishai, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2020, Part~I}, volume 12105 of {\em Lecture Notes
  in Computer Science}, pages 79--109. Springer, Heidelberg, May 2020.

\bibitem[BDGM20b]{EPRINT:BDGM20b}
Zvika Brakerski, Nico D{\"o}ttling, Sanjam Garg, and Giulio Malavolta.
\newblock Factoring and pairings are not necessary for {iO}: Circular-secure
  {LWE} suffices.
\newblock Cryptology ePrint Archive, Report 2020/1024, 2020.
\newblock \url{https://eprint.iacr.org/2020/1024}.

\bibitem[BG10]{C:BraGol10}
Zvika Brakerski and Shafi Goldwasser.
\newblock Circular and leakage resilient public-key encryption under subgroup
  indistinguishability - (or: Quadratic residuosity strikes back).
\newblock In Tal Rabin, editor, {\em Advances in Cryptology -- {CRYPTO}~2010},
  volume 6223 of {\em Lecture Notes in Computer Science}, pages 1--20.
  Springer, Heidelberg, August 2010.

\bibitem[BGI{\etalchar{+}}01]{C:BGIRSVY01}
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
  Salil~P. Vadhan, and Ke~Yang.
\newblock On the (im)possibility of obfuscating programs.
\newblock In Joe Kilian, editor, {\em Advances in Cryptology -- {CRYPTO}~2001},
  volume 2139 of {\em Lecture Notes in Computer Science}, pages 1--18.
  Springer, Heidelberg, August 2001.

\bibitem[BGI{\etalchar{+}}12]{JACM:BGIRSVY12}
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
  Salil Vadhan, and Ke~Yang.
\newblock On the (im)possibility of obfuscating programs.
\newblock {\em J. ACM}, 59(2), May 2012.

\bibitem[BHJ{\etalchar{+}}19]{EC:BHJKS19}
Boaz Barak, Samuel~B. Hopkins, Aayush Jain, Pravesh Kothari, and Amit Sahai.
\newblock Sum-of-squares meets program obfuscation, revisited.
\newblock In Yuval Ishai and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2019, Part~I}, volume 11476 of {\em Lecture Notes
  in Computer Science}, pages 226--250. Springer, Heidelberg, May 2019.

\bibitem[BHW15]{AC:BisHohWat15}
Allison Bishop, Susan Hohenberger, and Brent Waters.
\newblock New circular security counterexamples from decision linear and
  learning with errors.
\newblock In Tetsu Iwata and Jung~Hee Cheon, editors, {\em Advances in
  Cryptology -- {ASIACRYPT}~2015, Part~II}, volume 9453 of {\em Lecture Notes
  in Computer Science}, pages 776--800. Springer, Heidelberg,
  November~/~December 2015.

\bibitem[BKM{\etalchar{+}}18]{C:BKMPRS18}
Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova,
  and Kevin Shi.
\newblock A simple obfuscation scheme for pattern-matching with wildcards.
\newblock In Hovav Shacham and Alexandra Boldyreva, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2018, Part~III}, volume 10993 of {\em Lecture Notes in
  Computer Science}, pages 731--752. Springer, Heidelberg, August 2018.

\bibitem[BKP19]{STOC:BitKhuPan19}
Nir Bitansky, Dakshita Khurana, and Omer Paneth.
\newblock Weak zero-knowledge beyond the black-box barrier.
\newblock In Moses Charikar and Edith Cohen, editors, {\em 51st Annual {ACM}
  Symposium on Theory of Computing}, pages 1091--1102. {ACM} Press, June 2019.

\bibitem[BKSW18]{TCC:BKSW18}
Saikrishna Badrinarayanan, Dakshita Khurana, Amit Sahai, and Brent Waters.
\newblock Upgrading to functional encryption.
\newblock In Amos Beimel and Stefan Dziembowski, editors, {\em TCC~2018: 16th
  Theory of Cryptography Conference, Part~I}, volume 11239 of {\em Lecture
  Notes in Computer Science}, pages 629--658. Springer, Heidelberg, November
  2018.

\bibitem[BLMZ19]{EC:BLMZ19}
James Bartusek, Tancr{\`e}de Lepoint, Fermi Ma, and Mark Zhandry.
\newblock New techniques for obfuscating conjunctions.
\newblock In Yuval Ishai and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2019, Part~III}, volume 11478 of {\em Lecture Notes
  in Computer Science}, pages 636--666. Springer, Heidelberg, May 2019.

\bibitem[BLSV18]{EC:BLSV18}
Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan.
\newblock Anonymous {IBE}, leakage resilience and circular security from new
  assumptions.
\newblock In Jesper~Buus Nielsen and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2018, Part~I}, volume 10820 of {\em Lecture Notes
  in Computer Science}, pages 535--564. Springer, Heidelberg, April~/~May 2018.

\bibitem[BR13]{C:BraRot13}
Zvika Brakerski and Guy~N. Rothblum.
\newblock Obfuscating conjunctions.
\newblock In Ran Canetti and Juan~A. Garay, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2013, Part~II}, volume 8043 of {\em Lecture Notes in
  Computer Science}, pages 416--434. Springer, Heidelberg, August 2013.

\bibitem[BS16]{TCC:BelSte16}
Mihir Bellare and Igors Stepanovs.
\newblock Point-function obfuscation: {A} framework and generic constructions.
\newblock In Eyal Kushilevitz and Tal Malkin, editors, {\em TCC~2016-A: 13th
  Theory of Cryptography Conference, Part~II}, volume 9563 of {\em Lecture
  Notes in Computer Science}, pages 565--594. Springer, Heidelberg, January
  2016.

\bibitem[BS20]{STOC:BitShm20}
Nir Bitansky and Omri Shmueli.
\newblock Post-quantum zero knowledge in constant rounds.
\newblock In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam
  Kamath, and Julia Chuzhoy, editors, {\em 52nd Annual {ACM} Symposium on
  Theory of Computing}, pages 269--279. {ACM} Press, June 2020.

\bibitem[BVWW16]{ITCS:BVWW16}
Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs.
\newblock Obfuscating conjunctions under entropic ring {LWE}.
\newblock In Madhu Sudan, editor, {\em ITCS 2016: 7th Conference on Innovations
  in Theoretical Computer Science}, pages 147--156. Association for Computing
  Machinery, January 2016.

\bibitem[BW19]{PKC:BeuWee19}
Ward Beullens and Hoeteck Wee.
\newblock Obfuscating simple functionalities from knowledge assumptions.
\newblock In Dongdai Lin and Kazue Sako, editors, {\em PKC~2019: 22nd
  International Conference on Theory and Practice of Public Key Cryptography,
  Part~II}, volume 11443 of {\em Lecture Notes in Computer Science}, pages
  254--283. Springer, Heidelberg, April 2019.

\bibitem[Can97]{C:Canetti97}
Ran Canetti.
\newblock Towards realizing random oracles: Hash functions that hide all
  partial information.
\newblock In Burton~S. {Kaliski Jr.}, editor, {\em Advances in Cryptology --
  {CRYPTO}'97}, volume 1294 of {\em Lecture Notes in Computer Science}, pages
  455--469. Springer, Heidelberg, August 1997.

\bibitem[CD08]{EC:CanDak08}
Ran Canetti and Ronny~Ramzi Dakdouk.
\newblock Obfuscating point functions with multibit output.
\newblock In Nigel~P. Smart, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2008}, volume 4965 of {\em Lecture Notes in Computer Science},
  pages 489--508. Springer, Heidelberg, April 2008.

\bibitem[CGH12]{PKC:CasGreHoh12}
David Cash, Matthew Green, and Susan Hohenberger.
\newblock New definitions and separations for circular security.
\newblock In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, {\em
  PKC~2012: 15th International Conference on Theory and Practice of Public Key
  Cryptography}, volume 7293 of {\em Lecture Notes in Computer Science}, pages
  540--557. Springer, Heidelberg, May 2012.

\bibitem[CKVW10]{TCC:CKVW10}
Ran Canetti, Yael~Tauman Kalai, Mayank Varia, and Daniel Wichs.
\newblock On symmetric encryption and point obfuscation.
\newblock In Daniele Micciancio, editor, {\em TCC~2010: 7th Theory of
  Cryptography Conference}, volume 5978 of {\em Lecture Notes in Computer
  Science}, pages 52--71. Springer, Heidelberg, February 2010.

\bibitem[CRV10]{TCC:CanRotVar10}
Ran Canetti, Guy~N. Rothblum, and Mayank Varia.
\newblock Obfuscation of hyperplane membership.
\newblock In Daniele Micciancio, editor, {\em TCC~2010: 7th Theory of
  Cryptography Conference}, volume 5978 of {\em Lecture Notes in Computer
  Science}, pages 72--89. Springer, Heidelberg, February 2010.

\bibitem[CVW{\etalchar{+}}18a]{TCC:CVWWW18}
Yilei Chen, Vinod Vaikuntanathan, Brent Waters, Hoeteck Wee, and Daniel Wichs.
\newblock Traitor-tracing from {LWE} made simple and attribute-based.
\newblock In Amos Beimel and Stefan Dziembowski, editors, {\em TCC~2018: 16th
  Theory of Cryptography Conference, Part~II}, volume 11240 of {\em Lecture
  Notes in Computer Science}, pages 341--369. Springer, Heidelberg, November
  2018.

\bibitem[CVW18b]{C:CheVaiWee18}
Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee.
\newblock {GGH15} beyond permutation branching programs: Proofs, attacks, and
  candidates.
\newblock In Hovav Shacham and Alexandra Boldyreva, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2018, Part~II}, volume 10992 of {\em Lecture Notes in
  Computer Science}, pages 577--607. Springer, Heidelberg, August 2018.

\bibitem[DGK{\etalchar{+}}10]{TCC:DGKPV10}
Yevgeniy Dodis, Shafi Goldwasser, Yael~Tauman Kalai, Chris Peikert, and Vinod
  Vaikuntanathan.
\newblock Public-key encryption schemes with auxiliary inputs.
\newblock In Daniele Micciancio, editor, {\em TCC~2010: 7th Theory of
  Cryptography Conference}, volume 5978 of {\em Lecture Notes in Computer
  Science}, pages 361--381. Springer, Heidelberg, February 2010.

\bibitem[DHLW10]{AC:DHLW10}
Yevgeniy Dodis, Kristiyan Haralambiev, Adriana {L{\'o}pez-Alt}, and Daniel
  Wichs.
\newblock Efficient public-key cryptography in the presence of key leakage.
\newblock In Masayuki Abe, editor, {\em Advances in Cryptology --
  {ASIACRYPT}~2010}, volume 6477 of {\em Lecture Notes in Computer Science},
  pages 613--631. Springer, Heidelberg, December 2010.

\bibitem[DKL09]{STOC:DodKalLov09}
Yevgeniy Dodis, Yael~Tauman Kalai, and Shachar Lovett.
\newblock On cryptography with auxiliary input.
\newblock In Michael Mitzenmacher, editor, {\em 41st Annual {ACM} Symposium on
  Theory of Computing}, pages 621--630. {ACM} Press, May~/~June 2009.

\bibitem[DORS08]{SIAM:DORS08}
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith.
\newblock Fuzzy extractors: How to generate strong keys from biometrics and
  other noisy data.
\newblock {\em SIAM J. Comput.}, 38(1):97–139, March 2008.

\bibitem[DP08]{FOCS:DziPie08}
Stefan Dziembowski and Krzysztof Pietrzak.
\newblock Leakage-resilient cryptography.
\newblock In {\em 49th Annual Symposium on Foundations of Computer Science},
  pages 293--302. {IEEE} Computer Society Press, October 2008.

\bibitem[DRS04]{EC:DodReySmi04}
Yevgeniy Dodis, Leonid Reyzin, and Adam Smith.
\newblock Fuzzy extractors: How to generate strong keys from biometrics and
  other noisy data.
\newblock In Christian Cachin and Jan Camenisch, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2004}, volume 3027 of {\em Lecture Notes in
  Computer Science}, pages 523--540. Springer, Heidelberg, May 2004.

\bibitem[DS05]{STOC:DodSmi05}
Yevgeniy Dodis and Adam Smith.
\newblock Correcting errors without leaking partial information.
\newblock In Harold~N. Gabow and Ronald Fagin, editors, {\em 37th Annual {ACM}
  Symposium on Theory of Computing}, pages 654--663. {ACM} Press, May 2005.

\bibitem[Gen09]{STOC:Gentry09}
Craig Gentry.
\newblock Fully homomorphic encryption using ideal lattices.
\newblock In Michael Mitzenmacher, editor, {\em 41st Annual {ACM} Symposium on
  Theory of Computing}, pages 169--178. {ACM} Press, May~/~June 2009.

\bibitem[GGH15]{TCC:GenGorHal15}
Craig Gentry, Sergey Gorbunov, and Shai Halevi.
\newblock Graph-induced multilinear maps from lattices.
\newblock In Yevgeniy Dodis and Jesper~Buus Nielsen, editors, {\em TCC~2015:
  12th Theory of Cryptography Conference, Part~II}, volume 9015 of {\em Lecture
  Notes in Computer Science}, pages 498--527. Springer, Heidelberg, March 2015.

\bibitem[GJLS20]{EPRINT:GJLS20}
Romain Gay, Aayush Jain, Huijia Lin, and Amit Sahai.
\newblock Indistinguishability obfuscation from simple-to-state hard problems:
  New assumptions, new techniques, and simplification.
\newblock Cryptology ePrint Archive, Report 2020/764, 2020.
\newblock \url{https://eprint.iacr.org/2020/764}.

\bibitem[GKPV10]{ICS:GKPV10}
Shafi Goldwasser, Yael~Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan.
\newblock Robustness of the learning with errors assumption.
\newblock In Andrew~Chi{-}Chih Yao, editor, {\em Innovations in Computer
  Science - {ICS} 2010, Tsinghua University, Beijing, China, January 5-7, 2010.
  Proceedings}, pages 230--240. Tsinghua University Press, 2010.

\bibitem[GKVW20]{TCC:GKVW20}
Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, and Brent Waters.
\newblock On perfect correctness in (lockable) obfuscation.
\newblock In Rafael Pass and Krzysztof Pietrzak, editors, {\em TCC~2020: 18th
  Theory of Cryptography Conference, Part~I}, volume 12550 of {\em Lecture
  Notes in Computer Science}, pages 229--259. Springer, Heidelberg, November
  2020.

\bibitem[GKW17a]{FOCS:GoyKopWat17}
Rishab Goyal, Venkata Koppula, and Brent Waters.
\newblock Lockable obfuscation.
\newblock In Chris Umans, editor, {\em 58th Annual Symposium on Foundations of
  Computer Science}, pages 612--621. {IEEE} Computer Society Press, October
  2017.

\bibitem[GKW17b]{PKC:GoyKopWat17}
Rishab Goyal, Venkata Koppula, and Brent Waters.
\newblock Separating {IND}-{CPA} and circular security for unbounded length key
  cycles.
\newblock In Serge Fehr, editor, {\em PKC~2017: 20th International Conference
  on Theory and Practice of Public Key Cryptography, Part~I}, volume 10174 of
  {\em Lecture Notes in Computer Science}, pages 232--246. Springer,
  Heidelberg, March 2017.

\bibitem[GKW17c]{EC:GoyKopWat17}
Rishab Goyal, Venkata Koppula, and Brent Waters.
\newblock Separating semantic and circular security for symmetric-key bit
  encryption from the learning with errors assumption.
\newblock In Jean-S{\'{e}}bastien Coron and Jesper~Buus Nielsen, editors, {\em
  Advances in Cryptology -- {EUROCRYPT}~2017, Part~II}, volume 10211 of {\em
  Lecture Notes in Computer Science}, pages 528--557. Springer, Heidelberg,
  April~/~May 2017.

\bibitem[GKW18]{STOC:GoyKopWat18}
Rishab Goyal, Venkata Koppula, and Brent Waters.
\newblock Collusion resistant traitor tracing from learning with errors.
\newblock In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors,
  {\em 50th Annual {ACM} Symposium on Theory of Computing}, pages 660--670.
  {ACM} Press, June 2018.

\bibitem[GP20]{EPRINT:GayPas20}
Romain Gay and Rafael Pass.
\newblock Indistinguishability obfuscation from circular security.
\newblock Cryptology ePrint Archive, Report 2020/1010, 2020.
\newblock \url{https://eprint.iacr.org/2020/1010}.

\bibitem[HG01]{CaLC:Howgrave-Graham01}
Nick Howgrave-Graham.
\newblock Approximate integer common divisors.
\newblock In Joseph~H. Silverman, editor, {\em Cryptography and Lattices},
  pages 51--66, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.

\bibitem[HH09]{TCC:HaiHol09}
Iftach Haitner and Thomas Holenstein.
\newblock On the (im)possibility of key dependent encryption.
\newblock In Omer Reingold, editor, {\em TCC~2009: 6th Theory of Cryptography
  Conference}, volume 5444 of {\em Lecture Notes in Computer Science}, pages
  202--219. Springer, Heidelberg, March 2009.

\bibitem[HILL99]{SIAM:HasImp99}
Johan H\r{A}stad, Russell Impagliazzo, Leonid~A. Levin, and Michael Luby.
\newblock A pseudorandom generator from any one-way function.
\newblock {\em SIAM J. Comput.}, 28(4):1364–1396, March 1999.

\bibitem[HLR07]{EC:HsiLuRey07}
Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin.
\newblock Conditional computational entropy, or toward separating pseudoentropy
  from compressibility.
\newblock In Moni Naor, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2007}, volume 4515 of {\em Lecture Notes in Computer Science},
  pages 169--186. Springer, Heidelberg, May 2007.

\bibitem[HPS98]{ANTS:HofPipSil98}
Jeffrey Hoffstein, Jill Pipher, and Joseph~H. Silverman.
\newblock {NTRU:} {A} ring-based public key cryptosystem.
\newblock In Joe Buhler, editor, {\em Algorithmic Number Theory, Third
  International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998,
  Proceedings}, volume 1423 of {\em Lecture Notes in Computer Science}, pages
  267--288. Springer, 1998.

\bibitem[JLMS19]{EC:JLMS19}
Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai.
\newblock How to leverage hardness of constant-degree expanding polynomials
  overa {$\mathbb{R}$} to build {$i\mathcal{O}$}.
\newblock In Yuval Ishai and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2019, Part~I}, volume 11476 of {\em Lecture Notes
  in Computer Science}, pages 251--281. Springer, Heidelberg, May 2019.

\bibitem[JLS20]{EPRINT:JaiLinSah20}
Aayush Jain, Huijia Lin, and Amit Sahai.
\newblock Indistinguishability obfuscation from well-founded assumptions.
\newblock Cryptology ePrint Archive, Report 2020/1003, 2020.
\newblock \url{https://eprint.iacr.org/2020/1003}.

\bibitem[Klu20]{EPRINT:Kluczniak20}
Kamil Kluczniak.
\newblock Witness encryption from garbled circuit and multikey fully
  homomorphic encryption techniques.
\newblock Cryptology ePrint Archive, Report 2020/1502, 2020.
\newblock \url{https://eprint.iacr.org/2020/1502}.

\bibitem[Klu21]{EPRINT:Kluczniak21}
Kamil Kluczniak.
\newblock Lockable obfuscation from circularly insecure fully homomorphic
  encryption.
\newblock Cryptology ePrint Archive, Report 2021/1324, 2021.
\newblock \url{https://ia.cr/2021/1324}.

\bibitem[KRW15]{TCC:KopRamWat15}
Venkata Koppula, Kim Ramchen, and Brent Waters.
\newblock Separations in circular security for arbitrary length key cycles.
\newblock In Yevgeniy Dodis and Jesper~Buus Nielsen, editors, {\em TCC~2015:
  12th Theory of Cryptography Conference, Part~II}, volume 9015 of {\em Lecture
  Notes in Computer Science}, pages 378--400. Springer, Heidelberg, March 2015.

\bibitem[KW16]{C:KopWat16}
Venkata Koppula and Brent Waters.
\newblock Circular security separations for arbitrary length cycles from {LWE}.
\newblock In Matthew Robshaw and Jonathan Katz, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2016, Part~II}, volume 9815 of {\em Lecture Notes in
  Computer Science}, pages 681--700. Springer, Heidelberg, August 2016.

\bibitem[KY18]{EC:KomYog18}
Ilan Komargodski and Eylon Yogev.
\newblock Another step towards realizing random oracles: Non-malleable point
  obfuscation.
\newblock In Jesper~Buus Nielsen and Vincent Rijmen, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2018, Part~I}, volume 10820 of {\em Lecture Notes
  in Computer Science}, pages 259--279. Springer, Heidelberg, April~/~May 2018.

\bibitem[LPR10]{EC:LyuPeiReg10}
Vadim Lyubashevsky, Chris Peikert, and Oded Regev.
\newblock On ideal lattices and learning with errors over rings.
\newblock In Henri Gilbert, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2010}, volume 6110 of {\em Lecture Notes in Computer Science},
  pages 1--23. Springer, Heidelberg, May~/~June 2010.

\bibitem[LPS04]{EC:LynPraSah04}
Ben Lynn, Manoj Prabhakaran, and Amit Sahai.
\newblock Positive results and techniques for obfuscation.
\newblock In Christian Cachin and Jan Camenisch, editors, {\em Advances in
  Cryptology -- {EUROCRYPT}~2004}, volume 3027 of {\em Lecture Notes in
  Computer Science}, pages 20--39. Springer, Heidelberg, May 2004.

\bibitem[LPST16]{PKC:LPST16}
Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang.
\newblock Indistinguishability obfuscation with non-trivial efficiency.
\newblock In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang,
  editors, {\em PKC~2016: 19th International Conference on Theory and Practice
  of Public Key Cryptography, Part~II}, volume 9615 of {\em Lecture Notes in
  Computer Science}, pages 447--462. Springer, Heidelberg, March 2016.

\bibitem[LT17]{C:LinTes17}
Huijia Lin and Stefano Tessaro.
\newblock Indistinguishability obfuscation from trilinear maps and block-wise
  local {PRGs}.
\newblock In Jonathan Katz and Hovav Shacham, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2017, Part~I}, volume 10401 of {\em Lecture Notes in
  Computer Science}, pages 630--660. Springer, Heidelberg, August 2017.

\bibitem[NS09]{C:NaoSeg09}
Moni Naor and Gil Segev.
\newblock Public-key cryptosystems resilient to key leakage.
\newblock In Shai Halevi, editor, {\em Advances in Cryptology --
  {CRYPTO}~2009}, volume 5677 of {\em Lecture Notes in Computer Science}, pages
  18--35. Springer, Heidelberg, August 2009.

\bibitem[Pie09]{EC:Pietrzak09}
Krzysztof Pietrzak.
\newblock A leakage-resilient mode of operation.
\newblock In Antoine Joux, editor, {\em Advances in Cryptology --
  {EUROCRYPT}~2009}, volume 5479 of {\em Lecture Notes in Computer Science},
  pages 462--482. Springer, Heidelberg, April 2009.

\bibitem[RAD{\etalchar{+}}78]{rivest1978data}
Ronald~L Rivest, Len Adleman, Michael~L Dertouzos, et~al.
\newblock On data banks and privacy homomorphisms.
\newblock {\em Foundations of secure computation}, 4(11):169--180, 1978.

\bibitem[Reg05]{STOC:Regev05}
Oded Regev.
\newblock On lattices, learning with errors, random linear codes, and
  cryptography.
\newblock In Harold~N. Gabow and Ronald Fagin, editors, {\em 37th Annual {ACM}
  Symposium on Theory of Computing}, pages 84--93. {ACM} Press, May 2005.

\bibitem[Rot13]{TCC:Rothblum13}
Ron Rothblum.
\newblock On the circular security of bit-encryption.
\newblock In Amit Sahai, editor, {\em TCC~2013: 10th Theory of Cryptography
  Conference}, volume 7785 of {\em Lecture Notes in Computer Science}, pages
  579--598. Springer, Heidelberg, March 2013.

\bibitem[Wee05]{STOC:Wee05}
Hoeteck Wee.
\newblock On obfuscating point functions.
\newblock In Harold~N. Gabow and Ronald Fagin, editors, {\em 37th Annual {ACM}
  Symposium on Theory of Computing}, pages 523--532. {ACM} Press, May 2005.

\bibitem[WW20]{EPRINT:WeeWic20}
Hoeteck Wee and Daniel Wichs.
\newblock Candidate obfuscation via oblivious {LWE} sampling.
\newblock Cryptology ePrint Archive, Report 2020/1042, 2020.
\newblock \url{https://eprint.iacr.org/2020/1042}.

\bibitem[WZ17]{FOCS:WicZir17}
Daniel Wichs and Giorgos Zirdelis.
\newblock Obfuscating compute-and-compare programs under {LWE}.
\newblock In Chris Umans, editor, {\em 58th Annual Symposium on Foundations of
  Computer Science}, pages 600--611. {IEEE} Computer Society Press, October
  2017.

\bibitem[YZ16]{C:YuZha16}
Yu~Yu and Jiang Zhang.
\newblock Cryptography with auxiliary input and trapdoor from constant-noise
  {LPN}.
\newblock In Matthew Robshaw and Jonathan Katz, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2016, Part~I}, volume 9814 of {\em Lecture Notes in
  Computer Science}, pages 214--243. Springer, Heidelberg, August 2016.

\bibitem[Zha16]{C:Zhandry16}
Mark Zhandry.
\newblock The magic of {ELFs}.
\newblock In Matthew Robshaw and Jonathan Katz, editors, {\em Advances in
  Cryptology -- {CRYPTO}~2016, Part~I}, volume 9814 of {\em Lecture Notes in
  Computer Science}, pages 479--508. Springer, Heidelberg, August 2016.

\end{thebibliography}

 

\end{document}