How Quantum Computers Break The Internet… Starting Now

– En este momento, algunos estados nacionales y actores individuales están
interceptando y almacenando muchos datos cifrados como
contraseñas, datos bancarios y números de seguridad social. Pero no pueden abrir estos archivos. Entonces ¿por qué lo hacen? Bueno, porque creen que dentro de los próximos 10 a 20 años tendrán acceso
a una computadora cuántica que podrá romper el cifrado en minutos. Este procedimiento se conoce como Almacenar ahora, Descifrar después o SNDL. Y funciona porque
hoy en día existe información que seguirá siendo valiosa dentro de una década. Cosas como la investigación industrial y
farmacéutica y la inteligencia gubernamental ultrasecreta, y todo el mundo es consciente de esta amenaza. La Administración de Seguridad Nacional dice que, si se construyera una
computadora cuántica lo suficientemente grande, sería capaz de socavar todos los algoritmos de clave pública ampliamente implementados. – Ya sabes, en un plazo de cinco a diez años, la computación cuántica romperá el
cifrado tal como lo conocemos hoy. – Aunque todavía faltan años para que las
computadoras cuánticas sean lo suficientemente poderosas , ya son una amenaza debido
a Store Now Decrypt Later, razón por la cual el Congreso de los EE.

UU. acaba de
aprobar una legislación que obliga a todas las agencias a comenzar la transición ahora mismo a nuevos métodos de criptografía que no pueden ser descompuesto por computadoras cuánticas. Ya sabes, nuestros esquemas de cifrado actuales han tenido un éxito notable y han funcionado de manera efectiva durante más de 40 años. Hasta la década de 1970, si
querías intercambiar información privada con alguien, primero tenías que reunirte en persona y compartir una clave secreta. Esta misma clave se utilizaría para
cifrar y descifrar mensajes. Por eso se le conoce como
algoritmo de clave simétrica. Mientras nadie más tenga
en sus manos la clave, sus mensajes estarán seguros. Pero, ¿qué pasa si quieres enviar información a alguien que nunca has conocido y es demasiado difícil concertar
una reunión en persona? No puedes compartir una clave
a través de un canal no seguro como una línea telefónica o el correo, porque podría ser interceptada. Y esto es lo que en 1977
llevó a tres científicos, Riverst, Shamir y Adelman, a idear un gran
avance en materia de cifrado.

Hoy en día se le conoce por sus siglas RSA y funciona más o menos así. Cada persona tiene dos
números primos realmente grandes, todos ellos propios y que mantienen en secreto. Multiplican estos números para obtener un número aún mayor, que hacen público
para que todos lo vean. Ahora, si quiero enviarle a
alguien un mensaje privado, uso su gran
número público para distorsionar mi mensaje. Y lo confundo de tal
manera que es imposible descifrarlo sin conocer
los dos factores primos que formaron ese número. Este es un sistema de claves asimétricas, ya que se utilizan claves diferentes para cifrar y descifrar el mensaje.

Por lo tanto, es fácil decodificar para mi
destinatario, pero imposible para todos los demás, a menos que puedan factorizar
ese gran número público. Ahora bien, alguien podría intentar
factorizarlo, usando una supercomputadora, en el algoritmo de factorización más conocido, el General Number Field
Sieve, pero la criptografía moderna utiliza números primos que
tienen alrededor de 313 dígitos. Factorizar un producto de
dos primos de este tamaño, incluso con una supercomputadora, llevaría alrededor de 16 millones de años, pero no en una computadora cuántica. Mira, en las computadoras normales, un bit solo puede estar en un estado a la vez,
ya sea cero o uno. Entonces, si tuvieras dos bits, podrían estar en uno de cuatro
estados posibles, 00, 01, 10 u 11. Digamos que cada uno de estos
estados representa un número, 0, 1, 2 o 3. Si queremos hacer un cálculo,
por ejemplo, elevando siete a la potencia de uno de estos números, sólo podemos hacerlo para un estado a la vez, en este caso siete al cuadrado y así obtenemos la respuesta 49.

Las computadoras cuánticas están formadas por qubits que también tienen dos estados, cero o uno. Pero a diferencia de un bit clásico, un qubit no tiene que estar en
un solo estado a la vez. Puede ser una
combinación arbitraria de esos estados, una superposición si se
quiere, de cero y uno. Entonces, si tiene dos qubits,
pueden existir simultáneamente en una superposición de 0, 1, 2 y 3. Ahora, cuando repitamos el mismo cálculo, en realidad realizará el cálculo para todos esos números al mismo tiempo.

Y lo que nos queda es una superposición
de las diferentes respuestas. 1, 7, 49 y 343. Si añadimos otro qubit, duplicamos el número de estados posibles. Entonces, con tres qubits
podemos representar ocho estados y, por lo tanto, realizar ocho
cálculos a la vez. Aumente ese número a solo 20 qubits y ya podrá representar más de un millón de estados diferentes, lo que significa que podrá calcular simultáneamente más de un millón de respuestas diferentes. Con 300 qubits, se pueden
representar más estados que partículas
en el universo observable. Esto suena increíblemente poderoso y lo es, pero hay un gran problema. Todas las respuestas al
cálculo están incluidas en una superposición de estados, pero no se puede simplemente leer
esta superposición.

Cuando realiza una medición,
solo obtiene un valor de la superposición
básicamente al azar, y toda la demás información se pierde. Entonces, para aprovechar el
poder de una computadora cuántica, se necesita una forma inteligente de convertir
una superposición de estados en una que contenga solo
la información que desea. Esta es una tarea increíblemente difícil, razón por la cual, para la mayoría de las aplicaciones, las computadoras cuánticas son inútiles. Hasta ahora, sólo hemos
identificado unos pocos problemas en los que realmente podemos hacer esto,
pero por suerte, estos son precisamente los problemas
que forman la base de casi toda la criptografía de clave pública que
utilizamos hoy en día. En 1994, Peter Shor y
Don Coppersmith descubrieron cómo realizar una transformada cuántica de Fourier. Funciona como una
transformada de Fourier normal, se aplica a alguna señal periódica y devuelve las frecuencias
que están en esa señal. Puede que esto no parezca
particularmente interesante, pero considérelo. Si tenemos una superposición
de estados que es periódica, es decir, los términos de la
superposición están separados por una cantidad regular, podemos aplicar la
transformada cuántica de Fourier y nos quedarán estados que contienen la frecuencia de la señal.

Entonces esto lo podemos medir. La transformada cuántica de Fourier nos permite extraer información de frecuencia de una superposición periódica, y eso será útil. Entonces, ¿cómo
factoriza una computadora cuántica el producto de dos números primos mucho más rápido
que una computadora convencional? Quiero explicar esto repasando primero un ejemplo simple
sin necesidad de computadora cuántica, y luego mostraré cómo una computadora cuántica podría ejecutar este método incluso para un número muy grande
en un corto período de tiempo. Entonces digamos que tenemos un número N, que es el producto
de dos primos, p y q.

Para este ejemplo,
igualemos N a 77. Ahora apuesto a que puedes adivinar los factores primos, pero supongamos por el
momento que no los conocemos, porque con un producto de
primos realmente grandes, no lo sabríamos. t. Ahora quiero utilizar un dato sobre los números que parece mágico. Elija un número g que no
comparta ningún factor con N. Si multiplica g por sí mismo una
y otra vez, eventualmente siempre
alcanzará un múltiplo de N más uno. En otras palabras,
siempre puedes encontrar algún exponente r, tal que g elevado a r,
sea múltiplo de N más uno. Veamos cómo funciona esto. Escoge cualquier número menor que 77. Escogeré el número ocho. Este número no comparte factores con 77. Y si estuvieras haciendo
esto con números primos grandes, también sería extremadamente improbable que elijas un número que comparta factores con N.

Ahora multiplica ocho por sí mismo
una vez, dos veces, tres. multiplicado por cuatro, y así sucesivamente, elevando
ocho a potencias cada vez mayores y luego dividimos cada uno
de estos números entre 77. No estamos realmente interesados
en cuántas veces 77 cabe en el número,
solo el resto, lo que sobra, porque al En algún momento, 77 debería dividir uno de estos números con un resto de exactamente uno. Entonces ocho dividido por 77 es
cero con un resto de 8, 64 dividido por 77 es cero resto 64. 512 dividido por 77 es seis resto 50. Y a medida que continuamos, obtenemos restos de 15, 43, 36, 57, 71. ,
29, y finalmente uno. Ahí lo tenemos,
ocho elevado a 10 es uno más que un múltiplo de 77. Así que hemos encontrado el exponente R
que satisface esta ecuación. Pero, ¿cómo ayuda esto a
encontrar los factores de N? Bueno, reorganizamos la ecuación para llevar uno al lado izquierdo y luego podemos dividirla
en dos términos así. Y ahora, siempre que r sea
par, tenemos un número entero multiplicado por otro entero es
igual a un múltiplo de N.

Esto se parece notablemente
a p multiplicado por q es igual a N. Quiero decir, ya que sabemos que pyq están en el
lado derecho de esta ecuación, también deben estar en el lado izquierdo simplemente multiplicados por algunos
factores adicionales. Entonces, una forma de pensar en lo que hemos hecho es que hemos hecho una suposición errónea
para uno de los factores G y, al encontrar el exponente r, lo hemos convertido en
dos suposiciones mucho mejores que probablemente comparten factores con N. Como r era 10, los dos términos del lado izquierdo son ocho elevado a cinco más uno, 32,769 y ocho elevado a
cinco menos uno, 32,767. Estos dos números probablemente
comparten factores con N. Entonces, ¿cómo los encontramos? Usamos el algoritmo de Euclides. Si quieres encontrar el
máximo común divisor de dos números, digamos 32,769 y 77, divide el número mayor
por el menor y registra el resto. En este caso, 32,769 dividido
por 77 da un resto de 44. Luego desplaza los números una
posición hacia la izquierda y repite. Ahora dividimos 77 entre 44
y obtenemos un resto de 33.

Repetimos el proceso nuevamente. 44 dividido por 33 da un resto de 11 y nuevamente 33 dividido por 11 es
igual a tres resto cero. Cuando el resto es cero, el divisor es el máximo común divisor entre los dos números con los que empezaste. En este caso, es 11, que de hecho es un factor de 77 y 32,769. Podrías hacer el mismo procedimiento con el otro número o simplemente
dividir 77 entre 11 para obtener siete, su otro factor primo. Entonces, para resumir, si quieres
encontrar los factores primos p y q de un número N, primero, haz una mala suposición, g, segundo, descubre cuántas
veces r tienes que multiplicar g por sí mismo para llegar a uno
más que un múltiplo.

de N. En tercer lugar, use ese exponente para calcular dos números nuevos que probablemente
compartan factores con N. Y finalmente use el algoritmo de Euclides para encontrar los factores compartidos
entre esos números y N, lo que debería darle p y q. Ahora bien, no se necesita una computadora cuántica para ejecutar ninguno de estos pasos,
pero en una computadora clásica, este método no sería más
rápido que otros métodos. El proceso clave que
acelera una computadora cuántica es el paso dos, encontrar el
exponente que elevas G2 para que sea igual a uno más que un múltiplo de N. Para ver por qué, volvamos a nuestro ejemplo, donde ocho elevado a 10 es uno más. que un múltiplo de 77. Observe lo que sucede con los restos si seguimos pasando de
ocho elevado a 10, de 8 elevado a 11, de ocho elevado
a 12, y así sucesivamente.

Bueno, obtenemos restos
de 8, 64, 50, 15, 43, 36, 57, 71, 29 y nuevamente uno. Los restos circulan y
seguirán ciclando. Observa cómo el exponente
que arroja un resto de uno es 20, que es 10
más que el primer exponente que arroja un resto de uno. Entonces sabemos que ocho elevado a 30 y ocho elevado a 40, 8
elevado a cualquier potencia divisible por 10 también será uno
más que un múltiplo de 77. También vale la pena señalar que
si eliges cualquier resto, digamos 15, la próxima vez que Si
encuentras el mismo resto, el exponente habrá aumentado en 10. Entonces puedes encontrar el
exponente R que nos lleva a uno más que un múltiplo de n, observando el espaciado de
cualquier resto, no solo uno. Recuerda eso. Aquí estoy trazando los
restos en una escala logarítmica para que pueda ver que son
periódicos con un período de 10.

Si hubiera hecho una suposición diferente, digamos que hubiera elegido G igual a
15 en lugar de ocho, entonces el período sería diferentes y los restos serían diferentes pero siempre
habría un resto de uno. ¿ Por qué es esto? Bueno, ahora que puedes ver que
este es un patrón repetitivo, podemos volver al principio y cualquier número elevado a
la potencia de cero es uno. Entonces ese es en realidad el primer resto. Por lo que también debe aparecer cuando
el ciclo comienza nuevamente. Ahora estamos preparados para utilizar una computadora cuántica para factorizar cualquier producto grande de dos primos. Primero dividimos los
qubits en dos conjuntos. El primer conjunto lo preparamos
en una superposición de cero y uno y dos y tres y cuatro y cinco y seis y
siete y ocho y nueve, hasta 10 elevado
a 1234.

Sí, esta es una superposición enorme, pero si tuviéramos qubits perfectos, solo requeriríamos alrededor de 4.100. El otro conjunto contiene una
cantidad similar de qubits, todos dejados en estado cero por ahora. Ahora hacemos nuestra suposición G, que probablemente no
comparte factores con N. Elevamos G a la potencia
del primer conjunto de qubits y luego dividimos por N y almacenamos el resto en
el segundo conjunto de qubits dejando el primer conjunto. de qubits como era. Ahora tenemos una superposición
de todos los números con los que comenzamos y el
resto de elevar G a la potencia de esos
números divididos por N. Y mediante esta operación, hemos entrelazado nuestros dos conjuntos de qubits, pero no podemos simplemente medir
esto. superposición. Si lo hiciéramos, obtendríamos un
valor aleatorio y no aprenderíamos nada. Pero hay un truco que podemos usar. Si no medimos
toda la superposición, sino sólo la parte restante, obtendremos algún resto aleatorio. Pero este resto no ocurrirá sólo una vez. Ocurrirá varias veces cada vez que aparezca en el ciclo. Imagina que estuviéramos haciendo
esto con el ejemplo anterior donde N es igual a
77 y G es igual a ocho.

Si el resto que medimos fuera, digamos, 15, entonces habría múltiples
términos en nuestra superposición. Debido a que hay múltiples exponentes, puedes elevar G2 que
dé el mismo resto, exponentes 4, 14, 24, 34, etc. Cada uno de ellos está separado por 10, y ese valor es el exponente
que satisface nuestra ecuación. Entonces, de manera más general, después de
medir el resto, nos quedará una
superposición de estados que comparten el mismo resto y todos los exponentes estarán separados por la misma cantidad r. Este es el número que estamos buscando. Como el resto ahora es
el mismo para todos los estados, podemos dejarlo a un lado y ahora tenemos una
superposición periódica. Cada término está separado de
sus vecinos por una cantidad R. Si ahora aplicamos la
transformada cuántica de Fourier a esta superposición de estados y estoy simplificando un poco aquí, nos quedarán estados que
contienen uno sobre R. Así que todo lo que queda por hacer Lo que hacemos ahora es realizar una medición
y encontrar R invirtiéndola, y eso es todo para la parte cuántica. Ahora, siempre que r resulte ser par, podemos usar r para convertir nuestra mala suposición g en dos números que
probablemente compartan factores con N.

Y siempre que estos términos en sí mismos no sean múltiplos de N, podemos usar el algoritmo de Euclides.
para encontrar los factores de N y romper el cifrado. Esto sólo requeriría varios
miles de qubits perfectos, pero los qubits que tenemos
hoy son imperfectos, por lo que necesitamos qubits adicionales para que actúen como información redundante. En 2012, se estimó que se necesitarían
mil millones de qubits físicos para romper el cifrado RSA, pero cinco años después esa cifra se había reducido a 230 millones. Y en 2019, después de más
avances tecnológicos, esa estimación se desplomó a solo
20 millones de qubits físicos.

Entonces, ¿cuántos qubits tenemos hoy? Bueno, si miramos el estado
de las computadoras cuánticas de IBM, no estamos ni cerca de esa cantidad de qubits, pero el progreso parece ser exponencial. Así que ahora es sólo una cuestión de cuándo colisionarán estas dos curvas antes de que se pueda romper todo nuestro
cifrado de clave pública existente. Como sabemos desde hace mucho tiempo que
esta amenaza se avecina, los científicos han estado buscando
nuevas formas de cifrar datos, que puedan resistir ataques tanto de computadoras normales como cuánticas. En 2016, el Instituto Nacional
de Estándares y Tecnología o NIST lanzó un concurso para encontrar nuevos algoritmos de cifrado que no sean vulnerables
a las computadoras cuánticas. Criptógrafos de todo el mundo presentaron 82 propuestas diferentes, que fueron
probadas rigurosamente y algunas no funcionaron. Y luego, el 5 de julio de 2022, NIST seleccionó cuatro de
los algoritmos para formar parte de su
estándar criptográfico poscuántico.

Asique, como trabajan? Bueno, tres de los algoritmos se basan en las matemáticas de los látex. Entonces, hagamos un
ejemplo simple en el plano 2D. Tome dos vectores, r1 y
r2, sumando diferentes combinaciones enteras de estos vectores, digamos tres
por r1 y uno por r2, puede obtener dos puntos diferentes y todos los puntos a los que puede llegar combinando estos dos vectores de diferentes maneras son
lo que se llama celosía. Ahora también te daré el punto C, y tu tarea es decirme
qué combinación de r1 y r2 me llevará al
punto de la red más cercano a c. Es bastante fácil ver
que podemos llegar allí yendo dos veces en la dirección de r2 y dos veces en la dirección negativa de r1. Suficientemente simple. Pero esos vectores, r1 y r2, no son los únicos vectores que pueden
darte esta red.

Tomemos como ejemplo b1 y b2. Estos vectores también
forman la misma red. Y ahora, si te
vuelvo a hacer la misma pregunta, ¿ puedes decirme la
combinación de b1 y b2 que te lleva al
punto de la red más cercano a c? Esto se ha vuelto mucho
más difícil, pero ¿por qué? Cada vez que damos un paso,
intentamos acercarnos en la dirección X o Y,
pero con los vectores b, cada vez que damos un paso
en la dirección correcta con un vector, nos
desanima en la dirección correcta. otra dirección. Y es por eso que
es mucho más difícil trabajar con estos vectores. Al final, nos lleva una combinación de ocho veces b1 y
menos seis veces b2 para llegar al punto de la red más cercano.

Esto es mucho más difícil que antes, pero sigue siendo un
problema relativamente fácil de resolver. Pero si lo extendemos a tres dimensiones, esto ya se vuelve mucho más difícil, especialmente porque
no tienes la colección de todos los puntos de la red. Sólo te dan los
vectores que lo componen. Entonces, cuando encuentre un
punto de red cerca del objetivo, aún debe encontrar todos los
demás puntos de red cercanos para asegurarse de que el suyo sea el más cercano. Tomemos un círculo de
radio r en dos dimensiones. El número de
puntos de la red dentro del círculo es proporcional a r al cuadrado.

Agregue una tercera dimensión
y el número de puntos en la esfera es proporcional a r al cubo. Así que simplemente observe cómo crece el número
de puntos de la red a medida que aumentamos el número de dimensiones. Resolver el problema vectorial más cercano es pan comido para tu
computadora en tres dimensiones. Incluso cien dimensiones
deberían ser manejables. Pero en los esquemas de cifrado futuros propuestos, usaremos alrededor de mil dimensiones. Da un paso en la dirección correcta en una de esas dimensiones
y potencialmente podrías estar dando un paso equivocado en
las otras 999 dimensiones. Ganas algo, pierdes todo lo demás. Con tantas dimensiones, resulta extremadamente difícil
encontrar el punto más cercano incluso para las computadoras más potentes, a menos que conozcas
un buen conjunto de vectores.

Entonces, ¿cómo usamos eso para cifrar datos? Bueno, volvamos a nuestro
ejemplo bidimensional. Cada persona tiene un buen conjunto de vectores que describe una red, pero los mantiene en secreto y solo comparte su red públicamente utilizando un conjunto de vectores
con los que es difícil trabajar. Ahora, si quiero enviarle un mensaje a alguien, elijo un punto en su
red, por ejemplo, digo que este punto corresponde
al número siete. Entonces, si quiero enviar el número
siete, puedo tomar ese punto pero luego agregarle algo de ruido aleatorio. Entonces el mensaje que envío no está precisamente en ese punto sino cerca de él. Ahora, para decodificar el mensaje,
mi destinatario debe determinar qué punto de la red está
más cerca del punto del mensaje. En mil dimensiones, esto será extremadamente difícil de hacer a menos que tengas el buen conjunto de vectores, como lo tiene mi destinatario. Así que es fácil para el destinatario, que tiene los buenos vectores,
pero difícil para todos los demás.

Y hasta donde sabemos,
este problema es extremadamente difícil de resolver tanto para las
computadoras normales como para las cuánticas. Detrás de escena, hay
un ejército de investigadores, matemáticos y criptógrafos, nos aseguraremos de que sus
datos secretos permanezcan en secreto. Estos son algunos de los héroes anónimos que nos mantendrán seguros en el futuro, evitando la vigilancia masiva por parte de los gobiernos, manteniendo protegida la infraestructura crítica y permitiéndonos vivir
como si las computadoras cuánticas nunca se hubieran inventado. (zumbido digital) Algo que me fascina es poder ver hacia dónde se dirige el mundo.

Y ahora mismo está claro
que las computadoras cuánticas y los chatbots de IA
desempeñarán papeles cada vez más importantes en nuestras vidas en las próximas décadas. Incluso si no sabemos exactamente
cómo se implementarán, creo que es importante
aprender cómo funcionan ahora y puedes hacerlo con el
patrocinador de este video, Brilliant.

Brilliant tiene un curso increíble sobre algoritmos cuánticos. Este fue desarrollado conjuntamente
con Microsoft y Alphabet X. Me encanta que puedas simular
puertas cuánticas y escribir y ejecutar algoritmos cuánticos reales
directamente en la lección. No es necesario configurar su propio
entorno de desarrollo. Y si desea
profundizar en la criptografía, crear y descifrar códigos es
realmente una cuestión de estadísticas. Las sólidas habilidades de razonamiento estadístico nos ayudan a encontrar patrones en los datos y darles sentido, lo cual es crucial para dominar casi cualquier tema de matemáticas e informática.

El curso de Brilliant sobre análisis de datos le ayudará a avanzar rápidamente. Utiliza situaciones cotidianas, como modelos de negocio, para
ilustrar conceptos clave en estadística y es interactivo, por lo que puedes ponerte manos a la obra
con visualizaciones de datos y desarrollar una intuición real
para interpretarlas. Usted sabe que lo que
distingue a Brilliant es que saben cómo
dividir los fundamentos en sus componentes básicos, ya sea que esté aprendiendo
matemáticas, ciencias de la computación o análisis de datos, las miles de
lecciones interactivas breves de Brilliant lo ayudan a dominar conceptos clave y construir. a temas más avanzados. Puedes probar todo lo que
Brilliant tiene para ofrecer de forma gratuita durante 30 días completos. Simplemente vaya a shiny.org/veritasium. Pondré ese enlace
en la descripción.

Y para los espectadores de este
vídeo, Brilliant ofrece un 20 % de descuento en su suscripción premium anual a las primeras 200 personas que se registren. Así que quiero agradecer a Brilliant
por patrocinar este video y quiero agradecerles a ustedes por verlo..

As found on YouTube