One-out-of-q OT Combiners

Abstract

In 1-out-of-q Oblivious Transfer (OT) protocols, a sender is able to send one of q>=2 messages to a receiver, all while being oblivious to which message was actually transferred. Moreover, the receiver only learns one of these messages. OT protocols are fundamental cryptographic primitives, as they are used in several cryptographic constructions. Since perfectly secure OT protocols cannot be achieved, they must rely on security assumptions. To mitigate security concerns, one can aim at grounding their security in various assumptions at once. Oblivious Transfer combiners realize this by taking as input a set OT implementations, and producing a single protocol that is secure if sufficiently many of the original implementations are secure. Hence, the security of the resulting protocol holds even in the case that few of the OT implementations are insecure. Previous works on OT combiners address the q=2 case. Here, we present an OT combiner for the case where q>=2 is an arbitrary prime power. Our construction achieves the strong notion of perfect security against active (A,B)-adversaries. For q>2, we prove security against a larger class of adversaries than in previous works. If q is at least the number of used OT candidates, our construction is secure against active adversaries in the honest majority setting, improving on the previously studied q=2 case. The OT construction is based on secret sharing schemes that are of independent interest.

Els protocols de transferència inconscient (OT) 1-de-q permeten a un emissor enviar un de q>=2 missatges a un receptor, de manera que l'emissor desconeix quin dels missatges s'acaba transferint. A més, el receptor només pot rebre informació sobre un dels q missatges. Els protocols OT són primitives criptogràfiques fonamentals, ja que s'utilitzen a diverses construccions criptogràfiques. Atès que és impossible assolir protocols OT amb seguretat perfecta, és necessari basar la seguretat en assumpcions. Per tal de mitigar els problemes de seguretat que se'n poden derivar, una opció consisteix en basar la seguretat en diverses assumpcions a la vegada. Els combinadors OT assoleixen aquest objectiu, prenent com a entrada un conjunt d'implementacions OT, i produïnt un únic protocol la seguretat del qual es garanteix si s'assumeix la seguretat d'una quantitat suficient de les implementacions originals. Per tant, el protocol resultant seria segur fins i tot en el cas que part de les implementacions OT originals fossin insegures. Els treballs previs en combinadors OT tracten el cas q=2. En aquest treball, presentem un combinador OT pel cas on q>=2 és una potència arbitrària d'un nombre primer. La nostra construcció assoleix la noció de seguretat perfecta contra (A,B)-adversaris actius. Per q>2, demostrem la seguretat contra una classe d'adversaris més gran que en treballs anteriors. Si q és més gran o igual que el nombre de candidats OT usats, la nostra construcció és segura contra adversaris actius en el cas de majoria honesta, fet que millora el cas q=2 estudiat prèviament. La construcció OT es basa en esquemes de compartició de secrets que són d'interès independent.

Los protocolos de transferencia inconsciente (OT) 1-de-q permiten a un emisor enviar uno de q>=2 mensajes a un receptor, de manera que el emisor desconoce cual de los mensajes acaba transfiriéndose. Además, el receptor solamente recibe información sobre uno de los q mensajes. Los protocolos OT son primitivas criptográficas fundamentales, ya que se utilizan en varias construcciones criptográficas. Dado que es construir protocolos OT con seguridad perfecta es imposible, se necesita basar la seguridad en asunciones. Para mitigar los problemas de seguridad que pueden derivarse, una opción consiste en basar la seguridad en varias asunciones a la vez. Los combinadores OT consiguen este objetivo, tomando como entrada un conjunto de implementaciones OT, y produciendo un único protocolo cuya seguridad se garantiza si se asume la seguridad de una cantidad suficiente de las implementaciones originales. Por lo tanto, el protocolo resultante sería seguro incluso en el caso de que una cantidad limitada de las implementaciones OT originales fueran inseguras. Los trabajos previos en combinadores OT tratan el caso q=2. En este trabajo, presentamos un combinador OT para el caso donde q>=2 es una potencia arbitraria de un número primo. Nuestra construcción cumple la noción de seguridad perfecta contra (A,B)-adversarios activos. Para q>2, demostramos la seguridad contra una clase de adversarios mayor que en trabajos anteriores. Si q es mayor o igual que el número de candidatos OT usados, nuestra construcción es segura contra adversarios activos en el caso de mayoría honesta, hecho que mejora el caso q=2 estudiado previamente. La construcción OT se basa en esquemas de compartición de secretos de interés independiente.