-2
$\begingroup$

Problem Definition:
Alice wants to send a matrix $MR_A$ which encrypts its original private matrix $M_A$ ($M\times N$ size, all elements in $M_A$ is in {0,1,2,3,4,5}) to Bob without letting Bob knows any information about $M_A$.
Security Definition:
Alice and Bob communicate via a secure channel(no need to consider the other attacker, and no need to consider secrete recovery since this protocol is just one of the steps of another protocol which intends to securely compute data based on A and B). A and B are semi-honest.

A proposed secure protocol like this:

  1. Alice generates a one-time-use random matrix $R_A$ from the uniform continues distribution $U(a,b)$, where $a$ and $b$ is the minimum and maximum values in $M_A$., $R_A$ is used as the secret key.
  2. Then Alice add $M_A$ to $R_A$ to obtain $MR_A\quad \operatorname{Enc}(M_A) = M_A + R_A$,
  3. She sends $MR_A$ to Bob

My question:

  1. Is this protocol satisfy the one-time-pad encryption or secure?
  2. Regarding zero-knowledge, in the proposed protocol a, b defined as the minimum and maximum values of $M_A$, then the attacker will know the minimum and maximum values of $M_A$, is that violate zero-knowledge? How should I define the value of a and b in U(a, b) to generate $R_A$
  3. Actually, is the proposed protocol more like a random mask $M_A$ by $R_A$? I do not clearly know the difference between them.

Followings are my understanding of my question.

From the textbook, I know that the one-time-pad encryption is defined in the bitstream( the plaintext, key, ciphertext are transformed in the bit format) I also know that the secret key should be truly random and used only once.

Could you please help me to figure it out or discuss it with me?

Improve this question
$\endgroup$
  • $\begingroup$ From what set are the entries of MA? Which addition operation is used? $\endgroup$ – SEJPM♦ Sep 16 '20 at 16:46
  • $\begingroup$ In the first paragraph, I can't see how "him" could refer to Bob: send $M_A$ to Bob is making all information about $M_A$ known to Bob, isn't it? Also, in cryptography, we use reals with extreme caution: it's simply impossible to transfer an arbitrary real from one point to another over SSL, for most reals requires an infinite amount of information bits to be exactly represented. That use of reals (without quantified precision requirement) makes the question unorthodox, and the goal even less clear. $\endgroup$ – fgrieu♦ Sep 18 '20 at 10:46
  • $\begingroup$ Let me clarify. Bob will receive a matrix sent by Alice, this matrix should be an encrypted version of the true matrix(M_A) generated from Alice since the M_A is Alice's private data should be kept secret. For SSL used in the proposed protocol can be neglected. We only consider with the received encrypted version of M_A, bob knows nothing about M_A. @fgrieu Besides, I do not clearly know your meaning of impossible to transfer arbitrary real via SSL. For precision, the protocol is supposed to be no information lost when recovering M_A from the ciphertext given the decrypt key. $\endgroup$ – Amor Sep 19 '20 at 11:29
  • $\begingroup$ For any bit string of $n$ bits $b_i$, the real $x=\sum (1+b_i)\,4^{-b_i}$ reversibly encode the whole bitstring and its length, thus there is no limit to the number of bits necessary to encode some reals, thus there mathematically exists reals which storage or transmission by computer means is impossible. That's why computers never use reals (only approximations), and crypto does not deal with encryption of reals. $\endgroup$ – fgrieu♦ Sep 19 '20 at 12:04
  • $\begingroup$ Homomorphic encryption can be used to encrypt real numbers, the newly proposed Microsoft SEAL have many example to encrpyt matrix no matter integer or float, besides we can change the irrational number to the float. $\endgroup$ – Amor Sep 19 '20 at 12:32
0
$\begingroup$

Should the U(a,b) be continuous uniform distribution or discrete over the value space of MA?

Given that the input numbers are actually irrational non-uniformly distributed numbers, a continuous distribution would is necessary. As an example for this assume you have the entries $1,2,\sqrt 5$ in your matrix and if you'd use only these to mask then you could clearly tell which value was not encrypted. For example when you see $1+\sqrt 5$ as a ciphertext you know that $2$ could not have been encrypted which violates perfect secrecy.

Actually, is the proposed protocol more like a random mask $M_A$ by $R_A$?

There is no practical difference between "Masking" and "One-Time-Pad like encryption". The only theoretical difference I see in usage is that the former is usually used when the masked value is somehow processsed further (e.g. in blind signatures).

Is this protocol satisfy the one-time-pad encryption or secure?

Well, it doesn't specify how $R_A$ reaches B for decryption, but let's assume that it somehow confidentially does. As it stands the scheme does not achieve perfect secrecy. This is because if the largest element in $M_A$ is 10 and you see a ciphertext of 20 you know that it was constructed as $10+10$ or even weaker if you see a ciphertext larger than $12$ you know that the encrypted value could not have been smaller than 2 which violates the fact that you cannot learn anything about the underlying plaintext for perfectly secret encryption. This is why you need a wrap-around into the plaintext space (i.e. $10+1$ yielding e.g. 2) and a continuous distribution. Also note that using the actual maximum of the elements of $M_A$ for the above is not enough, you need to use the theoretically possible maximum as to not leak that e.g. the theoretical maximum is not actually reached.

However, I have an alternative scheme suggestion (which is different from previous versions of this question and saves you from worrying about ranges). You simply take memory representation of your matrix $M_A$ as a list / vector / array of bytes. Then you generate a container of uniformly random distributed bytes of the same length using your favourite cryptographically secure pseudo-random number generator. Then you XOR the memory representations bit-by-bit. The second container is effectively your $R_A$ now.

How about defining $a, b$ as samples from another uniform distribution $U(c,d)$, where $d > c > 0$

This would work if $0 < c \leq a \leq b\leq d$ holds as long as all addition results don't leave the interval $[c;d]$, e.g. using wrap-around so that everything above $d$ gets added on top of $c$ (with appropriate reversal during decryption). The idea here is that it suffices if the space of the randomness is larger than the plaintext space.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your help! Could you please give me some detailed explanation for the difference between "Masking" and "One-Time-Pad like encryption"? What is the definition of the range and wrap around at the edges in the sentence: if you generate your floats randomly continuously in the range and wrap around at the edges? (Do you mean the range of the M_A? Actually, I just wonder should I define the a and b of U(a,b) within the minimum and maximum values in 𝑀_A, How about defining a, b as samples from another uniform distribution U(c,d), where d > c > 0. $\endgroup$ – Amor Sep 17 '20 at 1:13
  • $\begingroup$ And for your proposed alternative scheme suggestion, the combination of 15 integers should be 15! combination, not very clear defining a lookup-table for each of the 15 combinations, and what the relationship between encoding them as 4-bit unsigned integers (i.e. packing two into one byte) and generate a uniformly random bit sequence for the encoded matrix? $\endgroup$ – Amor Sep 17 '20 at 1:20
  • $\begingroup$ @Amor I tried to clarify my answer, is there still something unclear? $\endgroup$ – SEJPM♦ Sep 17 '20 at 8:13
  • $\begingroup$ 1.for example, e.g. 2+4.3=2.3 to stay in the interval [1;5], it seems that all cipher numbers stay in the same range as the plaintext, with the ciphertext, the attacker will know the range of the plaintext. I just wonder whether it is zero-knowledge. $\endgroup$ – Amor Sep 18 '20 at 2:01
  • $\begingroup$ 2. Why we should always keep the addition result MR_A falls into the plaintext range(M_A), so could you please explain, the difference between M_A + R_Aand (M_A + R_A - a) % (a - b) ( % denotes mod operation), given M_A is in [a, b](actually the range of the former just falls into [2a, 2b]), besides, could you explain that the reason why This would work if 0<𝑐≤𝑎≤𝑏≤𝑑 holds as long as all addition results don't leave the interval [𝑐;𝑑]. $\endgroup$ – Amor Sep 18 '20 at 2:01

Your Answer

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

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