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

IEEE International Symposium on Information Theory (ISIT)

Secret function sharing schernes and their applications to the oblivious transfer

Yohei Kawamoto, H. Yamamoto

Published Jan 1, 2003• 4 citations
Publisher

Abstract

Secret function sharing schemes (SFSS), .which are first studied in (l), are defined and analyzed information theoretically. They are also extended to ramp schemes in the same way as (2). Furthermore, it is shown that an unconditionally secure distributed oblivious transfer (OT) protocol is constructed by combining the SFSS with multi-groups secret sharing scheme (MG-SSS) (3) and the protocol is more robust against collusion attacks than that shown in (4).

DOI
10.1109/isit.2003.1228296

Related papers

Exploratory designs of unconditionally secure distributed oblivious transfer protocols

Christian L. F. Corniaux

The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.

•Oct 26, 2022•0 citations

Shared OT and Its Applications

Lucas Piske, Jeroen van de Graaf, Anderson C. A. Nascimento +1 more

We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest. Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds.

IACR Communications in Cryptology•Jul 7, 2025•0 citations

Supersonic OT: Fast Unconditionally Secure Oblivious Transfer

Aydin Abadi, Yvo Desmedt

Oblivious Transfer (OT) is a fundamental cryptographic protocol with applications in secure Multi-Party Computation, Federated Learning, and Private Set Intersection. With the advent of quantum computing, it is crucial to develop unconditionally secure core primitives like OT to ensure their continued security in the post-quantum era. Despite over four decades since OT's introduction, the literature has predominantly relied on computational assumptions, except in cases using unconventional methods like noisy channels or a fully trusted party. Introducing "Supersonic OT", a highly efficient and unconditionally secure OT scheme that avoids public-key-based primitives, we offer an alternative to traditional approaches. Supersonic OT enables a receiver to obtain a response of size O(1). Its simple (yet non-trivial) design facilitates easy security analysis and implementation. The protocol employs a basic secret-sharing scheme, controlled swaps, the one-time pad, and a third-party helper who may be corrupted by a semi-honest adversary. Our implementation and runtime analysis indicate that a single instance of Supersonic OT completes in 0.35 milliseconds, making it up to 2000 times faster than the state-of-the-art base OT.

arXiv:2406.15529•Jun 21, 2024•0 citations

On Distributed Oblivious Transfer

Ventzislav Nikov, Svetla Nikova⋆, Bart Preneel A

This paper is about unconditionally secure distributed protocols for oblivious transfer, as proposed by Naor and Pinkas and generalized by Blundo et al. In this setting a Sender has ζ secrets and a Receiver is interested in one of them. The Sender distributes the information about the secrets to n servers, and a Receiver must contact a threshold of the servers in order to compute the secret. We present a non-existence result and a lower bound for the existence of one-round, threshold, distributed oblivious transfer protocols, generalizing the results of Blundo et al. A threshold based construction implementing 1-out-of-ζ distributed oblivious transfer achieving this lower bound is described. A condition for existence of distributed oblivious transfer schemes based on general access structures is proven. We also present a general access structure protocol implementing 1-out-of-ζ distributed oblivious transfer.

Serdica Journal of Computing•Sep 26, 2007•1 citation

Resource-Efficient OT Combiners with Active Security

Ignacio Cascudo, Ivan Damgård, Oriol Farràs +1 more

An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.

Lecture notes in computer science•Jan 1, 2017•6 citations

Efficient Threshold Function Secret Sharing With Information-Theoretic Security

Jinglong Luo, Liang Feng Zhang, Fuchun Lin +1 more

Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.

IEEE Access•Jan 1, 2020•7 citations
Secret function sharing schemes (SFSS), .which are first studied in (l), are defined and analyzed information theoretically. They are also extended to ramp schemes in the same way as (2). Furthermore, it is shown that an unconditionally secure distributed oblivious transfer (OT) protocol is constructed by combining the SFSS with multi-groups secret sharing scheme (MG-SSS) (3) and the protocol is more robust against collusion attacks than that shown in (4).
The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.
We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest. Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds.
Oblivious Transfer (OT) is a fundamental cryptographic protocol with applications in secure Multi-Party Computation, Federated Learning, and Private Set Intersection. With the advent of quantum computing, it is crucial to develop unconditionally secure core primitives like OT to ensure their continued security in the post-quantum era. Despite over four decades since OT's introduction, the literature has predominantly relied on computational assumptions, except in cases using unconventional methods like noisy channels or a fully trusted party. Introducing "Supersonic OT", a highly efficient and unconditionally secure OT scheme that avoids public-key-based primitives, we offer an alternative to traditional approaches. Supersonic OT enables a receiver to obtain a response of size O(1). Its simple (yet non-trivial) design facilitates easy security analysis and implementation. The protocol employs a basic secret-sharing scheme, controlled swaps, the one-time pad, and a third-party helper who may be corrupted by a semi-honest adversary. Our implementation and runtime analysis indicate that a single instance of Supersonic OT completes in 0.35 milliseconds, making it up to 2000 times faster than the state-of-the-art base OT.
This paper is about unconditionally secure distributed protocols for oblivious transfer, as proposed by Naor and Pinkas and generalized by Blundo et al. In this setting a Sender has ζ secrets and a Receiver is interested in one of them. The Sender distributes the information about the secrets to n servers, and a Receiver must contact a threshold of the servers in order to compute the secret. We present a non-existence result and a lower bound for the existence of one-round, threshold, distributed oblivious transfer protocols, generalizing the results of Blundo et al. A threshold based construction implementing 1-out-of-ζ distributed oblivious transfer achieving this lower bound is described. A condition for existence of distributed oblivious transfer schemes based on general access structures is proven. We also present a general access structure protocol implementing 1-out-of-ζ distributed oblivious transfer.
An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.