text:
\section{Introduction}
Consider a server hosting a closed-source program that is intended to solve a specific problem (say, an advanced optimization tool). As a customer, you wish to delegate the task of running this program on your data to the server. Naturally, your limited access to the software as well as your lack of trust in the server concerns you about the validity of the returned results. How can you verify that the server is indeed running the correct program on your data and providing you with the desired outcome? To convince yourself that the server is in possession of {\it some} program that solves the claimed problem you could {\it probe} the server at random input values for which you know the outcome (say, through a different commercial software to which you only have trial access). Nevertheless, the bigger concern is whether the server continues to run the correct program on your data once this initial trust has been established. From an economic perspective, the server may have the incentive not to spend his computational resources on your data, but rather provide you with random outputs. Worse yet, a malicious server may intentionally provide you with false evaluations if he knows that you do not check the correctness of the results.

The literature on verifiable computing \cite{goldwasser2008delegating,gennaro2010non,benabbas2011verifiable,fiore2012publicly} and functional commitment protocols \cite{libert2016functional,kate2010constant} allow the server (prover) to generate a proof of correctness of his results which can be checked by the users (verifiers). However, verifying such proofs is only possible if one has substantial knowledge about the underlying function, or if a verification key has been generated by a trusted party. Furthermore, the soundness of these algorithms relies on heuristic hardness assumptions that may be falsified at any time due to algorithmic breakthroughs or technological advancements.

In this paper, our goal is to design a commitment and verification algorithm that overcomes these challenges. Namely, (i) the verifiability property must hold regardless of the computation power of the prover, (ii) there must be no need for a trusted party, and (iii) the verifier must not learn more than a constant number of bits about the underlying function, regardless of his computation power. In the example above, the prover should be able to keep his program private from the verifier while at the same time provide him with verifiable results. This verification is performed against an initial commitment by the prover which contains almost no information about the program itself. Once the verifier receives the commitment to a specific function, the prover will only be able to pass the verification process if he provides evaluations of the same function that he has committed to.
Our focus will be specifically on functions that can be represented as polynomials. This encompasses a wide range of applications including transaction verification in cryptocurrencies \cite{polyshard}, verifiable secret sharing \cite{chor1985verifiable,kate2010constant}, and proof-of-storage \cite{zheng2012secure,benet2017proof,fiore2012publicly}

\subsection{Our contributions}
We propose \textsf{Info-Commit}, a protocol for polynomial commitment and verification. Specifically, \name{ } consists of a commitment phase and and evaluation phase.
During the commitment phase, the prover and the verifier engage in a private two-party computation algorithm in such a way that the verifier learns a private commitment to the polynomial.
In the evaluation phase, the verifier is interested in learning the evaluations of the polynomial at many input points with the help of the prover. \name{ } is verifiable, doubly-efficient and privacy-preserving. More specifically, \name{ } has the following salient features.
\begin{enumerate}
    \item {\bf Verifiability.} If the prover commits to a polynomial $f$ in the commitment phase, he must provide evaluations of the same polynomial $f$ in the evaluation phase. Otherwise, the verifier is able to detect the inconsistency with overwhelming probability. On the other hand, if the prover is honest, the verifier accepts the results with probability 1.

\item {\bf Double-efficiency.} For each round of evaluation, the verifier runs in $O(\sqrt{d})$ whereas the prover runs in $O(d)$. Note that we measure the efficiency of \name{ } in the amortized model \cite{gennaro2010non} where the initial commitment phase is followed by many rounds of evaluations. As a result, the one-time cost of the commitment phase can be neglected.

\item {\bf Privacy.} The other facet of \name{ } is its privacy-preserving property. Upon observing the initial commitment and the response of the prover to $m$ rounds of evaluation, the verifier only learns $O(m^2)$ symbols over the field about the coefficients of the polynomial.

\item {\bf Information-theoretic guarantees without relying on any trusted party.} Both the verifiability and the privacy of \name{ } are information-theoretic, meaning that the verifier and the prover can have unbounded computation power and may arbitrarily deviate from the prescribed protocol. Furthermore, \name{ } does not rely on any trusted party, not even in the initial commitment phase.
\end{enumerate}

The only assumption that underlies the privacy of \name{ } is the bounded storage assumption which states that there exists an upper-bound $N$ on the storage size of the verifier. This upper bound must be publicly known and must not exceed $n^2$, where $n$ is the minimum required storage for each party for the protocol to succeed. This assumption is used in the commitment phase where we rely on oblivious transfer algorithms in the bounded storage model  \cite{cachin1998oblivious,aumann2002everlasting,cachin2015information,ding2004constant}.

\subsection{Related work}

The closest works in the literature to the present paper are commitment protocols, including polynomial commitment \cite{kate2010constant,papamanthou2013signatures,ma2013verifiable,bultel2017verifiable}, vector commitment \cite{catalano2013vector}, cryptographic accumulators \cite{benaloh1993one}, and more generally functional commitments \cite{libert2016functional}. These protocols allow a prover to provide a cryptographic commitment to a specific function which reveals little to no information about the underlying function. A verifier can then request the prover to ``open" the commitment at specific locations. The verifier should be able to detect if the opening is inconsistent with the initial commitment. There are several factors that distinguish the model in the current paper from the traditional notion of functional commitment.

 The {\it first} difference is in the notion of privacy. The linear commitment model in \cite{libert2016functional} requires the initial commitment to reveal no information about the function. However, it does not impose any requirement on how much information is revealed upon observing the evaluations (opening) of the functions along with the initial commitment. On the other hand, the polynomial commitment scheme in \cite{kate2010constant} only requires the {\it evaluations} of the polynomial at unqueried points to remain hidden from the verifier, which is a rather weaker privacy constraint. In contrast, we impose rigorous {\it information-theoretic} constraints on how much information is revealed about the {\it coefficients} of the polynomial upon observing the initial commitment {\it and} the evaluations at a constant number of input points.

{\it Secondly}, our model does not permit the assumption of a trusted party, a component that is common in functional commitment protocols \cite{kate2010constant,libert2016functional}. This trusted party is usually in charge  of generating a public key  (that is later used for commitment, evaluation and verification) in a {\it setup} phase which is eliminated in our model.

{\it Thirdly}, while the literature on functional commitment is more concerned with the size of the commitment and the size of the opening, we are instead focused on designing doubly-efficient algorithms, i.e., algorithms with efficient provers and super-efficient verifiers.
   Furthermore, unlike the literature on functional commitment, our verifiability is information-theoretic.

Another relevant concept is zero-knowledge verifiable computation \cite{parno2013pinocchio} and zero-knowledge arguments of knowledge \cite{groth2016size,ben2019aurora,wu2018dizk,sasson2014zerocash}. Such algorithms enable a verifier and a prover to interact in order to compute $f(v,u)$ where $f$ is a publicly known function, $v$ is the input of the verifier and $u$ is the private input of the prover. The verifier will not learn anything about $u$ except for what is implied through $f(v,u)$. Furthermore, the verifier will be convinced that there exists some $u$ known to the prover such that the computed value corresponds to $f(v,u)$. For instance, $f$ could correspond to a Rank-1 Constraint System (R1CS) \cite{wu2018dizk}, $v$ a public input, and $u$ a private witness such that $(v,u)$ satisfies all the quadratic constraints of the R1CS. In the context of polynomial evaluation, $v$ could be the input to the polynomial, $u$ the coefficients of the polynomial, and $f$ an operator that maps $(v,u)$ to the evaluation of the polynomial. Unfortunately, this approach does not provide any binding guarantees, as the prover may change his polynomial for every input.

Other related notions in the literature are oblivious polynomial evaluation \cite{naor2006oblivious,hazay2018oblivious,tassa2013oblivious} which guarantees the privacy of both parties in a semi-honest setting, and verifiable computation \cite{gennaro2010non,fiore2012publicly,sahraei2019interpol} which guarantees efficient verifiability but generally ignores the privacy of the prover.

\section{Polynomial Commitment and Verification}
\label{sec:statement}
Suppose a prover is in possession of a private polynomial $f(x) = a_0 + a_1x + \cdots + a_{d-1}x^{d-1}$ selected uniformly at random among all polynomials of degree $d-1$ over $\mathbb{F}_q$. A verifier, who only knows the degree of the polynomial, wishes to delegate the evaluation of this polynomial at several input points $x\in\mathbb{F}_q$ to the prover and verify the correctness of the results in sublinear time in $d$. Before this evaluation phase, the prover commits to the polynomial $f$ during an initialization phase. Once this commitment is done, the prover is expected to evaluate the same polynomial $f$ for every input $x$ that is provided by the verifier. The verifier should be able to detect, efficiently and with high probability, if for any input $x\in\mathbb{F}_q$ the prover instead returns $y \neq f(x)$. We assume that the verifier is interested in evaluating the polynomial $f$ at many input points, so that the complexity of the commitment phase amortizes over many rounds of the evaluation phase \cite{gennaro2010non}. Therefore, efficiency is only measured with respect to the evaluation phase. Additionally, during the entire commitment and evaluation phase, the verifier should learn close to nothing about the coefficients of the polynomial $f$. Note that revealing a constant number of symbols over $\mathbb{F}_q$ about the coefficients of $f$ to the verifier is inevitable, since such amounts of information can be learned by investigating a single pair $(x,f(x))$. Formally, a polynomial commitment and verification protocol consists of the following algorithms.

\begin{itemize}
    \item {\bf Commit$(a_0,\cdots,a_{d-1},K_v,K_p)$}. In the commitment phase the verifier and the prover engage in a secure two-party computation algorithm commit$(a_0,$ $\cdots,$ $a_{d-1},K_v,K_p)$ to help the verifier learn a secret verification key VK which depends on his secret key, $K_v$, the prover's secret key, $K_p$, and the polynomial coefficients $a_0,\cdots,a_{d-1}$.
    \item {\bf Eval$(x,a_0,\cdots,a_{d-1},K_p)$}. The verifier reveals a desired input $x$ to the prover. The prover will then provide $val = ${\bf Eval}$(x,a_0,\cdots,a_{d-1},K_p)$ to help the verifier evaluate $f(x)$.
    \item {\bf Verify}$(x,val,\text{VK},K_v)$. The verifier checks the correctness of $val$ based on his secret key, $K_v$, and the output of the commitment phase, VK. If $val$ is incompatible with the initial commitment, he will reject the evaluation. Otherwise he will proceed to recovering $f(x)$.
    \item {\bf Recovery$(x,val)$}. If the verification process passes, the verifier will proceed to recover the evaluation $f(x)$ via an algorithm {\bf Recovery}$(x,val)$.
\end{itemize}
The only assumption that underlies the privacy of \name{ } is the bounded storage assumption stated as follows.
\begin{definition}[The bounded storage assumption \cite{cachin2015information,ding2004constant}] This assumption states that there exists an upper-bound $N$ on the storage size of the verifier. Furthermore, the storage size of both the verifier and the prover is at least $N^{\frac{1}{2}+\epsilon}$. The upper-bound $N$ is publicly known.
\end{definition}
We are interested in polynomial commitment and verification protocols that are private (in the bounded storage model) and verifiable as defined below.
\begin{definition}
A polynomial commitment and verification protocol is information-theoretically private and verifiable if it satisfies the following properties.
\begin{itemize}
    \item {\bf Correctness}. If the prover follows the {\bf Commit} and {\bf Eval} algorithms for the same polynomial $f$, then the {\bf Verify} algorithm must return 1 with probability 1.
    \item {\bf (Information-theoretic) Soundness}. If the prover commits to a polynomial with coefficients $a_0,\cdots,a_{d-1}$, then the probability that he can pass the verification test with $\hat{val}\neq \text{\bf Eval}(x,a_0,\cdots,a_{d-1},K_p)$ should be negligible, regardless of his computation power.
    \begin{align}
        \mathbb{P}(\text{\bf Verify}(x,\hat{val},\text{VK},K_v,K_p) = 1, \hat{val} \neq \text{\bf Eval}(x,a_0,\cdots,a_{d-1},K_p))\approx 0.
    \end{align}
    \item {\bf Efficient verification}. The two functions {\bf Verify} and {\bf Recovery} must run in sublinear time in $d$.
    \item {\bf Efficient evaluation}. The running time of {\bf Eval} must be comparable to the time required for evaluating the polynomial $f$, i.e., linear in $d$.
    \item {\bf (Information-theoretic) Privacy}. After running {\bf Commit} and {\bf Eval} for $m$ different inputs $x_1,\cdots,x_m$, the verifier should only learn $\rho = O(poly(m))$ symbols over the field about the coefficients of the polynomial $f$, regardless of his computation power but under the bounded storage assumption. Importantly, $\rho$ should be independent of the degree of the polynomial
    \begin{align}
        H_q(a_0,\cdots,a_{d-1}|\text{VK}, (x_1,val_1),\cdots,(x_m,val_m) ) = d - O(poly(m)).
    \end{align}
\end{itemize}
\label{def:requirements}
\end{definition}

\section{Preliminaries}
\label{sec:prem}
In the analysis of security and privacy of \textsf{Info-Commit}, we make use of several basic properties of the entropy of random variables which we review in this section. Furthermore, in the commitment phase of \textsf{Info-Commit}, we rely on a secure two-party computation algorithm. Here we explain how this can be accomplished via a series of reductions to a much simpler problem known as one-out-of-two Oblivious Transfer \cite{rabin1981exchange,even1985randomized}. An information-theoretic solution for the latter will be outlined in the bounded storage model borrowed from \cite{ding2001oblivious,cachin1998oblivious,ding2004constant,cachin2015information}.

\subsection{Entropy of random variables}
In this section we overview the definitions of various entropy functions of random variables, the notion of Markov chain, and some useful properties that will help us establish the soundness and verifiability of \textsf{Info-Commit}.
\begin{definition}[Entropy] Let $X,Y,Z$ be three random variables with domains ${\cal X}$, ${\cal Y}$ and ${\cal Z}$ respectively. Let $q$ be an arbitrary positive number.
\begin{itemize}
    \item The entropy of $X$ in base $q$ is a measure of its randomness and is defined as
    \begin{align}
        H_q(X) = -\sum_{x\in {\cal X}} \mathbb{P}(X = x) \log_q \mathbb{P}(X = x).
    \end{align}
    Note that for a uniformly distributed $X$ over ${\cal X}$ we have $H_q(X) =
    log_q |{\cal X}| $ whereas for a deterministic $X$ we have $H_q(X) = 0$.
    \item The joint entropy of $X$ and $Y$ is defined as
    \begin{align}
        H_q(X,Y) = -\sum_{(x,y)\in{\cal X}\times{\cal Y}} \mathbb{P}(X = x, Y = y)\log_q \mathbb{P}(X = x,Y = y).
    \end{align}
    \item The conditional entropy of $X$ given $Y$ is defined as
    \begin{align}
        H_q(X|Y) = H_q(X,Y) - H_q(Y).
    \end{align}
\end{itemize}
\end{definition}
Some useful properties of the entropy terms are as follows.
\begin{itemize}
    \item Property 1. All the entropy terms defined above are non-negative.
    \item Property 2. $\max\{H_q(X),H_q(Y)\} \le H_q(X,Y) \le H_q(X) + H_q(Y)$. This implies that conditioning cannot increase the entropy, $H(X|Y)\le H(X)$.
    \item Property 3. If $X$ is independent of $(Y,Z)$ then $H_q(Y|X,Z) = H_q(Y|Z)$.
\end{itemize}

\begin{definition}[Markov Chain] An ordered set of three random variables $(X,Y,$ $Z)$ with domain ${\cal X}\times {\cal Y}\times {\cal Z}$ is said to form a Markov chain if
\begin{align}
    \mathbb{P}(X = x,Z=z|Y = y) = \mathbb{P}(X= x|Y=y)\mathbb{P}(Z=z|Y=y)
\end{align}
for every $(x,y,z)\in {\cal X}\times {\cal Y}\times {\cal Z}$. Intuitively, this means that the two random variables $X$ and $Y$ are independent, conditioned on knowing $Y$.
This Markov chain is represented via $X\longleftrightarrow Y \longleftrightarrow Z$.
\end{definition}
\begin{itemize}
    \item Property 4. If $X\longleftrightarrow Y \longleftrightarrow Z$ forms a Markov chain, then $H_q(X|Y,Z) = H_q(X|Y)$.
\end{itemize}
\subsection{Information-theoretic Oblivious Transfer}
Suppose Alice has $c$ secrets $a_0,\cdots,a_{c-1}$  and Bob has a secret index $i\in[0:c-1]$. Bob is interested in learning $a_i$ without revealing any information about $i$ to Alice. On the other hand, Alice wishes to reveal no information about $a_0,\cdots, a_{c-1}$ to Bob except for the value of $a_i$.  This problem is referred to as Oblivious Transfer (OT) \cite{even1985randomized}. If each of Alice's $c$ secrets belongs to an alphabet ${\cal Y}$ of size $|{\cal Y}| = q$, we refer to the problem as ${c\choose 1}_q-$OT. In this paper we make use of an ${c\choose 1}_q-$OT algorithm in the commitment phase.
Information-theoretic algorithms for ${2\choose 1}_q$ and ${2\choose 1}_2$ have been proposed in the literature in the bounded storage model \cite{cachin2015information,cachin1998oblivious,ding2004constant}. Furthermore, there exist unconditional reductions from ${c\choose 1}_q-$OT to ${2 \choose 1}_q-$OT and from ${c\choose 1}_q-$OT to ${c \choose 1}_2-$OT \cite{brassard1986information}. We will provide brief overviews of these algorithms here and refer the readers to the corresponding references for a more detailed description.

\subsubsection{Reduction from ${c\choose 1}_q-$OT to ${2\choose 1}_q-$OT.}
Information-theoretic reductions from ${c\choose 1}_q$ to ${c\choose 1}_2$ and from ${c\choose 1}_2$ to ${2\choose 1}_2$ have been presented in \cite{brassard1986information}. Here we describe a reduction from ${c\choose 1}_q-$OT to ${2\choose 1}_q-$OT and refer the interested reader to \cite{brassard1986information} to see the other reductions. Alice generates $c-2$ random symbols over the alphabet ${\cal Y}$, namely $r_0,\cdots,r_{c-3}$. Alice and Bob agree on an ordering of the elements of ${\cal Y}$. Let $y_i$ be the $i$'th element of ${\cal Y}$ in this ordering for $i\in[0:q-1]$. Define the summation operation over ${\cal Y}$ as $y_{i} + y_{j} = y_{mod(i + j,q)}$. Bob relies on ${2\choose 1}_q-$OT to request one element of each column of Table \ref{tab:reductionnto1}.
\begin{table}
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
        Index &  Value $0$& Value $1$ & $\cdots$ & Value $c-3$ & Value $c-2$\\
        \hline
        $1$ & $a_0$ & $a_1 + r_0$ & $\cdots$ & $a_{c-3}+r_{c-4}$ & $a_{c-2} +r_{c-3}$\\
        \hline
        $2$ & $r_0$ & $r_0 + r_1$ & $\cdots$ & $r_{c-4} + r_{c-3}$ & $a_{c-1} + r_{c-3}$\\
        \hline
    \end{tabular}
    \caption{Unconditional reduction from ${c\choose 1}_q-$OT to $c-1$ invocations of ${2 \choose 1}_q-$OT.}
    \label{tab:reductionnto1}
\end{table}
If Bob is interested in $a_i$, he will choose the second row for every column $j<i$, but chooses the first row for the $i$'th column. Bob's request to the remaining columns does not make any difference in the overall outcome: Bob will only learn $a_i$ and nothing else about the remaining $a_j$ values. If Bob wants $a_{c-1}$, he will choose the second row for every column of the table. Privacy of Bob follows from the privacy of the underlying ${2\choose 1}_q-$OT algorithm.

\iffalse
\begin{table}
    \centering
    \begin{tabular}{|c|c|c|c|}
    \hline
         Index& Value $1$& $\cdots$ & Value $m$ \\
    \hline
         1 & $b_{1,1}$ & $\cdots$ & $b_{1,m}$\\
    \hline
         $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$\\
    \hline
         $c$ & $b_{c,1}$ & $\cdots$ & $b_{c,m}$\\
    \hline
    \end{tabular}
    \caption{Caption}
    \label{tab:redunctionqarytobinary}
\end{table}
If Bob is honest, he will request the same index $i$ for every invocation. At the end, he will receive the entire $b_i = b_{i,1}\cdots b_{i,m}$ from which he can compute $a_i = f(b_i)$. If he is dishonest, he will try to request different rows of the table for each column. But thanks to Property 2, he will not be able to gain any information about more than one $a_i$.
\fi

\subsubsection{${2\choose 1}_q-$OT in the bounded storage model.}
Several works have proposed ${2\choose 1}_q-$OT and ${2\choose 1}_2-$OT algorithms in the bounded storage model which remain secure even if the two parties have infinite computation power \cite{ding2004constant,aumann2002everlasting,cachin2015information,cachin1998oblivious}. It is only necessary to assume that an upper bound $N$ on the storage size of Bob is known to Alice. The actual required storage size $n$ for the algorithm to succeed is much smaller than $N$. For instance, the algorithm in \cite{ding2004constant} only needs $n = N^{1/2+\epsilon}$. The general idea behind all these algorithms is as follows. Alice generates a random string of $K$ bits such that $K>\alpha N$ for some $\alpha> 1$. Let $R_X$ represent the sub-sequence of the random string indexed by the set $X\subseteq[N]$. Alice broadcasts this sequence, and each of Alice and Bob randomly stores a subset of the sequence of size $\sqrt{2\ell N}$. Let $\Omega_A\subseteq[N]$ represent the indices of the bits stored by Alice and define $\Omega_B$ similarly. By the birthday paradox, with high probability $|\Omega_A\cap \Omega_B| \approx \ell$. Alice reveals $\Omega_A$ to Bob and Bob computes two sets $\Omega_A\cap \Omega_B$ and $\Omega_B\backslash \Omega_A$. Next, the two parties engage in an interactive hashing algorithm  \cite{cachin2015information} to generate two sets $X_0,X_1\subseteq \Omega_A$ of equal size such that $X_i\subseteq \Omega_B$ but $|X_{1-i}\cap \Omega_B|\ll |X_{1-i}|$ for some $i\in\{0,1\}$ chosen by Bob. The interactive hashing algorithm also guarantees that Alice does not learn $i$. Alice encodes $a_0$ with $R_{X_0}$ and $a_1$ with $R_{X_1}$ and sends both to Bob. Bob will be able to decode $a_i$, since he knows  $R_{X_i}$. However, his incomplete knowledge of the set $R_{X_{1-i}}$ prevents him from learning $a_{1-i}$.

While the state of the art ${2\choose 1}_q-$OT  and ${2\choose 1}_2-$OT algorithms \cite{ding2004constant,cachin2015information} guarantee perfect privacy for Bob, they only guarantee Alice's privacy with probability $1- 2^{-k^c}$ for some security parameter $k$ and an arbitrary constant $c$. The negligible probability that Alice's privacy is compromised will translate to a negligible probability that \name{ } fails to guarantee the privacy of the polynomial against the verifier. But we can choose $k$ large enough so that the privacy of Alice is virtually {\it perfect}. We will make this argument precise in the analysis of privacy of \textsf{Info-Commit}.

\subsection{Secure Two-party computation based on ${c\choose 1}_q-$OT}
A secure two-party computation algorithm {\bf S2PC}$(x,y,f,{\cal X}, {\cal Y},{\cal F})$ enables two parties Alice and Bob to evaluate $f(x,y)$, where $f:{\cal X}\times {\cal Y}\rightarrow {\cal F}$ is a publicly known function, $x\in{\cal X}$ is the private input of Bob and $y\in{\cal Y}$ is the private input of Alice \cite{yao1982protocols}. At the end, Bob must learn $f(x,y)$ but nothing else about $y$, whereas Alice must learn nothing (not even $f(x,y)$). {\bf S2PC} can be realized via an instantiation of ${|{\cal X}|\choose 1}_{|\cal F|}-$OT as follows. The two parties first agree on an ordering of the elements of the set ${\cal X}$. Let $\zeta_i$ represent the $i$'th element of ${\cal X}$ in this ordering. Let $j\in[|{\cal X}|]$ be such that the private input of Bob satisfies $x = \zeta_j$. Bob can request the $j$'th row of Table \ref{tab:alpha_table} via an ${|{\cal X}|\choose 1}_{|\cal F|}-$OT algorithm. Bob will learn $f(\zeta_j,y) = f(x,y)$ but nothing else about $y$, whereas Alice will learn nothing about $x$.
        \begin{table}[h]
    \centering
    \begin{tabular}{|c|c|}
    \hline
        index & requested value \\
        \hline
        $1$ & $f(\zeta_1,y)$\\
        \hline
        $\cdots$ & $\cdots$ \\
        \hline
         $|{\cal X}|$ & $f(\zeta_{|\cal X|},y)$\\
        \hline
    \end{tabular}
    \caption{In order to learn $f(x,y)$, the verifier will request the $j$'th row  of this table via an ${|{\cal X}|\choose 1}_{|{\cal F}|}-$OT algorithm where $j\in[|{\cal X}|]$ is such that $x =\zeta_j$.}
    \label{tab:alpha_table}
\end{table}

 \begin{algorithm}
\caption[caption]{Secure two-party computation, {\bf S2PC}$(x,y,f,{\cal X}, {\cal Y},{\cal F})$}
\begin{algorithmic}[1]
\Statex {{\bf Input:} Function $f:{\cal X}\times {\cal Y}\longrightarrow {\cal F}$, Bob's private input $x\in{\cal X}$, Alice's private input $y\in{\cal Y}$.}
\Statex {\bf Output: }{Bob learns $f(x,y)$ and nothing else about $y$. Alice will not learn anything.}
\Statex{}
 \State The two parties agree on an ordering of the elements of the set ${\cal X}$. Let $\zeta_i$ represent the $i$'th element of ${\cal X}$ in this ordering.
 \State Let $j\in [|{\cal X}|]$ be such that $x = \zeta_j$. The verifier requests the $j$'th row of Table \ref{tab:alpha_table} via an ${|{\cal X}|\choose 1}_{|{\cal F}|}-$OT algorithm.
\end{algorithmic}
\label{Alg:initialization}
\end{algorithm}

\section{An Overview of \textsf{Info-Commit}}
We start by noting that the polynomial $f(x) = a_0 + a_1 x + \cdots + a_{d-1}x^{d-1}$ can be rewritten as
\begin{align}
    f(x) = \begin{bmatrix} 1 & x^s & \cdots &x^{s(s-1)}\end{bmatrix}
A
    \begin{bmatrix}1 & x & \cdots & x^{s-1}\end{bmatrix}^T.
\end{align}
where $s = \sqrt{d}$ and
\begin{align}
A =     \begin{bmatrix}a_{0} & a_1 & \cdots & a_{s-1}\\
                    a_s & a_{s+1} & \cdots & a_{2s-1}\\
                    &\ddots &&\\
                    a_{s^2-s} & a_{s^2-s+1} & \cdots & a_{s^2-1}
    \end{bmatrix}.
    \label{eqn:poly_to_matrix}
\end{align}
\subsection{A basic algorithm}
A rather straightforward algorithm is for the verifier to generate a $c\times s$ matrix $\Lambda\in \mathbb{F}_q^{c\times s}$ uniformly at random. In the commitment phase, the verifier and the prover will engage in a secure two-party computation algorithm to help the verifier learn
\begin{align}
\Gamma = \Lambda A.
\label{eqn:simple_commitment}
\end{align}
In this process, the verifier will not learn anything about $A$ other than what is revealed through $\Gamma$, and the prover will not learn anything about $\Lambda$. In the evaluation phase, the verifier will ask the prover to compute $b = A \begin{bmatrix}1 & x & \cdots & x^{s-1}\end{bmatrix}^T.$ Suppose the prover responds with $\hat{b}$. The verifier checks if $\Lambda \hat{b} = \Gamma  \begin{bmatrix}1 & x & \cdots & x^{s-1}\end{bmatrix}^T$, which can be done in $O(\sqrt{d}).$ If $\hat{b}\neq b$, this identity holds only with probability $q^{-c}$ \cite{sahraei2019interpol}, since the prover does not know anything about $\Lambda$.  If the verification process is successful, the verifier can recover $f(x) = \begin{bmatrix} 1 & x^s & \cdots &x^{s(s-1)}\end{bmatrix} \hat{b}$ in $O(\sqrt{d})$. The main issue with this algorithm is that $\Gamma$ reveals $\sqrt{d}$ symbols over $\mathbb{F}_q$ about the polynomial $f$ during the commitment phase, and another $\sqrt{d}$ symbols for each evaluation $b$. We wish to reduce this to a constant. We will accomplish this in two steps: firstly, against a semi-honest verifier and next against a malicious verifier.

\subsection{Improved privacy against a semi-honest verifier}
In order to improve the privacy of this algorithm, the prover will generate a polynomial $g$ of degree $d-1$ uniformly among all polynomials of degree $d-1$ over $\mathbb{F}_q$. In the commitment phase, instead of directly committing to $f$, the prover will commit to both $h  = f+ g$ and $g$. Let $A$ and $B$ represent the $s\times s$ matrices corresponding to the polynomials $f$ and $g$, constructed similarly to \eqref{eqn:poly_to_matrix}. If both commitments have the same structure as in \eqref{eqn:simple_commitment}, the verifier will be able to gain substantial information about the matrix $A$ by choosing his two secret matrices to be linearly dependent. To prevent this, the protocol will require the prover to commit to $A+B$ ``from left" as in \eqref{eqn:simple_commitment}, whereas the commitment to $B$ will be done from right. More concretely, the verifier and the prover will engage in a secure two-party computation algorithm to help the verifier learn
\begin{align}
    \Gamma &= \Lambda(A+B),\nonumber\\
    \Omega &= B \Theta^T,
    \label{eqn:advanced_commitment}
\end{align}
for two $c\times s$ secret matrices $\Lambda$ and $\Theta$ generated randomly by the verifier. To gain intuition on how this helps with preserving the privacy of $A$, it helps to think of $c=1$. Knowing any single linear combination of the rows of $A+B$ and any single linear combination of the columns of $B$ cannot reveal more than one symbol over $\mathbb{F}_q$ about the elements of the matrix $A$. This argument will be made precise in the analysis of privacy of the \textsf{Info-Commit}. In the evaluation phase, the prover will be required to compute
\begin{align}
v &= (A+B) \begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T,\nonumber\\
u &= \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix}B.
\label{eqn:vector_uv}
\end{align}
Suppose the prover responds with $\hat{v}$ and $\hat{u}$. The verifier will check the correctness of each result via two parities
\begin{align}
\Gamma \begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T &= \Lambda \hat{v},\nonumber\\
    \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix}\Theta^T &=  \hat{u}\Omega.
    \label{eqn:verify_uv}
\end{align}
If both verification tests are successful, the verifier will recover
\begin{align}
\hat{h}(x) &= \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix} \hat{v},\nonumber\\
\hat{g}(x) &= \hat{u}\begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T.
\label{eqn:recover}
\end{align}
He will then find $\hat{f}(x) = \hat{h}(x) - \hat{g}(x)$ and will accept $\hat{f}(x)$ as the correct evaluation of $f(x)$. This algorithm guarantees the verifiability of the results with high probability following a similar analysis to \cite{sahraei2019interpol}. Nonetheless, the privacy only holds as long as $(\Lambda,\Theta)$ are generated randomly, i.e., if the verifier is semi-honest. We will overcome this limitation in the next subsection.

\subsection{Improving privacy against a malicious verifier}
If both parties follow this protocol as described, the verifier will only learn a constant number of symbols about the polynomial $f$ upon observing $(\Gamma,\Omega)$ and the pair $(v,u)$ for a constant number of inputs (see the analysis of privacy in Section \ref{sec:analysis}). However, a malicious verifier may deviate from this protocol by choosing $\Lambda$ and $\Theta$ in a deterministic manner. To elaborate on this, suppose $c =1$ and the verifier chooses $\Lambda$ as the standard unit vector $\Lambda = \begin{bmatrix}1 & 0 & \cdots & 0\end{bmatrix}$. This helps him learn $\Gamma = A_1 + B_1$, the first row of the matrix $A+B$. Subsequently, in the evaluation phase, he requests the $(v,u)$ pair for $x=0$. Based on this, he can learn $u = B_1$, which is the first row of the matrix $B$. He will then proceed to subtract $\Gamma - u$ in order to find the first row of the matrix $A$, which reveals $\sqrt{d}$ symbols about the polynomial $f$.

We will propose a mechanism to resolve this threat. Suppose the verifier requests the $(v,u)$ pair for $m$ different inputs $x_1,\cdots,x_m$. Define the matrices $X$ and $Y$ as
\begin{align}
    X &= \begin{bmatrix}
        1 & x_1 & \cdots & x_1^{s-1}\\
        & \cdots &\cdots &\\
        1 & x_m & \cdots & x_m^{s-1}
    \end{bmatrix},\nonumber\\
    Y&= \begin{bmatrix}
        1 & x_1^s & \cdots & x_1^{s(s-1)}\\
        & \cdots &\cdots &\\
        1 & x_m^s & \cdots & x_m^{s(s-1)}
    \end{bmatrix},
    \label{eqn:bigXY}
\end{align}
and let the matrices $U$ and $V$ be the concatenation of the vectors $u$ and $v$ for all $x\in\{x_1,\cdots,x_m\}$. In other words,
\begin{align}
    V &= (A+B)X^T,\nonumber\\
    U &= YB.
    \label{eqn:bigUV}
\end{align}
Since after $m$ rounds of evaluation, the verifier learns both $\Gamma = \Lambda(A+B)$ and $U=YB$, the prover must ensure that the matrices $\Lambda$ and $Y$ do not contain any linear dependencies among their rows. Otherwise, this linear dependency can be exploited to extract substantial amount of information about the matrix $A$ as outlined in the example above. Since $rank(Y) = m$ and $rank(\Lambda) = c$ (with high probability for randomly chosen $\Lambda$), the prover must be ensured that $rank(Y||\Lambda) = c + m$ where $||$ denotes the vertical concatenation of the two matrices. Similarly, we must have that $rank(X||\Theta) = c+m$. To accomplish this, we restrict the matrices $\Lambda$ and $\Theta$ to have the same Vandermonde structures as the matrices $Y$ and $X$, respectively. In other words, $\Lambda$ and $\Theta$ must be of the form
\begin{align}
\Lambda &=
\begin{bmatrix}
    1 & \lambda^s_1 & \cdots & \lambda_1^{s(s-1)}\\
     & \cdots & \cdots& \\
    1 & \lambda^s_c & \cdots & \lambda_c^{s(s-1)}
    \end{bmatrix},\nonumber\\
    \Theta &= \begin{bmatrix}
    1 & \theta_1 & \cdots & \theta_1^{s-1}\\
     & \cdots & \cdots& \\
    1 & \theta_c & \cdots & \theta_c^{s-1}
    \end{bmatrix}.
    \label{eqn:restricted}
\end{align}
Note that as long as
\begin{align}
|\{\lambda_1,\cdots,\lambda_c,x_1,\cdots,x_m\}| &= |\{\theta_1,\cdots,\theta_c,x_1,\cdots,x_m\}| = c + m,
\label{eqn:full_xy}
\end{align}
the two rank requirements will be satisfied. Note also that without loss of generality, we can assume that $\lambda_i \neq \lambda_j$, $\theta_i \neq \theta_j$ and $x_i \neq x_j$ for $i\neq j$, since the verifier cannot benefit form receiving the same evaluation twice.
Restricting the structure of $\Lambda$ and $\Theta$ as opposed to choosing them uniformly at random over $\mathbb{F}_q^{c\times s}$ would mean that the prover now has some side information about these matrices which he can utilize to bypass the verification test. Fortunately, the analysis in Section \ref{sec:analysis} shows that this probability remains sufficiently small.

It is left to convince the prover that \eqref{eqn:full_xy} holds. For this purpose, we designate a set $S\subseteq \mathbb{F}_q$ of prohibited values from which the elements $\lambda_i$ and $\theta_i$ can be chosen. ``{Prohibited}" means that in the evaluation phase, the verifier is not permitted to delegate the evaluation of the function $f$ at any member of $S$ to the prover. For instance, the verifier could provide an upper-bound $\xi$ on its input values to the prover, and then $S\subseteq \mathbb{F}_q$ could be chosen as a sufficiently large interval whose smallest member is strictly larger than $\xi$.

\subsection{Considerations regarding the size of the field}
The privacy of \name{ } as analyzed in Section \ref{sec:analysis} relies on the fact that the set $\{\alpha^s| \alpha \in S \}$ is of the same size as $S$ where $S$ is the set of prohibited values. This property holds if the function $g(x) = x^s$ is a permutation over $\mathbb{F}_q$ which is the case if $gcd(s,q-1) =1$. It is also important that there exists a prohibited subset of $\mathbb{F}_q$ of sufficiently large size. To ensure this, either the verifier should set his upper bound $\xi$ appropriately, or the field size should be increased once the verifier provides the upper-bound. Of course, this adjustment must be done without violating the first property.

\section{Formal Description of \textsf{Info-Commit}}

The formal description of the four functions of \textsf{Info-Commit}, namely {\bf Commit}, {\bf Eval}, {\bf Verify} and {\bf Recovery} are provided in Algorithms \ref{Alg:commit},\ref{Alg:eval},\ref{Alg:verify} and \ref{Alg:recovery}. Theorem \ref{thm:thm} establishes that \name{ } satisfies the requirements of an information-theoretically verifiable and private protocol for commitment and verification.
\begin{theorem}
\name{ } as described by the {\bf Commit}, {\bf Eval}, {\bf Verify} and {\bf Recovery} Algorithms \ref{Alg:commit},\ref{Alg:eval},\ref{Alg:verify} and \ref{Alg:recovery} satisfies the correctness, soundness, privacy and efficiency requirements as stated in Definition \ref{def:requirements}. Specifically,
\label{thm:thm}
\begin{itemize}

     \item If the prover is honest, the verifier will accept the results with probability 1.
     \item The probability that the prover can pass the verification process with a false result is negligible,
    \begin{align}
        \mathbb{P}(\text{\bf Verify}(x,\hat{val},\text{VK}, K_v) = 1,\hat{val} \neq {val}) \le \frac{2}{r^c}.
    \end{align}
    \item The verifier only learns $O(m^2)$ symbols about the coefficients of the polynomial $f$ after he receives $(\text{VK},val_1,\cdots,val_m)$ for any choice of $K_v$ and any $m$ input values $x_1,\cdots,x_m$.
        \begin{align}
        H_q(a_0,\cdots,a_{d-1}|\text{VK}, (x_1,val_1),\cdots,(x_m,val_m)) = d - O(m^2).
    \end{align}
    \item The complexity of the verifier per evaluation round is $O(\sqrt{d})$,
    \begin{align}
        {\cal C}_{\text{\bf Verify}} + {\cal C}_{\text{\bf Recovery}} = O(\sqrt{d}).
    \end{align}
    \item The complexity of the prover per evaluation round is $O(d)$,
    \begin{align}
        {\cal C}_{\text{\bf Eval}} = O(d).
    \end{align}
\end{itemize}
\end{theorem}

 \begin{algorithm}
\caption[caption]{The commitment function, {\bf Commit}$(a_0,\cdots,a_{d-1},K_v,K_p)$}
\begin{algorithmic}[1]
\Statex {{\bf Input:} The prover's private polynomial coefficients, $a_0,\cdots,a_{d-1}$, the verifier's secret key, $K_v$, the prover's secret key, $K_p$.}
\Statex {\bf Output:} The verifier learns the verification key VK$=(\Gamma,\Omega)$.
\Statex{}
    \State The verifier sends an upper-bound $\xi$ on its maximum input to the prover. The two parties agree on a prohibited set $S\subset \mathbb{F}_q$ of size $r(s-1)$ where $s=\sqrt{d}$ and $r$ is a small positive integer (for instance, $r=10)$. Every element of $S$ must be greater than $\xi$.
    \State The prover generates a random polynomial $g$ of degree $d-1$ with matrix representation $B$. Let $h = f + g$ and $K_p = B$.
    \State The verifier chooses $c$ distinct elements of $S$ uniformly at random, named $\lambda_1,\cdots,\lambda_c$ where $c$ is a small positive integer (for instance, $c=10$). Similarly, he chooses $\theta_1,\cdots,\theta_c$. Let $K_v = (\lambda_1,\cdots,\lambda_c,\theta_1,\cdots,\theta_c)$ and define $\Lambda$ and $\Theta$ as in \eqref{eqn:restricted}.
    \State The two parties run $c$ instances of {\bf S2PC}$(\alpha,A+B,\eta_1,S,\mathbb{F}^{s\times s},\mathbb{F}^s)$ for $\alpha \in \{\lambda_i| i\in [c]\}$ where $\eta_1(\alpha,A+B) := \begin{bmatrix}1 & \alpha^s&\cdots& \alpha^{s(s-1)}\end{bmatrix}(A+B)$. The verifier thus learns $\Gamma = \Lambda(A+B)$.
    \State The two parties run $c$ instances of {\bf S2PC}$(\alpha,B,\eta_2,S,\mathbb{F}^{s\times s},\mathbb{F}^s)$ for $\alpha \in \{\theta_i| i\in [c]\}$ where $\eta_2(\alpha,B) := B\begin{bmatrix}1 & \alpha&\cdots& \alpha^{s-1}\end{bmatrix}^T$. The verifier thus learns $\Omega = B\Theta^T$.
    \State Let VK$ = (\Gamma,\Omega)$ be the verification key.
\end{algorithmic}
\label{Alg:commit}
\end{algorithm}

 \begin{algorithm}
\caption[caption]{The evaluation function, {\bf Eval}$(x,a_0,\cdots,a_{d-1},K_p)$}
\begin{algorithmic}[1]
\Statex {{\bf Input:} The coefficients of the polynomial, $a_0,\cdots,a_{d-1}$, the prover's secret key, $K_p = B$, the input to the polynomial, $x$.}
\Statex {{\bf Output:} $val = (v,u)$.}
\Statex{}
        \Statex The prover evaluates
\begin{align}
v &= (A+B) \begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T,\nonumber \\
u &= \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix}B,
\label{eqn:uv_final}
\end{align}
and returns $val =(v,u)$ to the verifier.
\end{algorithmic}
\label{Alg:eval}
\end{algorithm}

 \begin{algorithm}
\caption[caption]{The verification function, {\bf Verify}$(x,\hat{val},\text{VK},K_v)$}
\begin{algorithmic}[1]
\Statex {{\bf Input:} The input to the polynomial, $x$, the evaluation provided by the prover, $\hat{val} = (\hat{v},\hat{u})$, the (secret) verification key, VK$=(\Gamma,\Omega)$, and the verifier's secret key, $K_v$.}
\Statex {{\bf Output:} The verifier either accepts or rejects $\hat{val}$.}
\Statex{}
    \Statex   The verifier checks the two parities
    \begin{align}
\Gamma \begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T &= \Lambda \hat{v},\nonumber\\
    \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix}\Theta^T &=  \hat{u}\Omega.
    \label{eqn:verification_final}
\end{align}
If either parity fails, then {\bf Verify} returns 0 (rejected), otherwise, it returns 1.
\end{algorithmic}
\label{Alg:verify}
\end{algorithm}

 \begin{algorithm}
\caption[caption]{The recovery function, {\bf Recovery}$(x,\hat{val})$}
\begin{algorithmic}[1]
\Statex {{\bf Input:} The input to the polynomial, $x$, and the evaluation provided by the prover, $\hat{val} = (\hat{v},\hat{u})$.}
\Statex {{\bf Output:} The evaluation of the polynomial $\hat{f}(x)$ based on $\hat{val}$.}
\Statex{}
        \Statex If {\bf Verify} returns $1$, the verifier will compute $\hat{h}(x)$ and $\hat{g}(x)$ based on
\begin{align}
\hat{h}(x) &= \begin{bmatrix} 1 & x^s & \cdots & x^{s(s-1)}\end{bmatrix} \hat{v}\nonumber\\
\hat{g}(x) &= \hat{u}\begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T.
\end{align}
and finds $\hat{f}(x) = \hat{h}(x) - \hat{g}(x)$.
\end{algorithmic}
\label{Alg:recovery}
\end{algorithm}

\section{The Analysis of \textsf{Info-Commit}}
\label{sec:analysis}
\noindent{\bf Correctness}. If the prover is honest, he will provide the evaluations of the same polynomial $f$ that he has committed to. Consequently, in the verification phase, identities \eqref{eqn:verification_final} trivially hold and the recovered value is equal to $h(x) - g(x) = f(x)$ as desired.\\
\noindent{\bf Efficiency}.The verification can be done in $O(\sqrt{d})$ since it only requires multiplying $c\times s$ matrices by vectors of length $s = \sqrt{d}$. The recovery can be done in $O(\sqrt{d})$ since the main operation in this phase is inner products of vectors of length $s$. Therefore, the overall complexity of the verifier in the evaluation phase is $O(\sqrt{d})$. The prover, on the other hand, must compute the two vectors $v$ and $u$ according to \eqref{eqn:uv_final} which can be done in  $O(d)$.\\
\noindent{\bf Soundness}. The analysis of soundness relies on the fact that the prover learns nothing about the secret values $\lambda_i,\theta_i$, $i\in[c]$, during the commitment phase. This follows from the property that the oblivious transfer algorithms in \cite{cachin2015information,ding2004constant} provide perfect privacy for the receiver. Without loss of generality we can assume that the prover has committed to the correct polynomial $f$. If not, we simply use the letter $f$ to denote the polynomial that the prover has committed to, and expect the soundness property to hold with respect to this $f$. Note that such a polynomial of degree $d-1$ exists regardless of how the prover responds to the queries in the commitment phase

Remember that for each input $x$, the prover is required to provide the verifier with two vectors $u$ and $v$ as defined in \eqref{eqn:uv_final}. Here, we analyze the probability that a malicious prover can pass the verification test \eqref{eqn:verification_final} with a $\hat{v}\neq v$ ($\hat{u}\neq u$) and show that this probability is negligible. Let $({\cal V},{\cal U})$ denote a random variable from which the prover draws the evaluation $(\hat{v},\hat{u})$. Note that $({\cal V},{\cal U})$ is independent of $({ \Lambda},{\Theta})$. The probability that the prover can pass the first verification test with an incorrect result is given by
\begin{align}
    p_v &= \mathbb{P}\Big(\Gamma \begin{bmatrix} 1 & x & \cdots & x^{s-1}\end{bmatrix}^T) = \Lambda {\cal V} , {\cal V}\neq v\Big) \nonumber\\
   &= \mathbb{P}\Big(\Lambda ({\cal V}-v) = {\bf 0} , {\cal V} \neq v\Big),
\end{align}
where the randomness is with respect to $(\Lambda,\Theta,{\cal V},{\cal U})$. We need an upper-bound on $p_v$ that holds for any $x$ and any $A,B$. Define $\begin{bmatrix}\gamma_0,\cdots,\gamma_{s-1}\end{bmatrix} = {\cal V}-v$. We can see this vector as the coefficients of a polynomial of degree $s-1$. The last equation is then the probability that the prover can provide a nontrivial polynomial of degree $s-1$ such that all $\lambda_i^s$, $i\in [c]$, are the roots of this polynomial. Note that the polynomial $\gamma(x) = \gamma_0 + \gamma_1 x + \cdots + \gamma_{s-1}x^{s-1}$ has at most $s-1$ roots in the set $S' = \{y^s|y\in S\}$. Note also that all the terms $\lambda_i^s, i\in[c]$, are distinct. This is because the field size $q$ is chosen in such a way that $gcd(s,q-1) =1$. As a result, the function $e(x) = x^s$ is a permutation, and the set $S'$ has $r(s-1)$ distinct elements. Let $T\subseteq S'$ of size at most $|T| \le s-1$ represent the roots of the polynomial $\gamma(x)$ that are in $S'$. In other words, $t\in T$, if and only if $\gamma(t) = 0$ and $t\in S'$. We are interested in the probability that $\lambda_i^s\in T$, $\forall i\in [c]$. Since ${\cal V}$ is independent of $\Lambda$, so is the set $T$. we can therefore bound $p_v$ as
\begin{align}
    p_v = \mathbb{P}(\lambda_i^s \in T, \forall i\in[c])\le \frac{{s-1 \choose c}}{{r(s-1) \choose c}}\le (\frac{s-1}{r(s-1)})^c = \frac{1}{r^c}.
\end{align}
 Similarly, one can bound the probability that the prover can pass the second verification test with $\hat{u}\neq u$ as $p_u \le \frac{1}{r^c}$. As a result,
 \begin{align}\mathbb{P}({\text{\bf Verify}(x,\hat{val},\text{VK},K_v) = 1,\hat{val}\neq val}) \le p_u + p_v \le  \frac{2}{r^c}.
 \end{align}
For instance, by choosing $r=10$ and $c=10$, this probability can be reduced to $2\times 10^{-10}$.

\noindent The next two lemmas will help us establish the privacy of \textsf{Info-Commit}.

\iffalse
\begin{lemma}
Let $X$ and $Y$ be two independent random variables with alphabets ${\cal X}$ and ${\cal Y}$ respectively. Let $f:{\cal X}\rightarrow {\cal Y}$ and $g:{\cal X}\rightarrow {\cal Z}$ be two arbitrary functions with domain ${\cal X}$. The sequence
\begin{align}
    f(X) + Y \longleftrightarrow f(X) \longleftrightarrow g(X)
\end{align}
forms a Markov chain.
\label{lem:provemarkov}
\end{lemma}
\begin{proof}
We will show that $\mathbb{P}(f(X)+ Y = z, g(X) = w | f(X)= u) = \mathbb{P}(f(X) + Y = z| f(X) = u)\mathbb{P}(g(X) = w|f(X) = u).$
\begin{align*}
   & \mathbb{P}(f(X)+ Y = z, g(X) = w | f(X)= u) =\mathbb{P}(Y=z-u, g(X) = w| f(X) = u)\\
&    =\frac{\mathbb{P}(Y= z-u, g(X) = w, f(X) = u)}{\mathbb{P}(f(X) = u)} = \frac{\mathbb{P}(Y =z-u)\mathbb{P}(g(X) =w,f(X) = u)}{\mathbb{P}(f(X) = u)}\\
&    = \mathbb{P}(Y = z-u)\mathbb{P}(g(X) = w|f(X) = u)\\
&= \mathbb{P}(Y = z-u| f(X) = u)\mathbb{P}(g(X) = w|f(X) = u)\\
&=    \mathbb{P}(Y + f(X) = z| f(X) = u)\mathbb{P}(g(X) = w|f(X) = u).
\end{align*}
\end{proof}
\begin{lemma}
Let $X,Y,Z$ be three random variables such that
\begin{itemize}
    \item $X$ is independent of $Y$,
    \item The sequence $X\longleftrightarrow Y \longleftrightarrow Z$ forms a Markov chain.
\end{itemize}
Then, $H_q(Y|X,Z) = H_q(Y|Z)$.
\label{lem:usemarkov}
\end{lemma}
\begin{proof}
We need to show that the two conditions above imply that $X$ is independent of $(Y,Z)$. The claim then follows from Property 3 of entropy terms in the preliminaries.
\begin{align}
    \mathbb{P}(X = x, Y= y, Z = z) &= \mathbb{P}(Y = y)\mathbb{P}(X = x|Y=y)\mathbb{P}(Z = z|Y = y)\\
    & =  \mathbb{P}(Y = y)\mathbb{P}(X = x)\mathbb{P}(Z = z| Y =y )\\
     & = \mathbb{P}(X = x)\mathbb{P}(Z = z, Y =y ).
\end{align}
\end{proof}
\fi

\begin{lemma}
Let $c,d,s$ be three positive integers such that $c,d\le s$. Let $E$ be an $s\times s$ random matrix uniformly distributed over $\mathbb{F}_q^{s\times s}$. Let $F$ and $G$ be arbitrary full-rank $c\times s$ and $s\times d$ matrices respectively. Then
\begin{align}
    H_q(FE | EG) \ge cs - cd.
\end{align}
\label{lem:conditional_matrix_entropy}
\end{lemma}
\begin{proof}
Since, $G$ is full-rank, we have that $EG$ is uniformly distributed over $\mathbb{F}_q^{s\times d}$ and as a result, $H_q(EG) = sd$. So, we only need to prove that $H_q(FE,EG) \ge cs + sd - cd$. Let $L\in\mathbb{F}_q^{s^2}$ be a column vector obtained from the vertical concatenation of the columns of $E$, such that $L_{i+ sj}  = E_{i,j}$ for all $i\in[0:s-1]$, $j\in[0:s-1]$. Let ${\cal F}  = \mathbf{I}_{s\times s}\otimes F$ where $\mathbf{I}_{s\times s}$ is the $s\times s$ identity matrix and $\otimes$ denotes the Kronecker product. Let ${\cal G} = G^T\otimes \mathbf{I}_{s\times s}$. Since the two vectors ${\cal F}L$ and ${\cal G}L$ are rearrangements of the the two matrices $FE$ and $EG$, respectively, we have that $H_q(FE,EG) = H_q({\cal F}L,{\cal G}L)$. The proof follows from the fact that the $(c+d)s$ by $s^2$ matrix ${\cal H} = {\cal F}||{\cal G}$ obtained from vertical concatenation of ${\cal F}$ and ${\cal G}$ has rank at least $(c+d)s - cd$ as long as $F$ and $G$ are full-rank (See Lemma \ref{lem:fullrank} in the appendix).
\end{proof}

\begin{lemma}
Let $E,F,G$ be three random variables with alphabets ${\cal E}, {\cal F}, {\cal G}$, satisfying the Markov chain $E \longleftrightarrow F \longleftrightarrow G$. Let $h: {\cal E}\times{\cal G}\rightarrow {\cal W}$ be an arbitrary function. Then, we have
\begin{align}
    H(E|F, h(E,G))\ge \min_{g\in {\cal G}} H(E|F,h(E,g))
\end{align}
\label{lem:replace_by_constant}
\end{lemma}
\begin{proof}
The following chain of inequalities prove the claim.
\begin{align}
   H(E|F, h(E,G))&\ge H(E|F,G, h(E,G)) \\
   &= \sum_{g \in {\cal G}}p(G = g)H(E|F,G=g, h(E,g))\\
   &\ge \min_{g\in {\cal G}}H(E|F,G=g, h(E,g))  = \min_{g\in {\cal G}}H(E|F,h(E,g)).
\end{align}
Note that the first inequality is due to Property 2 of entropy terms in the preliminaries, and the last inequality follows from Property 4. Specifically, since  $E \longleftrightarrow F \longleftrightarrow G$ forms a Markov chain, then  $E \longleftrightarrow (F,h(E,g)) \longleftrightarrow G$ forms a Markov chain too, which allows us to drop $G=g$ from conditioning.
\end{proof}
\noindent{\bf Privacy}. We prove that after $m$ rounds of evaluation, the verifier learns at most $(m+ c)^2$ symbols over $\mathbb{F}_q$ about the matrix $A$ which represents the polynomial $f$.  The analysis of privacy relies on the fact that the verifier learns nothing about $(A+B,B)$ in the commitment phase except for what is implied via $(\Gamma,\Omega)$. This follows because the secure two-party computation algorithm in \cite{cachin2015information,ding2004constant} provides perfect privacy for the sender except with negligible probability. The analysis also makes use of the fact that the $\lambda_i$ and $\theta_i$ values in the commitment phase are chosen from a ``prohibited" set. As a result of this, the matrices $\Lambda || Y$ and $\Theta|| X$ will be full-rank. Note that the verifier cannot benefit from selecting $x_i = x_j$, i.e., requesting the same evaluation point twice. Similarly, he cannot benefit from setting $\lambda_i = \lambda_j$ or $\theta_i= \theta_j$. Therefore, without loss of generality, we can assume that $rank(\Lambda ||Y) = rank(\Theta||X) = m + c$.

First, we assume that the privacy of the transmitter in the OT algorithm is perfect. At the end of the proof, we will show that the negligible probability that the privacy of the transmitter in the OT algorithm is compromised does not make a fundamental difference in our analysis. For $(X,Y,V,U)$ defined as in \eqref{eqn:bigXY},\eqref{eqn:bigUV}, we want to show that
\begin{align}
    H_q(A|V,U,\Gamma,\Omega) \ge d - (m + c)^2,
    \label{eqn:mutual_bound}
\end{align}
for any choice of the evaluation points $x_1,\cdots,x_m$ and for any choice of $\theta_1,\cdots,\theta_c,$ $\lambda_1,\cdots,\lambda_c$. We start by simplifying the left hand side of \eqref{eqn:mutual_bound}.
\begin{align}
    &H_q(A|V,U,\Gamma,\Omega) = H_q(A| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T)\nonumber\\
        &= H_q(A,(A+B)X^T,\Lambda (A+B)| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T) \nonumber\\
    &= H_q(A,BX^T,\Lambda B| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T) \nonumber\\
        &= H_q(BX^T, \Lambda B| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T)\nonumber\\
        &+ H_q(A|BX^T, \Lambda B,(A+B)X^T,YB,\Lambda(A+B),B\Theta^T)\nonumber\\
    &= H_q(BX^T, \Lambda B| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T)+ H_q(A|AX^T,\Lambda A),
\end{align}
\iffalse
\textcolor{blue}{Note: In the last step, we are treating $X$ as a constant. In general, this may not be the case. The verifier may choose $X$ after observing $\Gamma$ and $\Omega$. Intuitively, since $\Gamma$ and $\Omega$ are already in the conditioning, w.l.o.g., one should be able to treat $X$ as a constant. Here, we formalize this argument.\\
{\it Conjecture. Suppose we have three random variables $X,Y,Z$ in ${\cal X}, {\cal Y}, {\cal Z}$ which satisfy the Markov chain $X \leftrightarrow Y \leftrightarrow Z$. Suppose $f$ is an arbitrary deterministic function with domain $({\cal X}\times {\cal Y})$. We have the following hypothesis}
\begin{align}
    H(X|Y,f(X,Z)) \ge \min_{z\in {\cal Z}} H(X|Y, f(X,z)).
\end{align}
\begin{align}
    H(X|Y,f(X,Y)) \ge H(X|Y,Z,f(X,Z))\ge \min H(X|Y,Z=z, f(X,z))\\ = \min H(X|Y,f(X,z))
\end{align}
let's say $f(X,Z) = min(X,Z)$. The intuition behind this conjecture is that since $Y$ has already appeared in the conditioning, and due to the Markov chain, $Z$ does not contribute any extra information, and may be replaced by a constant. To gain further intuition, consider an extreme case where $f(X,Z) = Z$. In this case, the left hand size is equal to $H(X|Y,Z) = H(X|Y)$. The right hand side will be $H(X|Y,z) = H(X|Y)$ which is the same as the left hand side.\\
It may be tempting to conjecture that the inequality holds even if the Markov chain does not hold. But there are simple counter examples for this. For instance if $Z = X$ but $Y$ is independent of $X$, and $f(X,Z) = Z$, then the left hand side is zero, but the right hand side is $H(X)$.}\\
\fi
where the last equality follows from the fact that $A$ is independent of $B$.
The second term in the final expression can be easily bounded as
\begin{align}
    H_q(A|AX^T,\Lambda A) &= H_q(A) - H_q(AX^T,\Lambda A)\nonumber\\
    &\ge H_q(A) - H_q(AX^T) - H_q(\Lambda A)= d - ms - cs.
\end{align}
Therefore, we must show that the first term satisfies
\begin{align}H_q(BX^T, \Lambda B| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T) \ge ms + cs- (m + c)^2.\end{align} Observe that $\Big((A+B)X^T,\Lambda(A+B)\Big)$
is independent of $\Big(BX^T,\Lambda B, YB,B\Theta^T\Big)$ (because $A+B$ is independent of $B$). So, by Property 3 of the entropy terms in the preliminaries, we have

\begin{align}
H_q(BX^T, \Lambda B| (A+B)X^T,YB,\Lambda(A+B),B\Theta^T) = H_q(BX^T, \Lambda B|YB,B\Theta^T).
\end{align}
It is left to prove that $H_q(BX^T, \Lambda B|YB,B\Theta^T) \ge ms + cs - (m + c)^2$. Note that
\begin{align}
&H_q(BX^T, \Lambda B|YB,B\Theta^T) = H_q(BX^T, \Lambda B,YB,B\Theta^T)- H_q(YB,B\Theta^T)\nonumber\\
&= H_q(BX^T,B\Theta^T) + H_q(\Lambda B,YB|BX^T,B\Theta^T)  - H_q(YB,B\Theta^T).
\end{align}
Due to the fact that $x_i$ and $\theta_i$ values are chosen from two different sets, we know that $\Theta||X$ is a full-rank matrix. Therefore, $H_q( BX^T,B\Theta^T) = (c+m)s$. Similarly, the matrix $\Lambda||Y$ is full-rank, thus by Lemma \ref{lem:conditional_matrix_entropy} we have $H_q(\Lambda B, YB|BX^T,B\Theta^T)$ $ \ge (c+m)s  - (c+m)^2$. Also, $H_q(YB,B\Theta^T)\le H_q(YB) + H_q(B\Theta^T) = ms + cs$. Therefore, $H_q(BX^T, \Lambda B|YB,B\Theta^T) \ge ms + cs - (m+c)^2$. This gives us the desired inequality $H_q(A|V,U,\Gamma,\Omega)\ge d- (m + c)^2$.

We proved that $H_q(A| (A+B)X^T,YB,\Gamma,\Omega) \ge d - (m+c)^2$, for {\it every} choice of the evaluation points $x_1,\cdots, x_m$. Note that in general, the verifier may choose the evaluation points {\it after} observing the commitment ${(\Gamma,\Omega)}$. In other words, rather than assuming $(X,Y)$ are arbitrary constants, we must treat them as random variables which satisfy the Markov chain $(A,B)\longleftrightarrow (\Gamma,\Omega) \longleftrightarrow (X,Y)$. But thanks to Lemma \ref{lem:replace_by_constant}, since $(\Gamma,\Omega)$ appear in the conditioning, we have
\begin{align}
    &H_q(A| (A+B)X^T,YB,\Gamma,\Omega) \ge \\
    &\min_{x_1,\cdots,x_m} H_q(A| (A+B)\begin{bmatrix}
        1 & x_1 & \cdots & x_1^{s-1}\\
        & \cdots &\cdots &\\
        1 & x_m & \cdots & x_m^{s-1}
    \end{bmatrix}^T,\begin{bmatrix}
        1 & x_1^s & \cdots & x_1^{s(s-1)}\\
        & \cdots &\cdots &\\
        1 & x_m^s & \cdots & x_m^{s(s-1)}
    \end{bmatrix}B,\Gamma,\Omega).
\end{align}
Therefore, the analysis above also addresses the case where the evaluation points are chosen adaptively, after observing the commitment.

Finally, let us show that the negligible probability that the privacy of the transmitter is compromised in the OT protocol does not make any fundamental difference in the analysis above. Let $(\Gamma^*,\Omega^*)$ represent the random variable that the verifier learns by the end of the commitment phase. The analysis in \cite{ding2001oblivious,ding2004constant,cachin2015information} indicates that with overwhelming probability, $(\Gamma^*,\Omega^*)$ does not reveal any more information about $(A+B,B)$ than what is implied through $(\Gamma,\Omega)$. Put differently, with overwhelming probability, the sequence $(\Gamma^*,\Omega^*)\longleftrightarrow (\Gamma,\Omega)\longleftrightarrow (A+B,B)$ forms a Markov chain. Let $T$ be a binary random variable that is equal to 1 if and only if this Markov chain holds. We know that $P(T = 0) = \epsilon$ (see for instance, Theorem 1 in  \cite{ding2001oblivious}). Based on this, we can bound
 \begin{align}
    & H_q(A|V,U,\Gamma^*,\Omega^*) \ge     H_q(A|V,U,\Gamma^*,\Omega^*,T)\nonumber \\
    &  =\mathbb{P}(T=1)H_q(A|V,U,\Gamma,\Omega) + \mathbb{P}(T=0)H_q(A|V,U,\Gamma^*,\Omega^*, T = 0)\nonumber\\
    &  \ge (1-\epsilon)H_q(A|V,U,\Gamma,\Omega).
 \end{align}
 Note that $\epsilon$ can be made arbitrarily small by choosing a sufficiently large security parameter in the OT algorithm \cite{ding2001oblivious}. In particular, it can be made inversely proportional to $d$. Then
 \begin{align}
     H_q(A|V,U,\Gamma^*,\Omega^*) \ge H_q(A|V,U,\Gamma,\Omega) - O(1).
 \end{align}
 Therefore, it suffices to show that $H_q(A|V,U,\Gamma,\Omega) = d-O(m^2)$ which we accomplished in the first part of the proof.

\section*{Acknowledgement}
The authors would like to thank Mohammad Ali Maddah-Ali, Srivatsan Ravi and Ali Rahimi for the fruitful discussions and for revising the manuscript.
\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


text:
berthahenson
Archive for July, 2012|Monthly archive page
Desmond Kuek, M Ravi, Ram Tiwary, Tey Tsun Hang
In News Reports, Politics, Society on July 30, 2012 at 2:59 am
I didn't read the papers over the weekend. And my life went on! Not good. Shows I can do without. But in the interest of this blog, and to hew to my view that a citizen must be engaged in this country's conversation, I dutifully went through the copies….and found:
a. Gosh! Ram Tiwary got acquitted!
I have an interest in this Sydney double murder case because I was the ST news editor at that time and followed it real closely. It's simply too dramatic a case. A couple of young Singapore men bludgeoned, knifed to death in their home – supposedly by their flat mate. Lives cut short, even as they were pursuing that Singaporean dream of getting a degree. I read all the statements, twists and turns, what the judges said. I noted every contradictory statement that Tiwary made. The wheels of justice grind very slowly in Sydney…after eight years, he's acquitted by a court of appeal. After two previous juries pronounced him guilty.
I don't suppose that means he is CLEARED of a crime, that is, it was definitely NOT him who did the deed? His lawyer says it's due to lack of evidence, which means it is NOT clear that it was he who done them in. That is, he COULD have done it, but no one can prove it. Or maybe the acquittal was due a technicality as in his earlier trial, where the judge was said to have wrongly advised the jurors. Or maybe the jury system isn't working – can't assess the evidence – so a panel of wise men had to deliberate….
Speculation is premature I suppose. But the implications for Tiwary and the families of the men are enormous, as Ben Nadarajan said on Saturday. Tiwary is getting a passport to return home. I wonder how he feels. Clearly, for the affected families, there is no closure for their grief. I can't wait for the grounds of decision which led to his acquittal. Hopefully the wheels of justice in Sydney will turn a little faster.
b, Hmm….Desmond Kuek might be new SMRT head.
The third military man so far to head what is now commonly described as the "beleaguered" transport operator. Saw Phaik Hwa's term now looks like an aberration. A woman. Spiky hair. Retailer's instinct. Now man. Straight-backed. With experience in, I suppose, organisation and logistics. Looked like what the doctor ordered – go back and take the same old medicine. An image change as well although I'm sure the ex-CDF chief is eminently qualified for the thankless job of re-working the place. I like talking to military men. In my former life, I've had to deal with them a bit. Usually straight-talking, no nonsense but in a language that only men in the military are familiar wth. I recall one encounter with Kuek when he was still CDF chief. He thanked me for a Page 1 story on some change to SAF. He liked it, he said. I said, Thank you, but I didn't like the story at all. And we didn't write the story for you..The surprise on his face! And those in uniforms around him! Maybe I seemed ungracious and should have just said, You're welcome. Maybe no one talks back to the CDF? Anyway, he was interested enough to ask me why and I had a ball of a time telling him his people should speak in English instead of in army. And that half the population didn'tdo national service. He listened and I hope he will continue to do so. Heading the SMRT is more than a logistics exercise, it's about dealing with people. The commuters. Whom we all know are an exacting bunch!
c. I mean…what is Tey Tsun Hang up to?
So an academic got caught receiving favours, including a Mont Blanc pen and two tailored shirts (sheesh, she took his measurements?) Ok, he was charged with getting sex as well – apparently in exchange for giving the girl favorable grades. Which makes you wonder – did those favours REALLY result in her getting a second upper law degree? She really didn't earn it? Or did they just have consensual sex, a two-night stand under the influence? I suppose it's like the CNB guy who will go on trial because he had sex with someone who is involved in a business transaction with an agency. Did the women get what they want or said to have wanted? Will someone re-look her academic credentials? After all, the NUS moved the rest of his students when the case came up to other law lecturers….
Beyond that, it's intriguing howTey keeps referring to his academic writings. One particularly was named – on the supine, suppliant profession and its practice (being deliberately vague here because of contempt of court rules). Many people have read that to mean that he thinks the charges are to punish him for his academic work. That's muddying the waters a bit. Does he think the whole thing came up because "people" were digging for dirt as some kind of payback for his academic work? That his work is so water-tight that "people" couldn't catch him out for that and so went on another tack? It's like getting Al Capone for tax evasion, or getting someone for possessing porno at home? Except that people like me wouldn't know about his academic work until this case came up….so it has backfired on the "people"….Stupid "people". Sex and politics is such a heady mix…
d. And there goes…..M Ravi
Bipolar or eccentric. Publicity seeker or crank. Tree hugger. Singer. Dancer. Don't know. But he's certainly entertaining.
economics, immigration, Politics, population
People, oh people…
One of the objectives of the media must be to give citizens information to develop an opinion or make it easier for them to live their lives. Sometimes, the media points the way, taking apart a long-winded report or speech to give you the salient points (from their point of view of course) So there I was hoping that the various media have torn apart the Population report, pick out the key stuff and save me the trouble of reading the tome and figuring the statistics.
So I have from ST the point that the G wants feedback on birthrate, immigration etc. Not once, but twice within the paper. Helpfully, it seems the G has framed some discussion points like whether we would still tighten inflow of immigrants even if it means the population ages and shrinks and the foreign spouses of Singaporeans find it tough to get PR or citizenship.
I suppose there is a shock factor here: that there are plenty of Singaporeans married to foreigners who will want their spouses to live here – and they really haven't said much in this on-going debate so far. Trouble is, how many of them – and their children – are here? ST doesn't say but a graphic gives a 15 per cent figure of the non-resident population for dependents of citizens (old and new I presume), PRs and work pass holders.
From Today, which led off with new information instead of exhortation:
Immigration statistics revealed by the Government for the first time showed that, between 2007 and last year, the majority of those granted citizenship and permanent residence were not economically active — with the number of dependents outstripping working individuals. During this period, there were 259,040 new permanent residents (PRs) and 92,310 new citizens. Working individuals accounted for 48 per cent of the new PRs and 38 per cent of the new citizens.
I'm not so sure how to read the above statistics. So those that are not economically active are their wives and children? And if this continues, are we supposed to close the door on dependents of foreigners who want to live, and the foreign dependents of Singapore citizens?
The Today story jumps straight into population experts saying OF COURSE, you must give the foreign spouses citizenship.
One other question posed by the G which ST reported was which category of foreigners should be tightened? The maids, construction workers, your foreign spouse….Again, I guess this is to shock Singaporeans into thinking a bit deeper about the us-versus-them divide.
I wonder though if more fundamental questions should be asked, like whether we really need more people (that is, foreigners) to accelerate or maintain economic growth? Maybe, our productivity efforts will bear fruit….don't laugh. Or if the answer is no, would we accept (without complaint or whining) a slower rate of growth in exchange for feeling better about living in our own country (yep, loaded question but that's really what the discomfort is about right?)
BT has a rather strange angling – it was on all the G's plan to expand infrastructure over the next decade to cope with population growth over the years, even though inflow of immigrants has fallen since 2009. So there were stats on roads, rail, housing, medical care etc and how much has been budgeted for them. Is all this new? Or is it just a compilation of past announcements? How does this plan gel with the G's efforts to collect feedback? Is this to meet current demand? I mean, looks like everything's fixed for the next 10 years…
Never mind all that. I hope Singaporeans, especially young Singaporeans, speak up. I say young Singaporeans (those in school, about to leave school, or just starting work) because their life experience has been shaped differently from the rest. Already, they are studying with non-Singaporeans, interacting with them, and even doing National Service with them. Their parents and older folk have been shaped differently and will perhaps veer emotionally towards maintaining the status quo or hark back to a time before S-pass holders, Chinese national hawkers and Indian IT experts.
Anyway, it's time the whole population talked. And I guess I still have to go read that Population report for a fuller picture.
economics, Forbes, income inequality, rankings
Rich list; poor list; good list
In Money, News Reports, Society on July 27, 2012 at 12:05 am
Whenever I see a "rich" list, I feel so, so poor.
My eyes glaze over the names of the usual banking, property types to pick out new names. Who are these fellows? Foreigners, or rather ex-foreigners, and some very Singaporean brand names, like Hotel 81 and Sheng Siong, this time round. Oops! I mean their founders. Interesting that BT and Today went with headlines that said The rich got richer – by 9 per cent. So…that's the income divide fully manifested! ST buried it somewhere in the bowels of the story.
It's great that rich foreigners have decided to become citizens and sink their lot here. Even better to see the Hotel 81 and Sheng Siong bosses get into the list. So we can all aim to be like those Singapore entreprenuers and not depend on "family" money to be in the ranking.
What's also interesting is how the Forbes ranking gave some details of their philantrophic deeds – especially in education. Go buy BT. I suppose this provides some leavening. If you are so rich, there will be people who ask what you are doing with all that money. Churlish I suppose. You make your money, you can decide what to do with it. Except that with all that concern over income inequality, it seems in pretty bad taste to simply hoard it for your heirs.
Sometimes I wonder what would happen if there was a "poor" list instead. I guess that would be political unacceptable and explosive. There will be complaints that the ranking method is wrong (you don't really hear this about a rich list) and a lot of hand wringing and calls to do more for them. I wouldn't feel so so rich reading a poor list. I will just feel so so bad.
I wish there was an annual Philantrophy list. I know that there are various awards given to donors and the good people. But they are varied, scattered and even ad hoc. I want to know how those people who have benefited from being part of this place are giving back, whether in terms of their brain power or money. Will this be too onerous for our rich people? Pressuring them to give? By the way, I don't care if they are doing it for tax purposes. Nor do I care if this starts a race among top donors or foundation founders or scholarship boards. Better, I think, than Lim Chong Yah's formula to cut the wages at the top and give to the bottom. In this case, if you have extra, then give.
Let's have a "good" list.
It would dampen the politics of envy. And make me feel so so much better.
economics, growth, inflation
Money minefield
In Money, News Reports on July 26, 2012 at 1:10 am
Am I supposed to be worried about the economy dipping below 1 per cent growth or happy that core inflation is easing to 2 per cent? That's the conflicting emotion you get when you read more than one newspaper. BT went for the worried angle and ST the happy one.
Actually on Tuesday, we've already read about inflation – that it would be on the high side. No specifics then. Now we get specifics – from 3.5 to 4.5 per cent and now 4 to 4.5 per cent. I remember how my mother complained on Tuesday that the G was telling people what they already knew – that everything is getting more expensive. Then, no mention was made of core inflation, which covers everyday stuff minus cars and housing. In fact, what was reported was the impact of inflation on different income groups. Yup. You guessed it. The poor gets hit harder.
So what is this second bite at the cherry? This time, core inflation is said to be critical. The wordings are that the core inflation forecast hasn't been revised – its between 2.5 per cent to 3 per cent. But it will ease over the next few months to maybe 2 per cent, because oil price is lower and therefore electricity and petrol get cheaper. Yup. Excellent. But hey, when are town councils going to raise S&C charges as the ST reported today that they will do? Won't this bring core inflation – or is it headline inflation – back up? I mean, according to MAS, June's inflation numbers was due to no S&C rebates. Or is S&C charges part of housing cost – which is not part of core inflation….Sigh. Dunno. Confused. Give up.
Anyway, the below 1 per cent figure for growth seems to be a worst case scenario, based on factors like whether there will be a recession in the US, the eurozone implodes and a hard landing in China. MAS seems to have ruled out the last. So I guess we can still expect growth of between 1 and 3 per cent…
You know, I still can't decide if I am going to be better or worse-off
corruption, courts, doctors, lawyers, media, teachers
A moral mess
In News Reports, Society on July 26, 2012 at 12:29 am
What in heaven's name is happening to our doctors, teachers, lawyers and civil servants? Everyday, we're reading about these professionals being accused of or pleading guilty to a whole barrage of crimes: having sex with patients, underaged girls, students in return for doing favours or just for kicks; prescribing illegal stuff; favouring supposed friends; sleeping on the job; being loco etc. And I am not even talking about religious leaders aka known as the City Harvest people who can afford high-priced Senior Counsels.
Okay, I don't care who defends who – and some have yet to be proven guilty. And yes, they make for great reading and you start thinking, hey, maybe this is a sign that, never mind the Woffles Wu puzzle, the rich and famous do NOT get away with doing illegal stuff.
Except that, there seems to be too many of them….Or maybe it's just a coincidence that everything is happening in a clump.
What has happened to the ethical codes that underpin all these professions? What are their leaders doing about imbueing them in the members? I don't think it's enough to say, we caught the bad hats, we weeded them out and you shouldn't tar all of us with the same brush. Some introspection is surely expected.
Of course, there would need to be system changes, especially in the civil service. You've got a foreign service officer accused of fraud and now the NParks guy who bought expensive bikes. And every year, we've got to read reports from the Public Accounts Committee, Accountant-General etc lambasting some agency or other over its sloppy procurement procedures. I believe some suggestions were made to improve this process earlier this year. Has it been done? Is it an improvement over the Finance ministry's explanation about how those Bromption bikes were bought?
With so much de-moral-ising news, I always find the Bouquet column in ST's Forum Page a joy to read. It's short, snappy – and grateful. People remembering to thank others for doing nice things. I wish there were more of them to read to balance the daily diet.
PS. ST named the NUS law professor for his supposed sex-for-grades stunt although he hasn't been charged. I suppose this puts it one up on TNP which first broke the story? Can't be. I guess the stable of newspapers have different standards on naming people….Hmmm
Healthcare, Medifund, Medishield
Enough in Medifund?
In News Reports, Society on July 23, 2012 at 1:02 am
When a policy change kicks in, another must surely follow to keep pace. Now that Medishield changes have been announced with higher premiums and cash upfront before the insurance kicks in, is there enough in Medifund to keep pace?
Health Minister Gan Kim Yong says that the poor who can't afford the cash up front or deductible can turn to Medifund. The question is: How much does Medifund have? What have the pay outs been like? How much has gone into paying for deductibles and how much for other medical bills? I'm sure there have been past reports, but an update is timely given the new circumstances. Also, is Medifund the ONLY recourse? I believe there are others but signing up for them disqualifies you from Medifund aid.
I have always thought a newspaper has three functions: To inform, entertain and educate. In my view, they translate into news, views, reviews and news-you-can-use. I'd like to see more of the last. Interestingly, there was prominent explanation on U-save being applicable to households rather than individuals. A good newspaper's job must be to make our lives easier. In this case, it did. But as that old cliche goes, more can be done
Looking out for Linksters
My nephew, aged 3, is teaching his grandma how to use the iPhone. His tiny fingers fly across the iPad screen too, killing monsters and turning nursery rhymes on and off, low volume, high volume. Brows furrowed, he can spend hours focused on the gadgets. The house is quiet. Strange how in the past, how parents dump their children in front of the television set to keep them out of mischief. Now you achieve the same effect with smaller stuff.
I am not comfortable with his fascination for mobile gadgets. So whenever I am with him, we engage in sword-play, catching, a bout of wrestling, colouring and lego-building. He still doesn't want to look for caterpillars and grasshoppers on the condo grounds and said a definite no to hunting for spiders…Why am I not comfortable? I am not sure. Perhaps, because that was not the way my peers and I grew up.
Which was why I was interested to read the ST report on the Linksters, whose young lives revolve on their mobile gadgets. The survey confirmed what we already know – that they spend most of their time online, connected to friends and prefer to communicate virtually. That they grew up in affluent times and want different things from their parents and grandparents.
Okay. So what? Is this a good thing or bad thing? Something that society has to live with, because they will BE that society soon? Or something to counter now?
The only supposed consequence reported was that employers (those old fuddy duddies) will have a harder time dealing with them when they get out in the workplace. Yesterday's Sunday Times piece by Serene Goh also noted that their views will be formed by the peers, rather than the more steadying influence of the older and wiser. (PS. shouldn't the survey have been reported FIRST, before a commentary run?)
I was also drawn by sociologist Tan Ern Ser's remarks that the "good news" (in quotes) is that the youngsters are still exposed to community projects, internships and part-time jobs. I assume then that the survey is "bad news"?
I think parents badly need some guidance now on the pros and cons of bringing up a Linkster. Time and again, you see reports of studies on the good/bad effects of such connectedness. The general focus, however, has been to shield the youngsters from predators online and bad material. What about the whole online/mobile culture? Will Wikipaedia be the source of all knowledge? Will everything that happens or is said become a question of whether you Like it or not? Will friendship be measured by the number of Facebook friends you have, rather those friends who will offer you a REAL shoulder to cry on?
I consider them pressing questions because parents can switch off the television, but it's harder to keep a mobile phone out of a youngster's hands. Or maybe they shouldn't? We definitely need some pretty expert opinion here.
My nephew knows not to touch MY iPhone – on pain of the cane. I'd rather much prefer he gets bruised and knee scrapes and the house be filled with his hollering – than quiet tapping. Someone please tell me why.
economics, Tiger Beer, Writing
The Tiger of Lion City
In Money, News Reports, Writing on July 21, 2012 at 6:12 am
I declare today's ST page 1 story on the Heineken bid for APB unreadable. For crying out loud, you need the patience of a saint, go over the whole thing five times, and STILL can't make sense of who is fighting over which piece of what stuff. The article chokes you with numbers. You would have thought a graphic on all the parties and how they relate to each other would have clarified matters easily. So thankfully, there was BT, which had a graphic. Odd, since a business paper could roughly expect that its readers would understand the battle lines, but a general paper must expect that most of its readers would not….
Anyway, there I was trying to make sense of why this is such a big deal. A corporate battle is always interesting I suppose, especially among big name playersand with big money. I mean, won't I get to drink Tiger beer still? Then I turn to the Insight pages in ST about the worry pver yet another Singapore icon disappearing into foreign hands. Hmm. Sentimental value versus business considerations? How protective should we be about our treasured icons? If we are too protective, we can't blame other countries from doing the same to our Singapore businessmen who want a piece of something iconic from them. Some of our own already facesuch problems.
What we should be protective about is stuff that is of strategic value to Singapore – do we want PSA in foreign hands?
As Eu Yan Sang's Richard Eu said, its the heritage, not the owner that counts. Raffles hotel is still around never mind its ownership change. While we can't say Tiger Beer is Singapore-owned, we can say it's a Singaporean brand (generalise a bit lah)
Kudos to the Singaporeans who make money from this battle. May Tiger Beer live forever.
AFTERNOTE: I found a graphic in the ST Money pages. Too late. Should have been with the P1 story.
equality, Money, Pre-school
Paying for pre-school
In Money, News Reports, Society on July 20, 2012 at 5:50 am
I thought the most useful article today was in the Opinion page of the ST by the author of Starting Well, which argued for G intervention in the pre-school sector, or rather, a takeover.
It was filled with statistics on how Singapore's pre-school system fared against others (not well) and gave reasons on why this was so. It also referred to how other countries do it. It makes four recomendations to a) raise minimum teacher qualifications b) have more teachers so as to reduce class ratio c) bolster parental awareness of the importance of pre-school education 4) increase state spending.
On the last bit, it made the interesting point about subsidies being given to the demand side, that is, to parents. Rather than supply-side to the pre-school providers – and asked for a balance.
The report is laudable but methinks it lacks some bits – more Singapore numbers beyond the average pay of teachers here and teacher-student ratio.
First, do ALL in the Primary One cohort have a pre-school education, which is not mandatory?
Second, of those who do, how equipped are they? Is there a great difference in standards, say between the PCF trained and the privately trained?
Third, what IS the minimum standard that a kid has to start with in Primary school. Must he already know his alphabet and multiplication tables?
Fourth, is the teacher shortage due to low pay, therefore pushing teachers to take on more lucrative jobs as private tutors?
What is the issue about? I suppose the main thing is the general quality of pre-school education here compared to others. But I figure that for most parents it is a question of equitability. Those who cannot afford the fancier kindergartens will wonder how their kids will fare when they start primary school with their more "expensively-educated" classmates. Worse, they may blame themselves for not giving their kid a good head start. The 10 years of compulsory education starts at Primary One, but it doesn't seem to be that every child is at the same starting line.
Then there is the issue of teaching standards and curriculum. I believe the G has made some changes over the years regarding requirements of the syllabus and teacher qualifications. But the advent of the private sector and the willingness and ability of parents to pay means varying standards – and additional worry about some children being left behind . Parents expect money NOT to play too big a part in pre-school education, after all, education is affordable at the later primary and secondary school. But money DOES play a part , and so early in a child's life, even with G subsidies for them. In fact, I don't understand why the report says that Singapore doesn't have available its spending on pre-school children – surely it keeps track?
Hence, it seems that the G's oft-cited 10 years of schooling should be increased to at least 12. I think that is a far better way to raise the water level, far better than having even more universities and polytechnics which might actually lower the crest of the wave… Or it can take a closer look at the New Zealand model, which is private sector led, but with G help on both demand and supply side.
We've got to bring back that old maxim – That in Singapore, you study hard, you work hard, you can get a good job, raise a family and support your elders. That in Singapore, you don't have to depend on who your parents are, or how much money they have. Meritocracy will see you through.
journalism, Writing
Can die!
In News Reports, Writing on July 20, 2012 at 5:08 am
Dead men don't talk, but according to the LTA, they can plug leaks. Or that's what ST had the LTA saying in its headline on what the two men who died were up when the MRT roof scaffolding fell on them the day before. It's so hilarious, can die!
I wondered too about the P1 story on New canal to help ease Orchard floods. I would have thought the correct word was flooding. If it's a question of fitting the longer word in, then do away TO HELP. So you get New canal to ease Orchard flooding. By the way, I was intrigued to read about "high-profile" floods….A person is high-profile, even an event. But a flood???? It's like its issued a press statement announcing their arrival and plenty of drum banging preceded its coming….
This morning, May 10, my newspapers didn't arrive at my door step. It's not even a press holiday and I don't have my ST, BT, TNP and MYP. Has finally dawned on me that I am officially an ex-journalist and no longer entitled to free newspapers – which I have had ... Continue reading →
First POFMA case: About facts or interpretation of data?
2019: The good, the bad and the ugly
The execution of Pofma
A slight commotion over a motion
Is it because he's a foreigner? (He's not)

redpajama_set_name: RedPajamaCommonCrawl


These oval faceted cubic zirconia stones can easily be mistaken for the real thing. Hand set on sterling silver this bib necklace is a show stopper.
Click the button below to add the Cubic Zirconia Necklace to your wish list.


The chat "Invoice" – Right at the top, in big, adventurous letters. Leave no agnosticism in the apperception of your readers that this is a appeal for money that they charge appear to in adjustment to accumulate your services.
The balance date – That is, the date that you beatific the balance to your customer. This is the date that the acquittal agreement alpha ticking, and if you're ambidextrous with a aggregation of any size, they'll appetite to apperceive this information.


text:
Twitter is bringing a stripped down version to Android, targeting developing markets
By Victoria Ho 2017-09-25 08:53:52 UTC
Twitter is packaging its data-friendly, space-saving Lite mobile web app into a native app version, starting with Android.
The social media firm is testing the Android app only in the Philippines for now, paving the way for a mainstream release down the road, TechCrunch reports.
SEE ALSO: Twitter's crackdown on terrorism appears to be working
Like the mobile web version that was released earlier in April, the Twitter Lite app is made to take up less space on your device (less than 3MB), and demand less resources, so it can load faster on low-end to mid-range smartphones.
More importantly, the app is made to weather patchy data coverage, so it'll have some caching to work offline. It'll also show a preview of images and videos, and will only download media if the user chooses to.
Introducing Twitter Lite on mobile web! 📱
Loads quickly, takes up less space, and is data-friendly. Learn more: https://t.co/Zd825WOdQz pic.twitter.com/l1n0cYJuPc
— Twitter (@Twitter) April 6, 2017
Both the app and web version look fairly identical in terms of UI and function, but the app is likely to help draw more people to Twitter Lite by being listed on Google Play.
It's also more likely to retain user logins, compared with the mobile version, so it'll make the experience smoother.
The Philippines is a smart choice as an early testbed. The country's users are one of the world's most active on social media, and it adds mobile users at a faster rate than many other developing markets.
Twitter Lite comes over two years after Facebook launched its low-data version, Facebook Lite on Android.
By February this year, Facebook Lite already grew its user base to 200 million.
These "light" apps are essential for the companies to grow their user bases in developing markets, as more users experience the web for the first time via mobile handsets. Chances are, many of those handsets are lower-end Android devices — and not pricier iPhones — which is why we don't see developers bringing these to iOS.
WATCH: Celebrities are taking to Twitter to share their reactions to the Mexico earthquake
Topics: big-tech-companies, LITE, Philippines, smartphone, social-media-companies, Tech, Twitter


text:
Group-A Racing Kicks Off Aggressive Testing Program For 2020 Prep
Group-A Racing
Group-A Racing spent the 2019 season running part-time programs for rookies to get their feet wet in the Formula 4 United States Championship Powered by Honda, creating opportunities for young, inexperienced drivers with limited funding. However, the team still managed to score points with the youngsters and lead laps at Road Atlanta.
While most teams take some time off following the final race, Group-A Racing immediately went to its winter home base of MSR Houston to launch off-season testing programs. The season ended on a Sunday and the team was already back on track testing Tuesday morning to get prepared for 2020 season.
Group-A Racing has fielded drivers from the United States, the Caribbean and Europe coming in for the first week of on-track action, which was a very successful start to off-season testing. Group-A Racing scheduled testing days with several more drivers before the new year, and immediately following.
Established driver and Group-A Racing team manager, Jonathan Scarallo, got back behind the wheel to assess new set-ups. Scarallo exited the car with a big grin on his face from the great work the team has done on the car's performance.
"Our lead engineer is literally the best that money can buy and we are so fortunate to have him" commented Scarallo. "You name the classification of cars/series around the world, and he has competed in it and won in it. This past year we have been running a lot of new drivers, teaching them, and trying to stretch their budgets with basically no testing making his work a bit more difficult. With that, he has done a fantastic job using all the information from the manufacturers, formulas etc. to come up with phenomenal setups. I haven't driven a car in 2 years, but it was so easy for me to instantly be setting fast lap times due to how well he has our cars setup, just another confirmation that we have everything that our drivers need to go win races and championships."
With new drivers looking to join the team and current drivers returning, the team purchased a fourth Ligier JS F4 car to expand its operation accordingly. Group-A Racing will continue testing throughout the winter into early spring before doing the team's usual ground-up rebuilds on the cars leading into the first race, ensure that everything is fresh and up to date for the drivers at the start of their championship campaign, leaving no stone unturned. All the cars get the same professional treatment no matter if it's for drivers participating in their first ever race or the 100th race.
Limited testing opportunities are still available. Drivers interested in test and race opportunities with Group-A racing can contact Jonathan Scarallo 631-974-4379 info@GroupARacingTeam.com.
Everett Stack Joins Jensen for 2023 F4 US Championship
January 22, 2023 - Jensen Global Advisors is pleased to announce that Everett Stack has joined the race team for the 2023 season competing in the Formula 4 United States Championship Powered by Honda (F4 U.S.). Stack, who...Read more
Tanner DeFabis Joins the Jay Howard Driver Development F4 U.S. Program
January 23, 2023 – Continuing to add to their multi-program driver lineup, the Jay Howard Driver Development efforts are pleased to welcome Tanner DeFabis to the Indianapolis-based squad. Set to make his debut in the 2023 F4...Read more
Eric Wisniewski, 2022 SpeedTour Formula Development Driver Champion, On The Move
Will Compete in F4 U.S. with Jay Howard Driver Development in 2023 CHARLOTTE (January 9, 2023) – Eric Wisniewski was crowned the inaugural Driver Champion of SpeedTour Formula Development as the series joined Formula 4...Read more
Momentum Motorsports Returns to the F4 United States Championship Powered by Honda with Garrett Dettman
January 11, 2023 – Absent from the series since 2021, Momentum Motorsports will make their return in 2023 with Indiana resident and multi-time Formula Ford winner, Garrett Dettman. Advancing from the Formula Race Promotions...Read more
F4 U.S. Race 1 at Mission Foods Austin SpeedTour
Watch Round 16 of 18 of the 2022 Formula 4 United States Championship powered by Honda season! It's Race 1 of the weekend from Mission Foods Austin SpeedTour at Circuit of The Americas in Austin, Texas. Subscribe to the new...Read more


The hexadecimal #8a9a3d color RGB value is (138, 154, 61). The complement color is #4d3d9a. The CMYK color model (used in color printing) for #8a9a3d is 10% cyan, 0% magenta, 60% yellow and 40% black. The decimal value of this color is 9083453. Closest web safe color is: #999933.
Below, the color conversion values related to the color #8a9a3d are specified in detail.
Below you can see compatible color combinations for #8a9a3d.
Below you can see lighter and darker shades of #8a9a3d.
Below you can see alternatives to #8a9a3d.


text:
Q: Finding the Laurent Series for $e^{1/z}\cos(1/z)$ Finding the Laurent Series for $e^{1/z}\cos(1/z)$.
First, I begin by finding the expansion for $e^{1/z}$. Recall that $$e^{z}=\sum_{j=0}^{\infty}\frac{z^{j}}{j!}, \forall z\in \mathbb{C}$$
Then, I substitute in $1/z$ for $z$ to find the expansion for $e^{1/z}$, giving: $$e^{1/z}=\sum_{j=0}^{\infty}\frac{1}{z^{j}j!}, \forall |z|>0$$
Similarly for $\cos(1/z)$: $$\cos(1/z)=\sum_{j=0}^{\infty}\frac{(-1)^{j}}{z^{2j}(2j)!}, \forall |z|>0$$.
Here, is where I am confused. I know I am supposed to use Cauchy Product to produce an answer that is "1 term," but I am confused as to what to do after using the formula. I find: $$e^{1/z}\cos(1/z)=\sum_{k=0}^{\infty}\sum_{l=0}^{k}\frac{(-1)^{l}}{z^{k+l}(2l)!(k-l)!}, \forall |z|>0$$.
Is this my final answer? Can I simplify this further? Perhaps is there a better way to approach this problem altogether?

A: Actually, start with the Taylor series of $e^z\cos(z)$, utilizing DanielFischer's hint
$$f(1/z)=e^z\cos(z)=e^z\left(\frac{e^{iz}+e^{-iz}}2\right)=\frac12(e^{(1+i)z}+e^{(1-i)z})$$
$$f(1/z)=\frac12\sum_{n=0}^\infty\frac{[(1+i)z]^n+[(1-i)z]^n}{n!}=\frac12\sum_{n=0}^\infty\frac{(1+i)^n+(1-i)^n}{n!}z^n$$
Finally,
$$f(z)=\frac12\sum_{n=0}^\infty\frac{(1+i)^n+(1-i)^n}{n!}z^{-n}$$

redpajama_set_name: RedPajamaStackExchange


Detroit Tigers owner Mike Ilitch talks to reporters about his recent acquisition of the baseball club.
Professional hockey players Luke Richardson and Kelly Hrudey talk to reporters about whether or not fighting should be disallowed in the sport.
Professional hockey players Glen Wesley and Mike Milbury talk to reporters about whether or not fighting should be disallowed in the sport.
Mel Torme singing on set and being interviewed.
Jean Chretien speaking to reporters about Prime Minister Brian Mulrooney.
Former Canadian Prime Minister Brian Mulrooney speaking to reporters about an upcoming vote on a constitutional referendum.
Celebrity couple Heath Ledger and Michelle Williams attend a press conference.
Actress Jennifer Aniston being interviewed during various red carpet events.