0
$\begingroup$

I am presented with the following problem:

Given a set of matrices $M = \{A^i_{m,n} : 0 < i < 101 \}$ design a procedure to compose all of them into one encrypted matrix $E_{m,n}$ and later decompose (decrypt) it into the initial set. The procedure should be as difficult to break as possible (quantum-resistant preferably). It does not need to be fast, as the message will be sent only once (meaning the encryption process might take hours or days with the current technology). Presumably, there will exist an encryption key $k$, which should be smaller in size than the set of matrices (as small as possible, preferably). No need for dual-key systems, one is enough for this specific problem I have in mind.

One important note: all of the elements in all of the original matrices come from $Z/nZ$ with some given $n$ (therefore they are integers: $x : 0 \leq x < n$), although this fact does not need to be used in the procedure.

Bonus points if the procedure preserves ordering of the matrices (i.e. we have a sequence $S$ instead of a set $M$). Would that be even possible?

$\endgroup$
2
  • $\begingroup$ just as curious question: Are the matrices allowed to have a certain kind of inner structure or do they need to cover all possible matrices? And are they designed in that way that every $E_{m,n}$ has only a single set/sequence of matrices as inverse solution? $\endgroup$
    – J. Doe
    Commented Jan 11, 2023 at 0:02
  • $\begingroup$ @J.Doe : (1) all possible, I cannot predict what set $M$ I'll get; (2) They are not designed in any way. It is the core of my question to come up with a method which would introduce a bijective mapping between $M$ and $E$ under given $k$ $\endgroup$
    – max
    Commented Jan 11, 2023 at 0:14

1 Answer 1

1
$\begingroup$

Given a set of matrices $M = \{A^i_{m,n} : 0 < i < 101 \}$ design a procedure to compose all of them into one encrypted matrix $E_{m,n}$ and later decompose (decrypt) it into the initial set.

The standard way to address this would be to divide this up into a three step process:

  • Convert the sequence of matrices $M$ into a bit string $P$ (in an invertible way)

  • Hand the bit string $P$ to a standard symmetric encryption process (e.g. AES-SIV), keyed by your secret $k$, resulting in a slightly longer bit string $C$

  • Convert the bit string $C$ into the matrix $E_{m,n}$ (in an invertible way)

The decryption method should be obvious.

Yes, $E_{m,n}$ will take up as much space as all the matrices in $M$ (and actually slightly more; standard encryption methods do increase the length by a fixed amount); however any value-preserving method will has that property, so that's not that big of a deal. You might end up making the elements within $E_{m,n}$ elements of $\mathbb{Z}/n^{101}$ (101 rather than 100 to account for the expansion in step 2) - since we're using the elements within $M$ only as transport, that shouldn't be that big of a deal.

And, assuming your encoding method in step 1 preserves the matrix ordering, I get the bonus points as well - I wonder what I can spend them on :-)

$\endgroup$
2
  • $\begingroup$ With 100 matrices and if $m=1000, n=1000$ and all elements are from $mod 257$ I don't really see a way to easily compress it into a bit string which would not be way too long. Besides, anything may be converted into a bitstring and then using AES we get a secure message. But this is not the merit of my questions. I was thinking more of a matrix-convolution, multiplication etc... $\endgroup$
    – max
    Commented Jan 11, 2023 at 1:07
  • $\begingroup$ @max: "I don't really see a way to easily compress it into a bit string which would not be way too long"; is 100-200 Megabytes (depending on how aggressive your compression is) too long? I believe that there are computers with that much memory. And, this approach has the advantage of relying on well studied cryptography, which something involving matrix operations have not been. $\endgroup$
    – poncho
    Commented Jan 11, 2023 at 3:27

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.