Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lattice-based zero-knowledge proofs of knowledge

Ramiro Pinilla

Published Sep 29, 2023• 0 citations
Publisher

Abstract

(English) The main goal of this dissertation is to develop new lattice-based cryptographic schemes. Most of the cryptographic protocols that each and every one of us use on a daily basis are only secure under the assumption that two mathematical problems, namely the discrete logarithm on elliptic curves and the factorization of products of two primes, are computationally hard. That is believed to be true for classical computers, but quantum computers would be able to solve these problems much more efficiently, demolishing the foundations of plenty of cryptographic constructions. This reveals the importance of post-quantum alternatives, cryptographic schemes whose security relies on different problems intractable for both classical and quantum computers. The most promising family of problems widely believed to be hard for quantum computers are lattice-based problems. We increase the supply of lattice-based tools providing new Zero-Knowledge Proofs of Knowledge for the Ring Learning With Errors (RLWE) problem, perhaps the most popular lattice-based problem. Zero-knowledge proofs are protocols between a prover and a verifier where the prover convinces the verifier of the validity of certain statements without revealing any additional relevant information. Our proofs extend the literature of Stern-based proofs, following the techniques presented by Jacques Stern in 1994. His original idea involved a code-based problem, but it has been reiteratedly improved and generalized to be used with lattices. We illustrate our proposal defining a variant of the commitment scheme, a cryptographic primitive that allows us to ensure some message was already determined at some point without revealing it until a future time, defined by Benhamouda et al. in ESORICS 2015, and proving in zero-knowledge the knowledge of a valid opening. Most importantly we also show how to prove that the message committed in one commitment is a linear combination, with some public coefficients, of the committed messages from two other commitments, again without revealing any further information about the messages. Finally, we also present a zero-knowledge proof analogous to the previous one but for multiplicative relations, something much more involved that allows us to prove any arithmetic circuit. We give first an interactive version of these proofs and then show how to construct a non-interactive one. We diligently prove that both the commitment and the companion Zero-Knowledge Proofs of Knowledge are secure under the assumption of the hardness of the underlying lattice problems. Furthermore, we specifically develop such proofs so that the arising conditions can be directly used to compute parameters that satisfy them. This way we provide a general method to instantiate our commitment and proofs with any desired security level. Thanks to this practical approach we have been able to implement all the proposed schemes and benchmark the prototype im-plementation with actually secure parameters, which allows us to obtain meaningful results and compare its performance with the existing alternatives. Moreover, provided that multiplication of polynomials in the quotient ring ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, with 𝑝 prime and 𝑛 a power of two, is the most basic operation when working with ideal lattices we comprehensively study what are the necessary and sufficient conditions needed for applying (a generalized version of) the Fast Fourier Transform (FFT) to obtain an efficient multiplication algorithm in quotient rings as ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩ (where we consider any positive integer 𝑚 and generalize the quotient), as we think it is of independent interest. We believe such a theoretical analysis is fundamental to be able to determine when a given generalization can also be applied to design an efficient multiplication algorithm when the FFT is not defined for the ring we are considering. That is the case of the rings used for the commitment and proofs described before, where only a partial FFT is available. (Español) El objetivo principal de esta tesis es obtener nuevos esquemas criptográficos basados en retículos. La mayoría de los protocolos criptográficos que usamos a diario son únicamente seguros bajo la hipótesis de que el problema del logaritmo discreto en curvas elípticas y la factorización de productos de dos primos son computacionalmente difíciles. Se cree que esto es cierto para los ordenadores clásicos, pero los ordenadores cuánticos podrían resolver estos problemas de forma mucho más eficiente, acabando con las bases sobre las que se fundamenta una multitud de construcciones criptográficas. Esto evidencia la importancia de las alternativas poscuánticas, cuya seguridad se basa en problemas diferentes que sean inasumibles tanto para los ordenadores clásicos como los cuánticos. Los problemas de retículos son los candidatos más prometedores, puesto que se considera que son problemas difíciles para los ordenadores cuánticos. Presentamos nuevas herramientas basadas en retículos con unas Pruebas de Conocimiento Nulo para el problema Ring Learning With Errors (RLWE), seguramente el problema de retículos más popular. Las pruebas de Conocimiento Nulo son protocolos entre un probador y un verificador en los que el primero convence al segundo de la validez de una proposición, sin revelar ninguna información adicional relevante. Nuestras pruebas se basan en el protocolo de Stern, siguiendo sus técnicas presentadas en 1994. Su idea original involucraba un problema de códigos, pero se ha mejorado y generalizado reiteradamente para poder aplicarse a retículos. Ilustramos nuestra propuesta definiendo una variante del esquema de compromiso, una primitiva criptográfica que nos permite asegurar que un mensaje fue determinado en cierto momento sin revelarlo hasta pasado un tiempo, definido por Benhamouda et al. en ESORICS 2015, y probando que conocemos una apertura válida. Además mostramos cómo probar que el mensaje comprometido es una combinación lineal, con coeficientes públicos, de los mensajes comprometidos en otros dos compromisos. Finalmente también presentamos una prueba de Conocimiento Nulo análoga a la anterior pero para relaciones multiplicativas, algo mucho más laborioso que nos permite realizar circuitos aritméticos. Todo esto sin revelar ninguna información adicional sobre los mensajes. Mostramos tanto una versión interactiva como una no interactiva. Probamos que tanto el compromiso como las pruebas de Conocimiento Nulo que le acompañan son seguras bajo la hipótesis de que el problema de retículos subyacente sea difícil. Además planteamos estas pruebas específicamente con el objetivo de que las condiciones que surjan puedan ser utilizadas directamente para calcular los parámetros que las satisfagan. De esta forma proporcionamos un método genérico para instanciar nuestro compromiso y pruebas con cualquier nivel de seguridad. Gracias a este enfoque práctico hemos podido implementar todos los esquemas propuestos y evaluar el rendimiento con parámetros seguros, lo que nos permite obtener resultados relevantes que poder comparar con las alternativas existentes. Por otra parte, dado que la multiplicación de polinomios en el anillo cociente ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, con 𝑝 primo y 𝑛 una potencia de 2, es la operación más utilizada al trabajar con retículos ideales, estudiamos de forma exhaustiva cuáles son las condiciones suficientes y necesarias para aplicar (una versión generalizada de) la Transformada Rápida de Fourier (FFT, por sus siglas en inglés) para obtener algoritmos de multiplicación eficientes en anillos cociente ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩, (considerando cualquier 𝑚 positiva y generalizando el cociente), de interés por sí mismo. Creemos que este análisis teórico es fundamental para determinar cuándo puede diseñarse un algoritmo eficiente de multiplicación si la FFT no está definida para el anillo considerado. Es el caso de los anillos que utilizamos en el compromiso y las pruebas descritas anteriormente, donde solo es posible calcular una FFT parcial.

DOI
10.5821/dissertation-2117-396976

Related papers

Zero-knowledge proof systems for lattice-based cryptography

Nguyen, Ta Toan Khoa

Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof \n \nsystems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. \n \n \n \nIn this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: \n \n \n \n- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees \n \nfor 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. \n \n \n \n- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. \n \n \n \n- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes.

•Jan 1, 2013•0 citations

On the hardness of the hidden subspaces problem with and without noise. Cryptanalysis of Aaronson-Christiano’s quantum money scheme

Marta Conde Pena

[ES] El boom de internet ha marcado el comienzo de la era digital y ésta ha traído consigo un desarrollo espectacular de las tecnologías de la información y de las comunicaciones, entre las que la criptografía es la reina. La criptografía de clave pública actual está basada principalmente en dos problemas que la comunidad criptográfica asume como difíciles: la factorización y el logaritmo discreto. Sin embargo, si se llegase a construir un computador cuántico lo suficientemente potente, esta dificultad no sería tal. Así pues, la computación cuántica pondría en un grave aprieto a la criptografía moderna y, puesto que la trayectoria reciente del campo sugiere que ésta podría convertirse en una realidad en un futuro no muy lejano, la comunidad criptográfica ha comenzado a explorar otras opciones para estar lista en caso de que se logre construir un computador cuántico eficiente. Esto ha dado un im- pulso a lo que se conoce como criptografía post-cuántica, aquella cuya dificultad no se vería afectada por este nuevo paradigma de computación y que está basada en los llamados problemas resistentes a la computación cuántica. La criptografía post-cuántica ha suscitado mucho interés recientemente y actualmente está en proceso de estandarización, por lo que en el momento de iniciar esta tesis resultaba relevante estudiar problemas supuestamente resistentes al computador cuántico. La parte central de esta tesis es el análisis de la dificultad del problema de los subespacios ocultos (HSP por sus siglas en inglés) y del problema de los subespacios ocultos con ruido (NHSP), dos problemas resistentes al computador cuántico según sus autores. Además de la relevancia que su supuesta resistencia a la computación cuántica les confiere, estos dos problemas son también importantes porque en su dificultad se sustenta la seguridad de las dos versiones del primer esquema de dinero cuántico de clave pública que cuenta con una prueba de seguridad. Este primer esquema es el de Aaronson-Christiano, que implementa dinero cuántico — un tipo de dinero que explota las leyes de la mecánica cuántica para crear dinero infalsificable — que cualquiera puede verificar. Los resultados obtenidos acerca de la dificultad del HSP y del NHSP tienen un impacto directo sobre la seguridad del esquema de Aaronson-Christiano, lo cual nos motivó a centrar esta tesis en estos dos problemas. El Capítulo 3 contiene nuestros resultados acerca del problema de los subespacios ocultos y está fundamentalmente basado en nuestro trabajo [Conde Pena et al.,2015]. Los autores del HSP lo definieron originalmente sobre el cuerpo binario, pero nosotros extendemos la definición a cualquier otro cuerpo finito de orden primo, siempre considerando que la instanciación es la que los autores proponen. Después de modelar el HSP con un sistema de ecuaciones con buenas propiedades, usamos técnicas de criptoanálisis algebraico para explorar el sistema en profundidad. Para el HSP sobre cualquier cuerpo que no sea el binario diseñamos un algoritmo que resuelve de manera eficiente instancias que satisfacen una cierta condición. Utilizando técnicas distintas, construimos un algoritmo heurístico, sustentado por argumentos teóricos, que resuelve eficientemente instancias del HSP sobre el cuerpo binario. Ambos algo-ritmos comprometen la dificultad del HSP siempre que las instancias del problema sean escogidas como Aaronson-Christiano proponen. Como consecuencia, nuestros algoritmos vulneran la seguridad de la versión del esquema sin ruido. El capítulo 4 contiene nuestros resultados acerca del problema de los subespacios ocultos con ruido y está fundamentalmente basado en nuestro trabajo [Conde Pena et al., 2018]. Al igual que con el HSP, extendemos la definición del NHSP a cualquier otro cuerpo de orden primo y consideramos instancias generadas como especifi- can Aaronson-Christiano. Mostramos que el NHSP se puede reducir al HSP sobre cualquier cuerpo primo que no sea el binario para ciertas instancias, mientras que el NHSP sobre el cuerpo binario se puede resolver con una probabilidad mayor de la asumida por los autores en la conjetura sobre la que la seguridad de su esquema con ruido se sustenta. Aunque nuestros resultados se obtienen desde un punto de vista puramente no cuántico, durante el desarrollo de esta tesis otro autor demostró que existe una reducción cuántica del NHSP al HSP también en el caso binario. Por tanto, la dificultad del NHSP y la seguridad del esquema de Aaronson-Christiano con ruido se han visto comprometidas por nuestros descubrimientos acerca del HSP.

•Jan 1, 2018•0 citations

Hardness of Lattice Based Cryptography

Thor Tunge

In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.

•Jan 1, 2018•0 citations

Estabilidad y ley de área para sistemas cuánticos disipativos con equilibración rápida

Ángelo Lucia

Desde su origen, la teoría de la información ha tenido fuertes conexiones con la mecánica estadística. El mismo término entropía de la información fue elegido por Shannon a partir del término usado en termodinámica, bajo sugerencia de Von Neumann. La misma relación se ha desarrollado recientemente entre las correspondientes generalizaciones cuánticas de ambas teorías, que son la información cuántica, que estudia el almacenamiento y la manipulación de la información en sistemas cuánticos, y la física de muchos cuerpos. Las conexiones entre los dos campos aumentan cada día y van en las dos direcciones. Las herramientas e ideas de la información cuántica ayudan a solucionar problemas abiertos en teoría de la materia condensada, y nuevos modelos de muchos cuerpos se desarrollan para aplicaciones de la información cuántica. Al mismo tiempo la implementación y el control experimental de pequeños sistemas cuánticos ha mejorado de forma espectacular, aumentando la posibilidad de que estos experimentos se puedan llevar a cabo a escala más grande, abriendo la posibilidad de aplicaciones prácticas. Es reciente el interés de la comunidad de investigadores en información cuántica por estos modelos, y se ha empezado a ver este tipo de evoluciones no solamente como un problema que resolver, sino cómo un recurso que explotar. Este fundamental cambio de perspectiva ha abierto una nueva línea de investigación en el campo, incorporando ideas sobre cómo construir evoluciones artificiales en las cuales la disipación trabaja en nuestro favor en vez de en nuestra contra, incluso protegiendo el sistema de otros ruidos incontrolados. De esta manera se han planteado nuevos problemas interesantes, como cuál es el poder computacional de estos modelos y qué condiciones pueden garantizar la resistencia contra el ruido externo. Esta tesis es parte del esfuerzo para mejorar nuestro conocimiento de estos modelos. Nos hemos centrado en el estudio de las propiedades de evoluciones disipativas de sistemas cuánticos de espines en un retículo, bajo una hipótesis que llamamos equilibración rápida. Consideramos evoluciones disipativas con un único punto fijo, y que comprimen todo el espacios de estados iniciales en un entorno decreciente del punto fijo. La escala temporal a la cuál se tiene esta compresión, es decir el tiempo que tenemos que esperar para que cualquier estado inicial se encuentre arbitrariamente cercano al punto fijo, se llama tiempo de equilibración del proceso. La condición de equilibración rápida pide que este tiempo sea logarítmico en el tamaño del sistema. La contribución principal de esta tesis es demostrar que la equilibración rápida tiene importantes consecuencias en las propiedades del sistema. Este será estable bajo perturbaciones externas y sus puntos fijos satisfarán una ley de área para la información mutua. La parte más técnica de este trabajo se basa en las llamadas cotas de Lieb Robinson. Muy conocidas en el caso de sistemas cerrados, pero igualmente válidas para sistemas abiertos, las cotas de Lieb Robinson formalizan la idea que la información en un sistema de muchos cuerpos sólo puede moverse con una velocidad finita, dado que su propagación está mediada por las interacciones locales. Por lo tanto, controlar la escala temporal con la cuál la evolución converge permite a su vez controlar la escala espacial a la cuál se pueden crear correlaciones.

•Jan 1, 2016•0 citations

Shortcuts to adiabaticity in trapped ions

Mikel Palmero

A lo largo de los últimos 30 años, el campo de la óptica cuántica a sentido un notable desarrollo. La variedad de campos y aplicaciones, como la metrología,espectroscopia, comunicaciones, procesamiento de información cuántica, nuevas tecnologías basadas en fenómenos cuánticos, etc, hace de la óptica cuántica un tema muy atractivo para la investigación. La evolución de las técnicas nos ha permitido alcanzar un punto donde la manipulación de un solo átomo es muy precisa, y permite el desarrollo de estas aplicaciones basadas en fenómenos cuánticos. La importancia y alcanza de este progreso está reconocido y visibilidada través de numerosos galardones en los Premios Nobel. En 1989, mi año de nacimiento, Norman Ramsey por su trabajo con relojes atómicos y Hans Dehmelt yWolfgang Paul por desarrollar la técnica de atrapar iones compartieron el Nobel defísica. 8 años después, en 1997, el mismo galardón fue compartido por StevenChu, Claude Cohen-Tannoudji y William Phillips por el desarrollo de técnicas de enfriamiento de átomos. Otro Premio Nobel fue compartido en 2001 por WolfgangKetterle, Carl Wieman y Eric Cornell por diluir un condensado de Bose-Einstein,predicho teóricamente mucho tiempo atrás. En 2005 los premiados fueron RoyGlauber por su contribución a la teoría de coherencia óptica y John Hall y TheodorHänsch por desarrollar técnicas de espectroscopia de precisión. Finalmente, en 2012 el Premio Nobel de física fue otorgado también por contribuciones en elcampo de la óptica cuántica, ya que Serge Laroche y David Vineland lo ganaron por el desarrollo de técnicas que permitieron la medida precisa y el control desistemas cuánticos individuales. Estos 5 premios en los íntimos 30 años muestranclaramente el peso del este campo, no sólo en la comunidad física, sino en generalen la sociedad. Todos estos avances sucediéndose desde antes de mi nacimiento,y durante mi infancia y adolescencia, antes incluso de ser yo consciente de su existencia han traído al campo al punto en el que esta tesis ha sido escrita y tiene sentido como parte de la contribución al mismo.Uno de los temas calientes dentro de la óptica cuántica es el conocido como computación cuántica, que es un dispositivo propuesto, que usaría fenómenos cuánticos para procesar la información, basado en estados cuánticos (qubits) enlugar de los estados clásicos (bits), lo que debería ser tremendamente ventajoso para ciertas tareas frente al ordenador clásico. Un ordenador cuántico universal,equivalente a la máquina de Turing clásica, fue descrito teóricamente por DavidDeutsch ya en el año 1985, pero no fue hasta 1995 cuando Ignacio Cirac y PeterZoller propusieron un esquema físico donde el ordenador cuántico podría ser fabricado usando la tecnología de iones atrapados. La idea básica de esta propuesta era atrapar iones usando campos electromagnéticos (trampas de Paul),y almacenar el qubit haciendo uso de los niveles internos de energía de cada ion.Estos iones interactuarían entre ellos a través de la fuerza eléctrica, de forma quela información cuántica puede ser transferida de uno a otro. Usando láseres, se puede inducir acoplamiento o entrelazamiento entre iones, lo que es necesario para las operaciones lógicas. Desde entonces, ha sido demostrado cómo este esquema posibilita todos las operaciones básicas necesarias para la arquitectura de un ordenador basado en la cuántica, es decir, inicialización, lectura,manipulación de iones individuales y entrelazamiento. Adicionalmente, las fidelidades alcanzadas recientemente han sido lo suficientemente altas para considerar a los iones atrapados como un buen candidato para fabricar un ordenador a prueba de errores, es decir, un ordenador lo suficientemente robusto para funcionar a pesar de pequeños desvíos. La habilidad para controlar iones atrapados con precisión y para realizar diferentes operaciones con ellos la han convertido en la arquitectura lidere de procesamiento de información cuántica.Sin embargo, poco después de que Cirac y Zoller publicaran su carta, se volviómanifiesto que, a pesar de ser los iones atrapados una plataforma adecuada pararealizar operaciones básicas, manejar un número grande de iones en una única trampa iba a convertirse en una tarea complicada. Por esa razón, Wineland y sus colaboradores propusieron un esquema alternativo, donde los iones se manipulan individualmente o en grupos pequeños en una región de interacción pararealizarlas operaciones lógicas necesarias, y luego se llevan a una zona diferente arealizar la lectura. En este esquema, son necesarias numerosas zonas de interacción donde las operaciones están dándose simultáneamente para un gran número de iones. Este esquema evita la necesidad de manipular un gran número de iones en una sola trampa, pero requiere una sincronización entre diferentes regiones y la habilidad de realizar operaciones dinámicas a los iones, sin calentamiento o excitación que provocaría una pérdida de información del qubit que lleva. Desde entonces, numerosos trabajos han propuesto esquemas similareso desarrollado más el original. En 2009, en el NIST llevaron a cabo una prueba deprincipios para este esquema. Sin embargo, después de este trabajo, quedó claro que los lentos procesos adiabáticos, que mantienen el qubit inalterado, eran de hecho demasiado lentos, ya que las pequeñas imperfecciones en el diseño de las trampas producen calentamiento y de coherencia para procesos que se alargan más de unos 100 ¿m. Por otro lado, los procesos rápidos incontrolados provocan excitaciones diabéticas, que tampoco son deseables.Una posible salida es diseñar los procesos dinámicos necesarios usando los llamados ¿atajos a la adiabaticidad¿. Estos son procesos que llevan el sistema almismo estado cuántico que resultaría de un proceso adiabático en tiempos más rápidos de los usualmente requeridos para los procesos adiabáticos, aunque sin necesariamente seguir una evolución adiabática. Existen una serie de diferentes técnicas para diseñar tales procesos. Algunos están basados en optimizar procesos adiabáticos, de tal forma que hayan la ruta adiabática óptima, o queaceleran una evolución adiabática dada manipulando los parámetros de control.Otros excitan el sistema transitoriamente, pero están diseñados para recuperar elmismo autoestado inicial a tiempo final. Esquivar la necesidad de seguir laslimitaciones dadas por el teorema adiabático permite procesos muy rápidos (enocasiones incluso arbitrariamente rápidos), pero el diseño inteligente delHamiltoniano hace posible conseguir el mismo estado final.Una de las técnicas más usadas es la de ¿ingeniería inversa basada eninvariantes¿. Esta técnica se basa en diseñar primero la evolución del sistema cuántico de tal forma que alcance el estado final en el que estamos interesadosobligando al Hamiltoniano y al invariable a conmutar a tiempo inicial y final.Entonces, se obtiene inversamente los parámetros de control que conducirán e lHamiltoniano siguiendo este diseño. Este protocolo está limitado en cierto sentido,ya que necesitamos un invariante dinámico relacionado al tipo de Hamiltoniano quequeremos o podemos diseñar. Sin embargo, si es posible conseguir esteinvariante, el diseño del atajo es normalmente simple, y sobre todo, conseguimosresultados analíticos que se pueden aplicar inmediatamente en el laboratorio, o adaptar fácilmente si necesitamos variar valores de los parámetros. Una serie de procesos dinámicos para un solo átomo fueron diseñados usando esta técnica,incluyendo la expansión y el transporte de un solo átomo. Cuando consideramos la interacción de Coulomb entre iones de una cadena, no es posible encontrar un invariante, porque al tener un término inversamente proporcional a la posición no es posible cerrar el álgebra. Sin embargo, durante esta tesis, he encontrado útil usar los mismos invariantes que para los Hamiltonianos de un solo átomo, que funcionarán razonablemente bien bajo la aproximación de modos normales.En los capítulos 1 y 2 diseño atajos para transportar cadenas de iones, primero considerando iones de masas iguales y luego de masas diferentes. Este es probablemente el proceso dinámico más sensible para las arquitectura basadas en iones atrapados, ya que su proceso adiabático es el que implica tiempos finales más largos para los parámetros que se pueden alcanzar hoy en día en los laboratorios. In el capítulo 3, diseño puertas lógicas de fase rápidas. Las puertas lógicas cuánticas son, por supuesto, estrictamente necesarias en cualquier dispositivo de procesamiento cuántico. Aquí me baso en un esquema que ya ha sido aplicado en muchos laboratorios, y consigo acelerarlo usando los atajos a la adiabaticidad. Está basado en excitar los átomos desde su posición de reposo aplicando fuerzas (casi) lineales, que dependerán del estado interno.Matemáticamente, el problema es similar al del transporte, aunque implica unanálisis matemático más trillado ya que cada ion recibe fuerzas diferentes. El capítulo 4 ataca el problema de la expansión/compresión de cadenas de iones, y elcapítulo 5 el del la separación o recombinación de iones. Estos dos problemas sonen cierta manera similares bajo la aproximación de modos normales, ya que tienenque satisfacer las mismas ecuaciones de movimiento, aunque el problema deinversión es muy diferente para ambos problemas, ya que en la expansión/compresión se manipula un solo parámetro y en la separación/recombinación dos.Los capítulos 6 y 7 están dedicados a la rotación. En el capítulo 6 se diseña la rotación de un solo ion, que es un problema que no se había considerado hasta ahora. En el capítulo 7 extiendo este análisis a cadenas de 2 iones, tanto para masas iguales como diferentes. Finalmente, incluyo un breve capítulo en el que se extraen conclusiones y se da una visión global de todos los problemas considerados a lo largo de esta tesis

•Jan 20, 2017•0 citations

Post-Quantum Zero-Knowledge Proofs and Applications

Ron Steinfeld

Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 20, 2023•5 citations
(English) The main goal of this dissertation is to develop new lattice-based cryptographic schemes. Most of the cryptographic protocols that each and every one of us use on a daily basis are only secure under the assumption that two mathematical problems, namely the discrete logarithm on elliptic curves and the factorization of products of two primes, are computationally hard. That is believed to be true for classical computers, but quantum computers would be able to solve these problems much more efficiently, demolishing the foundations of plenty of cryptographic constructions. This reveals the importance of post-quantum alternatives, cryptographic schemes whose security relies on different problems intractable for both classical and quantum computers. The most promising family of problems widely believed to be hard for quantum computers are lattice-based problems. We increase the supply of lattice-based tools providing new Zero-Knowledge Proofs of Knowledge for the Ring Learning With Errors (RLWE) problem, perhaps the most popular lattice-based problem. Zero-knowledge proofs are protocols between a prover and a verifier where the prover convinces the verifier of the validity of certain statements without revealing any additional relevant information. Our proofs extend the literature of Stern-based proofs, following the techniques presented by Jacques Stern in 1994. His original idea involved a code-based problem, but it has been reiteratedly improved and generalized to be used with lattices. We illustrate our proposal defining a variant of the commitment scheme, a cryptographic primitive that allows us to ensure some message was already determined at some point without revealing it until a future time, defined by Benhamouda et al. in ESORICS 2015, and proving in zero-knowledge the knowledge of a valid opening. Most importantly we also show how to prove that the message committed in one commitment is a linear combination, with some public coefficients, of the committed messages from two other commitments, again without revealing any further information about the messages. Finally, we also present a zero-knowledge proof analogous to the previous one but for multiplicative relations, something much more involved that allows us to prove any arithmetic circuit. We give first an interactive version of these proofs and then show how to construct a non-interactive one. We diligently prove that both the commitment and the companion Zero-Knowledge Proofs of Knowledge are secure under the assumption of the hardness of the underlying lattice problems. Furthermore, we specifically develop such proofs so that the arising conditions can be directly used to compute parameters that satisfy them. This way we provide a general method to instantiate our commitment and proofs with any desired security level. Thanks to this practical approach we have been able to implement all the proposed schemes and benchmark the prototype im-plementation with actually secure parameters, which allows us to obtain meaningful results and compare its performance with the existing alternatives. Moreover, provided that multiplication of polynomials in the quotient ring ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, with 𝑝 prime and 𝑛 a power of two, is the most basic operation when working with ideal lattices we comprehensively study what are the necessary and sufficient conditions needed for applying (a generalized version of) the Fast Fourier Transform (FFT) to obtain an efficient multiplication algorithm in quotient rings as ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩ (where we consider any positive integer 𝑚 and generalize the quotient), as we think it is of independent interest. We believe such a theoretical analysis is fundamental to be able to determine when a given generalization can also be applied to design an efficient multiplication algorithm when the FFT is not defined for the ring we are considering. That is the case of the rings used for the commitment and proofs described before, where only a partial FFT is available. (Español) El objetivo principal de esta tesis es obtener nuevos esquemas criptográficos basados en retículos. La mayoría de los protocolos criptográficos que usamos a diario son únicamente seguros bajo la hipótesis de que el problema del logaritmo discreto en curvas elípticas y la factorización de productos de dos primos son computacionalmente difíciles. Se cree que esto es cierto para los ordenadores clásicos, pero los ordenadores cuánticos podrían resolver estos problemas de forma mucho más eficiente, acabando con las bases sobre las que se fundamenta una multitud de construcciones criptográficas. Esto evidencia la importancia de las alternativas poscuánticas, cuya seguridad se basa en problemas diferentes que sean inasumibles tanto para los ordenadores clásicos como los cuánticos. Los problemas de retículos son los candidatos más prometedores, puesto que se considera que son problemas difíciles para los ordenadores cuánticos. Presentamos nuevas herramientas basadas en retículos con unas Pruebas de Conocimiento Nulo para el problema Ring Learning With Errors (RLWE), seguramente el problema de retículos más popular. Las pruebas de Conocimiento Nulo son protocolos entre un probador y un verificador en los que el primero convence al segundo de la validez de una proposición, sin revelar ninguna información adicional relevante. Nuestras pruebas se basan en el protocolo de Stern, siguiendo sus técnicas presentadas en 1994. Su idea original involucraba un problema de códigos, pero se ha mejorado y generalizado reiteradamente para poder aplicarse a retículos. Ilustramos nuestra propuesta definiendo una variante del esquema de compromiso, una primitiva criptográfica que nos permite asegurar que un mensaje fue determinado en cierto momento sin revelarlo hasta pasado un tiempo, definido por Benhamouda et al. en ESORICS 2015, y probando que conocemos una apertura válida. Además mostramos cómo probar que el mensaje comprometido es una combinación lineal, con coeficientes públicos, de los mensajes comprometidos en otros dos compromisos. Finalmente también presentamos una prueba de Conocimiento Nulo análoga a la anterior pero para relaciones multiplicativas, algo mucho más laborioso que nos permite realizar circuitos aritméticos. Todo esto sin revelar ninguna información adicional sobre los mensajes. Mostramos tanto una versión interactiva como una no interactiva. Probamos que tanto el compromiso como las pruebas de Conocimiento Nulo que le acompañan son seguras bajo la hipótesis de que el problema de retículos subyacente sea difícil. Además planteamos estas pruebas específicamente con el objetivo de que las condiciones que surjan puedan ser utilizadas directamente para calcular los parámetros que las satisfagan. De esta forma proporcionamos un método genérico para instanciar nuestro compromiso y pruebas con cualquier nivel de seguridad. Gracias a este enfoque práctico hemos podido implementar todos los esquemas propuestos y evaluar el rendimiento con parámetros seguros, lo que nos permite obtener resultados relevantes que poder comparar con las alternativas existentes. Por otra parte, dado que la multiplicación de polinomios en el anillo cociente ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, con 𝑝 primo y 𝑛 una potencia de 2, es la operación más utilizada al trabajar con retículos ideales, estudiamos de forma exhaustiva cuáles son las condiciones suficientes y necesarias para aplicar (una versión generalizada de) la Transformada Rápida de Fourier (FFT, por sus siglas en inglés) para obtener algoritmos de multiplicación eficientes en anillos cociente ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩, (considerando cualquier 𝑚 positiva y generalizando el cociente), de interés por sí mismo. Creemos que este análisis teórico es fundamental para determinar cuándo puede diseñarse un algoritmo eficiente de multiplicación si la FFT no está definida para el anillo considerado. Es el caso de los anillos que utilizamos en el compromiso y las pruebas descritas anteriormente, donde solo es posible calcular una FFT parcial.
Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof \n \nsystems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. \n \n \n \nIn this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: \n \n \n \n- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees \n \nfor 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. \n \n \n \n- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. \n \n \n \n- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes.
[ES] El boom de internet ha marcado el comienzo de la era digital y ésta ha traído consigo un desarrollo espectacular de las tecnologías de la información y de las comunicaciones, entre las que la criptografía es la reina. La criptografía de clave pública actual está basada principalmente en dos problemas que la comunidad criptográfica asume como difíciles: la factorización y el logaritmo discreto. Sin embargo, si se llegase a construir un computador cuántico lo suficientemente potente, esta dificultad no sería tal. Así pues, la computación cuántica pondría en un grave aprieto a la criptografía moderna y, puesto que la trayectoria reciente del campo sugiere que ésta podría convertirse en una realidad en un futuro no muy lejano, la comunidad criptográfica ha comenzado a explorar otras opciones para estar lista en caso de que se logre construir un computador cuántico eficiente. Esto ha dado un im- pulso a lo que se conoce como criptografía post-cuántica, aquella cuya dificultad no se vería afectada por este nuevo paradigma de computación y que está basada en los llamados problemas resistentes a la computación cuántica. La criptografía post-cuántica ha suscitado mucho interés recientemente y actualmente está en proceso de estandarización, por lo que en el momento de iniciar esta tesis resultaba relevante estudiar problemas supuestamente resistentes al computador cuántico. La parte central de esta tesis es el análisis de la dificultad del problema de los subespacios ocultos (HSP por sus siglas en inglés) y del problema de los subespacios ocultos con ruido (NHSP), dos problemas resistentes al computador cuántico según sus autores. Además de la relevancia que su supuesta resistencia a la computación cuántica les confiere, estos dos problemas son también importantes porque en su dificultad se sustenta la seguridad de las dos versiones del primer esquema de dinero cuántico de clave pública que cuenta con una prueba de seguridad. Este primer esquema es el de Aaronson-Christiano, que implementa dinero cuántico — un tipo de dinero que explota las leyes de la mecánica cuántica para crear dinero infalsificable — que cualquiera puede verificar. Los resultados obtenidos acerca de la dificultad del HSP y del NHSP tienen un impacto directo sobre la seguridad del esquema de Aaronson-Christiano, lo cual nos motivó a centrar esta tesis en estos dos problemas. El Capítulo 3 contiene nuestros resultados acerca del problema de los subespacios ocultos y está fundamentalmente basado en nuestro trabajo [Conde Pena et al.,2015]. Los autores del HSP lo definieron originalmente sobre el cuerpo binario, pero nosotros extendemos la definición a cualquier otro cuerpo finito de orden primo, siempre considerando que la instanciación es la que los autores proponen. Después de modelar el HSP con un sistema de ecuaciones con buenas propiedades, usamos técnicas de criptoanálisis algebraico para explorar el sistema en profundidad. Para el HSP sobre cualquier cuerpo que no sea el binario diseñamos un algoritmo que resuelve de manera eficiente instancias que satisfacen una cierta condición. Utilizando técnicas distintas, construimos un algoritmo heurístico, sustentado por argumentos teóricos, que resuelve eficientemente instancias del HSP sobre el cuerpo binario. Ambos algo-ritmos comprometen la dificultad del HSP siempre que las instancias del problema sean escogidas como Aaronson-Christiano proponen. Como consecuencia, nuestros algoritmos vulneran la seguridad de la versión del esquema sin ruido. El capítulo 4 contiene nuestros resultados acerca del problema de los subespacios ocultos con ruido y está fundamentalmente basado en nuestro trabajo [Conde Pena et al., 2018]. Al igual que con el HSP, extendemos la definición del NHSP a cualquier otro cuerpo de orden primo y consideramos instancias generadas como especifi- can Aaronson-Christiano. Mostramos que el NHSP se puede reducir al HSP sobre cualquier cuerpo primo que no sea el binario para ciertas instancias, mientras que el NHSP sobre el cuerpo binario se puede resolver con una probabilidad mayor de la asumida por los autores en la conjetura sobre la que la seguridad de su esquema con ruido se sustenta. Aunque nuestros resultados se obtienen desde un punto de vista puramente no cuántico, durante el desarrollo de esta tesis otro autor demostró que existe una reducción cuántica del NHSP al HSP también en el caso binario. Por tanto, la dificultad del NHSP y la seguridad del esquema de Aaronson-Christiano con ruido se han visto comprometidas por nuestros descubrimientos acerca del HSP.
In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.
Desde su origen, la teoría de la información ha tenido fuertes conexiones con la mecánica estadística. El mismo término entropía de la información fue elegido por Shannon a partir del término usado en termodinámica, bajo sugerencia de Von Neumann. La misma relación se ha desarrollado recientemente entre las correspondientes generalizaciones cuánticas de ambas teorías, que son la información cuántica, que estudia el almacenamiento y la manipulación de la información en sistemas cuánticos, y la física de muchos cuerpos. Las conexiones entre los dos campos aumentan cada día y van en las dos direcciones. Las herramientas e ideas de la información cuántica ayudan a solucionar problemas abiertos en teoría de la materia condensada, y nuevos modelos de muchos cuerpos se desarrollan para aplicaciones de la información cuántica. Al mismo tiempo la implementación y el control experimental de pequeños sistemas cuánticos ha mejorado de forma espectacular, aumentando la posibilidad de que estos experimentos se puedan llevar a cabo a escala más grande, abriendo la posibilidad de aplicaciones prácticas. Es reciente el interés de la comunidad de investigadores en información cuántica por estos modelos, y se ha empezado a ver este tipo de evoluciones no solamente como un problema que resolver, sino cómo un recurso que explotar. Este fundamental cambio de perspectiva ha abierto una nueva línea de investigación en el campo, incorporando ideas sobre cómo construir evoluciones artificiales en las cuales la disipación trabaja en nuestro favor en vez de en nuestra contra, incluso protegiendo el sistema de otros ruidos incontrolados. De esta manera se han planteado nuevos problemas interesantes, como cuál es el poder computacional de estos modelos y qué condiciones pueden garantizar la resistencia contra el ruido externo. Esta tesis es parte del esfuerzo para mejorar nuestro conocimiento de estos modelos. Nos hemos centrado en el estudio de las propiedades de evoluciones disipativas de sistemas cuánticos de espines en un retículo, bajo una hipótesis que llamamos equilibración rápida. Consideramos evoluciones disipativas con un único punto fijo, y que comprimen todo el espacios de estados iniciales en un entorno decreciente del punto fijo. La escala temporal a la cuál se tiene esta compresión, es decir el tiempo que tenemos que esperar para que cualquier estado inicial se encuentre arbitrariamente cercano al punto fijo, se llama tiempo de equilibración del proceso. La condición de equilibración rápida pide que este tiempo sea logarítmico en el tamaño del sistema. La contribución principal de esta tesis es demostrar que la equilibración rápida tiene importantes consecuencias en las propiedades del sistema. Este será estable bajo perturbaciones externas y sus puntos fijos satisfarán una ley de área para la información mutua. La parte más técnica de este trabajo se basa en las llamadas cotas de Lieb Robinson. Muy conocidas en el caso de sistemas cerrados, pero igualmente válidas para sistemas abiertos, las cotas de Lieb Robinson formalizan la idea que la información en un sistema de muchos cuerpos sólo puede moverse con una velocidad finita, dado que su propagación está mediada por las interacciones locales. Por lo tanto, controlar la escala temporal con la cuál la evolución converge permite a su vez controlar la escala espacial a la cuál se pueden crear correlaciones.
A lo largo de los últimos 30 años, el campo de la óptica cuántica a sentido un notable desarrollo. La variedad de campos y aplicaciones, como la metrología,espectroscopia, comunicaciones, procesamiento de información cuántica, nuevas tecnologías basadas en fenómenos cuánticos, etc, hace de la óptica cuántica un tema muy atractivo para la investigación. La evolución de las técnicas nos ha permitido alcanzar un punto donde la manipulación de un solo átomo es muy precisa, y permite el desarrollo de estas aplicaciones basadas en fenómenos cuánticos. La importancia y alcanza de este progreso está reconocido y visibilidada través de numerosos galardones en los Premios Nobel. En 1989, mi año de nacimiento, Norman Ramsey por su trabajo con relojes atómicos y Hans Dehmelt yWolfgang Paul por desarrollar la técnica de atrapar iones compartieron el Nobel defísica. 8 años después, en 1997, el mismo galardón fue compartido por StevenChu, Claude Cohen-Tannoudji y William Phillips por el desarrollo de técnicas de enfriamiento de átomos. Otro Premio Nobel fue compartido en 2001 por WolfgangKetterle, Carl Wieman y Eric Cornell por diluir un condensado de Bose-Einstein,predicho teóricamente mucho tiempo atrás. En 2005 los premiados fueron RoyGlauber por su contribución a la teoría de coherencia óptica y John Hall y TheodorHänsch por desarrollar técnicas de espectroscopia de precisión. Finalmente, en 2012 el Premio Nobel de física fue otorgado también por contribuciones en elcampo de la óptica cuántica, ya que Serge Laroche y David Vineland lo ganaron por el desarrollo de técnicas que permitieron la medida precisa y el control desistemas cuánticos individuales. Estos 5 premios en los íntimos 30 años muestranclaramente el peso del este campo, no sólo en la comunidad física, sino en generalen la sociedad. Todos estos avances sucediéndose desde antes de mi nacimiento,y durante mi infancia y adolescencia, antes incluso de ser yo consciente de su existencia han traído al campo al punto en el que esta tesis ha sido escrita y tiene sentido como parte de la contribución al mismo.Uno de los temas calientes dentro de la óptica cuántica es el conocido como computación cuántica, que es un dispositivo propuesto, que usaría fenómenos cuánticos para procesar la información, basado en estados cuánticos (qubits) enlugar de los estados clásicos (bits), lo que debería ser tremendamente ventajoso para ciertas tareas frente al ordenador clásico. Un ordenador cuántico universal,equivalente a la máquina de Turing clásica, fue descrito teóricamente por DavidDeutsch ya en el año 1985, pero no fue hasta 1995 cuando Ignacio Cirac y PeterZoller propusieron un esquema físico donde el ordenador cuántico podría ser fabricado usando la tecnología de iones atrapados. La idea básica de esta propuesta era atrapar iones usando campos electromagnéticos (trampas de Paul),y almacenar el qubit haciendo uso de los niveles internos de energía de cada ion.Estos iones interactuarían entre ellos a través de la fuerza eléctrica, de forma quela información cuántica puede ser transferida de uno a otro. Usando láseres, se puede inducir acoplamiento o entrelazamiento entre iones, lo que es necesario para las operaciones lógicas. Desde entonces, ha sido demostrado cómo este esquema posibilita todos las operaciones básicas necesarias para la arquitectura de un ordenador basado en la cuántica, es decir, inicialización, lectura,manipulación de iones individuales y entrelazamiento. Adicionalmente, las fidelidades alcanzadas recientemente han sido lo suficientemente altas para considerar a los iones atrapados como un buen candidato para fabricar un ordenador a prueba de errores, es decir, un ordenador lo suficientemente robusto para funcionar a pesar de pequeños desvíos. La habilidad para controlar iones atrapados con precisión y para realizar diferentes operaciones con ellos la han convertido en la arquitectura lidere de procesamiento de información cuántica.Sin embargo, poco después de que Cirac y Zoller publicaran su carta, se volviómanifiesto que, a pesar de ser los iones atrapados una plataforma adecuada pararealizar operaciones básicas, manejar un número grande de iones en una única trampa iba a convertirse en una tarea complicada. Por esa razón, Wineland y sus colaboradores propusieron un esquema alternativo, donde los iones se manipulan individualmente o en grupos pequeños en una región de interacción pararealizarlas operaciones lógicas necesarias, y luego se llevan a una zona diferente arealizar la lectura. En este esquema, son necesarias numerosas zonas de interacción donde las operaciones están dándose simultáneamente para un gran número de iones. Este esquema evita la necesidad de manipular un gran número de iones en una sola trampa, pero requiere una sincronización entre diferentes regiones y la habilidad de realizar operaciones dinámicas a los iones, sin calentamiento o excitación que provocaría una pérdida de información del qubit que lleva. Desde entonces, numerosos trabajos han propuesto esquemas similareso desarrollado más el original. En 2009, en el NIST llevaron a cabo una prueba deprincipios para este esquema. Sin embargo, después de este trabajo, quedó claro que los lentos procesos adiabáticos, que mantienen el qubit inalterado, eran de hecho demasiado lentos, ya que las pequeñas imperfecciones en el diseño de las trampas producen calentamiento y de coherencia para procesos que se alargan más de unos 100 ¿m. Por otro lado, los procesos rápidos incontrolados provocan excitaciones diabéticas, que tampoco son deseables.Una posible salida es diseñar los procesos dinámicos necesarios usando los llamados ¿atajos a la adiabaticidad¿. Estos son procesos que llevan el sistema almismo estado cuántico que resultaría de un proceso adiabático en tiempos más rápidos de los usualmente requeridos para los procesos adiabáticos, aunque sin necesariamente seguir una evolución adiabática. Existen una serie de diferentes técnicas para diseñar tales procesos. Algunos están basados en optimizar procesos adiabáticos, de tal forma que hayan la ruta adiabática óptima, o queaceleran una evolución adiabática dada manipulando los parámetros de control.Otros excitan el sistema transitoriamente, pero están diseñados para recuperar elmismo autoestado inicial a tiempo final. Esquivar la necesidad de seguir laslimitaciones dadas por el teorema adiabático permite procesos muy rápidos (enocasiones incluso arbitrariamente rápidos), pero el diseño inteligente delHamiltoniano hace posible conseguir el mismo estado final.Una de las técnicas más usadas es la de ¿ingeniería inversa basada eninvariantes¿. Esta técnica se basa en diseñar primero la evolución del sistema cuántico de tal forma que alcance el estado final en el que estamos interesadosobligando al Hamiltoniano y al invariable a conmutar a tiempo inicial y final.Entonces, se obtiene inversamente los parámetros de control que conducirán e lHamiltoniano siguiendo este diseño. Este protocolo está limitado en cierto sentido,ya que necesitamos un invariante dinámico relacionado al tipo de Hamiltoniano quequeremos o podemos diseñar. Sin embargo, si es posible conseguir esteinvariante, el diseño del atajo es normalmente simple, y sobre todo, conseguimosresultados analíticos que se pueden aplicar inmediatamente en el laboratorio, o adaptar fácilmente si necesitamos variar valores de los parámetros. Una serie de procesos dinámicos para un solo átomo fueron diseñados usando esta técnica,incluyendo la expansión y el transporte de un solo átomo. Cuando consideramos la interacción de Coulomb entre iones de una cadena, no es posible encontrar un invariante, porque al tener un término inversamente proporcional a la posición no es posible cerrar el álgebra. Sin embargo, durante esta tesis, he encontrado útil usar los mismos invariantes que para los Hamiltonianos de un solo átomo, que funcionarán razonablemente bien bajo la aproximación de modos normales.En los capítulos 1 y 2 diseño atajos para transportar cadenas de iones, primero considerando iones de masas iguales y luego de masas diferentes. Este es probablemente el proceso dinámico más sensible para las arquitectura basadas en iones atrapados, ya que su proceso adiabático es el que implica tiempos finales más largos para los parámetros que se pueden alcanzar hoy en día en los laboratorios. In el capítulo 3, diseño puertas lógicas de fase rápidas. Las puertas lógicas cuánticas son, por supuesto, estrictamente necesarias en cualquier dispositivo de procesamiento cuántico. Aquí me baso en un esquema que ya ha sido aplicado en muchos laboratorios, y consigo acelerarlo usando los atajos a la adiabaticidad. Está basado en excitar los átomos desde su posición de reposo aplicando fuerzas (casi) lineales, que dependerán del estado interno.Matemáticamente, el problema es similar al del transporte, aunque implica unanálisis matemático más trillado ya que cada ion recibe fuerzas diferentes. El capítulo 4 ataca el problema de la expansión/compresión de cadenas de iones, y elcapítulo 5 el del la separación o recombinación de iones. Estos dos problemas sonen cierta manera similares bajo la aproximación de modos normales, ya que tienenque satisfacer las mismas ecuaciones de movimiento, aunque el problema deinversión es muy diferente para ambos problemas, ya que en la expansión/compresión se manipula un solo parámetro y en la separación/recombinación dos.Los capítulos 6 y 7 están dedicados a la rotación. En el capítulo 6 se diseña la rotación de un solo ion, que es un problema que no se había considerado hasta ahora. En el capítulo 7 extiendo este análisis a cadenas de 2 iones, tanto para masas iguales como diferentes. Finalmente, incluyo un breve capítulo en el que se extraen conclusiones y se da una visión global de todos los problemas considerados a lo largo de esta tesis
Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].