[Cryptography] Is "perfect forward secrecy" the biggest fraud of last decade?

[Dominik Pantůček]

On 29.8.2018 04:03, Tom Mitchell wrote:
> On Tue, Aug 28, 2018 at 1:45 PM, Ismail Kizir <ikizir at gmail.com
> <mailto:ikizir at gmail.com>> wrote:
> 
>     IBM warns of instant breaking of encryption by quantum computers:
>     'Move your data today':
> 
>     https://www.zdnet.com/article/ibm-warns-of-instant-breaking-of-encryption-by-quantum-computers-move-your-data-today/
>     <https://www.zdnet.com/article/ibm-warns-of-instant-breaking-of-encryption-by-quantum-computers-move-your-data-today/>
> 
> 
>     I think that the concept of "perfect forward secrecy" used in Signal
>     based applications forced us to rely solely on asymmetric algorithms,
>     which, will reveal all our secrecy in a few years!
>     Am I wrong?
> 
> 
...

> It is a game changer and tomorrow may bring more insight that crushes
> rules of thumb.
> 


I wouldn't rush to such conclusions. The largest number factored on an
actual quantum computer using Shor's algorithm was 21, see [1].

If you turn to adiabatic quantum computation (basically tweaked
annealing), the current record is 56153 being factored [2][3][4].

So if either Shor's algorithm can be physically scaled or specialized
quantum annealing can be used to target specific numbers (it is not as
straightforward as it may sound), it MAY change things eventually.

This shouldn't, of course, stop people from developing and testing
"quantum-resistant" algorithms. But reading IBM's PR article which
"warns" about instant breaking of all encryption and immediately
suggesting IBM's lattice-based solution - it sort of rings a completely
different bell :)


D.


[1] Martín-López, Enrique; Enrique Martín-López; Anthony Laing; Thomas
Lawson; Roberto Alvarez; Xiao-Qi Zhou; Jeremy L. O'Brien (12 October
2012). "Experimental realization of Shor's quantum factoring algorithm
using qubit recycling". Nature Photonics. 6 (11): 773.
arXiv:1111.4147 Freely accessible. Bibcode:2012NaPho...6..773M.
doi:10.1038/nphoton.2012.259.

[2] Nanyang Xu; Jing Zhu; Dawei Lu; Xianyi Zhou; Xinhua Peng; Jiangfeng
Du (30 March 2012). "Quantum Factorization of 143 on a Dipolar-Coupling
Nuclear Magnetic Resonance System". Physical Review Letters. 108 (13):
130501. Bibcode:2012PhRvL.108m0501X. doi:10.1103/PhysRevLett.108.130501.
PMID 22540684.

[3] Zyga, Lisa (28 November 2014). "New largest number factored on a
quantum device is 56,153". Phys.org. Science X Network. Retrieved 4
August 2015.

[4] Nikesh S. Dattani; Nathaniel Bryans (November 2014). "Quantum
factorization of 56153 with only 4 qubits". arXiv:1411.6758 Freely
accessible [quant-ph].