In a recent quantum oblivious transfer protocol proposed by Nagy et al., it was proven that attacks based on individual measurements and 2-qubit entanglement can all be defeated. Later we found that 5-body entanglemen...In a recent quantum oblivious transfer protocol proposed by Nagy et al., it was proven that attacks based on individual measurements and 2-qubit entanglement can all be defeated. Later we found that 5-body entanglement-based attacks can break the protocol. Here we further tighten the security bound, by showing that the protocol is insecure against 4-body entanglement-based attacks, while being immune to 3-body entanglement-based attacks. Also, increasing the number of qubits in the protocol is useless for improving its security.展开更多
In cryptography,oblivious transfer(OT)is an important multiparty cryptographic primitive and protocol,that is suitable for many upperlayer applications,such as secure computation,remote coin-flipping,electrical contra...In cryptography,oblivious transfer(OT)is an important multiparty cryptographic primitive and protocol,that is suitable for many upperlayer applications,such as secure computation,remote coin-flipping,electrical contract signing and exchanging secrets simultaneously.However,some nogo theorems have been established,indicating that one-out-of-two quantum oblivious transfer(QOT)protocols with unconditional security are impossible.Fortunately,some one-out-of-two QOT protocols using the concept of Crepeau’s reduction have been demonstrated not to conform to Lo’s no-go theorem,but these protocols require more quantum resources to generate classical keys using all-or-nothing QOT to construct one-out-of-two QOT.This paper proposes a novel and efficient one-out-of-two QOT which uses quantum resources directly instead of wasting unnecessary resources to generate classical keys.The proposed protocol is not covered by Lo’s no-go theorem,and it is able to check the sender’s loyalty and avoid the attack from the receiver.Moreover,the entangled state of the proposed protocol is reusable,so it can provide more services for the participants when necessary.Compared with otherQOT protocols,the proposed protocol is more secure,efficient,and flexible,which not only can prevent external and internal attacks,but also reduce the required resources and resource distribution time.展开更多
Oblivious transfer （OT） protocol is a fundamental cryptographical tool and widely used as a building block of secure computation. In this work, we propose two efficient t-out-of-n oblivious transfer schemes with the...Oblivious transfer （OT） protocol is a fundamental cryptographical tool and widely used as a building block of secure computation. In this work, we propose two efficient t-out-of-n oblivious transfer schemes with the designated receiver. A common advantage of the two schemes is efficient. The total computation cost of the sender and the receiver is n ＋ 2t ＋ 1 modular exponentiations in first scheme that is three-round, and the total one of the sender and receiver is n ＋ 3t modular exponentiations in second scheme that is two-round. Another advantage of both schemes is designable.展开更多
In ACM'CCS 2009,Camenisch,et al.proposed the Oblivious Transfer with Access Control(AC-OT) in which each item is associated with an attribute set and can only be available,on request,to the users who have all the ...In ACM'CCS 2009,Camenisch,et al.proposed the Oblivious Transfer with Access Control(AC-OT) in which each item is associated with an attribute set and can only be available,on request,to the users who have all the attributes in the associated set.Namely,AC-OT achieves access control policy for conjunction of attributes.Essentially,the functionality of AC-OT is equivalent to the sim-plified version that we call AC-OT-SV:for each item,one attribute is associated with it,and it is requested that only the users who possess the associated attribute can obtain the item by queries.On one hand,AC-OT-SV is a special case of AC-OT when there is just one associated attribute with each item.On the other hand,any AC-OT can be realized by an AC-OT-SV.In this paper,we first present a concrete AC-OT-SV protocol which is proved to be secure in the model defined by Camenisch,et al..Then from the protocol,interestingly,a concrete Identity-Based Encryption(IBE) with Anonymous Key Issuing(AKI) is given which is just a direct application to AC-OT-SV.By comparison,we show that the AKI protocol we present is more efficient in communications than that proposed by Chow.展开更多
Function secret sharing(FSS)is a secret sharing technique for functions in a specific function class,mainly including distributed point function(DPF)and distributed comparison function(DCF).As an important basis for f...Function secret sharing(FSS)is a secret sharing technique for functions in a specific function class,mainly including distributed point function(DPF)and distributed comparison function(DCF).As an important basis for function secret sharing,DPF and DCF are the foundation for the extension of this technique to other more general and complex function classes.However,the function classes corresponding to the current DPF and DCF schemes are almost all unary function classes,and there is no efficient construction for multivariate function classes.The applications of FSS can be extended with the development of a multivariate scheme,e.g.,a multi-keyword private information retrieval scheme can be constructed.To solve this problem,this paper presents a binary DCF scheme based on the“two-layer binary tree”structure.In a binary tree structure,each node computes the seed of its child nodes based on its own seed.The key technique is to realize the transition transfer of seeds by using oblivious transfer,to connect two unary structures.Theoretical analysis and experimental results show that our binary scheme changes from single-round communication in the original definition to multiround communication,and has great advantages in communication cost and computation efficiency.For the security parameterλand input length n,the key size is reduced from to O(λn^(2))to O(λn)In addition,we explore the extensions and applications of the above method.In the batch computation,this paper uses oblivious transfer(OT)extension to realize the one-time transmission of multiple pairs of seeds and optimize its communication efficiency.By extending the structure from“two-layer”to“multi-layer”,a secret sharing scheme of multivariate mixed basic function is proposed based on the serial thought.Furthermore,by employing the parallel thought,a general 2-layer FSS structure from OT for multivariate mixed basic functions is explored to enhance the efficiency,where the first layer is composed of d parallel binary trees with d representing the input dimension,and the second layer is one binary tree of depth d.And the applications of our schemes in multi-keyword private information retrieval are presented.展开更多
Because of the concise functionality of oblivious transfer （OT） protocols, they have been widely used as building blocks in secure multiparty computation and high-level protocols. The security of OT protocols built ...Because of the concise functionality of oblivious transfer （OT） protocols, they have been widely used as building blocks in secure multiparty computation and high-level protocols. The security of OT protocols built upon classical number theoretic problems, such as the discrete logarithm and factoring, however, is threatened as a result of the huge progress in quantum computing. Therefore, post-quantum cryptography is needed for protocols based on classical problems, and several proposals for post-quantum OT protocols exist. However, most post-quantum cryptosystems present their security proof only in the context of classical adversaries, not in the quantum setting. In this paper, we close this gap and prove the security of the lattice-based OT protocol proposed by Peikert et al. （CRYPTO, 2008）, which is universally composably secure under the assumption of learning with errors hardness, in the quantum setting. We apply three general quantum security analysis frameworks. First, we apply the quantum lifting theorem proposed by Unruh （EUROCRYPT, 2010） to prove that the security of the lattice-based OT protocol can be lifted into the quantum world. Then, we apply two more security analysis frameworks specified for post-quantum cryptographic primitives, i.e., simple hybrid arguments （CRYPTO, 2011） and game-preserving reduction （PQCrypto, 2014）.展开更多
A new secure oblivious transfer （OT） protocol from indistinguishability obfuscation （iO） is proposed in this paper. The candidate iO and a dual-mode cryptosystem are the main technical tools of this scheme. Garg e...A new secure oblivious transfer （OT） protocol from indistinguishability obfuscation （iO） is proposed in this paper. The candidate iO and a dual-mode cryptosystem are the main technical tools of this scheme. Garg et al. introduced a candidate construction of iO in 2013. Following their steps, a new k-out-of-1 OT protocol is presented here, and its realization from decisional Diffie-Hellman （DDH） is described in this paper, in which iO was combined with the dual-mode cryptosystem. The security of the scheme mainly relies on the indistinguishability of the obf-branches （corresponding to the two modes in dual-mode model）. This paper explores a new way for the application of iO.展开更多
The problem of two-party oblivious polynomial evaluation (OPE) is studied, where one party (Alice) has a polynomial P(x) and the other party (Bob) with an input x wants to learn P(x) in such an oblivious way that Bob ...The problem of two-party oblivious polynomial evaluation (OPE) is studied, where one party (Alice) has a polynomial P(x) and the other party (Bob) with an input x wants to learn P(x) in such an oblivious way that Bob obtains P(x) without learning any additional information about P except what is implied by P(x) and Alice does not know Bob's input x. The former OPE protocols are based on an intractability assumption except for OT protocols. In fact, evaluating P(x) is equivalent to computing the product of the coefficient vectors (a(0),...,a(n)) and (1,...,x(n)). Using this idea, an efficient scale product protocol of two vectors is proposed first and then two OPE protocols are presented which do not need any other cryptographic assumption except for OT protocol. Compared with the existing OPE protocol, another characteristic of the proposed protocols is the degree of the polynomial is private. Another OPE protocol works in case of existence of untrusted third party. Keywords oblivious polynomial evaluation, oblivious transfer, secure multi-party computation, information.展开更多
Privacy-Preserving Computation(PPC)comprises the techniques,schemes and protocols which ensure privacy and confidentiality in the context of secure computation and data analysis.Most of the current PPC techniques rely...Privacy-Preserving Computation(PPC)comprises the techniques,schemes and protocols which ensure privacy and confidentiality in the context of secure computation and data analysis.Most of the current PPC techniques rely on the complexity of cryptographic operations,which are expected to be efficiently solved by quantum computers soon.This review explores how PPC can be built on top of quantum computing itself to alleviate these future threats.We analyze quantum proposals for Secure Multi-party Computation,Oblivious Transfer and Homomorphic Encryption from the last decade focusing on their maturity and the challenges they currently face.Our findings show a strong focus on purely theoretical works,but a rise on the experimental consideration of these techniques in the last 5 years.The applicability of these techniques to actual use cases is an underexplored aspect which could lead to the practical assessment of these techniques.展开更多
Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a c...Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric. problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.展开更多
Secure multi-party computation(MPC)allows a set of parties to jointly compute a function on their private inputs,and reveals nothing but the output of the function.In the last decade,MPC has rapidly moved from a purel...Secure multi-party computation(MPC)allows a set of parties to jointly compute a function on their private inputs,and reveals nothing but the output of the function.In the last decade,MPC has rapidly moved from a purely theoretical study to an object of practical interest,with a growing interest in practical applications such as privacy-preserving machine learning(PPML).In this paper,we comprehensively survey existing work on concretely ecient MPC protocols with both semi-honest and malicious security,in both dishonest-majority and honest-majority settings.We focus on considering the notion of security with abort,meaning that corrupted parties could prevent honest parties from receiving output after they receive output.We present high-level ideas of the basic and key approaches for designing di erent styles of MPC protocols and the crucial building blocks of MPC.For MPC applications,we compare the known PPML protocols built on MPC,and describe the eciency of private inference and training for the state-of-the-art PPML protocols.Further-more,we summarize several challenges and open problems to break though the eciency of MPC protocols as well as some interesting future work that is worth being addressed.This survey aims to provide the recent development and key approaches of MPC to researchers,who are interested in knowing,improving,and applying concretely ecient MPC protocols.展开更多
文摘In a recent quantum oblivious transfer protocol proposed by Nagy et al., it was proven that attacks based on individual measurements and 2-qubit entanglement can all be defeated. Later we found that 5-body entanglement-based attacks can break the protocol. Here we further tighten the security bound, by showing that the protocol is insecure against 4-body entanglement-based attacks, while being immune to 3-body entanglement-based attacks. Also, increasing the number of qubits in the protocol is useless for improving its security.
基金supported in part by the Ministry of Science and Technology(MOST)in Taiwan under Grants MOST108-2638-E-002-002-MY2,MOST109-2222-E-005-002-MY3,MOST110-2627-M-002-002,MOST110-2221-E-260-014,MOST110-2222-E-006-011,MOST111-2218-E-005-007-MBK,and MOST111-2119-M-033-001supported in part by Higher Education Sprout Project,Ministry of Education to the Headquarters of University Advancement at National Cheng Kung University.
文摘In cryptography,oblivious transfer(OT)is an important multiparty cryptographic primitive and protocol,that is suitable for many upperlayer applications,such as secure computation,remote coin-flipping,electrical contract signing and exchanging secrets simultaneously.However,some nogo theorems have been established,indicating that one-out-of-two quantum oblivious transfer(QOT)protocols with unconditional security are impossible.Fortunately,some one-out-of-two QOT protocols using the concept of Crepeau’s reduction have been demonstrated not to conform to Lo’s no-go theorem,but these protocols require more quantum resources to generate classical keys using all-or-nothing QOT to construct one-out-of-two QOT.This paper proposes a novel and efficient one-out-of-two QOT which uses quantum resources directly instead of wasting unnecessary resources to generate classical keys.The proposed protocol is not covered by Lo’s no-go theorem,and it is able to check the sender’s loyalty and avoid the attack from the receiver.Moreover,the entangled state of the proposed protocol is reusable,so it can provide more services for the participants when necessary.Compared with otherQOT protocols,the proposed protocol is more secure,efficient,and flexible,which not only can prevent external and internal attacks,but also reduce the required resources and resource distribution time.
基金Supported by Scientific Research Common Programof Beijing Municipal Commission of Education ( KM200610009011)Open Fund of State Key Laboratory of Information Security(Institute of Software of Chinese Academy of Sciences) (02-4)
文摘Oblivious transfer （OT） protocol is a fundamental cryptographical tool and widely used as a building block of secure computation. In this work, we propose two efficient t-out-of-n oblivious transfer schemes with the designated receiver. A common advantage of the two schemes is efficient. The total computation cost of the sender and the receiver is n ＋ 2t ＋ 1 modular exponentiations in first scheme that is three-round, and the total one of the sender and receiver is n ＋ 3t modular exponentiations in second scheme that is two-round. Another advantage of both schemes is designable.
文摘In ACM'CCS 2009,Camenisch,et al.proposed the Oblivious Transfer with Access Control(AC-OT) in which each item is associated with an attribute set and can only be available,on request,to the users who have all the attributes in the associated set.Namely,AC-OT achieves access control policy for conjunction of attributes.Essentially,the functionality of AC-OT is equivalent to the sim-plified version that we call AC-OT-SV:for each item,one attribute is associated with it,and it is requested that only the users who possess the associated attribute can obtain the item by queries.On one hand,AC-OT-SV is a special case of AC-OT when there is just one associated attribute with each item.On the other hand,any AC-OT can be realized by an AC-OT-SV.In this paper,we first present a concrete AC-OT-SV protocol which is proved to be secure in the model defined by Camenisch,et al..Then from the protocol,interestingly,a concrete Identity-Based Encryption(IBE) with Anonymous Key Issuing(AKI) is given which is just a direct application to AC-OT-SV.By comparison,we show that the AKI protocol we present is more efficient in communications than that proposed by Chow.
基金supported by National Key R&D Program of China(No.2022ZD0161901)the National Natural Science Foundation of China(Grant No.62072023)+3 种基金Beijing Natural Science Foundation(No.4242024)the Open Project Fund of the State Key Laboratory of Cryptology,China(No.MMKFKT202120)the Exploratory Optional Project Fund of the State Key Laboratory of Complex&Critical Software Environment(No.SKLCCSE-2025ZX-XX)the Fundamental Research Funds of Beihang University,China(Nos.YWF-21-BJ-J-1041 and YWF-23-L-1033).
文摘Function secret sharing(FSS)is a secret sharing technique for functions in a specific function class,mainly including distributed point function(DPF)and distributed comparison function(DCF).As an important basis for function secret sharing,DPF and DCF are the foundation for the extension of this technique to other more general and complex function classes.However,the function classes corresponding to the current DPF and DCF schemes are almost all unary function classes,and there is no efficient construction for multivariate function classes.The applications of FSS can be extended with the development of a multivariate scheme,e.g.,a multi-keyword private information retrieval scheme can be constructed.To solve this problem,this paper presents a binary DCF scheme based on the“two-layer binary tree”structure.In a binary tree structure,each node computes the seed of its child nodes based on its own seed.The key technique is to realize the transition transfer of seeds by using oblivious transfer,to connect two unary structures.Theoretical analysis and experimental results show that our binary scheme changes from single-round communication in the original definition to multiround communication,and has great advantages in communication cost and computation efficiency.For the security parameterλand input length n,the key size is reduced from to O(λn^(2))to O(λn)In addition,we explore the extensions and applications of the above method.In the batch computation,this paper uses oblivious transfer(OT)extension to realize the one-time transmission of multiple pairs of seeds and optimize its communication efficiency.By extending the structure from“two-layer”to“multi-layer”,a secret sharing scheme of multivariate mixed basic function is proposed based on the serial thought.Furthermore,by employing the parallel thought,a general 2-layer FSS structure from OT for multivariate mixed basic functions is explored to enhance the efficiency,where the first layer is composed of d parallel binary trees with d representing the input dimension,and the second layer is one binary tree of depth d.And the applications of our schemes in multi-keyword private information retrieval are presented.
基金Project supported by the National Key R&D Program of China(No.2017YFB0802000)the National Natural Science Foundation of China(Nos.61672412,61472309,and 61572390)the China Scholarship Council(No.201406960041)
文摘Because of the concise functionality of oblivious transfer （OT） protocols, they have been widely used as building blocks in secure multiparty computation and high-level protocols. The security of OT protocols built upon classical number theoretic problems, such as the discrete logarithm and factoring, however, is threatened as a result of the huge progress in quantum computing. Therefore, post-quantum cryptography is needed for protocols based on classical problems, and several proposals for post-quantum OT protocols exist. However, most post-quantum cryptosystems present their security proof only in the context of classical adversaries, not in the quantum setting. In this paper, we close this gap and prove the security of the lattice-based OT protocol proposed by Peikert et al. （CRYPTO, 2008）, which is universally composably secure under the assumption of learning with errors hardness, in the quantum setting. We apply three general quantum security analysis frameworks. First, we apply the quantum lifting theorem proposed by Unruh （EUROCRYPT, 2010） to prove that the security of the lattice-based OT protocol can be lifted into the quantum world. Then, we apply two more security analysis frameworks specified for post-quantum cryptographic primitives, i.e., simple hybrid arguments （CRYPTO, 2011） and game-preserving reduction （PQCrypto, 2014）.
基金supported by Opening Project of State Key Laboratory of Cryptology, Scientific Research and Postgraduate Training Cooperation Project-Scientific Research Base-New Theory of Block Cipher and Obfuscation and their Application Research, and Information Management and Professional Building of Information System
文摘A new secure oblivious transfer （OT） protocol from indistinguishability obfuscation （iO） is proposed in this paper. The candidate iO and a dual-mode cryptosystem are the main technical tools of this scheme. Garg et al. introduced a candidate construction of iO in 2013. Following their steps, a new k-out-of-1 OT protocol is presented here, and its realization from decisional Diffie-Hellman （DDH） is described in this paper, in which iO was combined with the dual-mode cryptosystem. The security of the scheme mainly relies on the indistinguishability of the obf-branches （corresponding to the two modes in dual-mode model）. This paper explores a new way for the application of iO.
文摘The problem of two-party oblivious polynomial evaluation (OPE) is studied, where one party (Alice) has a polynomial P(x) and the other party (Bob) with an input x wants to learn P(x) in such an oblivious way that Bob obtains P(x) without learning any additional information about P except what is implied by P(x) and Alice does not know Bob's input x. The former OPE protocols are based on an intractability assumption except for OT protocols. In fact, evaluating P(x) is equivalent to computing the product of the coefficient vectors (a(0),...,a(n)) and (1,...,x(n)). Using this idea, an efficient scale product protocol of two vectors is proposed first and then two OPE protocols are presented which do not need any other cryptographic assumption except for OT protocol. Compared with the existing OPE protocol, another characteristic of the proposed protocols is the degree of the polynomial is private. Another OPE protocol works in case of existence of untrusted third party. Keywords oblivious polynomial evaluation, oblivious transfer, secure multi-party computation, information.
基金supported by the Basque Government through the ELKARTEK program for Research and Innovation,under the BRTAQUANTUM project(Grant Agreement No.KK-2022/00041)。
文摘Privacy-Preserving Computation(PPC)comprises the techniques,schemes and protocols which ensure privacy and confidentiality in the context of secure computation and data analysis.Most of the current PPC techniques rely on the complexity of cryptographic operations,which are expected to be efficiently solved by quantum computers soon.This review explores how PPC can be built on top of quantum computing itself to alleviate these future threats.We analyze quantum proposals for Secure Multi-party Computation,Oblivious Transfer and Homomorphic Encryption from the last decade focusing on their maturity and the challenges they currently face.Our findings show a strong focus on purely theoretical works,but a rise on the experimental consideration of these techniques in the last 5 years.The applicability of these techniques to actual use cases is an underexplored aspect which could lead to the practical assessment of these techniques.
文摘Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric. problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.
基金the National Key Research and Development Program of China(Grant No.2018YFB0804105)in part by the National Natural Science Foundation of China(Grant Nos.62102037,61932019).
文摘Secure multi-party computation(MPC)allows a set of parties to jointly compute a function on their private inputs,and reveals nothing but the output of the function.In the last decade,MPC has rapidly moved from a purely theoretical study to an object of practical interest,with a growing interest in practical applications such as privacy-preserving machine learning(PPML).In this paper,we comprehensively survey existing work on concretely ecient MPC protocols with both semi-honest and malicious security,in both dishonest-majority and honest-majority settings.We focus on considering the notion of security with abort,meaning that corrupted parties could prevent honest parties from receiving output after they receive output.We present high-level ideas of the basic and key approaches for designing di erent styles of MPC protocols and the crucial building blocks of MPC.For MPC applications,we compare the known PPML protocols built on MPC,and describe the eciency of private inference and training for the state-of-the-art PPML protocols.Further-more,we summarize several challenges and open problems to break though the eciency of MPC protocols as well as some interesting future work that is worth being addressed.This survey aims to provide the recent development and key approaches of MPC to researchers,who are interested in knowing,improving,and applying concretely ecient MPC protocols.
