virtue of smooth projective hash functions (SPHF) [15], as
implicit proofs of membership for certain languages, our
2PAKE UC-realizes the corresponding ideal functionality we
provide, and it’s the first provably secure one in the UC
framework. We make key establishment materials pass a-
long with authentication information, and bind to them vi-
a simulation-sound NIZK, to achieve that end. And our
2PASS analogously employs SPHF but as proofs of legal
servers rather than session keys of secure channels. That
technique may eliminate the unnecessary utilizations of zero-
knowledge proofs. As far as we know, the resulting protocol
also has a better computation complexity than the other
UC-secure PASS schemes. Comparisons of some existing
schemes are shown in Table 1 and Table 2, respectively.
Table 1: Comparison of two-server PAKE schemes
scheme struc. secur.
1
setup msgs
2
com.user
3
com.sers
KMT+[26] sym game CRS 6 15 70|70
YLW[36] sym none RO 6 4 5|5
YHB[35] sym game ID 7 23 32|32
YDH[34] asym none RO 10 5 6|3
Ours asym UC RO 7 12 20|20
1
The “secur.” column enumerates the accepted security models in
which schemes are proved;
2
The “msgs” column counts the total number of transmitted mes-
sages among parties.
3
The last two columns counts exponentiations in a prime-order group
performed by the client and servers, respectively.
Table 2: Comparison of PASS schemes in RO model
scheme range secur. setting msgs com.user com.sers
BJSL[1] (t, n) game PKI 3 8t + 17 16
JKK[25] (t, n) game CRS 2 2t + 3 3
CLLN[8] (t, n) UC CRS 10 14t + 24 7t + 28
CLN[10] (1, 2) UC PKI 8 19 26 | 30
Ours (1, 2) UC CRS 8 18 18
2. PRELIMINARIES
In this section, we first briefly recall cryptographic prim-
itives two kinds of public-key encryption schemes, smooth
projective hashing and simulation-sound non-interactive zero-
knowledge proofs used in the construction of our schemes,
and then give a review of the UC framework [11].
2.1 Public-Key Encryption Schemes
A CPA-secure public-key encryption scheme consists of
three algorithms (kg, enc, dec). The key generation algorith-
m kg generates the pair (pk, sk). The encryption algorith-
m takes as input pk, a message m, the randomness w and
outputs a ciphertext C:=enc
pk
(m; w), while the decryption
takes as input sk, a ciphertext C and outputs m:=dec
sk
(C).
We require it to have the indistinguishability under chosen
plaintext attack. The ElGamal cryptosystem [17] that meets
such requirements is needed in this literature.
A labeled CCA2-secure public-key encryption scheme is
also defined by three algorithms (KG, Enc, Dec). Its descrip-
tion of algorithms is similar to CCA2, except that the Enc
and Dec algorithms have an additional input parameter, re-
ferred to as a label, and the Dec consists progress of verify-
ing the ciphertext. More precisely, the Dec will not decrypt
the ciphertext, unless the input label is consistent with one
used in the Enc algorithm, and the ciphertext is verified,
otherwise the algorithm outputs a failure symbol ⊥. For the
CCA2-security, the adversary is allowed to query the de-
cryption oracle on the 2-tuples composed of the ciphertexts
and labels that are different from the challenge pair.
2.2 Smooth Projective Hash Functions
The notion of smooth projective hash functions was in-
troduced by Cramer and Shoup [15]. Here, we focus on our
eventual application, similarly to [23], and show a descrip-
tion based on the ElGamal encryption scheme.
For some ElGamal scheme (kg, enc, dec) with respect to
public key pk, Let X be the range of the encryption algorith-
m, and define the language L
pk,m
:={C|∃w : C:=enc
pk
(m; w)}
for a fixed plaintext m ∈ D. Obviously, L
pk,m
⊂ X.
Formally, a smooth projective hash function for the lan-
guage L
pk,m
is a keyed family of functions mapping elements
in the ciphertext space X to the set Π, along with a projec-
tion function α: K → S, where K is the hash key space, and
S is the projected key space, satisfying:
1. There exist four algorithms for (1) uniformly sampling
the hash key hk ← K, (2) deriving the projected key
hp := α(hk) for hk ∈ K, (3) computing the hash value
Hash(hk, C, m), for C ∈ X and m ∈ D, and (4) com-
puting the projected hash value ProjHash(hp, C, m, w),
where w is the witness C ∈ L
pk,m
.
2. The correctness guarantees that if C ∈ L
pk,m
with w
a witness of this membership, then the results giv-
en by these two hash algorithms are equivalent, i.e.,
Hash(hk, C, m) = ProjHash(hp, C, m, w).
3. The smoothness assures that if C /∈ L
pk,m
, the follow-
ing two distributions are statistically indistinguishable:
{(hp, H)|hk ← K; hp := α(hk); H := Hash(hk, C, m)},
{(hp, H)|hk ← K; hp := α(hk); H ← Π}.
2.3 Simulation-Sound NIZK
Simulation-sound non-interactive zero-knowledge proofs
introduced by [30, 16], are used to prove some certain rela-
tions among the ciphertexts in this paper. The simulation-
soundness, as the extended property of soundness, guaran-
tees that a malicious prover cannot give a convincing proof
for any new invalid statement, even if it has seen poly-
nomial many simulated proofs of invalid statements of its
choice. Additionally, we need the proof system to be zero-
knowledge that the adversary cannot distinguish the simu-
lated proof from a real one. In our schemes below, we use
NIZK{(w) : (w, v) ∈ R
Φ
} to denote the proof that a predi-
cate Φ(v) = 1 for a public value v and the corresponding wit-
ness w. Moreover, the label containing the open information
can be appended, on account of a labeled zero-knowledge
proof that is bound to a certain context. The instantiations
of proofs are provided in Section 3.3.
2.4 Universal Composability Framework
Universal composability [11] is the definition of secure
computation that considers an execution of a protocol in the
setting involving an environment Z, an adversary and par-
ties. This framework focuses on two worlds—the real-world