第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
论文研究-Fully Simulatable Oblivious Transfer via Proof of Partial K....pdf
http://www.paper.edu.cn
基于部分知识证明的全模拟茫然传输
魏晓超 ，赵川 ，蒋瀚 ，徐秋亮
山东大学计算机科学与技术学院，济南 250101
摘要： 茫然传输是一个重要的密码学基础工具，其可以被用来构造许多密码学方案，例如两
方安全计算协议。在恶意模型下构造基于茫然传输的密码学协议时，如何构造能够抵抗恶意敌
手的茫然传输协议是一个瓶颈问题。本文基于部分 DH 元组的知识的零知识证明的概念，给出
了一个基于标准 DDH 问题困难性假设且可以实现全模拟的 1-out-of-2 茫然传输协议。
关键词：安全两方计算；茫然传输；部分知识的零知识证明；全模拟
中图分类号： TP301
Fully Simulatable Oblivious Transfer via Proof
of Partial Knowledge
Wei Xiao-Chao , Zhao Chuan , Jiang Han , Xu Qiu-Liang
School of Computer Science and Technology, Shandong University, Jinan 250101
Abstract: Oblivious transfer (OT) is an important cryptographic basic tool and can be
used to construct many other cryptographic scheme, such as the secure two-party
computation protocol. As a sub-component of one scheme, the OT protocol must meet the
security requirement of the outside scheme. For example, when constructing a secure
two-party computation protocol in the presence of malicious adversary, the OT protocol used
should be fully simulated in the malicious model. We propose a OT2
simulation under the assumption of DDH problem, relying on the notion of zero-knowledge
proof of knowledge of partial (subset) Diffie-Hellman tuples.
Key words: secure two-party computation; Oblivious transfer; ZK proof of partial
knowledge; full simulation
1 protocol with full
0 Introduction
The notion of oblivious transfer (OT) was firstly proposed by Rabin in [1]. It has been an im-
portant basic cryptographic block and many cryptographic schemes use it as a sub-component,
such as secure two-party computation [2, 3, 4, 5]. In the oblivious transfer setting, there are
two parties which are described as sender and receiver respectively, the sender has two (or
Foundations: 安全多方计算基本运算与 UC 安全研究 (No.20110131110027)
Author Introduction: Wei Xiao-Chao（1990-），male，PhD student，major research direction：secure two-party compu-
tation. Correspondence author：Xu Qiu-Liang （1960-），male，professor，major research direction：Information security
and network security. Email: xql@sdu.edu.cn
- 1 -
http://www.paper.edu.cn
more) values and the receiver wants to obtain one (or more) from them. In addition, it must
satisfy the following security properties: (1) The sender can’t learn what the receiver obtains;
(2) The values which the receiver doesn’t choose is secret to the receiver.
It is obvious that the oblivious transfer is a concrete instance of secure two-party computation,
thus we can formally define the security of OT based on the security of the secure two-party
computation in [2, 6, 7], using the ideal/real simulation paradigm. That is, in the ideal world
there exists a trusted third party who receives inputs of the participants and sends correspond-
ing outputs to each party, but in real world the participants run some actual protocols. A
protocol is said to be secure if no adversary can do more harm in real world than in the ideal
world. For a specific protocol, we judge its security for a function by comparing the outputs
of the adversary and honest party in a real execution to their outputs in the ideal world. As
discussed in [2], there are three different notions of security for OT: privacy only, one-side-
simulation and full simulation. For this, we can construct OT protocols in different secure
models based on the security requirements we should satisfy.
The first oblivious transfer protocol proposed by Rabin was based on the difficult assumption of
quadratic residue and secure only in the semi-honest model. Then [6] gave a scheme relying on
the assumption of any enhanced trapdoor permutation, which was secure against semi-honest
adversaries. In [2] and [8], two protocols were proposed separately basing on the decisional
Diffie-Hellman problem and homomorphic encryption. Unfortunately, they were both insecure
for malicious adversaries.
As we all know, the OT protocol is an important component in constructing cryptographic
schemes,thus it must satisfy the secure requirements of the protocol outside. For example, if
we construct a secure two-party computation protocol in the malicious model, then the OT
protocol inside must also be secure in the presence of malicious adversaries. For this, it’s
imperative to construct OT protocols which are secure in the presence of malicious adversaries.
Regarding the malicious setting, a protocol in the chapter 7 of [3] was proposed, which was
based on the DDH assumption with full simulation. This protocol used the zero-knowledge
proof of knowledge of Diffie-Hellman tuple, which forcing the malicious adversary to run the
execution honestly.
[9] showed a more efficient OT protocol basing on the DDH assumption,
whose communication complexity is less than [3].
Except for using the zero-knowledge to transform an OT protocol which is secure against
semi-honest adversaries into a protocol that is secure in malicious model, Lindell [10] used the
cut-and-choose technique to generate a OT protocol with full simulation. The advantage of
this work is that it avoids using the inefficient zero-knowledge and is the most efficient up to
now. However, the protocol needs a statistical security parameter s, which is used to reflect
the possible error probability causing by the malicious adversary.
- 2 -
http://www.paper.edu.cn
1 Preliminaries and Definitions
Diffie-Hellman tuple. Given a group G of order q with generators g; h and a tuple (g; h; u; v),
we say that the tuple ia a Diffie-Hellman tuple if and only if there exists a w such that u = (g)w
and v = (h)w. On the contrary, the tuple is a non-Diffie-Hellman tuple if there not exists a w
satisfying this.
Zero-Knowledge Proof of Knowledge of Subset of DH tuples. The protocol presented
in [11] is aimed at proving that half of given set of tuples are Diffie-Hellman tuples. In other
words, it is a zero-knowledge proof of knowledge for the following relation
R = f(G; a; g0; g1; (h1
1); ; (hs
0; h1
1))g
0; hs
where G is a group of order q with generators g0; g1, and there exists at least a set of s/2 values
wi1; ; wis/2 such that for every j = 1; ; s/2 it holds that hij
1 = (g1)wij .
As a matter of fact, the above protocol is a concrete instance of the proofs of partial knowledge
presented in [7], you can refer to [7, 11] for detail.
Computationally Indistinguishable. Two distribution ensembles X = fX(a; n)ga∈{0;1};n∈N
and Y = fY (a; n)ga∈{0;1};n∈N are said to be computationally indistinguishable, denoted by
c Y , if for every probabilistic polynomial-time(PPT for short) algorithm D there exists a
0 = (g0)wij and hij
X
negligible function "(n) such that for every a 2 f0; 1g∗ and every n 2 N,
jPr[D(X(a; n)) = 1] Pr[D(Y (a; n)) = 1]j "(n):
Definition of security. We talk about the security of two-party computation in the presence
of malicious adversaries under idea/real model presented in [11]. The formal definition of
security for two-party computation in [2] is defined as follows:
Definition 1. Let f : f0; 1g∗ f0; 1g∗ ! f0; 1g∗ f0; 1g∗ be a two-party functionality and is
a real two-party protocol. Protocol is said to securely compute f with abort in the presence of
malicious adversaries if for every non-uniform polynomial-time adversary A for the real model,
there exists a non-uniform polynomial-time adversary S for the ideal model, such that for every
i 2 f1; 2g,
fIDEALf;S(z);i(x; y; z; n; s)g c fREAL;A(z);i(x; y; z; n; s)g
where x; y; z 2 f0; 1g∗ satisfying jxj = jyj ,and n; s 2 N.
2 Oblivious Transfer - Full Simulation
In this section, we firstly give the zero-knowledge proof of knowledge for two tuples with different
Diffie-Hellman forms. Then we construct a 1-out-of-2 oblivious transfer protocol which can be
fully simulated using the above zero-knowledge proof of knowledge.
- 3 -
http://www.paper.edu.cn
2.1 ZK Proof of Knowledge for Subset DH
The protocol of zero-knowledge proof of knowledge for subset DH has been presented in [3].
What can be used in our work is just a one-out-of-two variant. In other words, given two tuples,
we prove that one out of the two tuples is a Diffie-Hellman tuple. The following scheme has a
little difference from [3], but the technique is invariable.
PROTOCOL 3.1(ZK Proof of Knowledge for two tuples with different Diffie-
Hellman forms)
• Joint statement: The prover P and verifier V both know a group G of order q with
generators g0; g1. In addition, two pairs (h1
0; h1
1), (h2
1).
0; h2
• Auxiliary input for the prover: A witness (i; wi), where i 2 f1; 2g, and for the index
i it satisfies that hi
0 = (g0)wi and hi
1 = (g1)wi.
• The protocol:
1. Set up commitment to verifier challenge:
(a) The prover P chooses a random a Zq, computes = (g0)a and sends to V.
(b) The verifier V chooses random t; c Zq, computes C = (g0)c t and sends C
to P(this is a perfectly-hiding commitment to c).
2. Prover message 1:
(a) For the index 3 i, the prover P chooses random c3−i Zq and z3−i Zq and
sets A3−i = (g0)z3i (h3−i
)c3i and B3−i = (g1)z3i (h3−i
0
)c3i.
1
(b) For the index i, the prover P chooses random i Zq and sets Ai = (g0)i and
Bi = (g1)i.
(c) P sends (A1; B1), (A2; B2) to V.
3. Verifier query: V sends t; c as chosen above to V.
4. Prover message 2:
(a) P checks that C = (g0)c t and aborts if not. Otherwise it takes c as the verifier
query.
(b) For the index i, P sets ci = c + c3−i and zi = i ci wi, and sends (ci; zi) to V.
(c) For the index 3 i, P sends (c3−i; z3−i) as chosen above to V.
(d) In addition, P send a as chosen in the first step to V.
5. Verifier validation: V accepts if and only if the following hold:
(a) = (g0)a;
(b) c = c3−i ci;
- 4 -
http://www.paper.edu.cn
(c) For both i = 1; 2 it holds that Ai = (g0)zi (hi
0)ci and Bi = (g1)zi (hi
1)ci.
The security of the above protocol has been proved in [12], which introduces the notion of proof
of partial knowledge, and so we omit it.
Exact efficiency. The overall cost of the above protocol is 18 exponentiations and the exchange
of 10 group elements. In addition, the number of rounds of communication in the protocol is
five(the sender sends three messages and the receiver sends two messages).
2.2 Constructing an Oblivious Transfer Protocol
According to the definition of FOT , which denotes the functionality of 1-out-of-2 oblivious
transfer, the receiver can only obtain one value from the sender’s input (x0; x1). We assume
that if the receiver constructs two tuples satisfying that only one is a Diffie-Hellman tuple and
the other one is a non-Diffie-Hellman tuple, then the sender uses the two tuples to transfer
(x0; x1), and finally the receiver can just computes one value. However, a malicious receiver
can generates the two tuples incorrectly, for example both are Diffie-Hellman tuples, and then
obtains both (x0; x1). For this reason, the receiver must prove to the sender that he constructs
the tuples honestly. Such that we can use the zero-knowledge proof of knowledge presented
above to construct a OT protocol, which can be fully simulated in malicious setting.
PROTOCOL 3.2(1-out-of-2 Oblivious Transfer OT )
• Inputs: The sender S has a pair of values (x0; x1) and the receiver R has a bit 2 f0; 1g.
• Auxiliary input: Both parties have a security parameter 1n and a group G of prime
order q with a generators g0.
• The protocol:
1. The receiver R chooses random values r; 0; 1 Zq and computes g1 = (g0)r. R
0 =
then constructs T0 = (g0; g1; h1
(g0)1; h2
1 = (g1)1+1−), and sends (h1
0 = (g0)0; h1
1); (h2
1 = (g1)0+) and T1 = (g0; g1; h2
0; h2
1) to S.
0; h1
2. R proves using a zero-knowledge proof of knowledge to S that one of the tuples
1/g1) is Diffie-Hellman tuple. If S rejects then it
1/g1) and (g0; g1; h2
0; h2
0; h1
(g0; g1; h1
outputs ? and halts.
3. The sender S operates in the following way:
(a) Define the function RAN D(w; x; y; z) = (u; v), where u = (w)s (y)t and v =
(x)s (z)t, and the values s; t Zq are random.
(b) S computes (u0; v0) = RAN D(g0; g1; h1
1).
0; h2
(c) S sends the receiver the values (u0; w0) where w0 = v0 x0, and values (u1; w1)
1), and (u1; v1) = RAN D(g0; g1; h2
0; h1
where w1 = v1 x1.
- 5 -
3. The receiver outputs x = w/(u)r.
In order to see the correctness of the protocol, we analyse it separately for = 0 and = 1.
http://www.paper.edu.cn
0)r)t =
1)t x0
(g1)s (h1
(g1)s (h1
1. When = 0, T0 = (g0; g1; h1
(g1)s (h1
((g0)s (h1
w0
(u0)r =
0 = (g0)0; h1
1)t x0
0)t)r =
2. When = 1, T1 = (g0; g1; h2
(g1)s (h2
((g0)s (h2
1 = (g1)0) is a DH tuple, so we have that
(g1)s (h1
1)t x0
((g0)r)s ((h1
1)t = x0
1 = (g1)1) is a DH tuple, so we have that
(g1)s (h2
((g0)r)s ((h2
For this, the receiver can always obtain the desired ouput.
Regarding security, intuitively ,because of the Zero-Knowledge Proof of Knowledge, it’s obvi-
ously that one and only one of (T0; T1) is a DH tuple, so that the receiver can only get one
value from (x0; x1).
We now give the formal proof of the protocol:
0 = (g0)1; h2
1)t x1
0)t)r =
1)t x1
1)t = x1
(g1)s (h2
(g1)s (h2
w1
(u1)r =
1)t x1
0)r)t =
(1)
(2)
Theorem 2. If the Decisional Diffie-Hellman assumption holds in group G, then the protocol
OT securely computes FOT functionality in the presence of malicious adversaries.
Proof. We prove security in a hybrid model where the zero-knowledge proofs and proofs of
knowledge (ZKP OK) are computed by ideal functionalities. We separately prove security
when S is corrupted and R is corrupted.
The sender S is corrupted. Let A be an adversary that controls the receiver S in real word.
We construct a simulator SSEN D that invokes A on its input and works as follows:
1. SSEN D chooses random values r; 0; 1 Zq and computes g1 = (g0)r; h1
(g0)1 as the honest receiver R would. Then it sets h1
different from the way constructed by an honest R. SSEN D sends T0 = (g0; g1; h1
T1 = (g0; g1; h2
1 = (g1)0; h2
1) to A.
0; h2
0 = (g0)0; h2
0 =
1 = (g1)1, which is
1) and
0; h1
2. S simulates the ideal zero-knowledge proof of knowledge from R to S by handing 1 to A
meaning success, as if it comes from the ZKP OK ideal functionality.
3. Upon receiving back (u0; w0) and (u1; w1), S computes both the values (x0; x1) like an
honest receiver. Then it sends (x0; x1) to the trusted party computing the oblivious
transfer functionality and outputs whatever A outputs and halts.
We claim that the joint output distribution of the ideal execution between SSEN D and an honest
R is identical to the output of a real execution with A and an honest R, that is
fIDEALFOT ;SSEND(z);S((x0; x1); ; n)g c fHY BRIDZK
OT ;A(z);S((x0; x1); ; n)g.
- 6 -
http://www.paper.edu.cn
1 and h2
Note that the only difference is that SSEN D generates h1
1 incorrectly, such that the
tuples(T0; T1) are both Diffie-Hellman tuples in ideal execution. But in the real world, only one
of the two tuples is a Diffie-Hellman tuple. Assuming that there exists a distinguisher who can
distinguish the IDEAL and HYBRID execution with some non-ignorable probability, then there
must exists a distinguisher with the same probability for the DDH problem that can distinguish
a Diffie-Hellman tuple from a non-Diffie-Hellman tuple, however this is impossible. The above
fact implies that the IDEAL and HYBRID distributions are computationally indistinguishable,
as required.
The receiver R is corrupted. Let A be an adversary that controls the receiver R in real
word. We construct a simulator SREC that invokes A on its input and works as follows:
1. SREC receives T0 = (g0; g1; h1
1) from A and verifies the zero-
1) and T1 = (g0; g1; h2
0; h1
0; h2
knowledge proof as the honest sender would.
(a) If the verification fails, SREC sends ? to the trusted party computing the oblivious
transfer functionality and halts.
(b) Otherwise, SREC runs the extractor and extracts a witness w. Then S sets = 0 if
0 = (g0)w and h2
h2
1/g1 = (g1)w, and = 1 if h1
0 = (g0)w and h1
1/g1 = (g1)w.
2. The simulator SREC sends to the trusted party computing the oblivious transfer func-
tionality and receives back x.
3. SREC computes (u; u) using the value x as an honest sender and sets (u1−; w1−) to be
random elements of G. Then it sends these values to A and outputs whatever A outputs
and halts.
As above, we must prove that
fIDEALFOT ;SREC (z);R((x0; x1); ; n)g c fHY BRIDZK
OT ;A(z);R((x0; x1); ; n)g.
Note that the honest sender doesn’t output anything, so we only need to show that the distri-
bution of A′
s output with the simulator SREC in ideal execution is computationally indistin-
guishable from the distribution with an honest sender S in hybrid execution. We observe that
the only difference between the IDEAL and HYBRID distributions is the way (u1−; w1−)
are generated.
In the real protocol, the sender S computes RAN D(T1−), and then gener-
ates (u1−; w1−). But in ideal world, the simulator SREC sets (u1−; w1−) to be random
elements of G. We know that the tuple T1− is a non-Diffie-Hellman tuple, therefore the values
(u1−; w1−) generated by the honest S using T1− in the real protocol are also random in G.
For this, we can deduce the above conclusion, as desired.
This completes the proof of the theorem.
Exact efficiency. We analyse the efficiency of the protocol according to the following three
aspects:
- 7 -
http://www.paper.edu.cn
• Number of rounds: The number of rounds of the protocol OT including the zero-
knowledge sub-protocol is six (note that the first message which R sends to S in OT can
be combined with the first message of the zero-knowledge sub-protocol).
• Local exponentiations: In the protocol OT without the zero-knowledge sub-protocol,
the sender computes eight exponentiations (the RAN D function) and the receiver com-
putes six exponentiations (five values g1; h1
1 and one in the last step for de-
crypting x). Combing with the exponentiations in the zero-knowledge sub-protocol, the
overall exponentiations is 32.
0; h2
1; h2
0; h1
• Bandwidth: The bandwidth means the number of group elements exchanged between
the two parties. Without the zero-knowledge sub-protocol, the sender sends four group
elements (u0; w0; u1; w1) and the receiver sends five group elements (g1; h1
1).
0; h2
Combing with the bandwidth in the zero-knowledge sub-protocol, the overall bandwidth
is 19.
0; h1
1; h2
3 Conclusion
In this paper, we apply the notion of proof of partial knowledge to construct a 1-out-of-2
oblivious transfer protocol. We use the technique of zero-knowledge proof of knowledge for
partial DH tuples proposed in [3, 12] to construct a OT1
2 protocol which can be fully simulated
in malicious model. In detail, the receiver constructs a tuple-pair containing two tuples with
the property that one tuple is a DH tuple and the other one is a non-DH tuple. In order to
force the receiver to construct the tuple-pair honestly, the receiver should prove to the sender
using a zero-knowledge proof of knowledge that one of the two tuples is a DH tuple. Then
the sender uses the two tuples to encrypt his own inputs separately. Finally the receiver can
decrypt the value encrypted using the DH tuple, and the other value encrypted using a non-DH
tuple is obviously secret to the receiver. The OT protocol we construct has the same number
of rounds, local computation complexity and bandwidth as the most efficient scheme [9] in
ZKPOK hybrid model.
参考文献（References）
[1] RABIN M O. How to exchange secrets by oblivious transfer[R]. Harvard University, 1981.
[2] HAZAY C, LINDELL Y. Efficient Secure Two-Party Protocols:Techniques and Construc-
tions[M]. Springer Berlin Heidelberg, November 2010.
- 8 -
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
