Kvantová hrozba: Která kryptografie zanikne a která přežije? (Nebo: Proč jsou ZK-STARKY pq-bezpečné?) Dříve jsem vysvětloval, jak kvantový počítač funguje: Představte si řešení problémů jako pokus uniknout bludišti. Existuje mnoho možných cest a musíte každou zkontrolovat, dokud nenajdete východ. Takto funguje klasický (nekvantový) počítač. Ale zákony kvantové mechaniky umožňují dělat to lépe. Umožňují systému (spoustě částic) paralelně prozkoumávat *všechny* různé cesty v bludišti. Cesty vedoucí k východu zůstávají životaschopné, zatímco ty, které vedou do slepé uličky, zmizí. Pak vesmír náhodně vybere jednu z životaschopných zbývajících cest (to je část, která se Einsteinovi nelíbila, když říká "Bůh nehraje kostky", ale on to skutečně dělá). Takto QC řeší problémy, které by klasickému počítači trvaly miliony let. Ale existují druhy kryptografických primitiv, které kvantový počítač dokáže rozbít, a takové, které zůstávají bezpečné. Jak je to možné? Ve svém předchozím vysvětlení jsem vynechal zásadní část: Ne všechna bludišta jsou stejná. Jsou tam bludiště, kde slepé cesty mizí a vesmír má jen dobrou cestu vedoucí k východu. Nazývám je "kvantově snadná bludiště", protože když vesmír vzorkuje cestu pro takové bludiště, vždy to bude cesta vedoucí k východu. Snadno dosažitelný konec bludište znamená snadné prolomení. Nicméně v "kvantově těžkých bludištech" zůstávají všechny cesty "živé", ať už vedou do slepé uličky nebo východu. Pro takové bludiště není kvantový počítač lepší než klasický počítač. Když Bůh hodí kostkou a vybere cestu, všechny cesty – dobré i špatné – se stejně pravděpodobně objeví. Kvantový počítač tedy provádí analogii klasického počítače, náhodně kontroluje jednu cestu v bludišti. Teď se asi ptáte: Která bludiště jsou kvantově snadná a která ne? ...