Score:0

What is the best method to compose a set of matrices into one and then unambiguously decrypt it?

dm flag
max

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?

J. Doe avatar
at flag
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?
max avatar
dm flag
max
@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$
Score:1
my flag

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 :-)

max avatar
dm flag
max
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...
poncho avatar
my flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.