Timeline for Public key cryptography based on non-invertible matrices?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2022 at 13:27 | history | edited | Joseph Van Name | CC BY-SA 4.0 |
deleted 855 characters in body
|
| Mar 31, 2022 at 12:10 | comment | added | David E Speyer | An addition to what Joseph Van Name wrote, no reason to go all the way to Jordan form. Just use find bases for $\text{Ker}(M^n)$ and $\text{Im}(M^n)$. These will be complementary, so we can use them to block diagonalize $M$ as $\left[ \begin{smallmatrix} U&0 \\ 0&N \end{smallmatrix} \right]$ with $U$ invertible and $N$ nilpotent. | |
| Mar 31, 2022 at 11:40 | comment | added | Joseph Van Name | The discrete logarithm for singular matrices is not harder than the discrete logarithm for invertible matrices. If $M_{0}$ is a singular $n\times n$-matrix, then to solve $M_{0}^{X}=A$, one first puts $M_{0}$ into Jordan normal form. One can then test the cases when $X\leq n$ one by one, but if $X\geq n$, then all the Jordan blocks in $M_{0}^{X}$ with eigenvalue $0$ will become zero, so the problem for $X\geq n$ then reduces to the problem about solving the discrete logarithm for invertible matrices. | |
| Mar 31, 2022 at 11:31 | history | edited | Joseph Van Name | CC BY-SA 4.0 |
added 53 characters in body
|
| Mar 31, 2022 at 7:20 | comment | added | joro | Also, do you break the discrete logarithm for singular matrices? Can you find X such that M_0^X=A with M_0 singular? In the exchange you can fix one of the keys to be of your choice. | |
| Mar 31, 2022 at 4:52 | comment | added | joro | What do you mean by " An adversary will be able to recover MAMBy if the adversary has access to a pair like (MB,z)"? The public information is only 5 matrices (M0,P_A,P_B,S_A,S_B)? | |
| Mar 31, 2022 at 3:54 | comment | added | joro | Thanks. How do you explain the experimental observation that there are many solutions to the construction, but only few give the shared secret? | |
| Mar 31, 2022 at 3:18 | history | answered | Joseph Van Name | CC BY-SA 4.0 |