Cryptography using matrices
I thought about this idea as a method of cryptography. I appreciate if someone could advice if it is wrong.
The method applies a SVD (singular value decomposition) method known in the linear algebra.
It still applies the trap-door algorithm in such way that Alice should send the public key to Bob but keeps the private key for herself. Later she will use the private key to open the message received from Bob.
Here is the sketch of the method:
1) Alice constructs a matrix $M$; consists of $m$ rows and $n$ columns, where $m$ and $n$ are large numbers and very close in the number of digits. Say (1000 x 995). The matrix entries are complex numbers.
2) Alice uses SVD to decompose $M$ yields $M=USV^T$, where $S$ is the matrix with complex eigen values.
3) Alice shares the public key which is $U^TS^{-1}$ where $U^T$ is the transpose of $U$ and $S^{-1}$ is the inverse of $S$.
4) Bob constructs his message in the form of a column vector $Q$ with entries of natural numbers, and he performs $[QU^TS^{-1}]^T$ and gets $q^T$. Note that $q$ is reduced vector on a lower dimension space with length, m or n whichever shorter in number of digits. Bob then sends $q$ to Alice.
5) Alice retrieves $Q`$ by using; $Q`=USq$.
Because $m$ and $n$ are large but unequal in the numbers of digits, $U^TS^{-1}$ can not be a square matrix. This will not allow Eve, a spy agent, to invert it and get $US$.
Eve also, can not retrieve neither $U$ nor $S$ by multiplying $U^TS^{-1}$ by its transpose. This because when doing so, she may only get the value modulus of the complex number representing the eigen values of $S$ but she can not get argument (the phase factor).
And because $m$ and $n$ are so large, the omitting of the smaller $m-n$ number of the eigen values will not affect the round approximation $Q`$ to $Q$.
linear-algebra cryptography
asked Nov 18 at 15:46
isaac
163
|
show 1 more comment
I thought about this idea as a method of cryptography. I appreciate if someone could advice if it is wrong.
The method applies a SVD (singular value decomposition) method known in the linear algebra.
It still applies the trap-door algorithm in such way that Alice should send the public key to Bob but keeps the private key for herself. Later she will use the private key to open the message received from Bob.
Here is the sketch of the method:
1) Alice constructs a matrix $M$; consists of $m$ rows and $n$ columns, where $m$ and $n$ are large numbers and very close in the number of digits. Say (1000 x 995). The matrix entries are complex numbers.
2) Alice uses SVD to decompose $M$ yields $M=USV^T$, where $S$ is the matrix with complex eigen values.
3) Alice shares the public key which is $U^TS^{-1}$ where $U^T$ is the transpose of $U$ and $S^{-1}$ is the inverse of $S$.
4) Bob constructs his message in the form of a column vector $Q$ with entries of natural numbers, and he performs $[QU^TS^{-1}]^T$ and gets $q^T$. Note that $q$ is reduced vector on a lower dimension space with length, m or n whichever shorter in number of digits. Bob then sends $q$ to Alice.
5) Alice retrieves $Q`$ by using; $Q`=USq$.
Because $m$ and $n$ are large but unequal in the numbers of digits, $U^TS^{-1}$ can not be a square matrix. This will not allow Eve, a spy agent, to invert it and get $US$.
Eve also, can not retrieve neither $U$ nor $S$ by multiplying $U^TS^{-1}$ by its transpose. This because when doing so, she may only get the value modulus of the complex number representing the eigen values of $S$ but she can not get argument (the phase factor).
And because $m$ and $n$ are so large, the omitting of the smaller $m-n$ number of the eigen values will not affect the round approximation $Q`$ to $Q$.
linear-algebra cryptography
asked Nov 18 at 15:46
isaac
163
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55
|
show 1 more comment
I thought about this idea as a method of cryptography. I appreciate if someone could advice if it is wrong.
The method applies a SVD (singular value decomposition) method known in the linear algebra.
It still applies the trap-door algorithm in such way that Alice should send the public key to Bob but keeps the private key for herself. Later she will use the private key to open the message received from Bob.
Here is the sketch of the method:
1) Alice constructs a matrix $M$; consists of $m$ rows and $n$ columns, where $m$ and $n$ are large numbers and very close in the number of digits. Say (1000 x 995). The matrix entries are complex numbers.
2) Alice uses SVD to decompose $M$ yields $M=USV^T$, where $S$ is the matrix with complex eigen values.
3) Alice shares the public key which is $U^TS^{-1}$ where $U^T$ is the transpose of $U$ and $S^{-1}$ is the inverse of $S$.
4) Bob constructs his message in the form of a column vector $Q$ with entries of natural numbers, and he performs $[QU^TS^{-1}]^T$ and gets $q^T$. Note that $q$ is reduced vector on a lower dimension space with length, m or n whichever shorter in number of digits. Bob then sends $q$ to Alice.
5) Alice retrieves $Q`$ by using; $Q`=USq$.
Because $m$ and $n$ are large but unequal in the numbers of digits, $U^TS^{-1}$ can not be a square matrix. This will not allow Eve, a spy agent, to invert it and get $US$.
Eve also, can not retrieve neither $U$ nor $S$ by multiplying $U^TS^{-1}$ by its transpose. This because when doing so, she may only get the value modulus of the complex number representing the eigen values of $S$ but she can not get argument (the phase factor).
And because $m$ and $n$ are so large, the omitting of the smaller $m-n$ number of the eigen values will not affect the round approximation $Q`$ to $Q$.
linear-algebra cryptography
asked Nov 18 at 15:46
isaac
163
I thought about this idea as a method of cryptography. I appreciate if someone could advice if it is wrong.
The method applies a SVD (singular value decomposition) method known in the linear algebra.
It still applies the trap-door algorithm in such way that Alice should send the public key to Bob but keeps the private key for herself. Later she will use the private key to open the message received from Bob.
Here is the sketch of the method:
1) Alice constructs a matrix $M$; consists of $m$ rows and $n$ columns, where $m$ and $n$ are large numbers and very close in the number of digits. Say (1000 x 995). The matrix entries are complex numbers.
2) Alice uses SVD to decompose $M$ yields $M=USV^T$, where $S$ is the matrix with complex eigen values.
3) Alice shares the public key which is $U^TS^{-1}$ where $U^T$ is the transpose of $U$ and $S^{-1}$ is the inverse of $S$.
4) Bob constructs his message in the form of a column vector $Q$ with entries of natural numbers, and he performs $[QU^TS^{-1}]^T$ and gets $q^T$. Note that $q$ is reduced vector on a lower dimension space with length, m or n whichever shorter in number of digits. Bob then sends $q$ to Alice.
5) Alice retrieves $Q`$ by using; $Q`=USq$.
Because $m$ and $n$ are large but unequal in the numbers of digits, $U^TS^{-1}$ can not be a square matrix. This will not allow Eve, a spy agent, to invert it and get $US$.
Eve also, can not retrieve neither $U$ nor $S$ by multiplying $U^TS^{-1}$ by its transpose. This because when doing so, she may only get the value modulus of the complex number representing the eigen values of $S$ but she can not get argument (the phase factor).
And because $m$ and $n$ are so large, the omitting of the smaller $m-n$ number of the eigen values will not affect the round approximation $Q`$ to $Q$.
linear-algebra cryptography
linear-algebra cryptography
asked Nov 18 at 15:46
isaac
163
asked Nov 18 at 15:46
isaac
163
edited Nov 18 at 18:30
asked Nov 18 at 15:46
isaac
163
asked Nov 18 at 15:46
isaac
163
asked Nov 18 at 15:46
isaac
163
163
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55
|
show 1 more comment
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55
|
show 1 more comment
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003700%2fcryptography-using-matrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003700%2fcryptography-using-matrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
The Wikipedia page for SVD says that $S$ is a non-square diagonal matrix and that $U$ and $V$ are unitary, which would mean that their inverse and conjugate transpose are equal. It also says that $USV^T$ should be $USV^dagger$, where $V^dagger$ is the conjugate transpose. I'm also not sure what you mean when you say that $S$ has complex eigenvalues; $S$ isn't square, so it doesn't have eigenvalues. $S$ also doesn't have one well-defined inverse (its right and left inverses are not the same, because they produce identity matrices of different sizes).
– probably_someone
Nov 18 at 19:09
$S$ is effectively a square matrix since all other extra eigen values along the diagonal=0. Also $S$ is the matrix where the entries are the eigen values and being not having a well defined inverse is in favor of my point that Eve can not invert it.
– isaac
Nov 18 at 19:53
"effectively a square matrix" $neq$ a square matrix, for inversion purposes. You're going to have to at least specify whether $S^{-1}$ corresponds to the left inverse or the right inverse. Along those same lines, if Eve can't invert $S$, then what makes you think that Alice can? Alice needs to invert $S$ to make the public key in the first place.
– probably_someone
Nov 18 at 20:31
Because Eve does not have access on $S^-1$, she has only access to $U^TS^-1$ and she can not retrieve $S^-1$ from it.
– isaac
Nov 18 at 21:53
$S$ is square matrix, or in my words, can be effectively a square matrix after omitting the small-values $m-n$ eigen values that represent the small redundant noise. This is similar to the dimension reduction algorithm.
– isaac
Nov 18 at 21:55