main.tex

\def\shownotes{1}
\def\lncs{1}

\ifnum\lncs=0
	\documentclass[11pt]{article}
	\usepackage[top=3cm, bottom=3cm, left=2cm, right=2cm]{geometry}  
	\usepackage{amsthm}
	\pagestyle{plain}
	\newtheorem{proposition}{Proposition}[section]
	\newtheorem{theorem}{Theorem}[section]
	\newtheorem{lemma}{Lemma}[section]
	\newtheorem{corollary}{Corollary}[section]
	\newtheorem{conjecture}{Conjecture}[section]
	\newtheorem{claim}{Claim}[section]
	\newtheorem{definition}{Definition}[section]
	\newtheorem{assumption}{Assumption}[section]
	\newtheorem{construction}{Construction}[section]
\else
	\documentclass[runningheads]{llncs}
	\pagestyle{plain}
	\newtheorem{construction}{Construction}
	\newtheorem{assumption}{Assumption}
	\renewcommand{\paragraph}[1]{\subsubsection{#1}}
\fi
\usepackage{amsfonts, amstext, amsmath, amscd, amssymb, hyperref, float, longtable}
\usepackage{mathtools}
\usepackage[]{algorithm2e}
\usepackage{epsfig, graphics, psfrag}
\usepackage{graphicx}
\usepackage{color}
\usepackage[font=small, labelfont=bf]{caption}
\usepackage{float}
\usepackage{framed}
\ifnum\shownotes=1
\newcommand{\authnote}[2]{{\textcolor{red}{\textsf{#1 notes: }\textcolor{blue}{ #2}}\marginpar{\textcolor{red}{\textbf{!!!!!}}}}}
\else
\newcommand{\authnote}[2]{}
\fi

\newcommand{\bnote}[1]{{\authnote{Ben}{#1}}}
\newcommand{\pnote}[1]{{\authnote{Peter}{#1}}}

\newenvironment{psketch}{\renewcommand{\proofname}{Proof Sketch}\proof}{\endproof}

\DeclareMathOperator*{\expe}{\mathbb{E}}
\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}
\newcommand{\rep}{\ensuremath{\class{Rep}}\xspace}
\newcommand{\sketch}{\ensuremath{\class{SS}}\xspace}
\newcommand{\seed}{\ensuremath{\class{seed}}\xspace}
\newcommand{\rec}{\ensuremath{\class{Rec}}\xspace}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\mac}{\ensuremath{\class{Tag}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}
\newcommand{\hash}{\ensuremath{\class{hash}}\xspace}
\newcommand{\prg}{\ensuremath{\class{prg}}\xspace}
\newcommand{\zo}{\ensuremath{\{0, 1\}}}
\newcommand{\vect}[1]{\ensuremath{\mathbf{#1}}}
\newcommand{\zq}{\ensuremath{\mathbb{Z}_q}}
\newcommand{\Fq}{\ensuremath{\mathbb{F}_q}}
\newcommand{\sample}{\ensuremath{\class{Sample}}\xspace}
\newcommand{\neigh}{\ensuremath{\class{Neigh}}\xspace}
\newcommand{\error}{\ensuremath{\class{Err}}\xspace}
\newcommand{\weight}{\ensuremath{\class{Wgt}}\xspace}
\newcommand{\dis}{\ensuremath{\mathsf{dis}}}
\newcommand{\decode}{\ensuremath{\mathsf{Decode}}}
\newcommand{\guess}{\mathsf{guess}}


\newcommand{\A}{\mathcal{A}}
\newcommand{\Succ}{\mathsf{Succ}}
\newcommand{\Adv}{\mathbf{Adv}}
 \newcommand{\Exp}{\mathbf{Exp}}

\newcommand{\calG}{{\cal G}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calA}{{\cal A}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calC}{{\cal C}}


\newcommand{\metric}{\ensuremath{\mathtt{Metric}}\xspace}
\newcommand{\hill}{\ensuremath{\mathtt{HILL}}\xspace}
\newcommand{\hillrlx}{\ensuremath{\mathtt{HILL\mhyphen rlx}}\xspace}
\newcommand{\yao}{\ensuremath{\mathtt{Yao}}\xspace}
\newcommand{\unp}{\ensuremath{\mathtt{unp}}\xspace}
\newcommand{\unprlx}{\ensuremath{\mathtt{unp\mhyphen rlx}}\xspace}
\newcommand{\metricstar}{\ensuremath{\mathtt{Metric}^*}\xspace}
\newcommand{\metricd}{\ensuremath{\mathtt{Metric}^*\mathtt{-d}}\xspace}
\newcommand{\hillstar}{\ensuremath{\mathtt{HILL}^*}\xspace}
\newcommand{\hillprime}{\ensuremath{\mathtt{HILL'}}\xspace}
\newcommand{\metricprime}{\ensuremath{\mathtt{Metric'}}\xspace}
\newcommand{\metricprimestar}{\ensuremath{\mathtt{Metric'}^*}\xspace}
\newcommand{\hillprimestar}{\ensuremath{\mathtt{HILL'}^*}\xspace}
\newcommand{\poly}{\ensuremath{\mathtt{poly}}\xspace}
\newcommand{\rank}{\ensuremath{\mathtt{rank}}\xspace}
\newcommand{\ngl}{\ensuremath{\mathtt{ngl}}\xspace}
\newcommand{\Hoo}{\mathrm{H}_\infty}
\newcommand{\Hav}{\tilde{\mathrm{H}}_\infty}
\newcommand{\Hfuzz}{\mathrm{H}^{\mathtt{fuzz}}_{t,\infty}}
\newcommand{\Huse}{\mathrm{H}_{\mathtt{usable}}}
\newcommand{\Dom}{\mathsl{Dom}}
\newcommand{\Range}{\mathsl{Rng}}
\newcommand{\Keys}{\mathsl{Keys}}
\def\col{\mathrm{Col}}

\newcommand{\ddetbin}{\ensuremath{\mathcal{D}^{det,\{0,1\}}}}
\newcommand{\drandbin}{\ensuremath{\mathcal{D}^{rand,\{0,1\}}}}
\newcommand{\ddetrange}{\ensuremath{\mathcal{D}^{det,[0,1]}}}
\newcommand{\drandrange}{\ensuremath{\mathcal{D}^{rand,[0,1]}}}

\newcommand{\expinfo}{\ensuremath{\mathcal{E}}}
\newcommand{\ext}{\ensuremath{\mathtt{ext}}}
\newcommand{\uhash}{\ensuremath{\mathtt{hash}}}
\newcommand{\cext}{\ensuremath{\mathtt{cext}}}
\newcommand{\cond}{\ensuremath{\mathtt{cond}}}
\newcommand{\rext}{\ensuremath{\mathtt{rext}}}
\newcommand{\cons}{\ensuremath{\mathtt{cons}}}
\newcommand{\decons}{\ensuremath{\mathtt{decons}}}


\newcommand{\lwe}{\class{LWE}}
\newcommand{\LWE}{\class{LWE}}
\newcommand{\distLWE}{\ensuremath{\class{dist\mbox{-}LWE}}}
\newcommand{\ve}{\vect{e}}
\newcommand{\vm}{\vect{m}}
\newcommand{\vy}{\vect{y}}
\newcommand{\vE}{\vect{E}}
\newcommand{\vS}{\vect{S}}
\newcommand{\vA}{\vect{A}}
\newcommand{\vc}{\vect{c}}
\newcommand{\vW}{\vect{W}}
\newcommand{\vQ}{\vect{Q}}
\newcommand{\vR}{\vect{R}}
\newcommand{\vU}{\vect{U}}
\newcommand{\vT}{\vect{T}}
\newcommand{\vX}{\vect{X}}
\newcommand{\vB}{\vect{B}}
\newcommand{\vz}{\vect{z}}
\newcommand{\vd}{\vect{d}}
\newcommand{\vs}{\vect{s}}
\newcommand{\vx}{\vect{x}}
\newcommand{\va}{\vect{a}}
\newcommand{\vb}{\vect{b}}
\newcommand{\vgamma}{\mathbf{\Gamma}}
\newcommand{\vt}{\vect{t}}
\newcommand{\vu}{\vect{u}}
\newcommand{\vF}{\vect{F}}
\newcommand{\recout}{x}
\newcommand{\ignore}[1]{}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Vol}{\mathsf{Vol}}
\newcommand{\subsetEntropy}{\alpha}
\newcommand{\subsetSize}{k}
\newcommand{\sourcelen}{n}
\newcommand{\composition}{\ell}
\newcommand{\reusability}{\rho}

\newcommand{\lockkey}{\mathsf{key}}
\newcommand{\lockval}{\mathsf{val}}
\newcommand{\locknonce}{\mathsf{nonce}}
\newcommand{\locksec}{\mathsf{s}}
\newcommand{\securityparam}{\lambda}
\newcommand{\lock}{\mathsf{lock}}
\newcommand{\unlock}{\mathsf{unlock}}
\newcommand{\pointlock}{\mathsf{lockPoint}}
\newcommand{\pointunlock}{\mathsf{unlockPoint}}
\newcommand{\lockres}{\mathsf{c}}
\newcommand{\idealunlock}{\mathsf{idealUnlock}}
\newcommand{\oraclequeries}{q(\securityparam)}
\newcommand{\keylength}{\kappa}
\newcommand{\numerrors}{t}
\newcommand{\fuzzerror}{\delta}
\newcommand{\lockerror}{\gamma}


%\newenvironment{psketch}{\renewcommand{\proofname}{Proof Sketch}\proof}{\endproof}
\title{Non-malleable Digital Lockers\\for Efficiently Sampleable Distributions}
\ifnum\lncs=0
\author{Peter Fenteany\footnote{Email: \texttt{peter.fenteany@uconn.edu}. University of Connecticut.} \and Benjamin Fuller\footnote{Email: \texttt{benjamin.fuller@uconn.edu}.  University of Connecticut.}}
\fi
\begin{document}

\maketitle

\begin{abstract}
An obfuscated program reveals nothing about its design other than its
input/output behavior. A digital locker is an obfuscated program that outputs
a stored cryptographic key if and only if a user enters a previously stored
password. A digital locker is private if it provides an adversary with no
information with high probability. An ideal digital locker would also prevent an
adversary from mauling an obfuscation on one password and key into a new
program that obfuscates a related password or key. Such a primitive is 
achievable using a common reference string or in the random oracle model.
However, there are no known standard model
constructions of non-malleable digital lockers. %In the standard model, 
Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive: a
 \emph{non-malleable point function} which is a digital locker with no key. %For this functionality, a user can only
%confirm if their point is correct. %Their construction prevents an adversary from transforming
%an obfuscation into an obfuscation on a related password.

This work describes the first non-malleable digital locker.  
This construction is built in two main steps:

\begin{enumerate}
\item Constructing non-malleable digital lockers for short keys. We present one construction for a single bit key and a second for a logarithmic length keys.  These constructions can be safely composed with the same input password.  This composed construction is non-malleable with respect to the password. 
\item An extension to polynomial length keys that additionally provides nonmalleability over the stored key. This extension combines the digital locker for short keys, non-malleable codes, and
seed-dependent condensers.  Our use of seed-dependent condensers require the password distribution to be efficient sampleable. 
\end{enumerate}
Nonmalleability for the password is ensured for functions that can be represented as low degree polynomials. Key nonmalleability is ensured for the class of functions prevented by the non-malleable code.

  \textbf{Keywords:} Digital Lockers; Point obfuscation; Virtual black-box obfuscation; Non-malleable codes; Seed-dependent condensers
\end{abstract} 

\section{Introduction}

Obfuscation hides the implementation of a program from all users of the program. This work is concerned with \emph{virtual black-box obfuscation}, where an obfuscator creates a program that reveals nothing about the program other than its input and output behavior \cite{barak2001possibility,barak2012possibility}.  (We do not consider indistinguishability obfuscation in this work~\cite{garg2013candidate,garg2016candidate,sahai2014use,pass2014indistinguishability,gentry2015indistinguishability,ananth2015indistinguishability} \cite{brakerski2017obfuscating}.)
Barak et al.\,\,showed that a virtual black-box obfuscator cannot exist for all polynomial time circuits~\cite{barak2001possibility}. However, this leaves open the possibility of virtual black-box obfuscators for interesting classes of programs~\cite{canetti2008obfuscating,bitansky2010strong} \cite{canetti2010obfuscation,wichs2017obfuscating,brakerski2017obfuscating}.  %One recent class, called  compute and compare programs~\cite{wichs2017obfuscating}, obfuscates a program storing $f, y$ and $z$ which outputs $z$ when $f(\mathtt{input}) = y$ for polynomial time $f$. 

%This work considers virtual black-box obfuscation.
Our focus is on \emph{digital lockers}.  A digital locker obfuscator inputs a value, $\lockval$, and key, $\lockkey$.  The output is a program $\unlock_{ \lockval, \lockkey}(\cdot)$ which outputs $\lockkey$ if and only if the input is $\lockval$.  Privacy says $\unlock_{\lockval, \lockkey}$ should reveal nothing about $\lockval$ or $\lockkey$ if the adversary cannot guess $\lockval$.  A digital locker is also known as a multi-bit point obfuscation~\cite{canetti2008obfuscating,bitansky2010strong}.  Digital lockers have applications in password~\cite{canetti1997towards} and biometric authentication~\cite{canetti2016reusable,alamelou2018pseudoentropic}.

A simpler object to construct is a \emph{point function} $\pointunlock_{\lockval}$ which stores $\lockval$, opening if and only if the input is $\lockval$. An obfuscated point function only needs to hide $\lockval$~\cite{canetti1997towards}. It is possible to compose point functions to build a digital locker (if the point function retains security when composed)~\cite{canetti2008obfuscating}. The construction is straightforward, for each bit of the $\lockkey$, either a random point or $\lockval$ is obfuscated producing $\pointunlock_{y_i}$.  When running the program, the user tries to open each $\pointunlock_{y_i}$, the point functions that open represent $1$s in $\lockkey$.  The point function functions that do not open correspond to a $0$ in $\lockkey$.   We call this digital locker the \emph{real-or-random} construction.  %More precise For key bit $\lockkey_i =1$, the password is obfuscated, when $\lockkey_i=0$, a random point is obfuscated.

\ifnum\lncs=1
\textbf{Nonmalleability}
\else
\paragraph{Nonmalleability}
\fi
A desirable property of an obfuscated program is non-malleability. A \emph{non-malleable} obfuscator prevents any tampering of the obfuscation (for some family of functions $\mathcal{F}$) to obtain a related obfuscation~\cite{CanettiVaria2009}. For example, it is desirable to prevent $\pointunlock_{\lockval}$ from being mauled to $\pointunlock_{f(\lockval)}$.  In the random oracle model, designing non-malleable digital lockers and point functions is easy: for random oracle $\mathsf{RO}$ one outputs the program $\mathsf{RO}(\lockval) \oplus (\lockkey || \mathsf{RO}(\lockkey))$, where $\mathsf{RO}(\lockkey)$ is truncated.  Furthermore, in the common reference string model, one can achieve nonmalleability using appropriate zero-knowledge proofs of knowledge~\cite{boldyreva2009foundations}.

Recently, Komargodski and Yogev showed how to build a non-malleable  point obfuscators in the standard model~\cite{komargodski2018another}. Their construction is as follows, let $g$ be a fixed group generator, to obfuscate the point $\lockval$, the obfuscator computes a random $r$ and outputs $\mathcal{O}(x) = (r, r^{g^{h(\lockval)}})$. Here $h(x)= x^4+x^3+x^2+x$.  As we explain below, the function $h$ is designed specifically to prevent mauling.

Security of the construction relies on two variants of the Decisional Diffie-Hellman (DDH) assumption~\cite{diffie1976new} - the strong DDH assumption (see~\cite{bitansky2010strong}) and the power DDH assumption (introduced in~\cite{golle2002cryptographic}). For an obfuscated point $\lockval$, the construction prevents the adversary from changing $\lockval$ to $f(\lockval)$ for a polynomial $f$ (whose degree is related to the assumed hardness in the power DDH assumption).  The question of this work is:
\begin{quote}
Do non-malleable digital lockers exist in the standard model?
\end{quote}

One could try and compose Komargodski and Yogev's construction for each bit of the key using the \emph{real-or-random} construction. However, that approach does not ensure nonmalleability over the bits of $\lockkey$.   It is easy to permute bits of $\lockkey$ by reordering group elements and to set individual bits of $\lockkey$ to $0$ by replacing a group element by a random  group element.  %Non-malleability of $\lockkey$ is more important than non-malleability over $\lockval$.  
Consider a case when a user encrypts their files with $\lockkey$. If the adversary can create $\lock_{\lockval, \lockkey'}(\cdot)$, the user may use some cryptographic key that is known to the adversary or susceptible to cryptanalytic attack~\cite{bellare2011cryptography}. %On the other hand, causing a user to authenticate with some value $\lockval'$ requires a separate attack.  


\subsection{Our Contribution}
We present the first construction of a non-malleable digital locker in the standard model.  
As mentioned, the \emph{real-or-random} digital locker does not prevent mauling of $\lockkey$.  To prevent mauling of $\lockkey$, a natural idea is to use some integrity primitive $\mac$ and include $\mac(\lockkey)$ in the real-or-random construction. %You could use a ``keyed'' primitive where $\mac$ has some private information or ``keyless'' primitive were the adversary is assumed to know the description of $\mac$.  %Both approaches are problematic:

%\begin{description}
%\item[Keyed] 
A natural primitive is a one-time message authentication code (MAC) or a non-malleable extensions~\cite{dodis2009non}.  However, the only private randomness in the system is $\lockval$.  No distribution is assumed over $\lockkey$ from the construction's perspective. However, from the attacker's perspective, $\lockval$ and $\lockkey$ might be drawn from correlated random variables.  If we use $\lockval$ to ``key'' the MAC, then the MAC used must be secure for low entropy keys and have some circular security properties~\cite{boneh2008circular,brakerski2010circular}.   Dealing with these issues seems to require new techniques.% our solution combines seed-dependent condensers and non-malleable codes (see Section~\ref{ssec:authstrategy}).

Before detailing our authentication approach, we make a small but important change to the cryptographic primitive that is being composed.  Instead of composing point functions, we compose digital lockers that natively store a small number of key bits. We present two constructions of digital lockers that support short keys and are secure when composed with the same $\lockval$: one that supports a single bit and the second for a logarithmic number of bits.  %This change removes some trivial attacks: this prevents the adversary from forcibly obfuscating a ``0'' bit of $\lockkey$ by obfuscating a random point, a risk with the \emph{real-or-random} construction.

\ifnum\lncs=1
\paragraph{The single-bit digital locker}
\else
\paragraph{The single-bit digital locker}
\fi
Point obfuscators output 1 on the correct input and $0$ everywhere else.  Our \emph{single-bit digital locker} has three possible outputs: $1$, $0$, and $\perp$ (to indicate an incorrect point). To specify the output, the obfuscator now takes an additional bit $b$ as input.  %There are two reasons for this change. First, the change prevents the trivial attack: changing a group element to a random value to set it to an obfuscation of the bit $0$.  Second, the employed techniques will be crucial for supporting non-malleable codes with nonbinary symbols.
Our construction of a single-bit digital locker is:
\[
    \mathcal{O}(\lockval, b) = (r, r^{g^{h(2*\lockval+b)}}) = (r, r^{g^{h(\lockval || b)}}).
\]
Here $h(x) = x^4+x^3+x^2+x$ as in Komargodski and Yogev's point function obfuscator.  With a known value $\lockval'$ the user attempts to unlock with both values of $b$.  Since the underlying function $h$ is one-to-one, the construction remains correct.  The intuitive argument for nonmallability of a single obfuscation is simple, if an adversary could change either $x$ or $b$ that would correspond to a break of the original system.

However, to create a digital locker requires composition of several obfuscations.  This small modification makes it more difficult to show nonmalleability (even just for functions on $\lockval$).  This is because the adversary now gets access to obfuscations of two distinct points $2\lockval$ and $2\lockval+1$.  Now the adversary may be able to compute a function $f'$ that takes $h(2\lockval), h(2\lockval +1)$ and $1$, yielding $h(2\lockval'+b')$.  Despite this additional information provided to the adversary, Theorem~\ref{thm:digital locker} states it is still difficult to maul using a bounded degree polynomial.

In Theorem~\ref{thm:digital locker}, we have to directly reduce to the strong power and strong vector Diffie-Hellman assumptions (defined in Section~\ref{ssec:hardness assumptions}).  Previous constructions of multi-bit point obfuscators~\cite{canetti2008obfuscating,bitansky2010strong} could be constructed generically from any point obfuscator (assuming the underlying point obfuscator is ``secure'' when composed).  

\paragraph{Extending to nonbinary alphabet}
Our second construction builds a digital locker that encodes a logarithmic number of bits in a pair of group elements.  %This construction enables substantially more flexibility in providing nonmalleability over the locked $\lockkey$ in a digital locker.  
Suppose that we wish to encode $\tau$ bit symbols in each group element.  The most natural idea is to extend our first construction by computing $h(2^\tau *\lockval +\lockkey_i)$.  As stated above, in the single bit case, nonmalleability required showing that given $h(2\lockval)$ and $h(2\lockval+1)$ it was difficult to compute $h(2\lockval'+b')$.  Under the power DDH assumption (see Section~\ref{ssec:hardness assumptions}) this requires one to show that $h(2\lockval'+b)$ is linearly independent of $h(2\lockval)$ and $h(2\lockval+1)$.  Since $h(x)=x^4+x^3+x^2+x$, the space spanned by differed $h(x)$ is only dimension $4$.  Naturally, as the adversary is given more linearly independent values $h(2^\tau*\lockval+\lockkey_i)$ these span a larger dimensional space and it becomes impossible to show that fresh values are linearly independent.  
To address this problem we use a new hash function for symbols $y\in\zo^\tau$:
\[
h(x , y) = \left(\sum_{i=\tau}^{4+\tau} (x+2)^{i} \right) +\left(\sum_{i=0}^{\tau-1}y_j \cdot (x+2)^i\right).
\]
This construction ensures that all $2^\tau$ different values of $y$ span at most a $ \tau$ dimensional subspace and cannot be used to predict the value of the hash function for any $x'\neq x$.  There are a few notes about this new construction:
\begin{enumerate}
\item Opening checks each possible $y$ value, running time is proportional to $2^{\tau}$ making this construction efficient when $\tau = O(\log (\lambda))$.
\item Our single bit construction used a polynomial that included four nonzero powers.  This construction has $5$ powers that are not multiplied by part of $y$.  If only $4$ powers are not multiplied by a bit of $y$, there are three values of $\tau$ where nonmalleability is not guaranteed.  This is because the choice of $\tau$ introduces a new degree of freedom to the linear system.  The three values of $\tau$ are solutions to  $\tau^3-15\tau^2 -52\tau -12 \equiv 0 \mod p$.  It would be possible to avoid these $\tau$ by checking when $\tau$ is a solution for a particular $p$. Instead, our construction adds another power of $x$, which retains a single bad $\tau$ which is $\tau \equiv p-5$.  This value of $\tau$  never occurs for logarithmic $\tau$.
\item To ensure the construction is correct and one-to-one, we restrict $x\in\zo^{\lambda-1}$ and compute powers of $x+2$.  We can think of the construction as taking a subset of powers of $x$, we need to manually exclude $x\in\{0,1\}$ to ensure the function is one-to-one.
\item The group operations need to be in a group of size $(6+\tau)\lambda$ to ensure that operations do not overflow.  In the first construction this size is only $5\lambda$.
\end{enumerate} 

\noindent We note that neither of these constructions make any attempt to prevent tampering of $\lockkey$.

\subsection{Authenticating the $\lockkey$}
\label{ssec:authstrategy}
Having described digital lockers for a small number of bits, we now turn to authenticating $\lockkey$.  Our authenticator combines seed-dependent condensers~\cite{dodis2012randomness} and non-malleable codes~\cite{dziembowski2010non}.  Our goal is construct a string $s$ that decodes to $\lockkey$ and is difficult to tamper.  Our strategy has two components: 1) use a non-malleable code to ensure an adversary can only tamper to independent values and 2) use a seed-dependent condenser to ensure an independent value is unlikely to authenticate.  The construction proceeds as follows:
\begin{enumerate}
\item First, we compute $d = \cond(\lockval, \seed)$ where $\cond$ is a seed-dependent condenser.   A seed dependent condenser is an object that has a high entropy output even if the distribution over $\lockval$ is adversarially dependent on the randomness $\seed$.  Seed-dependent condensers for efficiently sampleable distributions are instantiable using collision-resistant hash functions~\cite[Theorem 4.1]{dodis2012randomness}.  Since there is no requirement on the distribution of $\lockval$ being independent of $\seed$, the same $\seed$ can be used universally and be a system parameter. 

We then compute $c = \lockkey || \cond(\lockval; \seed)$.  Note, an adversary outputting any fixed $\tilde{c}$, that does not depend on the received obfuscated programs, is unlikely to match the output of the condenser.

\item To ensure that an adversary is limited to ``independent'' tampering, we use a non-malleable code.
Let $\mathcal{F}$ be some function class.  A non-malleable code is a pair \enc and \dec where for functions $f\in\mathcal{F}$ the value $\tilde{s} = \dec(f(\enc(s)))$ is independent of $s$. We set \[s = \enc(c) = \enc(\lockkey || \cond(\lockval ; \seed)).\]  

However, there is a problem with using a non-malleable code here.
In a non-malleable code, the adversary specifies the tampering function before seeing any information about $\enc(\lockkey)$.  In our setting, the adversary sees obfuscations correlated to $\enc(\lockkey)$ before deciding how to tamper. We show that non-malleable codes can be used a nonstandard way where the tampering function is chosen after seeing the obfuscated values (assuming a pseudorandomness condition,  see Theorem~\ref{thm:adaptive nmc}).
%\item% The main application of non-malleable codes is for tamper resilient storage.  In this setting, letting the adversary tamper to an independent value $\overline{\lockkey}$ does not affect the security of $\lockkey$. 
%Non-malleable codes allow tampering to an independent value $\tilde{s}$. Having to match the output of the condenser guarantees such an attack is likely to be detected.  
%%\item Many non-malleable codes require an \emph{alphabet} size of more than a single bit.  Its not clear how to encode more than a single bit in the real-or-random digital locker construction.
%\end{enumerate}
\end{enumerate}

\ifnum\lncs=1
\textbf{Other approaches}
\else
\paragraph{Other approaches}
\fi
%A tempting solution is to set $s =\lockkey || \cond(\lockval ||, \seed)$ (removing the non-malleable code).  The guarantee of a seed-dependent condenser is that the output has entropy even if the input distribution depends on the seed.  On its own, it provides no non-malleability.
Non-malleable extractors~\cite{dodis2009non,cohen2014nonmalleable} and non-malleable one-way hashes~\cite{boldyreva2009foundations,baecher2011expedient,chen2016non} may be suitable for authenticating $\lockkey$.  These objects  guarantee that the adversary tampers to an independent value like non-malleable codes.  We such analysis of such constructions as future work. 

%We consider the state of affairs when using just a non-malleable code.  Suppose that the non-malleable code directly encodes the final $\lockkey$.  That is, the untampered $c =\enc(\lockkey)$.  First, under the strong vector DDH assumption (see Section~\ref{ssec:hardness assumptions}), it is possible to show the values provided to the adversary are pseudorandom even knowing $c = \enc(\lockkey)$.  That is,
%\begin{align}
%(\{r_i, r_i^{g^{h(2*\lockval+c_i)}}\}_{i=1}^k, c) \approx (\{(r_i, u_i)\}_{i=1}^k, c) \label{eq:pseudorandomness}
%\end{align}
% for uniform group elements $u_i$.  This pseudorandomness results from uncertainty in $\lockval$.  For an adversary $\mathcal{A}'$, we consider the two distributions of functions 
% \begin{align*}
% \mathcal{F}_{real} &\overset{def}=\mathcal{A}'(\{r_i, r_i^{g^{h(2*\lockval+c_i)}}\}_{i=1}^k)\\
% \mathcal{F}_{ideal}&\overset{def}=\mathcal{A}'(\{(r_i, u_i)\}_{i=1}^k).
% \end{align*} By the security of non-malleable codes for an average $f\leftarrow \mathcal{F}_{ideal}$ should only be able to tamper to $\overline{c}$ where $\dec(\overline{c})$ is independent of $\lockkey$.  If we can design a test to tell when the adversary tampers to an independent value, by Equation~\ref{eq:pseudorandomness}, we can ensure the same is true for an average element of $\mathcal{F}_{real}$.  That is, we can allow the adversary to adaptive define the tampering function without a loss in security (in the presence of such a test). 
% 
%We use the keyed primitive to create this test. For a digital locker to provide security, $\lockval$ must be drawn from a distribution with super-logarithmic min-entropy.  Since we know the adversary is tampering to an independent value, one could simple include $\lockval$ as part of the encoded value $s  = \enc( \lockkey || \lockval)$.  However, this would break the pseudorandomness in Eq~\ref{eq:pseudorandomness}.  Instead, we use a universal hash, $\uhash$, of $\lockval$, to create $s=\enc(\lockkey || \uhash(\lockval))$.  It is important for $\lockval$ to have entropy conditioned on the universal hash, so the output length of the hash must depend on the starting entropy of $\lockval$.

%Ideally, we would include $\uhash$ as part of the obfuscated value.  We are not aware of an method to extract entropy when the adversary is allowed to adaptively maul the public randomness, given the legitimate output value.  As an example, randomness extractors~\cite{nisan1993randomness} take a source of min-entropy and convert it nearly uniformly random.  Randomness extractors require a short \emph{public} $\mathtt{seed}$ to perform this task.  That is, $(\ext(\lockval, \mathtt{seed}), \mathtt{seed})$ is close to random.  There are non-malleable extractors~\cite{dodis2009non}.  In a non-malleable extractor, an adversary can maul a $\mathtt{seed}$ into a related $\overline{\mathtt{seed}}$.  The security guarantee is that the extractor should have independent outputs on $\mathtt{seed}$ and $\overline{\mathtt{seed}}$.  However, the adversary would receive both $(\ext(\lockval, \mathtt{seed}), \mathtt{seed})$ before selecting $\overline{\mathtt{seed}}$.  non-malleable extractors provide no guarantees in this setting.

%Instead, we resort to placing the description of a universal hash function, $\uhash$, in a \emph{common reference string} (CRS) that cannot be tampered by the adversary.  We note that the construction already requires the description of a group and a generator to be universal parameters.  By adding a check if the end of $\dec(\overline{c})_{n...n+\alpha} = \uhash(\lockval)$ we solve two problems simultaneously 1) it is possible to argue that the tampering function $f$ does not depend on the provided values and 2) it is possible to test if the tampering function outputs an independent value.  The probability of any independent value matching $\uhash(\lockval)$ is small.  Importantly, we require the distribution of input points $X$ to be independent of the $\uhash$ description. ($X$ may be correlated with the group description and generator.)


\ifnum\lncs=1
\textbf{Choosing a non-malleable code}
\else
\paragraph{Choosing a non-malleable code}
\fi
There are non-malleable codes that prevent the adversary from permuting the bit vector, setting individual bits, and arbitrary functions that are applied separately to different parts of the encoded value.  This class of of adversary is called a ``split-state'' adversary.  More recently, Chattopadhyay and Li described a construction that prevents tampering in the class $\mathtt{AC0}$~\cite{chattopadhyay2017non}.  We recommend using a non-malleable code that prevents at least setting and flipping of individual bits and permutations~\cite{agrawal2015explicit} \cite{agrawal2015rate}.  One concern about non-malleable codes is that the adversary is \emph{necessarily} restricted to low complexity classes, not including the code's encoding and decoding functions.  Note, we are encoding and decoding the code ``in the clear'' while the adversary is tampering ``in the exponent.''

\ifnum\lncs=1
\textbf{Non-malleable codes with manipulation detection}
\else
\paragraph{Non-malleable codes with manipulation detection}
\fi
Recently, Kiayias  et al.~\cite{kiayias2018non} introduced \emph{non-malleable codes with manipulation detection}.  Here, the adversary has low probability of producing any codeword $\tilde{c}$ that successfully decodes. (Clearly, the class of tampering functions cannot contain constant functions.)  Kiayias et al.\,constructed a non-malleable code with manipulation detection but their construction requires each symbol of the code to come from a polynomial size alphabet or equivalently for each symbol to have logarithmic length. Note this can be handled by our second construction.  With this strengthened object our construction does not need the seed-dependent condenser.  However, Kiayias et al.'s construction does not exclude functions which are efficiently computable against our construction such as permutations. If stronger non-malleable codes with manipulation detection are discovered, the construction may be easily ported.

\ifnum\lncs=1
\textbf{Open Questions}
\else
\paragraph{Open Questions}
\fi
We present two main open questions resulting from this work.  The first is whether our construction can be modified to use other non-malleable primitives such as extractors or one-way hashes.
The second open question is for our multi-bit digital locker: would a different polynomial allow for a more compact group and thus more efficient operations?  It seems necessary for the group size to scale with $\tau$ if the linear independence argument is used.  It may be possible to compress group size by allowing imperfect correctness.

\ifnum\lncs=1
\textbf{Organization}
\else
\paragraph{Organization}
\fi
The rest of this work is organized as follows Section~\ref{sec:Definitions} reviews definitions and computational assumptions, Section~\ref{sec:single bit} introduces the single bit digital locker and shows security under composition for $\lockval$, Section~\ref{sec:full construction} adds nonmalleability for $\lockkey$, lastly Section~\ref{sec:multibit} shows how to support multiple bits in each pair of group elements, enabling support for  logarithmic size symbols.
\section{Definitions and Background}

\label{sec:Definitions}
\label{sec:preliminaries}
For a random variables $X_i$ over some alphabet $\mathcal{Z}$ we denote by $X = X_1,..., X_\sourcelen$  the tuple $(X_1,\dots, X_\sourcelen)$.  For a set of indices $J$, $X_{J}$ is the restriction of $X$ to the indices in $J$.  The {\em minentropy} of $X$ is $\Hoo(X) = -\log(\max_x \Pr[X=x])$,
and the {\em average (conditional)} minentropy~\cite[Section 2.4]{DBLP:journals/siamcomp/DodisORS08} of $X$ given $Y$ is  \[\Hav(X|Y) = -\log\left(\expe_{y\in Y} \max_{x} \Pr[X=x|Y=y]\right).\]
The {\em statistical distance} between random variables $X$ and $Y$ with the same domain is \[\Delta(X,Y) = \frac12 \sum_x |\Pr[X=x] - \Pr[Y=x]|.\]
For a distinguisher $D$, the \emph{computational distance} between $X$ and $Y$ is $\delta^D(X,Y) = \left| \expe[D(X)]-\expe[D(Y)]\right |$ (we extend it to a class of distinguishers $\mathcal{D}$ by taking the maximum over all distinguishers $D\in\mathcal{D}$).  We denote by $\mathcal{D}_{s}$ the class of randomized circuits which output a single bit and have size at most $s$.
 Logarithms are base $2$.
Usually, we use capitalized letters for random variables and corresponding lowercase letters for their samples. 

%\subsection{Point Functions and Digital Lockers}

\paragraph{Single Bit Digital Locker}
A point function is a function $I_\lockval$: $\{0,1\}^n \mapsto \{0,1\}$ outputs 1 on input $x$ and 0 elsewhere. An obfuscator  preserves functionality while hiding the point $\lockval$ if $\lockval$ is not provided as input to the program.  We will build a function that outputs a single bit when $\lockval$ is provided: $I_{\lockval, b}$: $\{0,1\}^n \mapsto \{\perp, 0, 1\}$.  Here $I_{\lockval, b}(\lockval) =b$ and $I_{\lockval,b}(\lockval') = \perp$ for all other points $\lockval'\neq \lockval$. We call this primitive a \emph{single-bit digital locker}.  All definitions all include a requirement of \emph{polynomial slowdown}, which is omitted for brevity.  We define a single-bit digital locker by adapting Komargodski and Yogev's definition~\cite{komargodski2018another}:

\begin{definition} \label{def:PointObfuscator}
For security parameter $\lambda\in\mathbb{N}$
a \textbf{single bit digital locker} $\lock$ is a probabilistic polynomial-time algorithm that inputs a point $\lockval \in \{0,1\}^{\lambda-1}$ and a bit $b\in\zo$, and outputs a circuit $\unlock$ such that the following two conditions are met:

\begin{enumerate}
    \item \textbf{Completeness}: For all $\lambda\in\mathbb{N}$, all $x\in\{0,1\}^{\lambda-1}$, and either $b\in\{0,1\}$, it holds that $\Pr[\unlock(\cdot) \equiv I_{x, b}(\cdot) | \unlock \leftarrow \lock(x, b)] = 1$, where the probability is over the randomness of $\lock$.

    \item \textbf{Soundness}: For every probabilistic polynomial-time algorithm $\mathcal{A}$ and any polynomial function $p$, there exists a (possibly inefficient) simulator $\mathcal{S}$ and a polynomial $q(\lambda)$ such that, for all large enough $\lambda\in\mathbb{N}$, all $\lockval\in\{0,1\}^{\lambda-1}$, any single bit $b$, and for any $\mathcal{P}: \{0, 1\}^\lambda \mapsto \{0,1\}$,
\[
        \left|\Pr[\mathcal{A}(\lock(\lockval, b)) = \mathcal{P}(\lockval,b)] - \Pr[\mathcal{S}^{I_{\lockval,b}}(1^\lambda) = \mathcal{P}(\lockval, b)]\right| \leq \frac{1}{p(\lambda)},
\]
where $S$ is allowed  $q(\securityparam)$ oracle queries to $I_{\lockval, b}$
and the probabilities are over the internal randomness of $\mathcal{A}$ and $\lock$, and of $\mathcal{S}$, respectively.  Here $I_{x, b}$ is an oracle that returns $b$ when provided input $x$ otherwise $I_{x, b}$ returns $\perp$.
\end{enumerate}

\end{definition}

\noindent
We note the above definition is \emph{virtual grey-box obfuscation} as the simulator is allowed unbounded time but a limited number of queries.  The definition of a point function is analagous with the removal of $b$ and a suitable change to the ideal oracle $I$.

We directly adapt the definition of nonmalleability from Komargodski and Yogev.  We do note that in their definition the adversary that is performing the mauling must output the mauling function $f$.  See Komargodski and Yogev for definitional considerations~\cite{komargodski2018another}.  Their construction also depends on an obfuscation being easy to recognize.  Our constructions consist of pairs of group elements and are easy to recognize.

\begin{definition}
A PPT algorithm $\mathcal{V}$ for a digital locker, $\lock$, for $\lockval\in\zo^{\lambda-1}$, $b\in\zo$  is  called a verifier if for all $\lambda \in \mathbb{N}$ and all $\lockval\in\{0,1\}^{\lambda-1},b\in\zo$, it holds that $\Pr[\mathcal{V}(\lock(x,b)) = 1]=1$, (prob. over the randomness of $\mathcal{V}$ and $\lock$).
\end{definition}

With this definition, we can define nonmalleability.  Our definition includes the bit $b$, does not assume a distribution over $b$, and does not assume hardness of the adversary tampering with $b$.

\begin{definition}
\label{def:non malleability}
Let $\lock$ be a single bit digital locker for $\lockval\in\{0,1\}^{\lambda-1}$ with an associated verifier $\mathcal{V}$.  Let $ \mathcal{F}: \zo^{\lambda-1} \rightarrow \zo^{\lambda-1}$ be a family of functions and let $\mathcal{X}$ be a family of distributions over $\zo^{\lambda-1}$.
A single bit digital locker $\lock$ is \emph{non-malleable} for $\mathcal{F}$ and $\mathcal{X}$ if for any polynomial-time adversary $\mathcal{A}$, there exists a negligible function $\epsilon$, such that for all $b\in \zo$ it holds that:
\[
\Pr_{\lockval\leftarrow {\mathcal{X}}}\left[ \mathcal{V} (C) = 1, f\in\mathcal{F},(I_{f(\lockval),0}  \equiv C \vee I_{f(\lockval),1}  \equiv C )| (C, f) \leftarrow \mathcal{A}(\lock(\lockval)) \right] \le \epsilon.
\]

\end{definition}

\paragraph{Digital Locker}
Our full construction is a non-malleable digital locker.  In this section we present two definitions, the first ensures nonmalleability over just the encoded point $\lockval$.  The second provides nonmalleability over both the encoded point $\lockval$ as well as $\lockkey$.  These definitions are used in Section~\ref{sec:single bit} and Section~\ref{sec:full construction} respectively. 

\begin{definition}
\label{def:digital lockers}
The algorithm $\lock$ with security parameter $\securityparam$ is secure digital locker 
%= \lockerror(\securityparam)$
 if the following hold:

\begin{itemize}
\item \textbf{Correctness} For every $\lockkey$ and $\lockval$, \[\Pr[\unlock(\cdot) \equiv I_{\lockval, \lockkey}(\cdot) | \unlock\leftarrow \lock(\lockval, \lockkey)] = 1.\]
\item \textbf{Security} For every PPT adversary $\mathcal{A}$ and every positive polynomial $p$, there exists a simulator $S$ and a polynomial $\oraclequeries$ such that for any sufficiently large $\lambda$,  any polynomially-long sequence of values $(\lockval_i, \lockkey_i)$ for $i=1,\dots, \composition$, and for any predicate $\mathcal{P}$, 
\[
\left  | \Pr \left[\mathcal{A}\left(\lock(\lockval, \lockkey)\right) = \mathcal{P}(\lockval, \lockkey)\right]- \Pr\left[\mathcal{S}^{I_{\lockval,\lockkey}}(1^\lambda) = \mathcal{P}(\lockval, \lockkey)\right]\right|\le \frac{1}{p(\lambda)}
\]
where $\mathcal{S}$ is allowed  $q(\securityparam)$ oracle queries to the oracle $I_{\lockval, \lockkey}$.
\end{itemize}
\label{def:basic digital locker}
\end{definition}

\begin{definition}
Let  $\mathcal{F}:\zo^{\lambda}\rightarrow \zo^{\lambda}$ be a family of functions and let $\mathcal{X}$ be a family of distributions over $\zo^{\lambda}$.  A digital locker, $\lock$, with security parameter $\lambda$ is \emph{point} non-malleable for $\mathcal{F}$ if for any PPT $\mathcal{A}$ there exists a negligible function $\epsilon$ such that for all $\lockkey\in\zo^k$ it holds that:
\begin{align*}
\Pr_{x\leftarrow \mathcal{X}}\left[\begin{tabular}{c}
$ (\unlock', f) \leftarrow \mathcal{A}(\lock(\lockval, \lockkey))$\\
$ \mathcal{V} (\unlock') = 1, f\in\mathcal{F},\exists \lockkey'\in \zo^k\wedge (I_{f(\lockval),\lockkey'}  \equiv \unlock')$
 \end{tabular} \right] \le \epsilon.
\end{align*}
\end{definition}

\begin{definition}
Let  $\mathcal{F}:\zo^{\lambda}\rightarrow \zo^{\lambda}, \mathcal{G}:\zo^n\rightarrow \zo^n$ be families of functions and let $\mathcal{X}$ be a family of distributions over $\zo^{\lambda}$.  A digital locker, $(\lock, \unlock)$, with security parameter $\lambda$ is \emph{point} non-malleable for $\mathcal{F}$ and \emph{key} non-malleable for $\mathcal{G}$ if for any PPT $\mathcal{A}$ there exists a negligible function $\epsilon$ such that for all $\lockkey\in\zo^k$ it holds that:
\begin{align*}
\Pr_{x\leftarrow X}\left[
\begin{tabular}{c}
$(\unlock', f, f') \leftarrow \mathcal{A}(\lock(\lockval, \lockkey)) $\\
$ \mathcal{V} (\unlock') = 1, f\in\mathcal{F}, f'\in\mathcal{G}\wedge(I_{(f(\lockval),f'(\lockkey))}  \equiv \unlock')$\end{tabular} \right] \le \epsilon.
\end{align*}
\end{definition}

\subsection{Hardness Assumptions}
\label{ssec:hardness assumptions}

Our constructions will rely on multiple decisional assumptions in suitable groups.  The most well known assumption is the decisional Diffie-Hellman (DDH) assumption which says that for a prime $p$ for a generator $g$ of $\mathbb{Z}_p^*$ the tuple $(g, g^x, g^y, g^{xy})$ is computationally indistinguishable from $(g, g^x, g^y, g^u)$ where $x$, $y$, $u$ are uniform elements in $\mathbb{Z}_p^*$.  
We consider an ensemble of groups with efficient operations where $\mathbb{G}_\lambda$ is a group of prime order $p\in(2^{\lambda}, 2^{\lambda+1})$.

The first assumption that we will use is the strong $\ell$-vector assumption introduced by Bitansky and Canetti~\cite{bitansky2010strong}.  This strengthens the DDH assumption in two ways.  First, the values $x$ are not drawn from uniform powers but rather from a well spread distribution.  Second, the adversary is given multiple samples from correlated distributions $\mathcal{X}_1,..., \mathcal{X}_\ell$.  The only guarantee is on the marginal distribution of each $\mathcal{X}_i$.  Nothing is guaranteed about the joint distribution.  As an example, each distribution could be identically distributed.  Here we introduce a new variant of this assumption where each distribution has average min-entropy. 

\begin{definition}
\label{def:well spread}
An ensemble of joint distributions $(\mathcal{X}, \mathcal{Y}) = \{X_\lambda, Y_\lambda\}_{\lambda \in \mathbb{N}}$, where $\mathcal{X}_\lambda$ is over $\zo^\lambda$, is \emph{average case well-spread} if 
\begin{enumerate}
\item It is efficiently and uniformly samplable.  That is, there exists a PPT algorithm given $1^\lambda$ as input whose output is identically distributed as $(X_\lambda, Y_\lambda)$.
\item For all large enough $\lambda \in\mathbb{N}$, it has super-logarithmic conditional min-entropy.  Namely,
$
\Hav(X_\lambda | Y_\lambda) = \omega (\log \lambda).
$
\end{enumerate}
\end{definition}

\begin{assumption}[$t$-Strong Average Vector DDH]
Let $\ell = \poly(\lambda)$ be a parameter and let $\mathbb{G}_\lambda$ be an ensemble of groups with efficient representation and operations.  We say that the \emph{$t$-strong average vector decision Diffie-Hellman assumption} holds if for any vector $\mathcal{X}, \mathcal{Y}$ where $\mathcal{X}$ is a vector in $(\mathbb{Z}_p^*)^t$ that is average case well-spread it holds that for every $s_{sec} = poly(\lambda)$ there exists some $\epsilon = \ngl(\lambda)$ such that :
\begin{align*}
\delta^{s_{sec}} \left( (g_1, g_1^{x_1}, y_1,..., g_t, g_t^{x_t}, y_t), (g_1, g_1^{u_1}, y_1,..., g_t, g_t^{u_t}, y_t)\right)\le \epsilon.
\end{align*}
Where $((x_1, y_1), ..., (x_t, y_t)\leftarrow (\mathcal{X}, \mathcal{Y})$ and $u_i$ is sampled uniformly from $\mathbb{Z}_p^*$.
\end{assumption}

We use this variant as it is conceptually cleaner but random variables with super logarithmic average min-entropy have worst-case super-logarithmic min-entropy with overwhelming probability.  Thus, there is not a qualitative difference between the average case assumption and a worst case formulation.

The second assumption we will consider is a variant of the power DDH assumption.  The $t$-power DDH assumption~(introduced in~\cite{golle2002cryptographic}) says that increasing powers of a single element $x$ are indistinguishable from uniformly random.  That is, $(g, g^x, g^{x^2},..., g^{x^t})$ is pseudorandom for a uniformly random $x$.
%\begin{assumption}[$t$-Power DDH] The $t$-power DDH assumption asserts that a the group $\mathbb{G}_\lambda$ with associated generator $g$, for any $s_{sec} = \poly(\lambda)$ there exists $\epsilon = \ngl(\lambda)$ such that 
%\begin{align*}
%\delta^{s_{sec}} ((g, g^{x} , g^{x^2}, ..., g^{x^t}), (g, g^{r_1}, g^{r_2},..., g^{r_t})) \le \epsilon.
%\end{align*}
%Here the elements $x, r_1,..., r_t$ are sampled uniformly at random from $\mathbb{Z}_p^*$.
%\end{assumption}
One can naturally extend the power DDH assumption assumption to the strong setting:
\begin{assumption}[$t$-Strong Average Power DDH]
\label{ass:power ddh}
The \emph{$t$-strong average DDH assumption} is said to hold for an ensemble of groups $\mathbb{G}_\lambda$ with associated generator $g$ if for any average-case well-spread distribution ensemble $\mathcal{X}, \mathcal{Y}$, the following holds for any $s_{sec} = \poly(\lambda)$ there exists $\epsilon = \ngl(\lambda)$ such that 
\begin{align*}
\delta^{s_{sec}} ((g, g^{X_\lambda} , g^{X_\lambda^2}, ..., g^{X_\lambda^t}, Y_\lambda), (g, g^{r_1}, g^{r_2},..., g^{r_t}, Y_\lambda)) \le \epsilon.
\end{align*}
where the distribution $(X_\lambda, Y_\lambda)$ is jointly sampled.  Here the elements $r_1,..., r_t$ are sampled uniformly at random from $\mathbb{Z}_p^*$.\end{assumption}
\section{Non-malleability for the locked value}
\label{sec:single bit}
\begin{construction}
Let $\lambda\in\mathbb{N}$ be a security parameter and let $\zo^{\lambda}$ be the domain.  Let $\mathcal{F}_{t,\poly} \overset{def}=\{f:\zo^{\lambda}\rightarrow \zo^{\lambda}\}_{\lambda\in\mathbb{N}}$ the ensemble of all functions that can be computed by polynomials of degree at most $t$ except constant and identity functions.  Let $\mathcal{G} = \{\mathbb{G}_\lambda\}_{\lambda\in\mathbb{N}}$ be a group ensemble with efficient representation and operations where each $\mathbb{G}_\lambda$ is a group of prime order $p\in(2^{\lambda}, 2^{\lambda+1})$.  We assume that for every $\lambda\in\mathbb{N}$ there is a canonical and efficient mapping between the elements of $\zo^{\lambda}$ to $\mathbb{G}_\lambda$.  Let $g$ be a generator of a group $\mathbb{G}_{5\lambda}$.  For known generator $g\in\mathbb{G}_{5\lambda}$, Our single bit digital locker gets an element $x\in\zo^{\lambda-1}, b\in\zo$ and randomness $r\in\mathbb{G}_{5\lambda}$. and outputs:
\[
\lock(x,b;r) \overset{def}= \left( r, r^{g^{(2x+b)^4+(2x+b)^3+(2x+b)^2+(2x+b)}} \right).
\]

\noindent
Given a program $\unlock$ consisting of two group elements $r', y'$ for test password $x$ and obfuscated program $\unlock$, the user runs both $\unlock(x, 0)$ and $\unlock(x, 1)$. That is, the user computes:
\begin{align*}
\unlock(x, 0) &= \left( (r')^{g^{(2x)^4+(2x)^3+(2x)^2+(2x)}} \overset{?}=y'.\right)\\
\unlock(x, 1) &= \left( (r')^{g^{(2x+1)^4+(2x+1)^3+(2x+1)^2+(2x+1)}} \overset{?}=y'.\right)
\end{align*}If $\unlock(x, b)$ outputs $1$ then the user outputs $b$.  Otherwise, $\perp$ is the  output.
\label{con:single bit digital locker}
\end{construction}

We will first show this construction is secure when the adversary receives a single instance and then discuss nonmalleability when composed.  %We will use two finite fieldsSo, for each bit $b$ in the output key, we create the following point function obfuscation. 
Throughout our discussion we use $h(z) = z^4+z^3+z^2+s$ as shorthand for the polynomial being computed in the exponent.
%Using a finite field of size greater than 5 times the security parameter $\lambda$ and using key $x = \{0,1\}^\lambda$ with $b$, we find the value $2x+b$ and calculate $h(2x+b)=(2x+b)^4+(2x+b)^3+(2x+b)^2+(2x+b)$ in the field. Then, we sample a random generator $r$ from $\mathbb{Z}_p^*$. Along with another parameter generator $g$, we first raise $g$ to the value $h(2x+b)$, and then raise $r$ to that power. Finally, we output $\mathcal{O}(x, b) = (r, r^{g^{h(2x+b)}})$.
In order to prove security of this construction for a single obfuscation we reduce to the construction of  Komgrodski and Yogev which computes $\pointlock(x; r) = (r, r^{g^{h(x)}})$ for input $x\in\zo^\lambda$.  The proof is deferred to Appendix~\ref{sec:one time}.


\begin{theorem}
\label{thm:single time digital locker}
Suppose that $\pointlock(x; r) = (r, r^{g^{h(x)}})$ is a non-malleable point function obfuscator for points $x\in\zo^{\lambda}$ for all distributions $X = \mathcal{X}_\lambda$ such that $H_\infty(X) = \omega(\log \lambda)$.  Then $\lock(x, b) = \pointlock(2x+b)$ is a single bit digital locker for inputs $x\in\zo^{\lambda-1}, b\in \zo$ for all distributions $X$ such that $H_\infty(X) = \omega(\log \lambda)$.
\end{theorem}

\subsection{Composing the Single Bit Construction} \label{Composability}

We now show this construction can be composed to built digital locker. This requires showing that soundness, completeness, and nonmalleability are preserved when the adversary is provided with single bit digital lockers that are correlated.  There are two things that could go wrong when an adversary receives single bit digital lockers on correlated points: 1) the inclusion of correlated points may allow the adversary to maul and 2) having multiple samples of points under different randomness may break privacy.  To prevent against tampering, we show security against an adversary that obtains $g^{h(2x)}$ and $g^{h(2x+1)}$.  That is, we don't rely on the generators $r_i$ in providing any protection against tampering. To show that privacy is preserved we rely on the $t$-strong vector DDH assumption.  Our construction is a simple concatenation of the single bit digital locker but the proof is substantially more involved.

\begin{construction}
Let all variables be as in Construction~\ref{con:single bit digital locker} and let $\lockkey\in \zo^n$ be some arbitrary value.  Then define $\lock(\lockval, \lockkey)$ as follows (initialize $\mathtt{Out}=\perp$): for $i=1$ to $n$ compute:
\begin{enumerate}
\item Sample $r_i \leftarrow \mathbb{G}_{5\lambda}$.
\item Append $\mathtt{Out} = \mathtt{Out} || (r_i,  (r_i)^{g^{(2\lockval+\lockkey_i)^4+(2\lockval+\lockkey_i)^3+(2\lockval+\lockkey_i)^2+(2\lockval+\lockkey_i)}})$.
\end{enumerate}
Define $\unlock(\lockval)$ as follows for input $\{r_i, y_i\}_{i=1}^n$: 

\noindent
For $i=1$ to $n$ compute:
\begin{align*}
\gamma_{i,0} &= (2\lockval)^4+(2\lockval)^3+(2\lockval)^2+(2\lockval)\\
\gamma_{i,1} &= (2\lockval+1)^4+(2\lockval+1)^3+(2\lockval+1)^2+(2\lockval+1)\\
P(x, 0, i) &= \left( r_i^{g^{\gamma_{i,0}}} \overset{?}=y_i.\right)\\
P(x, 1, i) &= \left( r_i^{g^{\gamma_{i,1}}} \overset{?}=y_i.\right)
\end{align*}\,\,\,\,\,If $P(x, b, i)$ outputs $1$ then the user sets $\lockkey_i = b$.  Otherwise output $\perp$.
\label{cons:digital locker}
\end{construction} 

\begin{theorem}
Suppose that 
\begin{enumerate}
\item The $n$-strong vector DDH assumption holds,
\item The $4t$-strong power DDH assumption holds,
\item The selected prime $p\not\in\{ 2,3,5,7,11\}$. (As $\mathbb{G}_\lambda$ increases these primes will never be selected.)
\item $X$ is a distribution over $\zo^{\lambda-1}$ such that $\Hoo(X) = \omega(\log \lambda)$.
\end{enumerate}
Then Construction~\ref{cons:digital locker} is point non-malleable for $\mathcal{F}=\{f | \deg(f)\le t\}$ (excluding constant polynomials and the identity polynomial).
\label{thm:digital locker}
\end{theorem}

\begin{proof}
We separately consider correctness, soundness, and nonmalleability.  Correctness is a direct extension of correctness for the single bit digital locker whose correctness is shown in Theorem~\ref{thm:single time digital locker}.  (The crucial fact is that $g^{h(2x+b)}$ is a one-to-one function.)

\noindent
\textbf{Privacy}
Define the random variables $\vec{X}\overset{def}=\{X_i = (X || \lockkey_i)\}_{i=1}^n$.  Since $X$ is distribution where $\Hoo(X) = \omega(\log \lambda)$, $\vec{X}$ is a average-case well spread distribution (according to Definition~\ref{def:well spread}).  Since the function \[f(x, b) = g^{(2x+b)^4+(2x+b)^3+(2x+b)^2+(2x+b)}\] is one-to-one it is also true that $g^{h(\vec{X})}$ is average-case well spread.  Komargodski and Yogev showed that a one-to-one function can be applied before obfuscation without effecting privacy~\cite[Claim 3.1]{komargodski2018another}.  This proof directly carries over to the single bit digital locker setting.  The strong vector DDH assumption then says that $\{r_i, r_i^{X_i}\}_{i=1}^n \approx \{r_i, u_i\}_{i=1}^n$ for uniform group elements $u_i$.  This means the construction satisfies a weaker notion called distributional indistinguishability~\cite[Definition 5.3]{bitansky2010strong}, which says no adversary can tell between obfuscations of related points and independent uniform points.  Bitanski and Canetti~\cite{bitansky2010strong} show that this definition implies composition for virtual-grey box obfuscation.  (Their proof is for point obfuscators but can be modified for this setting.)  Overall virtual grey box security then follows using arguments from~\cite{canetti2008obfuscating}.

\noindent
\textbf{Nonmalleability} We first recall that we use $h(x)$ to denote $x^4+x^3+x^2+x$.  
In order to prove nonmalleability is preserved, we will show how, given an adversary that can maul our obfuscation given two distinct obfuscations with the same point $x$, we can create an algorithm that can break the Strong Power DDH assumption.  We assume that $\lockkey$ is a value known to both the reduction and the adversary.  (That is, we do not rely on any uncertainty with respect to $\lockkey$.)  That is, we assume that there exists some $\lockkey$ and a PPT $\mathcal{A}$ such that for all negligible functions $\epsilon$:
\begin{align*}
\Pr_{x\leftarrow X}\left[\begin{tabular}{c}$ (\unlock', f) \leftarrow \mathcal{A}(\lock(\lockval, \lockkey)) $ \\$ \mathcal{V} (\unlock') = 1, f\in\mathcal{F},\exists \lockkey'\zo^n \wedge (I_{(f(\lockval),\lockkey')}  \equiv C)$\end{tabular}\right] >\epsilon.
\end{align*}
We show how to construct $\mathcal{A}'$ that breaks the $\tau = 4t$ strong power DDH assumption (Assumption~\ref{ass:power ddh}).
Suppose we receive a sequence $\{g, g^{z_1}, g^{z_2}, ..., g^{z_{\tau}}\}$ where each $z_i$ either equals $x^i$ (sampled $x\leftarrow X$ where $X\in \zo^{\lambda-1}$) or a random group element $r_i$.
We first compute two values: 
\begin{align*}
y_0 &= g^{16z_4+8z_3+4z_2+2z_1}= g^{16*z_4}\cdot g^{8*z_3} \cdot g^{4z_2}\cdot g^{2z_1},\\
y_1 &= g^{16z_4+40z_3 +40z_2+20z_1+4}.
\end{align*}
$\mathcal{A}'$ then computes a vector based on these values:
\begin{align*}
\{r_i\overset{\$}\leftarrow \mathbb{G}, r_i^{y_{\lockkey_i}}\}_{i=1}^n.
\end{align*}
Then $\mathcal{A}$ is initialized based on these values and outputs a function $f$ and a $2n$ vector of group elements $ \{r_{\mathcal{A},i }, w_{\mathcal{A}, i}\}_{i=1}^n$.  We assume $f$ is specified by coefficients (if not, these coefficients can be interpolated using points from the distribution $X$, see~\cite{komargodski2018another}).  We can then use the $f$ provided by $\mathcal{A}$ to check if each point in the vector is a valid single bit digital locker of $f(x)$ and a bit $0$ or $1$.  Details for this check are in Algorithm~\ref{alg:AdversaryDigitalLocker}.  We proceed to analyze the success of this algorithm in both the real case $z_i = x^i$ and the random case $z_i = r_i$.

\textbf{The real case} In the real case the adversary $\mathcal{A}$  sees pairs $\left(r_i, r_i^{g^{h(2x+\lockkey_i)}}\right)$.  This is exactly the distribution expected by $\mathcal{A}$.  Furthermore, $\mathcal{A}'$ outputs $1$ when the mauled obfuscation is a valid obfuscation of $x$ on some $\lockkey'$.  Thus, given the real distribution $\mathcal{A}'$ outputs $1$ with probability at least $\epsilon$.



\begin{figure}[t]
%    \centering
%\begin{centering}
    \vspace{0pt}
   \begin{algorithm}[H] 
\begin{framed}

\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{$g, g^{z_1},..., g^{\tau}$}
\Output{$\mathcal{P}(x)$}
\BlankLine
\begin{enumerate}
\item Sample $\lockkey\leftarrow \zo^n$.
\item Compute $y_0=g^{16z_4+8z_3+4z_2+2z_1}$ and $y_1 =g^{16z_4+40z_3 +40z_2+20z_1+4}$.
\item Compute $\{r_i\overset{\$}\leftarrow \mathbb{G}, r_i^{y_{\lockkey_i}}\}_{i=1}^n.$.
\item Run $(f, \{r_{\mathcal{A},i }, w_{\mathcal{A}, i}\}_{i=1}^n)\leftarrow \mathcal{A}( \{r_i, r_i^{y_{\lockkey_i}}\}_{i=1}^n)$.  If the output is not a function followed by $2n$ group elements output $0$.
\item Compute coefficients $\alpha_i$ of $h(2f(x))$ and $\beta_i$ of $h(2*f(x)+1)$.
\item For $i=1$ to $n$
\begin{enumerate}
\item Check if $w_{\mathcal{A},i} \overset{?} = r_{\mathcal{A}, i}^{(\sum_{i=0}^{\tau} \alpha_i z_i)}$ or
$w_{\mathcal{A},i} \overset{?} = r_{\mathcal{A}, i}^{(\sum_{i=0}^{\tau} \beta_i z_i)}$.  
\item If neither check is true, output $0$.
\end{enumerate}
\item Output $1$.
\end{enumerate}\vspace{-.15in}
\caption{Construction of $\mathcal{A}'$ from $\mathcal{A}$}
\label{alg:AdversaryDigitalLocker}
\end{framed}
\end{algorithm}
\end{figure}

\textbf{The random case}
We now assume that each $z_i$ is a uniform and randomly distributed $s_i$ for $1\le i \le \tau$.  We assume that the adversary is computationally unbounded and is provided with two points $c_0 = 16s_4+8s_3+4s_2+2s_1$ and $c_1 = 16s_4+40s_3 +40s_2+20s_1+4$.  (We can provide the adversary also with the values $r_i$.)  That is, we give the adversary direct access to the value in the exponent.  Its clear if no adversary can win in this game, then no adversary can win in the original game.

In order for $\mathcal{A}$ to succeed she needs to compute $c_\alpha= \sum_{i=0}^{\tau} \alpha_i s_i$ or $c_\beta = \sum_{i=0}^{\tau} \beta_i s_i$ (the vectors $\vec{\alpha}$ and $\vec{\beta}$ are defined in Algorithm~\ref{alg:AdversaryDigitalLocker}).  If the degree of the polynomial $f$ is greater than $1$ this requires computing a linear combination with some $s_i$ where $i>4$ that is independent of the adversary's view.  In this case, both the distribution of both random variables $C_\alpha$ and $C_\beta$ has entropy $\log |G_{\lambda}| = \lambda$ conditioned on the adversary's view~\cite[Claim 4.4]{komargodski2018another}.  By a union bound the probability of matching either $C_\alpha$ or $C_\beta$ for some $i$ is at most $\Pr[\text{success}] \le \frac{2}{2^{\lambda}} = \frac{1}{2^{\lambda-1}}$.

%So, we will test our derived $\mathcal{O}_{real}(f(x), b)$ against the outputted $\mathcal{O}_{out}(f(x), b)$. Now we must consider when our original inputs were real or random values. If we were originally given the real values, then of course $\mathcal{O}_{real}=\mathcal{O}_{out}$. We go on to show that, if the original inputs were of the form $g^{r_i}$, we will receive $\mathcal{O}_{real}=\mathcal{O}_{out}$ with negligible probability.

We now move to the case where the polynomial $f$ is of degree $1$.  That is, $f(x) = \mu x+\nu$.
%In the random case, we need to ensure that this process above will result in the value we receive being correct with only a negligible probability. For functions $f$ of degree greater than 1, this explanation is simple and the same as in [KY18]. If the degree of the polynomial is greater than 1, then the resulting polynomial will have degree at minimum 5. Because the adversary has no knowledge of $r_5$ or greater (in fact, it only has knowledge of the sum $r_1+r_2+r_3+r_4$), and because each random value is selected uniformly from the distribution, the adversary only has a probability of 1 over the field size of choosing the correct value of $r_5$ (and any higher $r_i$), a negligible amount.
If the function $f$ is a linear one, then we will show how an accurate obfuscation of $h(2f(x') + b)$ cannot be formed from the inputs. To do this, we will look at what information about the points that the adversary receives. The adversary receives a multiple linear combinations of $s_1,s_2, s_3, s_4$.
\[
\begin{bmatrix*}[r]
16 & 8 & 4 & 2 & 0\\
16 & 40 & 40 &20 & 4\\
0 & 0 & 0 &0 & 1
\end{bmatrix*}
\begin{bmatrix}
s_4\\
s_3\\
s_2\\
s_1\\
1
\end{bmatrix}
= \begin{bmatrix}
c_0\\
c_1\\
1
\end{bmatrix}.
\]
The first row of the above matrix corresponds to the linear combination used when $\lockkey_i = 1$, the second row when $\lockkey_i=0$ and the last row is the constant group element.
As stated, the function $f$ can be rewritten as $f(x)=\mu*x'+\nu$. By substituting and simplifying, $f$ can finally be rewritten as:
\begin{align*}
    2f(x)+b' & = 2*(\mu x+ \nu)+b'
     = 2\mu x + 2\nu + b'
     = 2a x + b
\end{align*}
for some $b\in \zo$ and $a$ is a field element. Note we consider this as an existential argument so $a = (\mu x+\nu)x^{-1} = \mu+\nu x^{-1}$ is a valid assignment for $a$. 
We can write the desired linear combination as follows:

\[
\begin{bmatrix*}[l]
16a^4\\
32a^3 b + 8a^3\\
20a^2b^2 + 16a^2b + 4a^2\\
6a b^3 + 6a b^2 + 6a b + 2a\\
b^4+b^3+b^2+b
\end{bmatrix*}^{\intercal}
\begin{bmatrix}
s_4\\
s_3\\
s_2\\
s_1\\
1
\end{bmatrix}.
\]

\noindent
We now show that even for an unbounded $\mathcal{A}$, this value is information theoretically hidden (given $c_0, c_1, 1$).
\begin{lemma}
Let $S_1, S_2, S_3, S_4$ be uniformly distributed in $\mathbb{G}_{5\lambda}$ then define $C_0 = 16S_1+ 8S_2 + 4S_3+2S_4 \mod{G}_{5\lambda}$ and $C_1 = 16S_1+ 40S_2 + 40S_3+20S_4+4 \mod{G}_{5\lambda}$ Define for $a\in\mathbb{G}_{5\lambda}, b\in\zo$, 
\begin{align*}
C^*_{a, b} &= 16a^4S_4 + (32a^3 b + 8a^3)S_3 + (20a^2b^2 + 16a^2b + 4a^2)S_2\\&+(6a b^3 + 6a b^2 + 6a b + 2a)S_1+ (b^4+b^3+b^2+b).
\end{align*}
Then the value $\Hoo(C^*_{a, b}| C_0 , C_1) \ge \lambda -1$ if $a\neq 0, 1$ and $p\not \in\{2,3,5,11,17\}$.
\label{lem:lin independence}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lem:lin independence}]
We first show that when $a\neq 0, 1$, the value $c_{a,b}$ is linearly independent of the values $c_0, c_1, 1$.� That is, we show the following system has no solutions $\alpha_0 c_0 + \alpha_1 c_1 + \alpha_2 c_2 = c_{a,b}$. To show linear independence we consider the following system of equations: Since $\mathcal{A}$ only has access to linear combinations of these variables in order for $\mathcal{A}$ to properly output some correct mauled obfuscation, they must find a solution to the following:

\begin{center}
\[
\begin{bmatrix*}[r]
16 & 8 & 4 & 2 & 0\\
16 & 40 & 40 &20 & 4\\
0 & 0 & 0 &0 & 1
\end{bmatrix*}^{\intercal}
\begin{bmatrix*}[l]
\alpha_0\\
\alpha_1\\
\alpha_2
\end{bmatrix*}
=
\begin{bmatrix*}[l]
16a^4\\
32a^3 b + 8a^3\\
20a^2b^2 + 16a^2b + 4a^2\\
6a b^3 + 6a b^2 + 6a b + 2a\\
b^4+b^3+b^2+b
\end{bmatrix*}
\]
\end{center}

\noindent
where $\alpha_0, \alpha_1, \alpha_2$ are field elements. Because $b$ is a single bit (i.e. either 0 or 1), we will examine the existence of solutions under these two possibilities.  In both cases we assume that the adversary can exactly solve the last equation using $\alpha_2$ as a free variable and consider the following reduced system:

\[
\begin{bmatrix*}[r]
16 & 16\\
40 & 8 \\
40 & 4 \\
20 & 2 
\end{bmatrix*}
\begin{bmatrix*}[r]
\alpha_0\\
\alpha_1
\end{bmatrix*}
=
\begin{bmatrix*}[l]
16a^4\\
32a^3 b + 8a^3\\
20a^2b^2 + 16a^2b + 4a^2\\
6a b^3 + 6a b^2 + 6a b + 2a
\end{bmatrix*}
\]

\paragraph{Case 1: $b=0$} Considering the two by two system formed by the second and third equation yields that:
\begin{align*}
40\alpha_0 &=8a^2 -8a^3,\\
4\alpha_1 &= 8a^3 - 4a^2.
\end{align*}
Substituting these values into the fourth equation yields a quadratic for $a$:
\[
4a^2-2a=0
\]
This has solutions of $a=0, 2^{-1}$.  Substituting the solutions for $\alpha_0, \alpha_1$ into the constraint from the first equation yields the quartic:
\[
16a^4-(32+16*5^{-1})a^3 + (16-16*5^{-1})a^2=0
\]
This equation is consistent with the solutions where $a=0$.  However, when $a=2^{-1}$, the first equation is only satisfied when $3\equiv 0 \mod p$. Thus, it suffices for $p\neq 3$.
Since the solution when $a=0$ is considered trivial, nontrivial solutions exist in this case only when $p=3$.

\paragraph{Case 2: $b=1$} Again starting with the second and third linear constraints we have that:
\begin{align*}
\alpha_0 &=2a^2-a^3,\\
\alpha_1 &=10a^3-10a^2.
\end{align*}
Substituting these values into the fourth equation yields $
180a^3-160a^2-20a=0.$ 
Which has the trivial solutions of $a=0,1$ and nontrivial solution $a=-1*9^{-1}$.  However, when $a=-1*9^{-1}$, the first equation is only satisfied when $11968\equiv 0 \mod p$. Thus, it suffices for $p\not\in\{2,11,17\}$.
Since the solution when $a=0$ is considered trivial, nontrivial solutions exist only when $p\in\{2,11,17\}$.

\paragraph{Putting things together}
So, regardless of choice of $b$, if $a$ is nontrivial, the value $c_{a, b}$ is linearly independent of $c_0, c_1$ and $1$.  Consider the following system of equations:
\[
\begin{bmatrix*}[r]
16 & 16 & 0 & 16a^4\\
8 & 40 & 0 & 32a^3 b + 8a^3\\
1 & 40 & 0 & 20a^2b^2 + 16a^2b + 4a^2\\
2 & 20 &0 & 6a b^3 + 6a b^2 + 6a b + 2a\\
0 & 4 & 1 & b^4+b^3+b^2+b
\end{bmatrix*}^{\intercal}
\begin{bmatrix}
s_4\\
s_3\\
s_2\\
s_1\\
1
\end{bmatrix}
=\begin{bmatrix}
c_0\\
c_1\\
1\\
c_{a,b}
\end{bmatrix}
\]

This system of equations is rank $4$ (in the case when $a$ is nontrivial).  This means for any particular $c_0, c_1$ there are at least $2^{\lambda}$ tuples of $S_1, S_2, S_3, S_4$ that produce any particular value of $c_{a,b}$.  In particular, the probability that $\Pr[C_{a,b} =c | C_0, C_1] = \frac{1}{2^{\lambda}}$.  Since the adversary has to match one of two values by union bound they succeed with probability at most $2^{-\lambda+1}$.
This completes the proof of Lemma~\ref{lem:lin independence}.
\end{proof}
Thus, in both random cases the probability of mauling is at most $2^{-(\lambda-1)}$.  This allows us to state the distinguishing capability of $\mathcal{A}$:
\[
\Pr[\mathcal{A}(\{g^{x^i}\}_{i=1}^{\tau}) = 1]- \Pr[\mathcal{A}(\{g^{r_i}\}_{i=1}^{\tau}) = 1]\ge \epsilon-\frac{1}{2^{\lambda-1}}.
\]
This is a contradiction and completes the proof of Theorem~\ref{thm:digital locker}.
\end{proof}

\section{Non-malleability for the key}
\label{sec:full construction}

In this section, we extend our construction to prevent tampering over both $\lockval$ and $\lockkey$.  We need several new tools including non-malleable codes and seed-dependent condensers.  We introduce these in turn.
%\paragraph{Non-malleable codes}
We first need to introduce the notion of non-malleable codes introduced by Dziembowski, Pietrzak, and Wichs~\cite{dziembowski2010non}.
\begin{definition}
A pair of algorithms $(\enc, \dec)$ is called a \emph{coding scheme} if for $\enc:\zo^k\rightarrow \zo^n$ is randomized and $\dec:\zo^n\rightarrow \zo^k \cup \perp$ is deterministic and for each $s\in \zo^k$ it holds that $\Pr[\dec(\enc(s)) = s ] =1.$
\end{definition}

\begin{definition}
A coding scheme, $(\enc, \dec)$ is called $(\epsilon_{nmc}, s_{nmc}, \mathcal{F})$-non-malleable  if for each $f\in\mathcal{F}$ and each $s\in\zo^k$ there exists a distribution $D_f()$ over $\{\zo^k, \mathtt{same}\}$  that is efficiently samplable given oracle access to $f$ such that the following holds:
\begin{align*}
\delta^{s_{nmc}}(&\{c\leftarrow \enc(s); \overline{c} \leftarrow f(c), \overline{s} = \dec(\overline{c}): \text{Output }\overline{s} \},\\
&\{\tilde{s}\leftarrow D_f,\text{ Output }s\text{ if }\tilde{s} = \mathtt{same}\text{ else }\tilde{s} \}) \le \epsilon_{nmc}.
\end{align*}
\end{definition}


\paragraph{Seed Dependent Condensers}
Seed dependent condensers were introduced by Dodis, Ristenpart, and Vadhan~\cite{dodis2012randomness}.  The goal of a condenser is similar to a traditional randomness extractor except that rather than considering a uniform output, the output only has to be statistical close to a distribution with min-entropy.  Importantly, it is possible to construct condensers where the adversary is allowed to output the chosen distribution after seeing the seed (called \emph{seed-dependent}).

\begin{definition}
\label{def:condenser} 
Let $\cond:\zo^\lambda \times \zo^d\rightarrow\zo^\alpha$ is a $(k, k', s, \epsilon)$ \emph{seed-dependent condenser} if for all probabilistic adversaries of size at most $s$ who take a random seed $\seed\leftarrow U_d$ and output a distribution $X_{\seed} \leftarrow \mathcal{A}(\seed)$ of entropy $\Hoo(X|\seed)\ge k$, then for the joint distribution $(X, U_d)$ over $X_{\seed}$ arising from a random $\seed\leftarrow U_d$, there exists a distribution $Y$ such that $\Hav(Y| U_d)$ such that 
\[
\Delta((Y, U_d) , (\cond(X; U_d), U_d))\le \epsilon.
\]
\end{definition}

\noindent
Dodis, Ristenpart, and Vadhan showed that seed-dependent condensers can be constructed using the standard tool of collision resistant hash functions:
\begin{definition}
A family of hash functions $\mathcal{H}=\{h:\zo^\lambda\rightarrow \zo^\alpha$ is $(t, \delta)$-\emph{collision resistant} if for any circuit $\mathcal{A}$ of size at most $t$,
\[
\Pr_{h\leftarrow \mathcal{H} \wedge (x_1, x_2)\leftarrow \mathcal{A}(h)}[h(x_1) = h(x_2) \wedge x_1 \neq x_2]\le \delta.
\]
\end{definition}

The following theorem states that collision-resistance translates into a seed-dependent condenser:
\begin{theorem}~\cite[Theorem 4.1]{dodis2012randomness}
\label{thm:good condensers}
Let $\mathcal{H}$ be a $(2s, \delta)$-collision-resistant hash function family, then $\cond(x; h) = h(x)$ for $h\leftarrow \mathcal{H}$ is a $(-\log (\delta), \frac{-\log (\delta) -1}{2}, s,0)$-seed-dependent condenser.
\end{theorem} 

\subsection{The Construction}
Intuitively, we can combine non-malleable codes and seed-dependent condensers to check if the adversary tampers over the $\lockkey$ value.  We use the locked point $\lockval$ as input to a seed dependent condenser as part of the value encoded in the non-malleable code.  If the adversary tampers to an \emph{independent value} there are unlikely to match the output of the condenser on the real $\lockval$.
\begin{construction}

Let $\lambda\in\mathbb{N}$ be a security parameter and let $\zo^{\lambda}$ be the domain. 
\begin{enumerate}
\itemsep0em
\item Let $\mathcal{F}_{t,\poly}$ be as above. 
\item Let $(\enc, \dec)$ be a coding scheme where $\enc:\zo^{k+\beta}\rightarrow \zo^n$.  
\item Let $\mathcal{G} = \{\mathbb{G}_\lambda\}_{\lambda\in\mathbb{N}}$ be a group ensemble with efficient representation and operations where each $\mathbb{G}_{5\lambda}$ is a group of prime order $q\in(2^{5\lambda}, 2^{5\lambda+1})$.  
\item $X$ is a distribution such that $\Hoo(X)\ge \mu = \omega(\log \lambda)$. There is no requirement that $X$ is independent of system parameters (in particular $\seed$) as long as it is efficiently samplable.
\item Suppose for any $s = \poly(\lambda)$ there exists $\beta = \omega(\log\lambda)$ such $\cond: \zo^{\lambda}\times \zo^d\rightarrow \zo^\alpha$ is a $(\mu, \beta, s, 0)$-seed-dependent condenser (instantiable using Theorem~\ref{thm:good condensers}).
\item Let a description of $\mathbb{G}_{5\lambda}$, a generator $g$ for $\mathbb{G}_{5\lambda}$ and $\seed\leftarrow \zo^d$ be system parameters.  
\end{enumerate}
Define the algorithms $(\lock, \unlock)$ as in Figure~\ref{alg:full non-malleable lock}.

\begin{figure}[t]
%    \centering
%\begin{centering}
\begin{framed}
    \begin{minipage}[t]{.43\textwidth}
$\lock(\lockval, \lockkey)$, input in $\zo^{\lambda+k}$:
\begin{enumerate}
\itemsep0em
\item Compute $y= \cond(\lockval,\seed) $.
\item Compute $z = \enc(\lockkey || y)$.
\item Initialize $\mathtt{Out} = \perp$.
\item For $i=1$ to $n$ compute:
\begin{enumerate}
\itemsep0em
\item Sample random generator\\ $r_i \leftarrow \mathbb{G}_{5\lambda}$.
\item Compute 
\begin{align*}\gamma_i &= (2\lockval+z_i)^4+(2\lockval+z_i)^3\\&+(2\lockval+z_i)^2+(2\lockval+z_i).\end{align*}
\item Append $\mathtt{Out} = $ \\$\mathtt{Out} ||$ $(r_i , (r_i)^{g^{\gamma_i}})$.
\end{enumerate}
\item Output $\mathtt{Out}$.
\end{enumerate}
%\vspace{.05in}
    \end{minipage}%
    \begin{minipage}[t]{0.55\textwidth}
    $\unlock(\lockval)$, input in $\zo^\lambda$:
    \begin{enumerate}
    \itemsep0em
    \item Compute $y = \cond(\lockval,\seed)$.
    \item For $i=1$ to $n$, input $r_i, y_i$ compute:
\begin{align*}
\gamma_{i,0} &= \sum_{j=1}^4(2\lockval)^j\\
\gamma_{i,1} &= \sum_{j=1}^4(2\lockval+1)^j\\
P(x, 0, i) &= \left( r_i^{g^{\gamma_{i,0}}} \overset{?}=y_i.\right),\\
P(x, 1, i) &= \left( r_i^{g^{\gamma_{i,1}}} \overset{?}=y_i.\right)
\end{align*}
\begin{enumerate}
\itemsep0em
\item If $P(x, b, i)$ outputs $1$, set $z_i = b$.  Otherwise output $\perp$.
\end{enumerate}
\item Run decode $\lockkey' = \dec(z)$.
\item If $\lockkey'_{k...k+n} \neq y$ output $\perp$.  \\Else output $\lockkey'_{0...k-1}$.
    \end{enumerate}
    \end{minipage}
        \end{framed}
        \vspace{-.1in}
            \caption{Non-malleable digital locker preventing tampering over both $\lockval$ and $\lockkey$.  A group generator $g$ and a $\seed$ of a seed-dependent condenser are global system parameters. }
    \label{alg:full non-malleable lock}

\end{figure}

\label{con:full construction}
\end{construction}
\begin{theorem}
Suppose that 
\begin{enumerate}
\item The $n$-strong average vector DDH assumption holds,
\item The $4t$-strong average power DDH assumption holds,
\item The selected prime $p\not\in\{ 2,3,5,7,11\}$. 
\item Suppose that $\mu - \beta = \omega(\log \lambda)$. 
\item The code $(\enc, \dec)$ is an $(\epsilon_{nmc}, s_{nmc}, \mathcal{F}_{nmc})$ non-malleable code.
\end{enumerate}
Then $(\lock, \unlock)$ in Construction~\ref{con:full construction} is point non-malleable for $\mathcal{F}_{\poly,t}$ and key nonmallable for $\mathcal{F}_{nmc}$.
\label{thm:main theorem}
\end{theorem}

\begin{proof}
We note a couple of key differences between the above theorem and Theorem~\ref{thm:digital locker} that provided non-malleable only over the point $\lockval$.  First, the condition on the distribution $X$ is changed.  We now require that $X|(\cond(X; S) , S)$ has min-entropy (recalling that $X$ can be chosen dependent on $S$).  Note that if the output length $\beta$ is a constant fraction of $\Hoo(X)$ this condition is implied by the entropy of $X$ using standard entropy arguments~\cite[Lemma 2.2b]{DBLP:journals/siamcomp/DodisORS08}. % This follows by the universality of the hash function and independence of $h$ and $X$ using standard arguments (see~\cite[Lemma B.2]{fuller2016fuzzy}).

Correctness, privacy, and point nonmalleability follow using the same arguments as Theorem~\ref{thm:digital locker} under the strengthened average case vector and power DDH assumptions.   The core of our proof is a theorem (which may be of independent interest) that allows us to use non-malleable codes in a nontraditional way where the adversary is provided with pseudorandom information that is correlated to the encoded codeword before choosing which function $f\in\mathcal{F}$ to tamper with.  We first define an adaptive tampering experiment as follows for arbitrary distributions $X, Y, Z$ and binary predicate $\mathtt{Test}$:
\begin{center}
\begin{minipage}{1in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\Exp^{\mathrm{ad-nmc}}_{\calF_{nmc},X, Y, Z, \mathcal{A}, \mathtt{Test}}$: \\
Sample $(x, y, z)\leftarrow (X, Y, Z)$ \\
Sample $f\leftarrow \mathcal{A}(x)$.\\
If $f\not\in \mathcal{F}_{nmc}$ output $0$.\\
If $f(y) = y$ output $0$.\\
If $\mathtt{Test}(f(y), z)$ output $1$.\\
Else output $0$.
\end{tabbing} \end{minipage}
\end{center}

\begin{theorem}
\label{thm:adaptive nmc}
Let $Z\in \zo^\alpha$ be a distribution such that $\Hoo(Z) \ge \beta$.  Let $(\enc, \dec)$ be a $(\epsilon_{nmc}, s_{nmc}, \mathcal{F}$) non-malleable code and $\enc:\zo^{k} \rightarrow \zo^n$ where $k=\alpha+\gamma$.  Let $\lockkey\in \zo^\gamma$, define the distribution $Y_\lockkey$ by sampling $z\leftarrow Z$ and computing $\enc(\lockkey, z)$.  For inputs $y$ and $z$, define $\mathtt{Test}(y, z) = 1$ if and only if $\dec(y)_{\gamma...(\gamma+\alpha-1)} = z$.
Suppose that 
\begin{enumerate}
\itemsep0em
\item For all $f\in\mathcal{F}$ it is possible to compute $f$ in a circuit of size at most $s_{\mathcal{F}, \mathtt{eval}}$.
\item It is possible to evaluate $\mathtt{Test}$ using a circuit of size at most $|\mathtt{Test}|$ and $s_{nmc} > |\mathtt{Test}|$.
\item For a function $f$ it is possible to check if $f\in\mathcal{F}$ in size at most $s_{\mathcal{F}, \mathtt{check}}$.  Furthermore, this check is correct with probability $1$.
\item $X$ be an arbitrary distribution over $\mathcal{M}$ such that \[\delta^{\mathcal{D}_{s_{pr}}}((X, Y_\lockkey, Z), (U_\mathcal{M}, Y_\lockkey, Z)) \le \epsilon_{pr}.\]
\end{enumerate}
Then for all $\mathcal{A}$ of size $s$ it holds that

\[
\Pr\left[\Exp^{\mathrm{ad-nmc}}_{\calF,X, Y, Z, \mathcal{A}}=1\right] \le 2^{-\beta} + \epsilon_{nmc} + \epsilon_{pr}.
\]
Here $s =\min\{s_{pr}- |\mathtt{Test}| - s_{\mathcal{F}, \mathtt{eval}} - s_{\mathcal{F}, \mathtt{check}}, s_{nmc}\}$.
\end{theorem}
The above lemma says that provided an adversary with some information $X$ that may be correlated to the encoded codeword $Y$ is not harmful as long as $X$ is pseudorandom in the presence of $Y$.  Crucially, it must be possible to test if the adversary tampers to an independent codeword.  This necessitates the use of the auxiliary distribution $Z$ that is part of the value encoded in $Y$.  (In our construction $Z$ is the output of a seed-dependent condenser applied to $\lockval$.)

\begin{proof}
We begin by defining a standard non-malleable code experiment with a simulator for a function $f$ defined by a distribution $D_f(\cdot)$:
\begin{center}
\begin{minipage}{1in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\Exp^{\mathrm{sim}}_{f,Z, D_f}$: \\
Sample $\tilde{s} \leftarrow D_f(\cdot), z\leftarrow Z$\\
If $\tilde{s} = \mathtt{same}$ output $0$.\\
If $\mathtt{Test}(\tilde{s}, z) = 1$ output $1$.\\
Else output $0$.
\end{tabbing} \end{minipage}
\end{center}
\begin{lemma}
\label{cl:sim game hard}
Suppose that $\Hoo(Z) \ge \beta$, for any $f$, $\Pr[\Exp^{\mathrm{sim}}_{f,Z, D_f}(k) =1 ] \le 2^{-\beta}$.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{cl:sim game hard}] We note that whenever $\tilde{s} = \mathtt{same}$ the output of the experiment is $0$.  Thus, we can restrict our attention to cases when $\tilde{s} \neq \mathtt{same}$.  Then $\Pr[Z = \tilde{s}_{k - \alpha...k}] \le 2^{-\Hoo(Z)} = 2^{-\beta}.$  This completes the proof of Lemma~\ref{cl:sim game hard}.
\end{proof}
We will now argue that the adversary in the adaptive adversary does not perform substantially better than in the simulated experiment.  We use a hybrid argument with two intermediate games, $\Exp^{1}_{\calF,Y, Z, \mathcal{A}}$ and $\Exp^{2}_{\calF,X, Y, Z, \mathcal{A}}$.  In moving from $\Exp^{\mathrm{ad-nmc}}_{\calF,X, Y, Z, \mathcal{A}}$ to $\Exp^{1}_{\calF,Y, Z, \mathcal{A}}$ we will replace the distribution $X$ with a random distribution that is uncorrelated to $Y, Z$.  In $\Exp^{2}_{f,Y, Z}$ we will eliminate the uniform distribution as input and move from the adversary picking a function to defining the experiment for a particular function $f$. Finally in moving to $\Exp^{\mathrm{sim}}_{f,Z, D_f}(k)$ we will rely on the hardness of non-malleable codes.  The two experiments are described formally below.

\begin{center}
\begin{tabular}{c|c}
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\Exp^{1}_{\calF, Y, Z, \mathcal{A}}$: \\
Sample $( y, z)\leftarrow (Y, Z)$ \\
Sample $u\leftarrow \mathcal{M}$.\\
Sample $f\leftarrow \mathcal{A}(u)$.\\
If $f\not\in \mathcal{F}$ output $0$.\\
If $f(y) = y$ output $0$.\\
Output $\mathtt{Test}(f(y), z)$.
\end{tabbing} \end{minipage} &
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\Exp^{2}_{f, Y, Z}$: \\
Sample $(y, z)\leftarrow (Y, Z)$ \\
If $f(y) = y$ output $0$.\\
Output $\mathtt{Test}(f(y), z)$.
\end{tabbing} \vspace{.3in}\end{minipage}
\end{tabular}
\end{center}
We now show each of these games are computationally close.
\begin{lemma}
Suppose that
\begin{enumerate}
\itemsep0em
\item For each $f\in\mathcal{F}$, the function $f$ is computable in size at most $s_{\mathcal{F}}$.
\item For $f$ it is possible to correctly check $f\in\mathcal{F}$ in size $s_{\mathcal{F}, \mathtt{check}}$.  
\item That $\delta^{\mathcal{D}_{s_{pr}}}((X, Y_\lockkey, Z), (U_\mathcal{M}, Y_\lockkey, Z)) \le \epsilon_{pr}.$
\end{enumerate}
Then for $\mathcal{A}$ of size at most $s_{pr}- |\mathtt{Test}| - s_{\mathcal{F}, \mathtt{eval}} - s_{\mathcal{F}, \mathtt{check}}$,
\[
\left| \Pr\left[\Exp^{\mathrm{ad-nmc}}_{\calF,X, Y, Z, \mathcal{A}}(k)=1\right] - \Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}(k) = 1]\right|\le \epsilon_{pr}.
\]
\label{cl:indistgame0 and 1}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{cl:indistgame0 and 1}]  Suppose not. That is, suppose that there exists an $\mathcal{A}$ of size at most $s_{pr}- |\mathtt{Test}| - s_{\mathcal{F}, \mathtt{eval}} - s_{\mathcal{F}, \mathtt{check}}$ such that \[|\Pr[\Exp^{\mathrm{ad-nmc}}_{\calF,X, Y, Z, \mathcal{A}}=1] - \Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}= 1]|> \epsilon_{pr}.\]  Then the following program $D$ (of size at most $s_{pr}$) is a distinguisher for $((X, Y, Z)$ and $(U_{\mathcal{M}}, Y, Z))$:
\begin{enumerate}
\item On input $x, y, z$.
\item Run $f\leftarrow \mathcal{A}(x)$.
\item If $f\not\in \mathcal{F}$ or $f(y) = y$ output $0$.
\item Else output $\mathtt{Test}(f(y), z)$.
\end{enumerate}
That is,
\begin{align*}
&\left|\Pr[D(X, Y, Z) = 1] - \Pr[D(U_\mathcal{M}, Y, Z)=1 ] \right| \\&=\left|\Pr[\Exp^{\mathrm{ad-nmc}}_{\calF,X, Y, Z, \mathcal{A}}=1] - \Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}} = 1]\right|> \epsilon_{pr}.
\end{align*}
This contradicts the pseudorandomness of $X| ( Y, Z)$ and completes the proof of Lemma~\ref{cl:indistgame0 and 1}.
\end{proof}
\begin{lemma}
There exists some $f\in\mathcal{F}$ such that for any $\mathcal{A}$ (here $\mathcal{A}$ need not be computationally bounded):
\[
\Pr[\Exp^{2}_{f,Y, Z}(k) = 1]   \ge  \Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}(k) = 1].
\]
\label{cl:game1 and 2}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{cl:game1 and 2}]
First we consider the circuits $\mathcal{A}$ that always output $f\in \mathcal{F}$.  Given any $\mathcal{A}$ that outputs an $f\not\in\mathcal{F}$ we can design another $\mathcal{A}'$ that runs $f\leftarrow \mathcal{F}$ and simply outputs a fixed $f'\in\mathcal{F}$ whenever $f\not\in\mathcal{F}$.  This $\mathcal{A}'$ does not perform worse in $\Exp^{1}$ than $\mathcal{A}$.

Now consider some $\mathcal{A}$ that always outputs functions $f\in\mathcal{F}$.  There is a distribution $D_{\mathcal{A}}$ that outputs exactly the distribution that is output by $\mathcal{A}$.  Note that this distribution is independent of $y$.  Note that
\[
\Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}} = 1] = \sum_{f\in\mathcal{F}} \Pr\left[D_\mathcal{A} =f \right] \Pr_{(y, z)\leftarrow (Y, Z)}\left[f(y) \neq y \wedge \mathtt{Test}(y, z) =1 \right].
\]
Now suppose that for all $f\in \mathcal{F}$,
\[
\Pr[\Exp^{2}_{f,Y, Z}(k) = 1]   <  \Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}(k) = 1].
\]
Then one has
\begin{align*}
\Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}= 1] &= \sum_{f\in\mathcal{F}} \Pr\left[D_\mathcal{A} =f \right] \Pr_{(y, z)\leftarrow (Y, Z)}\left[f(y) \neq y \wedge \mathtt{Test}(y, z) =1 \right]\\
&=\sum_{f\in\mathcal{F}} \Pr\left[D_\mathcal{A} =f \right] \Pr[\Exp^{2}_{f,Y, Z}= 1] \\
&<\sum_{f\in\mathcal{F}} \Pr\left[D_\mathcal{A} =f \right]\Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}= 1] \\
&=\Pr[\Exp^{1}_{\calF, Y, Z, \mathcal{A}}= 1]
\end{align*}
This is a contradiction and completes the proof of Lemma~\ref{cl:game1 and 2}.
\end{proof}
Before showing distinguishability of the last two games we consider the definition of non-malleable codes where the encoded secret is drawn from a distribution instead of considering a single point:
\begin{lemma}
Let $(\enc, \dec)$ be a $(\epsilon_{nmc}, s_{nmc})$-non-malleable code for functions in $\mathcal{F}$.  Then for any distribution $Z$ over points in $\zo^k$ it holds that
\begin{align*}
\delta^{\mathcal{D}_{s_{nmc}}}(&\left(\{c\leftarrow \enc(Z); \overline{c} \leftarrow f(c), \overline{s} = \dec(\overline{c}): \text{Output }\overline{s} \}, Z\right), \\&\left(
\{\tilde{s}\leftarrow D_f,\text{ Output }Z\text{ if }\tilde{s} = \mathtt{same}\text{ else }\tilde{s} \}, Z\right)) \\&\le \epsilon_{nmc}.
\end{align*}
\label{prop:distnmc}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{prop:distnmc}]
Suppose not, that is there exists some $Z$ for which the statement is not true.  In particular, there must be some $z\in Z$ where $\Pr[Z=z]>0$ such that there exists $\mathcal{D}_{s_{nmc}}$,
\begin{align*}
\delta^{\mathcal{D}_{s_{nmc}}}(&\left(\{c\leftarrow \enc(z); \overline{c} \leftarrow f(c), \overline{s} = \dec(\overline{c}): \text{Output }\overline{s} \}, z\right), \\&\left(
\{\tilde{s}\leftarrow D_f,\text{ Output }z\text{ if }\tilde{s} = \mathtt{same}\text{ else }\tilde{s} \}, z\right) \\&> \epsilon_{nmc}.
\end{align*}
This contradicts security of the non-malleable code.
\end{proof}
\noindent
With this distributional version of security for non-malleable codes we can turn to indistinguishability of the last two games.
\begin{lemma}
For every $f\in\mathcal{F}$, if $s_{nmc} \ge |Test|$ then
\[
\left|\Pr[\Exp^{\mathrm{sim}}_{f,Z, D_f}=1] - \Pr[\Exp^{2}_{f,Y, Z} = 1] \right| \le \epsilon_{nmc}.
\]
\label{cl:game2 and 3}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{cl:game2 and 3}]
Suppose not, that is suppose that there exists some $f\in\mathcal{F}$ such that
\[
\left|\Pr[\Exp^{\mathrm{sim}}_{f,Z, D_f}(k)=1] - \Pr[\Exp^{2}_{f,Y, Z}(k) = 1] \right| > \epsilon_{nmc}.
\]
Then we have a distinguisher $D$ (of size $|\mathtt{Test}|$) for the distributional version of non-malleable code security guarantee 1) input $\tilde{s}, z$ and 2) Compute $\mathtt{Test}(\tilde{s}, z)$.
This completes the proof of Lemma~\ref{cl:game2 and 3}.
\end{proof}
\noindent
Combining Lemmas~\ref{cl:sim game hard}, \ref{cl:indistgame0 and 1}, \ref{cl:game1 and 2} and \ref{cl:game2 and 3} completes the proof of Theorem~\ref{thm:adaptive nmc}.
\end{proof}
\noindent
Application of Theorem~\ref{thm:adaptive nmc} yields Theorem~\ref{thm:main theorem}.
\end{proof}

\section{Encoding multiple key bits in each digital locker}
\label{sec:multibit}

In this section, we transform Construction~\ref{cons:digital locker} to support encoding multiple bits in each group element.  The reason for this extension is to support non-malleable codes where $\mathcal{F}_{nmc}$ allows tampering over nonbinary symbols. An example of this type of non-malleable code is the recent work by Kiayias et al.~\cite{kiayias2018non}.  We show how to support $\tau$ bits in each obfuscation at the cost of running time proportional to $2^{\tau}$.  This increase in running time is due to exhaustively checking each possible value of the symbol.  In addition, it allows a weaker vector DDH assumption at the cost of a stronger power DDH assumption.  It thus allows a tradeoff between these two parameters.  

\begin{construction}
Let all variables be as in Construction~\ref{con:single bit digital locker}, let $\lockkey\in \zo^n$ be some arbitrary value, and let $\tau = O(\log \lambda)$.  Then define $\lock(\lockval, \lockkey)$ as follows: for $i=1$ to $n/\tau$ compute:
\begin{enumerate}
\item Sample $r_i \leftarrow \mathbb{G}_{(6+\tau)\lambda}$.
\item Set $z=x+2$.
\item Output $(r_i,  (r_i)^{g^{z^{4+\tau}+z^{3+\tau}+z^{2+\tau}+z^{1+\tau}+z^{\tau} + \sum_{i=0}^{\tau-1} \lockkey_{i} z^{i}}})$.
\end{enumerate}
Define $\unlock(\lockval)$ as follows: for $i=1$ to $n/\tau$, input $r_i, y_i$ for each $v_j\in[ 0,2^{\tau})$ compute:
\begin{align*}
P(x, v_j, i) &= \left( r_i^{g^{(x+2)^{4+\tau}+(x+2)^{3+\tau}+(x+2)^{2+\tau}+(x+2)^{1+\tau}+(x+2)^{\tau} + \sum_{j=0}^{\tau-1} v_{j} (x+2)^{j}}} \overset{?}=y_i\right).\\
\end{align*}If $P(x, v_j, i)$ outputs $1$ then the user sets $\lockkey_i = v_j$.  Otherwise output $\perp$.
\label{cons:multi bit digital locker}
\end{construction} 

\textbf{Nonmalleability over keys} This construction can be augmented using a seed-dependent condenser and a non-malleable code in the same method as in Construction~\ref{con:full construction}. In theorem below we only consider nonmalleability over the locked $\lockval$ and assume no distribution over $\lockkey$. 

\begin{theorem}
Suppose that 
\begin{enumerate}
\item The $\frac{n}{\tau}$-strong average vector DDH assumption holds,
\item The $(5+\tau)t$-strong average power DDH assumption holds,
\item The selected prime $p\not\in\{ 2, 31, 41,73\}$. (As $\mathbb{G}_\lambda$ increases these primes will never be selected.  We include this condition as the proof does not apply if $p\in\{2,31, 41,73\}$.)
\item $X$ is a distribution over $\zo^{\lambda-1}$ such that $\Hoo(X) = \omega(\log \lambda)$.
\end{enumerate}
Then the $(\lock, \unlock)$ in Construction~\ref{cons:multi bit digital locker} is point non-malleable for $\mathcal{F}=\{f | \deg(f)\le t\}$ (excluding constant polynomials and the identity polynomial).
\label{thm:multi digital locker}
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm:multi digital locker}]
As before we separately consider correctness, soundness, and nonmalleability.  

\paragraph{Correctness}  For correctness first note that 
\[
(x+1)^{4+\tau}+(x+1)^{3+\tau}+(x+1)^{2+\tau}+(x+1)^{1+\tau}+(x+1)^{\tau} >
\sum_{i=0}^{4+\tau} x^i
\]

\noindent
In particular, the binomial expansion of $(x+1)^{4+\tau}$ has nonzero coefficients on every power $i\le 4+\tau$.  This shows that for any $\lockkey, \lockkey'\in\zo^\tau$ and any $x>x'$ it is true that 
\begin{align*}
&g^{(x+2)^{4+\tau}+(x+2)^{3+\tau}+(x+2)^{2+\tau}+(x+2)^{1+\tau}+(x+2)^{\tau} + \sum_{i=0}^{\tau-1} \lockkey_{i} (x+2)^{i}}\neq \\&g^{(x'+2)^{4+\tau}+(x'+2)^{3+\tau}+(x'+2)^{2+\tau}+(x'+2)^{1+\tau}+(x'+2)^{\tau} + \sum_{i=0}^{\tau-1} \lockkey'_{i} (x'+2)^{i}}.
\end{align*}
That is, the value of $\lockkey$ cannot cause the obfuscation to unlock on a different point.  Furthermore, the function is one-to-one as long as $x\not\in\{0,1\}$.  These cases are avoiding by computing $x+2$ before computing the polynomial.  Note that since $x\in\zo^{\lambda-1}$ it always holds that $(x+2)\in\zo^\lambda$.  

\paragraph{Privacy}
The privacy argument for this construction is exactly the same as in Theorem~\ref{thm:digital locker} since the function \[f(x, \lockkey_i)=g^{(x+2)^{4+\tau}+x^{3+\tau}+(x+2)^{2+\tau}+(x+2)^{1+\tau}+(x+2)^{\tau} + \sum_{j=0}^{\tau-1} \lockkey_{i,j} (x+2)x^{j}}\] is a one-to-one function.


\paragraph{Nonmalleability}The analysis for the random case when the mauling function has degree greater than 1 are exactly the same as in Theorem~\ref{thm:digital locker}.  We focus on showing that the adversary cannot find a function linear $f$ using linear combinations of the known values.  We can think of the adversary being given values of following type:

\[
\begin{bmatrix*}[l]
 1 & 1 & 1 & 1 & 1 & \lockkey_{0,0} &... &\lockkey_{0,\tau-1}\\
  1 & 1 & 1 & 1 & 1 & \lockkey_{0,0} &... & \lockkey_{0,\tau-1}\\
  ...\\
   1 & 1 & 1 & 1 & 1 & \lockkey_{n/\tau,0} &... & \lockkey_{n/\tau,\tau-1}\\
\end{bmatrix*}
\begin{bmatrix}
r_{4+\tau}\\
r_{3+\tau}\\
r_{2+\tau}\\
r_{1+\tau}\\
r_\tau\\
...\\
r_1
\end{bmatrix}
= \begin{bmatrix}
c_0\\
c_2\\
...\\
c_{n/tau}
\end{bmatrix}
\]

Without loss of generality, we assume that an adversary can perfectly set/predict the powers $x^{j}$ where $j<\tau$.  However, to change the obfuscated point they will also need to change the higher order powers.  We can think of the adversary having to find $\alpha, \beta, \gamma$ such that 
\[
\sum_{i=0}^4(\alpha x+\beta)^{i+\tau} = \gamma \sum_{i=0}^4 x^{i+\tau}.
\]
\noindent
We can write the desired linear combination as follows:
\[
\begin{bmatrix*}[l]
\alpha^{4+\tau}\\
\alpha^{3+\tau}\left({\tau +4 \choose 1} \beta+ {\tau+ 3\choose 0}\right)\\
\alpha^{2+\tau}\left({\tau + 4 \choose 2}\beta^2+{\tau+3 \choose 1}\beta + {\tau +2 \choose 0} \right)\\
\alpha^{1+\tau}\left(\sum_{i=0}^{3} \left({\tau+ 4- i\choose 3-i}\beta^{3-i}\right)\right)\\
\alpha^{\tau}\left(\sum_{i=0}^{4} \left({\tau+ 4- i\choose 4-i}\beta^{4-i}\right)\right)
\end{bmatrix*}^{\intercal}
\begin{bmatrix}
r_{4+\tau} & 0 & 0 & 0 &0\\
0 & r_{3+\tau} & 0 & 0 &0\\
0 & 0 & r_{2+\tau} & 0 &0\\
0 & 0 &0 & r_{1+\tau} & 0\\
0 & 0 &0 &0 & r_{\tau}
\end{bmatrix}
= \gamma\begin{bmatrix} r_{4+\tau}\\
r_{3+\tau}\\
r_{2+\tau}\\
r_{1+\tau}\\
r_{\tau}
\end{bmatrix}
\]
Substituting one has that
\begin{enumerate}
\item If $\beta=0$ then this implies $\alpha^{\tau+4} = \alpha^{\tau+3} = \alpha^{\tau+2}=\alpha^{\tau+1} = \alpha^{\tau}$ which only has solutions if $\alpha=0$ or $\alpha=1$.  These are both considered trivial solutions.
\item $\gamma = \alpha^{\tau+4}$ (using first equation),
\item $(\tau+4)\beta+1 = \alpha$ (using second equation),
\item $(\tau+4)\beta =2$ (using third equation, and relying on $\beta\neq 0$).
\item $\alpha =3$ (substitution of third constraint into second equation)
\item $\gamma = 81$ (substitution of $\alpha$ in first equation)
\item $\tau =-5$ or $\tau = -114*31^{-1}$ (solving fourth equation using prior constraints).
\end{enumerate}
Thus, using the first four equations we are able rule out all solutions unless $\tau = -5 $ or $\tau=-114*31^{-1}$.  Using the last equation we can almost always rule out this second possibility for $\tau$.
Namely, the fifth equation (recalling that $\beta = 2/(\tau+4)$)
\[
{\tau +4 \choose 4}\left(\frac{2}{\tau+4}\right)^4 + {\tau+3\choose 3}\left(\frac{2}{\tau+4}\right)^3+{\tau+2 \choose 2}\left(\frac{2}{\tau+4}\right)^2+(\tau+1)\frac{2}{\tau+4}+ 1 =81
\]

This solution is only satisfied for $\tau=-114*31^{-1}$ if $191552\equiv 0 \mod p$.  Thus, it suffices to choose $p\not \in \{2, 31, 41, 73\}$.  This allows us to conclude that the adversary's value in the random case is linearly independent, which again leads to this value having entropy $\lambda$.  Since the adversary only has to match a single value for each index by union bound their overall probability may be as high as $\tau/2^{\lambda}$.  Thus, in both random cases the probability of mauling is at most $\chi/2^{(\lambda)}$.  We note that since $\tau = O(\log \lambda)$ for large enough $\lambda$ one can be sure that $\tau\not\equiv -5 \mod \mathbb{G}_\lambda$.  This allows us to state the distinguishing capability of $\mathcal{A}$:
\[
\Pr[\mathcal{A}(\{g^{x^i}\}_{i=1}^{4t}) = 1]- \Pr[\mathcal{A}(\{g^{r_i}\}_{i=1}^{4t}) = 1]\ge \epsilon-\frac{\tau}{2^{\lambda}}.
\]
In particular, this breaks the $(5+\tau)t$-strong average power DDH assumption.  
This is a contradiction and completes the proof of Theorem~\ref{thm:multi digital locker}.
\end{proof}

\ifnum\lncs=0
\section*{Acknowledgements}  The work of Peter Fenteany was funded by a grant from Comcast Inc.  The authors thank Luke Demarest, Pratyay Mukherjee, and Alex Russell for their helpful feedback.
\fi

\bibliographystyle{alpha}
\bibliography{crypto}

\appendix
\section{Analysis of One Time Security}
\label{sec:one time}

\begin{proof}[Proof of Theorem~\ref{thm:single time digital locker}]
We separately argue completeness, soundness, and nonmalleability.

\textbf{Completeness}
For completeness, it suffices to show that the pair  $(r, r^{g^{h(2x+b)}})$ is unique for each choice of $x$ and $b$ is unique for each pair $x, b$. First note that $2x+b$ is injective in both variables. Then $h(x) = x^4+x^3+x^2+x$ is injective, thus the value $h(2x+b)$ will also be unique for each $x, b$. Let $p$ be the prime corresponding to the chosen group $\mathbb{G}_{5\lambda}$.  Then, it holds that $h(2x+b)\le 2^{5\lambda}$ and thus, the value of $g^{h(2x+b)}$ is one-to-one.  This ensures the pair $(r, r^{g^{h(2x+b)}})$ is unique for unique $x, b$.  Completeness immediately follows.

\textbf{Soundness}
 Note no distribution is assumed on the bit $b$.  Fix some $b\in\zo$.  
Let $\mathcal{Z}_{\lambda}$ be the set of distributions $Z$ over $\zo^\lambda$ where $\Hoo(Z) = \omega(\log \lambda)$ and similarly define the set of distributions $\mathcal{X}_{\lambda -1}$ as the set of distributions $X$ over $\zo^{\lambda-1}$ where $\Hoo(X) =\omega(\log \lambda)$.  Lastly, define the set of distributions $\mathcal{Y} = \{2X+b | X\in\mathcal{X}_{\lambda-1}\}$ where we understand $2X+b$ to be a distribution created by sampling $x\leftarrow X$ and computing $2x+b$.   Then $\mathcal{Y}\subseteq \mathcal{Z}_{\lambda}$.  That is, for each distribution that $\lock$ is intended to secure it is contained in the set of distributions that $\pointlock'$ is intended to secure.  Similarly, let $Z\in \mathcal{Z}_{\lambda}$ and define the distribution $X$ using the probability density function $\Pr[X=x] =\Pr[Z=(2x+0)] + \Pr[Z=(2x+1)]$.  Then $\Hoo(X) \ge \omega(\log \lambda)$, thus $X\in \mathcal{X}_{\lambda-1}$.

We show soundness by  contradiction. First assume that the construction described $\pointlock(x) = (r, r^{g^{h(x)}})$ is sound. That is, for all $c\in\mathbb{Z}^+$ there exists some $\lambda_{p,c}$ such that for $\lambda >\lambda_{p,c}$ for all PPT $\mathcal{A}_p$, there exists a simulator $\mathcal{S}_p$ such that:

\[
  \left| \Pr_{x\in\{0,1\}^\lambda}[\mathcal{A}_p(\pointlock(x)) = 1 ] - \Pr_{x\in\{0,1\}^\lambda}[\mathcal{S}_p^{I_x}(1^\lambda) = 1]\right| \leq \frac{1}{\lambda^c}.
\]

\noindent
In addition, suppose our construction is insecure, that is, there exists some $c\in\mathbb{Z}^+$ such that for all $\lambda_{c, dl}$ there exists a $\lambda>\lambda_{c, dl}$ such that there exists a PPT $\mathcal{A}_{dl}$ where for all $S_{dl}$ using a polynomial number of queries

\[
    \left| \Pr_{x\in\{0,1\}^{\lambda^*}}[\mathcal{A}_{dl}(\lock(x, b)) = 1] - \Pr_{x\in\{0,1\}^{\lambda}}[\mathcal{S}_{dl}^{I_{x, b}}(1^{\lambda^*}) = 1]\right| > \frac{1}{\lambda^{c}}.
\]

For a fixed $c\in\mathbb{Z}^+$, denote by $\lambda_{\max,c} = \max\{\lambda_{p,c}, \lambda_{dl,c}\}$.  There must exist some $\lambda>\lambda_{c,max}$ where the distance between $\mathcal{A}_p$ and $S_p$ is less than $1/\lambda^c$ while there exists some $\mathcal{A}_{dl}$ such that for all $\mathcal{S}_{dl}$ the distance between $\mathcal{A}_{dl}$ and $\mathcal{S}_{dl}$ is greater than $1/\lambda^c$.  Denote by $\mathcal{A}^*_{dl}$ one such adversary, that is for $\mathcal{A}^*_{dl}$ and all $S_{dl}$ making a polynomial number of queries their statistical distance is at least $1/\lambda^c$.
With the goal of arriving at a contradiction we use $\mathcal{A}^*_{dl}$ to construct an adversary $\mathcal{A}^*_p$ for $\lock$ that cannot be effectively simulated.

This adversary $\mathcal{A}^*_p$ works as follows, on input $\pointlock(x)$ where $x\in\zo^\lambda$, $\mathcal{A}^*_p$ initializes $\mathcal{A}^*_{dl}$ with input $\pointlock(x)$.  Note this is equivalent to initializing $\mathcal{A}^*_{dl}$ with input $\lock(x'||b)$ for $x=x'||b$.  Any predicate $\mathcal{P}( x' || b) = \mathcal{P}(x)$ output by $\mathcal{A}^*_{dl}$ is a valid predicate on on $x$. So, this predicate can be immediately output.  


Thus, $\mathcal{A}^*_{dl}$ implies the existence of an $\mathcal{A}^*_p$ that outputs $1$ with the same probability, and in particular they succeed with the same probability because we have exactly produced the probability distribution that $\mathcal{A}^*_{dl}$ is expecting.  That is,
\[
 \Pr[\mathcal{A}^*_p[(\pointlock(x)) = 1] = \Pr[\mathcal{A}^*_{dl}(\lock(x', b)) = 1].
\]
By assumption for each $\mathcal{A}_p$ there exists $\mathcal{S}_p$ such that for $\lambda >\lambda_{\max, c}$, 
\[
  \left| \Pr_{x\in\mathcal{Z}^\lambda}[\mathcal{A}_p(\pointlock(x)) = \mathcal{P}(x) ] - \Pr_{x\in\mathcal{Z}^\lambda}[\mathcal{S}_p^{{I_x(\cdot)}}(1^\lambda) = \mathcal{P}(x)]\right| \leq \frac{1}{\lambda^c}.
\]

 This $\mathcal{S}_p$ implies the existence of an $\mathcal{S}_{dl}$ that computes any predicate $\mathcal{P}$ on $(x', b)$. $\mathcal{S}_{dl}$ initializes $S_p$ and for every query from $S_{p}$ it drops the last bit and asks its oracle the query.  It only returns a match to $S_p$ if the returned bit matches the last bit of $S_p$'s query.  A formal description is in Algorithm~\ref{alg:simulatoralgorithm}.



\begin{figure}[t]
%%    \centering
%%\begin{centering}
%    \begin{minipage}[t]{.45\textwidth}
%    \vspace{0pt}
%   \begin{algorithm}[H] 
%\begin{framed}
%
%\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
%\Input{$\pointlock(x)=(r, r^{g^{h(x)}})$}
%\Output{$\mathcal{P}(x)$}
%\BlankLine
%
%%Set $x'||b = 2x'+b = x$
%
%%Input $\mathcal{O}'(x) = \mathcal{O}(x', b)$ into $\mathcal{A}*$
%
%Output $\mathcal{A}^*_{dl}(\pointlock(x))$.
%\vspace{.7in}
%\caption{Construction of $\mathcal{A}^*_p$ from $\mathcal{A}^*_{dl}$}
%\label{alg:AdversaryAlgorithm}
%\end{framed}
%\end{algorithm}
%    \end{minipage}%
%    \begin{minipage}[t]{0.55\textwidth}
    \vspace{0pt}
        \centering
    \begin{algorithm}[H]
\begin{framed}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{Oracle access to $I_{x, b}$}
\Output{$\mathcal{P}(x, b)$}
\BlankLine

Initialize $\mathcal{S}_p$.

Receive query $y$ from $\mathcal{S}_p$, send $x_{0,...\lambda-2}$ to $I_{x,b}$.

If response $b$, check if $x_{\lambda-1} = b$, if so return $1$.

Otherwise {\bf return} $\perp$ to $S'$.

Output $S_{dl}$s output.

\caption{Construction of $\mathcal{S}_{dl}$ from $\mathcal{S}_p$}
        \label{alg:simulatoralgorithm}
\end{framed}
\end{algorithm}

%    \end{minipage}
\end{figure}
%\IncMargin{1em}
So, the existence of $\mathcal{S}_p$ directly leads to the simulator $\mathcal{S}_{dl}$ that computes a $1$ with the same probability.  That is,
\[
\Pr[\mathcal{S}_p^{I_x}(1^\lambda) = 1] = \Pr[\mathcal{S}_{dl}^{I_{x, b}}(1^\lambda) = 1].
\]
These three equations allow us to state:

\begin{align*}
 \left| \Pr_{x\leftarrow X}[\mathcal{A}^*_{dl}(\lock(x, b)) = 1] - \Pr_{x\leftarrow X}[\mathcal{S}^{I_{x, b}}_{dl}(1^{\lambda^*}) = 1] \right|  \leq \frac{1}{\lambda^c}.
\end{align*}
This is a contradiction and completes the argument of soundness.

\paragraph{Nonmalleability}
We proceed by contradiction assuming that there exists some ensemble $X_\lambda'$ where $\Hoo(X_\lambda) = \omega(\log \lambda)$, some $\mathcal{A}_{dl}$, and some bit $b\in\zo$ such that there exists some $c$ where 
\[
\Pr_{x'\leftarrow X_\lambda'}\left[\begin{tabular}{c}$ (\lock', f) \leftarrow \mathcal{A}_{dl}(\lock(x', b))$\\$\mathcal{V} (\lock') = 1, f\in\mathcal{F},(I_{f(x'),0}  \equiv \lock' \vee I_{f(x'),1}  \equiv \lock' )|$\end{tabular} \right] > 1/\lambda^c
\]

We build an mauling adversary for the original obfuscation $\pointlock$.  We consider the ensemble of distributions $Z_\lambda = X_\lambda || b$, that is the distribution of $X_\lambda$ with the bit $b$ appended.  Note that this is a valid ensemble for the obfuscator $\pointlock$
In showing non-malleability, we are able to inherit the non-malleability guarantees of the underlying obfuscation, with a slight adjustment for bounds. This follows both for polynomial functions of $x$ as well as for bit flipping on $b$.  We design $\mathcal{A}_p$ as follows:
\begin{enumerate}
\itemsep0em
\item Receive $\pointlock(x)$ as input (equivalently receive $\lock(2x'+b)$).
\item Initialize $\mathcal{A}_{dl}$ with $\pointlock(x)$.
\item Receive $\lock', f$.
\item Set $f_0(x) = 2^{-1}(x-b)$ and $f_2(x)=2*(x)+b$.  Compute $f_3= f_2\circ f\circ f_0$.
\item Flip $r\overset{\$}\leftarrow\zo$.  If $r=0$ set $f' =f_3 -b$.  Else set $f'=f_3-b+1$.
\item Output $\lock', f'$.
\end{enumerate}

There are two pieces to how $\mathcal{A}_p$ is using $\mathcal{A}_{dl}$.  First, $\mathcal{A}_p$ is trying to produce a tampering function on $x\in \zo^\lambda$, while $\mathcal{A}^*$ is tampering on $x'$ contained in $x'|| b$.  Consider the example when $f(x) = 3x+1$ is output by the adversary.  This is akin to the adversary producing a valid obfuscation of $6x+2+1$ or $6x+2$.  The two functions $f_0$ and $f_2$ are for this difference.  The second main difference is that the $\mathcal{A}_{dl}$ does not know if the last bit of $x$ will be $0$ or $1$ so they output each possibility with probability $1/2$.  Together these facts allow us to conclude:

\begin{align*}
\Pr_{x\leftarrow Z_\lambda}&\left[\begin{tabular}{c}$ (\pointlock', f) \leftarrow \mathcal{A}_p(\pointlock(x))$\\$ \mathcal{V} (\pointlock') = 1, f\in\mathcal{F},(I_{f(x)}  \equiv \pointlock')$\end{tabular} \right]  \\
&= \Pr[R=r]\Pr_{x'\leftarrow X_\lambda}\left[ \begin{tabular}{c}$(\pointlock', f) \leftarrow \mathcal{A}_p(\pointlock(x'))$\\ $\mathcal{V} (\pointlock') = 1, f\in\mathcal{F},(I_{f(x'),r}  \equiv \pointlock)$\end{tabular}  \right]\\
&=\frac{1}{2} \Pr_{x'\leftarrow X_\lambda}\left[ \begin{tabular}{c}$ (\lock', f) \leftarrow \mathcal{A}_{dl}(\lock(x', b)$\\ $\mathcal{V} (\lock') = 1, f\in\mathcal{F},(I_{f(x'),0}  \equiv \lock' \vee I_{f(x'),1}  \equiv \lock' )$\end{tabular} \right]\\ &> \frac{1}{2\lambda^c}.
\end{align*}
This contradicts the nonmalleability of $\pointlock$ and completes the proof of nonmalleability.  This completes the proof of Theorem~\ref{thm:single time digital locker}.
%
%The single bit digital locker $\mathcal{O}$ is \emph{non-malleable} for $\mathcal{F}$ and $\mathcal{X}$ if for any polynomial-time adversary $\mathcal{A}$, there exists a negligible function $\epsilon$, such that for all $b\in \zo$ it holds that:
%\[
%\Pr_{x\leftarrow X}\left[ \mathcal{V} (C) = 1, f\in\mathcal{F},\text{ and }(I_{f(x),0}  \equiv C \vee I_{f(x),1}  \equiv C )| (C, f) \leftarrow \mathcal{A}(\mathcal{O}(x)) \right] \le \epsilon.
%\]
%
%Assuming $\mathcal{O}'(x)$ is non-malleable for the class of functions $\mathcal{F}_{poly}$ and supposing that $\mathcal{O}(x, b)$ can be mauled by some subset of $\mathcal{F}_{poly}$, we can show that a contradiction arises. First, we note that $h(2x+b)$ is a polynomial shift of $\mathcal{O}'(x)$, where $f(x) = 2x$ or $f(x) = 2x + 1$. We then choose some polynomial function $g\in\mathcal{F}_{poly}$ such that $g$ can maul $\mathcal{O}$. Because we know $f(x)$ (or can guess it nontrivially from two options), we can consider $\mathcal{O}(g(x), b)$ as $\mathcal{O}'(g(f(x))$. Finally, we note that, because $g$ and $f$ are both polynomial shifts, their composition can be represented as some polynomial function $h(x) = g(f(x))$. Because $h\in\mathcal{F}_{poly}$, though, this leads to a contradiction, as we have effectively mauled $\mathcal{O}'(x)$.
%
%The same reasoning can then be used to show that $b$ can not be mauled by bit flipping, either.
\end{proof}



\end{document}