I will try to define easily the cryptographic system of this paper. The author designs a communication game for $N$ players. The private information of every player is denoted as $t_i\in T_i$ and represents the type of player $i$. The encryption system that the players use to communicate is based in the following reporting correspondences.

$\textbf{Reporting correspondences:}$ Let $\mathcal{R}_i$ be a non-empty, finite set and define the reporting correspondence $R_i : T_i\to 2^{\mathcal{R}_i}-\{\emptyset\}$ to be a mapping from player $i$’s type space to the collection of subsets of $\mathcal{R}_i$. An element $r\in\mathcal{R}_i$ is called a type-dependent message and $R_i(t_i)$ is the set of type-dependent messages available to type $t_i$ of player $i$. Type-dependent messages certify a player’s statement about his type. For example, if $S\in T_i$ is the set of types of player $i$ who can send the message $r\in R_i$, then $r$ certifies a statement of the type “my type is in $S$”. The set $S$ is therefore called a certifiable event.

$\textbf{Certifiability Configurations:}$ Let $E_i\subseteq 2^{T_i}-\{\emptyset\}$ be a set of subsets of $T_i$ that is closed under intersection. A certifiability configuration is an $N$-tuple of particular reporting correspondences $C_i:T_i\to E_i$ for every $i = 1, ..., N$, with $$C_i(t_i)=\{e_i\in E_i|t_i\in e_i\},\quad\text{$\forall t_i\in T_i$} $$

These reporting correspondences have two very useful properties. First, each message is identical to the event that it certifies. Second, any event that is certifiable by a combination of messages in $C_i(t_i)$ is also included in the set.

Let $R=(R_i)_{i\in I}$ be an arbitrary profile of reporting correspondences, and for every player $i\in I$, let $E_i^R$ denote the smallest set that contains $\{R^{-1}(r_i)|r_i\in \mathcal{R}_i\}$ andd is closed under intersection. $E_i^R$ is the set of all events that player $i$ can certify with $R_i$. The profile $R$ can be uniquely associated with a certifiability configuration $C_R=(C_i^R)_{i\in I}$, where $$C_i^R(t_i)=\{e_i\in E_i^R|t_i\in e_i\}$$

The certifiability configuration $C_i^R$ of $R$ expresses the certifiable information explicitly as events in a player’s type space.

$\textbf{Encryption:}$ Let $C=(C_i)_{i\in I}$ be a certifiability configuration. If verifiable information is encrypted, for every $i\in I$, every certifiable event $e_i\in E_i$ is encoded using a cryptographic algorithm, called a cipher. A cipher is a mapping $ρ_i: E_i × Y_i → X_i$ that has as inputs the private information $e_i$ and a piece of additional information $y_i\in Y_i$, called the key, and produces as output a code $x_i\in X_i$. It is assumed that the set of keys $Y_i$ is sufficiently large, i.e. $|Y_i| ≥ |E_i|$, and that for each $y_i\in Y_i$ the mapping $ρ(\cdot, y_i)$ is bijective, so that every pair $(x_i, y_i)$ is associated with exactly one certifiable event $e_i$. When a player’s information is encrypted, his type-dependent messages are pairs consisting of a piece of code and a key. At the time when players learn their types, nature chooses publicly a cipher $ρ_i$ for player $i\in I$ and a private key $y_i$ uniformly from the set $Y_i$. Player $i$’s reporting correspondence is then given by

$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=ρ_i(e_i, y_i), e_i\in C_i(t_i)\}$$

One natural interpretation of messages in $R_i$ is as pieces of encrypted evidence regarding player $i$’s type, provided by a trusted third party which uses a publicly known cipher and a private key to encrypt the information. Note that if $C=C^R$, then the profiles $R(\cdot)=(R_i(\cdot))_{i\in I}$ and $\hat{R}(\cdot,y)=(\hat{R}_i(\cdot,y_i))_{i\in I}$ have a common certifiability configuration for every combination of keys $y\in(Y_i)_{i\in I}$

Let $E^R=(E_i^R)_{i\in I}$ be the profile of sets of events that are certifiable with $R$. The set $E_i^R$ is finite, so that all its elements may be labeled in an arbitrary order with an index from $1$ to some positive integer $n_i$. Each certifiable event can then be associated with its index, i.e., a number in the set $\{1,...,n_i\}$. I will write $z_i(e_i)$ to refer to the number representing the event $e_i$ and, by a slight abuse of notation, I will write $e_i(z_i)$ to refer to the event whose index is equal to $z_i$.

The following lemma is needed

$\textbf{Lemma:}$ If $z_i$ is a random variable with support on $\{1,...,n_i\}$ and $y_i$ is uniformly distributed over $\{1,...,n_i\}$ independent of $z_i$, then the random variable $x_i$ defined by $x_i=z_i−y_i(mod{n}_i)$ is also uniformly distributed over $\{1,...,n_i\}$.

Here, $z_i$ represents a certifiable event, $y_i$ represents a key, and $x_i$ is the code generated by the cipher $ρ_i(e_i,y_i)=z_i(e_i)−y_i(mod{n}_i)$. Now, suppose player $i$’s private information is encrypted and his reporting correspondence is

$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=z_i(e_i)−y_i(mod{n}_i), e_i\in C_i(t_i)\}$$

so that player $i$ can send a pair $(x_i,y_i)$ if the event $e_i$ represented by $z_i=x_i+y_i(mod{n}i)$ is in $C_i^R(t_i)$. The certifiability configuration generated in this way is identical to the certifiability configuration of $R$: if only types of player $i$ who can certify $e_i$ with $R_i$ can send a pair $(x_i, y_i)$ that satisfies $z_i=x_i+y_i(mod{n}_i)$, then sending such a pair is the same as certifying $e_i$. By Lemma $1$, both $x_i$ and $y_i$ are uniformly distributed over $\{1,...,n_i\}$, and thus, individually, $x_i$ and $y_i$ contain no information about $e_i$.

$\textbf{Question:}$ If we assume that in the case of the above mathematical structure the cipher that is defined as bijective where every pair $(x_i,y_i)$ refers to a linear equation such that $h(x)=ax+b$, $b=e_i$. If two players know $(x_i,y_i)$ the can combine them and take what it misses to them so as $x_i+y_i(nod{n}_i)=z_i(e_i)\quad\text{or $e_i(z_i)$}$. Hence in case we take for $h$ a polynomial of degree $t<2N$ such that

$$h(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0,\quad\text{where $a_0=e_i(z_i)$}$$

what is the equivalent representation of $\rho_i$, where know they are needed $t+1$ pairs to calculate $h(x)$ with constant term $e_i(z_i)$ (which in essence means that $t+1$ pair $(x_i,y_i)$ are associated with only one $e_i$ (bijective))?

In other words the question changes in the equivalent one that says: "Could anybody help in a simple polynomial representation of the cipher $\rho_i$"?

$\textbf{Hint:}$ With a slight abuse of notation I think the author uses $\{1,...,n_i\}$ instead of $\{0,1,...,n_i-1\}$.

  • $\begingroup$ @kelalaka this is one cryptosystem that I think it suits in my previous question fully. So, I write this here... $\endgroup$
    – Nav89
    Jan 14, 2022 at 17:51
  • $\begingroup$ P.s. I know that all these questions are hard to be answered but whoever answers one or some of them, I will vote up. I just want answers. No problem if someone could help in answering just one of them. I would appreciate any help! Thank you in advance! $\endgroup$
    – Nav89
    Jan 14, 2022 at 17:52
  • $\begingroup$ i think I must change my questions from many to one $\endgroup$
    – Nav89
    Jan 14, 2022 at 19:25
  • $\begingroup$ Wll it seems to me that you wrote the whole model to get an answer for this question math.stackexchange.com/questions/4355406/… right? $\endgroup$ Jan 15, 2022 at 0:00
  • 1
    $\begingroup$ Anyway...the reporting correspondences have always this formulation? $$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=z_i(e_i)-y_i(mod{n}_i), e_i\in C_i(t_i)\}$$ where you obtain the information that you want by just adding the code and the key? Is this a universal scheme? $z_i(e_i)=x_i+y_i(mod{n}_i)$ $\endgroup$
    – Nav89
    Jan 15, 2022 at 9:00

1 Answer 1


Well just a thought...in case the cipher takes more valeus as keys or codes doesnt this mean that you arw working in a scheme where the BGW protocols are applied? Namely with one key and one code it means that you have a lienar mapping for the cihper $\rho_i$ however when you have more points then you work with polynomials. If this is the case you can hust generalize the scheme working for polynomial ciphers and then this may preserve the properties that you want and this is the new mechanism.

P.s. A generalization of BGW Protocol proof if any could help you with the maths and the definitions...

I can tag some people who are awae with such schemes, but change if you want the question like if the BGW protocol could be applied somehow in this scheme...for the many codes and keys that will be nothing more or less than pairs of the random polynomial cipher $\rho_i$ that will be given to the players so as none could learn $e_i$ by her own but they must further make some calculations. Furthermore, if a player leanrs $e_i$ in fact he does not lear $t_i$, becasue as you see $t_i\in e_i$, which means that it is informative enough but does not give presicely $t_i$ maybe it contains some noise or something like that.

  • $\begingroup$ good thought but do we know that for every polynomial of degree $k$ for instance we have $k$ pairs $(x_i,y_i)$ that uniquely determine the polynomial $f$ with constant term the information $e_i$? Because if this is the case, the bijective assumption about $\rho_i$ remains $\endgroup$
    – Nav89
    Jan 15, 2022 at 12:24
  • $\begingroup$ after your comment I think that this is the exact point. I will redefine my question now $\endgroup$
    – Nav89
    Jan 15, 2022 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.