CRIPTOGRAFÍA

Alex Biryukov es criptógrafo , actualmente profesor titular en la Universidad de Luxemburgo . Su notable trabajo incluye el diseño del cifrado de flujo LEX , así como el criptoanálisis de numerosas primitivas criptográficas . En 1998, desarrolló un criptoanálisis diferencial imposible junto con Eli Biham y Adi Shamir . ^[1] En 1999, desarrolló el ataque de deslizamiento junto con David Wagner . En 2009 desarrolló, junto con Dmitry Khovratovich , el primer ataque criptoanalítico en ronda completaAES -192 y AES-256 que es más rápido que un ataque de fuerza bruta . ^[2] En 2015 desarrolló la función de derivación de clave Argon2 con Daniel Dinu y Dmitry Khovratovich. ^[3] Desde 1994 Alex Biryukov es miembro de la Asociación Internacional para la Investigación Criptológica .









Alfred Menezes es coautor de varios libros sobre criptografía , incluido el Manual de criptografía aplicada , y es profesor de matemáticas en la Universidad de Waterloo en Canadá .

Educación [ editar ]

La familia de Alfred Menezes es de Goa , un estado en el oeste de la India, pero nació en Tanzania y creció en Kuwait, excepto durante unos años en un internado en la India. Sus títulos universitarios y de posgrado son de la Universidad de Waterloo . ^[3] : 302

Carrera académica [ editar ]

Después de cinco años enseñando en la Universidad de Auburn , en 1997 regresó a la Universidad de Waterloo, donde ahora es profesor de matemáticas en el Departamento de Combinatoria y Optimización. Cofundó y es miembro del Centro de Investigación Criptográfica Aplicada , y ha servido como su Director Gerente. ^[4] Las principales áreas de investigación de Menezes son criptografía de curva elíptica (ECC), seguridad comprobable y áreas relacionadas. El es ciudadano canadiense.

El libro de Menezes Elliptic Curve Public Key Cryptosystems , publicado en 1993, ^[5] fue el primer libro dedicado por completo a ECC. Es coautor del libro de referencia ampliamente utilizado Handbook of Applied Cryptography . ^[6] Menezes ha sido organizador de conferencias o miembro del comité del programa durante aproximadamente cincuenta conferencias sobre criptografía. ^[7] Fue presidente del programa para Crypto 2007, y en 2012 fue orador invitado en Eurocrypt. ^[8]

En 2001, Menezes ganó la Medalla Hall del Instituto de Combinatoria y sus Aplicaciones .

Algebraic Eraser ( AE ) ^{[nota 1]} es un protocolo de acuerdo de clave anónimo que permite a dos partes, cada una con un par de claves pública-privada AE, establecer un secreto compartido sobre un canal inseguro . ^[1] Este secreto compartido se puede usar directamente como una clave, o para derivar otra clave que luego se puede usar para cifrar las comunicaciones posteriores utilizando un cifrado de clave simétrica . El borrador algebraico fue desarrollado por Iris Anshell, Michael Anshell, Dorian Goldfeld y Stephane Lemieux. SecureRF posee patentes que cubren el protocolo ^[2]e intentó sin éxito (a partir de julio de 2019) estandarizar el protocolo como parte de ISO / IEC 29167-20, ^[3] un estándar para asegurar dispositivos de identificación por radiofrecuencia y redes inalámbricas de sensores .

Parámetros del conjunto de claves [ editar ]

Antes de que dos partes puedan establecer una clave, primero deben acordar un conjunto de parámetros, llamados parámetros del conjunto de claves. Estos parámetros comprenden:

• $${\ displaystyle N}, el número de hebras en la trenza,
• $${\ displaystyle q}, el tamaño del campo finito $${\ displaystyle \ mathbb {F} _ {q}},
• $${\ displaystyle M _ {*}}, la matriz inicial de semillas NxN en $${\ displaystyle \ mathbb {F} _ {q}},
• $${\ displaystyle \ mathrm {T}}, un conjunto de $${\ displaystyle N} elementos en el campo finito $${\ displaystyle \ mathbb {F} _ {q}} (también llamados valores T), y
• $${\ displaystyle A, B}Un conjunto de conjugados en el grupo de trenzas diseñado para conmutar entre sí.

E-multiplicación [ editar ]

La operación fundamental del borrador algebraico es una función unidireccional llamada multiplicación E. Dada una matriz, permutación, un generador de Artin $${\ displaystyle \ beta}en el grupo de trenzas y valores T, uno aplica la multiplicación E convirtiendo el generador en una matriz de Burau coloreada y permutación de trenzas,$${\ displaystyle (CB (\ beta), \ sigma _ {\ beta})}, aplicando la permutación y los valores T, y luego multiplicando las matrices y permutaciones. La salida de la multiplicación E es en sí misma un par de matriz y permutación:$${\ displaystyle (M ', \ sigma') = (M, \ sigma _ {0}) * (CB (\ beta), \ sigma _ {\ beta})}.

Protocolo de establecimiento de clave [ editar ]

El siguiente ejemplo ilustra cómo hacer un establecimiento clave. Supongamos que Alice quiere establecer una clave compartida con Bob , pero el único canal disponible puede ser escuchado por un tercero. Inicialmente, Alice y Bob deben acordar los parámetros del conjunto de claves que usarán.

Cada parte debe tener un par de claves derivado del conjunto de claves, que consiste en una clave privada (por ejemplo, en el caso de Alice) $${\ displaystyle (m_ {A}, \ mathrm {B} _ {a})} dónde $${\ displaystyle m_ {A}} es un polinomio de la matriz semilla seleccionado al azar $${\ displaystyle m_ {A} = \ sum _ {i = 0} ^ {N-1} {a_ {i} M _ {*} ^ {i}}} y una trenza, que es un conjunto de conjugados e inversos seleccionados al azar elegidos de los parámetros del conjunto de claves (A para Alice y B para Bob, donde (para Alice) $${\ displaystyle \ mathrm {B} _ {a} = \ prod _ {i = 1} ^ {k} A_ {i} ^ {\ pm 1}})

A partir de su material de clave privada, Alice y Bob calculan su clave pública. $${\ displaystyle (Pub_ {A}, \ sigma _ {a})} y $${\ displaystyle (Pub_ {B}, \ sigma _ {b})} donde, por ejemplo, $${\ displaystyle (Pub_ {A}, \ sigma _ {a}) = (m_ {A}, id) * b_ {a}}, es decir, el resultado de la multiplicación E de la matriz privada y la permutación de identidad con la trenza privada.

Cada parte debe conocer la clave pública de la otra parte antes de la ejecución del protocolo.

Para calcular el secreto compartido, Alice calcula $${\ displaystyle (S_ {ab}, \ sigma _ {ab}) = (m_ {A} Pub_ {B}, \ sigma _ {b}) * \ mathrm {B} _ {a}} y Bob calcula $${\ displaystyle (S_ {ba}, \ sigma {ba}) = (m_ {B} Pub_ {A}, \ sigma _ {a}) * \ mathrm {B} _ {b}}. El secreto compartido es el par matriz / permutación$${\ displaystyle (S_ {ab}, \ sigma _ {ab})}, que es igual $${\ displaystyle (S_ {ba}, \ sigma _ {ba})}. Los secretos compartidos son iguales porque los conjuntos conjugados$${\ displaystyle A} y $${\ displaystyle B} son elegidos para viajar y tanto Alice como Bob usan la misma matriz de semillas $${\ displaystyle M _ {*}} y valores T $${\ displaystyle \ mathrm {T}}.

La única información sobre su clave privada que Alice expone inicialmente es su clave pública. Por lo tanto, ninguna otra parte que Alice puede determinar la clave privada de Alice, a menos que esa parte pueda resolver el problema de Búsqueda de separación de conjugación simultánea de Braid Group. La clave privada de Bob es igualmente segura. Ninguna otra parte, excepto Alice o Bob, puede calcular el secreto compartido, a menos que esa parte pueda resolver el problema de Diffie-Hellman .

Las claves públicas son estáticas (y confiables, digamos a través de un certificado) o efímeras. Las claves efímeras son temporales y no necesariamente se autentican, por lo que si se desea la autenticación, se deben obtener garantías de autenticidad por otros medios. La autenticación es necesaria para evitar ataques de hombre en el medio . Si una de las claves públicas de Alice o Bob es estática, los ataques de intermediario se frustran. Las claves públicas estáticas no proporcionan confidencialidad directa ni resistencia a la suplantación de compromisos clave, entre otras propiedades de seguridad avanzadas. Los titulares de claves privadas estáticas deben validar la otra clave pública y deben aplicar una función de derivación de clave segura al secreto compartido sin procesar de Diffie-Hellman para evitar la filtración de información sobre la clave privada estática.

Seguridad [ editar ]

La seguridad de AE ​​se basa en el problema de búsqueda de conjugaciones simultáneas generalizadas (GSCSP) ^[4] dentro del grupo de trenzas . Este es un problema difícil distinto y diferente que el Problema de búsqueda de conjugaciones (CSP), que ha sido el problema central difícil en lo que se llama criptografía de grupo de trenzas . ^[5] Incluso si CSP se rompe uniformemente (lo que no se ha hecho hasta la fecha), no se sabe cómo esto facilitaría una ruptura de GSCSP.

Ataques conocidos [ editar ]

El primer ataque de Kalka, Teicher y Tsaban muestra una clase de llaves débiles cuando$${\ displaystyle M _ {*}} o $${\ displaystyle m_ {A}}son elegidos al azar ^[6] Los autores de Algebraic Eraser siguieron con una preimpresión sobre cómo elegir los parámetros que no son propensos al ataque. ^[7] Ben-Zvi, Blackburn y Tsaban mejoraron el primer ataque en uno que, según los autores, puede romper los parámetros de seguridad publicitados (se afirma que proporcionan seguridad de 128 bits) con menos de 8 horas de CPU y menos de 64 MB de memoria. ^[8] Anshel, Atkins y Goldfeld respondieron a este ataque en enero de 2016. ^[9]

Un segundo ataque de Myasnikov y Ushakov, publicado como preimpresión, muestra que los conjugados elegidos con una trenza de conjugación demasiado corta se pueden separar, rompiendo el sistema. ^[10] Este ataque fue refutado por Gunnells, al mostrar que las trenzas conjugadoras del tamaño adecuado no se pueden separar. ^[4]

En 2016, Simon R. Blackburn y Matthew JB Robshaw publicaron una serie de ataques prácticos contra el borrador de enero de 2016 del protocolo aéreo ISO / IEC 29167-20, incluida la suplantación de una etiqueta de destino con una cantidad insignificante de tiempo y memoria y recuperación completa de clave privada que requiere 2 ⁴⁹ veces y 2 ^{48 de} memoria. ^[11] Atkins y Goldfeld respondieron que agregar un código de autenticación de mensaje o hash al borrador del protocolo anula estos ataques.

secuencia algorítmicamente aleatoria (o secuencia aleatoria ) es una secuencia infinita de dígitos binarios que aparece ^{[se necesita aclaración ] al} azar para cualquier algoritmo. La noción se puede aplicar de manera análoga a secuencias en cualquier alfabeto finito (por ejemplo, dígitos decimales). Las secuencias aleatorias son objetos clave de estudio en la teoría de la información algorítmica .

Como a veces se consideran diferentes tipos de algoritmos, que van desde algoritmos con límites específicos en su tiempo de ejecución hasta algoritmos que pueden hacer preguntas a una máquina oráculo , existen diferentes nociones de aleatoriedad. El más común de estos se conoce como aleatoriedad de Martin-Löf (o aleatoriedad 1 ), pero también existen formas de aleatoriedad más fuertes y más débiles. El término "aleatorio" utilizado para referirse a una secuencia sin aclaración generalmente se toma como "aleatorio de Martin-Löf" (definido a continuación).

Debido a que se pueden identificar secuencias infinitas de dígitos binarios con números reales en el intervalo unitario, las secuencias binarias aleatorias a menudo se denominan números reales aleatorios . Además, las secuencias binarias infinitas corresponden a funciones características de conjuntos de números naturales; por lo tanto, esas secuencias pueden verse como conjuntos de números naturales.

La clase de todas las secuencias aleatorias (binarias) de Martin-Löf se denota por RAND o MLR.

Historia [ editar ]

La primera definición adecuada de una secuencia aleatoria fue dada por Per Martin-Löf en 1966. Investigadores anteriores como Richard von Mises habían intentado formalizar la noción de una prueba de aleatoriedad para definir una secuencia aleatoria como una que pasó todas las pruebas para aleatoriedad; sin embargo, la noción precisa de una prueba de aleatoriedad se dejó vaga. La idea clave de Martin-Löf fue utilizar la teoría de la computación para definir formalmente la noción de una prueba de aleatoriedad. Esto contrasta con la idea de aleatoriedad en la probabilidad ; en esa teoría, no se puede decir que ningún elemento particular de un espacio muestral sea aleatorio.

Desde su inicio, se ha demostrado que la aleatoriedad de Martin-Löf admite muchas caracterizaciones equivalentes, en términos de compresión , pruebas de aleatoriedad y juegos de azar , que tienen poca semejanza externa con la definición original, pero cada una de ellas satisface nuestra noción intuitiva de propiedades aleatorias. las secuencias deberían tener: las secuencias aleatorias deberían ser incompresibles, deberían pasar pruebas estadísticas de aleatoriedad y debería ser difícil ganar dinero apostandoen ellos. La existencia de estas múltiples definiciones de aleatoriedad de Martin-Löf, y la estabilidad de estas definiciones bajo diferentes modelos de computación, dan evidencia de que la aleatoriedad de Martin-Löf es una propiedad fundamental de las matemáticas y no un accidente del modelo particular de Martin-Löf. La tesis de que la definición de aleatoriedad de Martin-Löf "correctamente" captura la noción intuitiva de aleatoriedad se ha llamado la Tesis de Martin-Löf-Chaitin ; es algo similar a la tesis de la Iglesia-Turing . ^[1]

Tres definiciones equivalentes [ editar ]

La definición original de Martin-Löf de una secuencia aleatoria fue en términos de cubiertas nulas constructivas; definió una secuencia como aleatoria si no está contenida en ninguna de esas cubiertas. Leonid Levin y Claus-Peter Schnorr demostraron una caracterización en términos de complejidad de Kolmogorov : una secuencia es aleatoria si hay un límite uniforme en la compresibilidad de sus segmentos iniciales. Schnorr dio una tercera definición equivalente en términos de martingales . El libro de Li y Vitanyi, Introducción a la complejidad de Kolmogorov y sus aplicaciones, es la introducción estándar a estas ideas.

• Complejidad de Kolmogorov (Schnorr 1973, Levin 1973): la complejidad de Kolmogorov puede considerarse como un límite inferior en la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). Asigna a cada una de esas secuencias w un número natural K (w) que, intuitivamente, mide la longitud mínima de un programa de computadora (escrito en algún lenguaje de programación fijo) que no recibe entrada y dará salida wcuando corre Se requiere que la complejidad esté libre de prefijos: el programa (una secuencia de 0 y 1) es seguido por una cadena infinita de 0s, y la longitud del programa (suponiendo que se detenga) incluye el número de ceros a la derecha del programa que lee la máquina universal de Turing. El requisito adicional es necesario porque podemos elegir una longitud tal que la longitud codifique la información sobre la subcadena. Dado un número natural c y una secuencia w , decimos que w es c -compresible si$${\ displaystyle K (w) \ geq | w | -c}.

Una secuencia infinita S es aleatoria de Martin-Löf si y solo si hay una constante c tal que todos los prefijos finitos de S sean incompresibles en c .

• Cubiertas nulas constructivas (Martin-Löf 1966): esta es la definición original de Martin-Löf. Para una cadena binaria finita w, dejamos que C _w denote el cilindro generado por w . Este es el conjunto de todas las secuencias infinitas que comienzan con w , que es un conjunto abierto básico en el espacio de Cantor . La medida del producto μ ( C _w ) del cilindro generado por w se define como 2 ^{- | w |}. Cada subconjunto abierto del espacio de Cantor es la unión de una secuencia contable de conjuntos abiertos básicos disjuntos, y la medida de un conjunto abierto es la suma de las medidas de cualquier secuencia de este tipo. Un conjunto abierto efectivo es un conjunto abierto que es la unión de la secuencia de conjuntos abiertos básicos determinada por una secuencia recursivamente enumerable de cadenas binarias. Un conjunto constructivo de cobertura nula o medida efectiva 0 es una secuencia recursivamente enumerable$${\ displaystyle U_ {i}} de conjuntos abiertos efectivos tales que $${\ displaystyle U_ {i + 1} \ subseteq U_ {i}} y $${\ displaystyle \ mu (U_ {i}) \ leq 2 ^ {- i}}para cada número natural i . Cada cubierta nula efectiva determina un$${\ displaystyle G _ {\ delta}} conjunto de medida 0, es decir, la intersección de los conjuntos $${\ displaystyle U_ {i}}.

Una secuencia se define como Martin-Löf al azar si no está contenida en ninguna $${\ displaystyle G _ {\ delta}} conjunto determinado por una constructiva cubierta nula.

• Martingalas constructivas (Schnorr 1971): una martingala es una función$${\ displaystyle d: \ {0,1 \} ^ {*} \ a [0, \ infty)}tal que, para todas las cadenas finitas w ,$${\ displaystyle d (w) = (d (w ^ {\ smallfrown} 0) + d (w ^ {\ smallfrown} 1)) / 2}, dónde $${\ displaystyle a ^ {\ smallfrown} b}es la concatenación de las cadenas a y b . Esto se llama la "condición de equidad": si una martingala se ve como una estrategia de apuestas, entonces la condición anterior requiere que el apostador juegue contra probabilidades justas. Se dice que una martingala d tiene éxito en una secuencia S si$${\ displaystyle \ limsup _ {n \ to \ infty} d (S \ upharpoonright n) = \ infty,} dónde $${\ displaystyle S \ upharpoonright n}es los primeros n bits de S . A martingala d es constructiva (también conocido como computable débilmente , bajar semi-computable , subcomputable ) si existe una función computable$${\ displaystyle {\ widehat {d}}: \ {0,1 \} ^ {*} \ times \ mathbb {N} \ to {\ mathbb {Q}}}tal que, para todas las cadenas binarias finitas w

1. {\ displaystyle {\ widehat {d}} (w, t) \ leq {\ widehat {d}} (w, t + 1) para todos los enteros positivos t ,
2. $${\ displaystyle \ lim _ {t \ to \ infty} {\ widehat {d}} (w, t) = d (w).}

Una secuencia es aleatoria de Martin-Löf si y solo si ninguna martingala constructiva tiene éxito en ella.

Interpretaciones de las definiciones [ editar ]

La caracterización de la complejidad de Kolmogorov transmite la intuición de que una secuencia aleatoria es incompresible: ningún programa puede producir un prefijo mucho más corto que el prefijo.

La caracterización de la cubierta nula transmite la intuición de que un número real aleatorio no debe tener ninguna propiedad que sea "poco común". Cada conjunto de medidas 0 puede considerarse como una propiedad poco común. No es posible que una secuencia no se encuentre en conjuntos de medidas 0, porque cada conjunto de un punto tiene una medida 0. La idea de Martin-Löf era limitar la definición para medir conjuntos de 0 que se puedan describir efectivamente; la definición de una cobertura nula efectiva determina una colección contable de conjuntos de medidas 0 que se pueden describir de manera efectiva y define una secuencia como aleatoria si no se encuentra en ninguno de estos conjuntos de medidas 0 particulares. Dado que la unión de una colección contable de conjuntos de medidas 0 tiene la medida 0, esta definición lleva inmediatamente al teorema de que hay un conjunto de secuencias aleatorias de la medida 1.Medida de Lebesgue .

La caracterización de martingala transmite la intuición de que ningún procedimiento efectivo debería ser capaz de ganar dinero apostando contra una secuencia aleatoria. Una martingala d es una estrategia de apuestas. d lee una cadena finita w y apuesta dinero en el siguiente bit. Apuesta una fracción de su dinero a que el próximo bit será 0, y luego el resto de su dinero a que el siguiente bit será 1. d duplica el dinero que colocó en el bit que realmente ocurrió, y pierde el resto. d ( w ) es la cantidad de dinero que tiene después de ver la cadena w . Dado que la apuesta realizada después de ver la cadena w se puede calcular a partir de los valores d (w ), d ( w 0) yd ( w 1), calcular la cantidad de dinero que tiene es equivalente a calcular la apuesta. La caracterización de martingala dice que ninguna estrategia de apuestas implementable por cualquier computadora (incluso en el sentido débil de las estrategias constructivas, que no son necesariamente computables ) puede hacer que el dinero apueste en una secuencia aleatoria.

Propiedades y ejemplos de secuencias aleatorias de Martin-Löf [ editar ]

• La probabilidad de detención de Chaitin Ω es un ejemplo de una secuencia aleatoria.
• RAND ^c (el complemento de RAND) es un subconjunto de medida 0 del conjunto de todas las secuencias infinitas. Esto está implícito en el hecho de que cada cubierta nula constructiva cubre un conjunto de medidas 0, solo hay contablemente muchas cubiertas nulas constructivas, y una unión contable de conjuntos de medidas 0 tiene la medida 0. Esto implica que RAND es un subconjunto de medidas 1 del conjunto de todas las secuencias infinitas.
• Cada secuencia aleatoria es normal .
• Hay una cubierta nula constructiva de RAND ^c . Esto significa que todas las pruebas efectivas de aleatoriedad (es decir, cubiertas nulas constructivas) están, en cierto sentido, incluidas en esta prueba universal de aleatoriedad, ya que cualquier secuencia que pase esta prueba única de aleatoriedad pasará todas las pruebas de aleatoriedad. (Martin-Löf 1966)
• Hay una martingala constructiva universal d . Esta martingala es universal en el sentido de que, dada cualquier martingala constructiva d , si d tiene éxito en una secuencia, d también tiene éxito en esa secuencia. Por lo tanto, d tiene éxito en cada secuencia en RAND ^c (pero, dado que d es constructivo, no tiene éxito en ninguna secuencia en RAND). (Schnorr 1971)
• La clase RAND es un $${\ displaystyle \ Sigma _ {2} ^ {0}} subconjunto del espacio de Cantor, donde $${\ displaystyle \ Sigma _ {2} ^ {0}}se refiere al segundo nivel de la jerarquía aritmética . Esto se debe a que una secuencia S está en RAND si y solo si hay un conjunto abierto en la cubierta nula efectiva universal que no contiene S ; esta propiedad puede verse como definible por un$${\ displaystyle \ Sigma _ {2} ^ {0}} fórmula.
• Hay una secuencia aleatoria que es $${\ displaystyle \ Delta _ {2} ^ {0}}, es decir, computable en relación con un oráculo para el problema de detención. (Schnorr 1971) El Ω de Chaitin es un ejemplo de tal secuencia.
• Ninguna secuencia aleatoria es decidible , computablemente enumerable o co-computablemente enumerable . Dado que estos corresponden a la$${\ displaystyle \ Delta _ {1} ^ {0}}, $${\ displaystyle \ Sigma _ {1} ^ {0}}y $${\ displaystyle \ Pi _ {1} ^ {0}}niveles de la jerarquía aritmética , esto significa que$${\ displaystyle \ Delta _ {2} ^ {0}} es el nivel más bajo en la jerarquía aritmética donde se pueden encontrar secuencias aleatorias.
• Cada secuencia es Turing reducible a alguna secuencia aleatoria. (Kučera 1985/1989, Gács 1986). Por lo tanto, hay secuencias aleatorias de alto grado de Turing arbitrariamente .

Aleatoriedad relativa [ editar ]

Como cada una de las definiciones equivalentes de una secuencia aleatoria de Martin-Löf se basa en lo que es computable por una máquina de Turing, uno puede naturalmente preguntar qué es computable por una máquina de oráculo de Turing . Para un oráculo fijo A , se dice que una secuencia B que no solo es aleatoria sino que, de hecho, satisface las definiciones equivalentes de computabilidad en relación con A (por ejemplo, ninguna martingala que es constructiva en relación con el oráculo A tiene éxito en B ) se dice que es aleatoria relativa a Una . Dos secuencias, si bien al azar, pueden contener información muy similar y, por lo tanto, ninguna será aleatoria en relación con la otra. Cada vez que hay una reducción de Turingde una secuencia a otra, la segunda secuencia no puede ser aleatoria en relación con la primera, así como las secuencias computables no son aleatorias; en particular, esto significa que el Ω de Chaitin no es aleatorio en relación con el problema de detención .

Un resultado importante relacionado con la aleatoriedad relativa es el teorema de van Lambalgen , que establece que si C es la secuencia compuesta de A y B al intercalar el primer bit de A , el primer bit de B , el segundo bit de A , el segundo bit de B , y así sucesivamente, entonces C es algorítmicamente aleatorio si y sólo si a es algorítmicamente azar, y B es algorítmicamente aleatorio en relación con a . Una consecuencia estrechamente relacionada es que si A y B son aleatorios, entonces Aes aleatorio con respecto a B si y sólo si B es aleatorio con respecto a A .

Más fuerte que la aleatoriedad de Martin-Löf [ editar ]

Aleatoriedad relativa nos da la primera noción que es más fuerte que Martin-Löf aleatoriedad, que es la aleatoriedad en relación con algún oráculo fijo Una . Para cualquier oráculo, esto es al menos tan fuerte, y para la mayoría de los oráculos, es estrictamente más fuerte, ya que habrá secuencias aleatorias Martin-Löf que no son al azar en relación con el oráculo A . Los oráculos importantes que a menudo se consideran son el problema de detención,$${\ displaystyle \ emptyset '}Y el n º oráculo salto,$${\ displaystyle \ emptyset ^ {(n)}}, ya que estos oráculos pueden responder preguntas específicas que surgen naturalmente. Una secuencia que es aleatoria en relación con el oráculo.$${\ displaystyle \ emptyset ^ {(n-1)}}se llama n- aleatorio; una secuencia es 1 aleatoria, por lo tanto, si y solo si es Martin-Löf aleatorio. Una secuencia que es n- aleatoria para cada n se llama aritméticamente aleatoria. Las secuencias n- aleatorias a veces surgen cuando se consideran propiedades más complicadas. Por ejemplo, solo hay innumerables$${\ displaystyle \ Delta _ {2} ^ {0}}conjuntos, por lo que uno podría pensar que estos deberían ser no aleatorios. Sin embargo, la probabilidad de detención Ω es$${\ displaystyle \ Delta _ {2} ^ {0}}y 1 al azar; es solo después de que se alcanza la aleatoriedad 2 que es imposible que un conjunto aleatorio sea$${\ displaystyle \ Delta _ {2} ^ {0}}.

Aleatoriedad más débil que Martin-Löf [ editar ]

Además, hay varias nociones de aleatoriedad que son más débiles que la aleatoriedad de Martin-Löf. Algunos de estos son aleatoriedad débil de 1, aleatoriedad de Schnorr, aleatoriedad computable, aleatoriedad computable parcial. Yongge Wang mostró ^[2] que la aleatoriedad de Schnorr es diferente de la aleatorización computable. Además, se sabe que la aleatoriedad de Kolmogorov-Loveland no es más fuerte que la aleatoriedad de Martin-Löf, pero no se sabe si en realidad es más débil.

En el extremo opuesto del espectro de aleatoriedad existe la noción de un conjunto K-trivial . Estos conjuntos son antirandom en que todos los segmentos iniciales tienen la menor complejidad K hasta una constante b. Es decir,$${\ displaystyle K (w) \ leq K (| w |) + b} para cada segmento inicial w.