While reading Laurent Bussard's thesis, Section 4.5.1, p91 (p119 of the pdf) I wondered about the following paragraph (emphasis mine):

the prover first picks a random symmetric key $k \in_R \{0, 1\}^m$ and uses it to encrypt her private key $x$ according to a publicly known symmetric key encryption method $\mathcal{E} : \{0, 1\}^m \rightarrow \{0, 1\}^m$. This leads to $e = \mathcal{E}_k (x) \in \{0, 1\}^m$. Note that as in every encryption scheme, only the knowledge of both $e$ and $k$ allows to compute the private key $x = \mathcal{D}_k (e)$.


In the $i$-th interaction, the prover releases either $k[i]$ or $e[i]$ ... Note that $k[i]$ (resp. $e[i]$) denotes the $i$-th bit in the binary representation of $k$ (resp. $e$)

It appears to me that only an ideal cipher achieves the required property: wouldn't knowing some bits of $k$ and the complementing bits of $e$ reveal some information on $x$ in any real-world encryption scheme such as AES? (See also property 4.3(b) in the same thesis). Could one estimate how much information of $x$ is leaked upon multiple executions of this protocol (where an ephemeral $k$ is chosen each protocol execution)?

(Note that in section 4.7.3 he actually uses a one-time pad for encryption, which does appear to have the required property).

  • $\begingroup$ Why are "complementing bits" of $e$ relevant? If the leaked information depends on known bit positions of $e$ and $k$ being disjoint you either have an OTP or a very bad block cipher. $\endgroup$ – kodlu Aug 23 '18 at 5:42
  • $\begingroup$ I may have phrased that awkwardly. With complementing bits I mean that for every index $i$ the protocol reveals either $k[i]$ or $e[i]$, so if $k[i]$ is not leaked, than $e[i]$ is leaked. I don't know if this is relevant at all, I just observed this from the protocol description. $\endgroup$ – Sebastian Aug 23 '18 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.