At Indocrypt 2005, Viet et al.[21], have proposed an anonymous password-authenticated key exchange (PAKE) protocol and its threshold construction both of which are designed for client's password-based authentication and anonymity against a passive server, who does not deviate the protocol. In this paper, we first point out that their threshold construction is completely insecure against off-line dictionary attacks. For the threshold t > 1, we propose a secure threshold anonymous PAKE (for short, TAP) protocol with the number of clients n upper-bounded, such that n 2 -1, where N is a dictionary size of passwords. We rigorously prove that the TAP protocol has semantic security of session keys in the random oracle model by showing the reduction to the computational Diffie-Hellman problem. In addition, the TAP protocol provides unconditional anonymity against a passive server. For the threshold t=1, we propose an efficient anonymous PAKE protocol that significantly improves efficiency in terms of computation costs and communication bandwidth compared to the original (not threshold) anonymous PAKE protocol [21].

An augmented PAKE (Password-Authenticated Key Exchange) protocol is said to be secure against server-compromise impersonation attacks if an attacker who obtained password verification data from a server cannot impersonate a client without performing off-line dictionary attacks on the password verification data. There are two augmented PAKE protocols where the first one [12] was proposed in the IEEE Communications Letters and the second one [15] was submitted to the IEEE P1363.2 standard working group [9]. In this paper, we show that these two augmented PAKE protocols [12], [15] (claimed to be secure) are actually insecure against server-compromise impersonation attacks. More specifically, we present generic server-compromise impersonation attacks on these augmented PAKE protocols [12],[15].

Secure channels can be realized by an authenticated key exchange (AKE) protocol that generates authenticated session keys between the involving parties. In, Shin et al., proposed a new kind of AKE (RSA-AKE) protocol whose goal is to provide high efficiency and security against leakage of stored secrets as much as possible. Let us consider more powerful attacks where an adversary completely controls the communications and the stored secrets (the latter is denoted by "replacement" attacks). In this paper, we first show that the RSA-AKE protocol is no longer secure against such an adversary. The main contributions of this paper are as follows: (1) we propose an RSA-based leakage-resilient AKE (RSA-AKE2) protocol that is secure against active attacks as well as replacement attacks; (2) we prove that the RSA-AKE2 protocol is secure against replacement attacks based on the number theory results; (3) we show that it is provably secure in the random oracle model, by showing the reduction to the RSA one-wayness, under an extended model that covers active attacks and replacement attacks; (4) in terms of efficiency, the RSA-AKE2 protocol is comparable to in the sense that the client needs to compute only one modular multiplication with pre-computation; and (5) we also discuss about extensions of the RSA-AKE2 protocol for several security properties (i.e., synchronization of stored secrets, privacy of client and solution to server compromise-impersonation attacks).

Anonymous password-based authentication protocols are designed to provide not only password-based authentication but also client anonymity. In [22], Qian et al. proposed a simple anonymous password-based authentication protocol (SAPAKE). In this paper, we reconsider the SAPAKE protocol [22] by first showing that an (third party) active attacker can impersonate the server and compute a session key with probability 1. After giving a formal model that captures such attacks, we propose a simple and secure anonymous password-based authentication (for short, S2APA) protocol that provides security against modification attacks on protocol-specific values and is more efficient than YZWB09/10 [32], [33] and SAPAKE [22]. Also, we prove that the S2APA protocol is AKE-secure against active attacks as well as modification attacks under the computational Diffie-Hellman problem in the random oracle model, and provides unconditional client anonymity against a semi-honest server, who honestly follows the protocol.

The RSA-based Password-Authenticated Key Exchange (PAKE) protocols have been proposed to realize both mutual authentication and generation of secure session keys where a client is sharing his/her password only with a server and the latter should generate its RSA public/private key pair (e,n),(d,n) every time due to the lack of PKI (Public-Key Infrastructures). One of the ways to avoid a special kind of off-line (so called e-residue) attacks in the RSA-based PAKE protocols is to deploy a challenge/response method by which a client verifies the relative primality of e and φ(n) interactively with a server. However, this kind of RSA-based PAKE protocols did not give any proof of the underlying challenge/response method and therefore could not specify the exact complexity of their protocols since there exists another security parameter, needed in the challenge/response method. In this paper, we first present an RSA-based PAKE (RSA-PAKE) protocol that can deploy two different challenge/response methods (denoted by Challenge/Response Method1 and Challenge/Response Method2). The main contributions of this work include: (1) Based on the number theory, we prove that the Challenge/Response Method1 and the Challenge/Response Method2 are secure against e-residue attacks for any odd prime e; (2) With the security parameter for the on-line attacks, we show that the RSA-PAKE protocol is provably secure in the random oracle model where all of the off-line attacks are not more efficient than on-line dictionary attacks; and (3) By considering the Hamming weight of e and its complexity in the RSA-PAKE protocol, we search for primes to be recommended for a practical use. We also compare the RSA-PAKE protocol with the previous ones mainly in terms of computation and communication complexities.

The concept of personal networks is very user-centric and representative for the next generation networks. However, the present security mechanism does not consider at all what happens whenever a mobile node (device) is compromised, lost or stolen. Of course, a compromised, lost or stolen mobile node (device) is a main factor to leak stored secrets. This kind of leakage of stored secrets remains a great danger in the field of communication security since it can lead to the complete breakdown of the intended security level. In order to solve this problem, we propose a 3-way Leakage-Resilient and Forward-Secure Authenticated Key Exchange (3LRFS-AKE) protocol and its security architecture suitable for personal networks. The 3LRFS-AKE protocol guarantees not only forward secrecy of the shared key between device and its server as well as providing a new additional layer of security against the leakage of stored secrets. The proposed security architecture includes two different types of communications: PN wide communication and communication between P-PANs of two different users. In addition, we give a performance evaluation and numerical results of the delay generated by the proposed security architecture.

Password-based anonymous authentication schemes provide not only password-based authentication but also user anonymity. In [15], Yang et al., proposed a password-based anonymous authentication scheme (we call it YZWB10 scheme) using the password-protected credentials. This scheme has being standardized in ISO/IEC 20009-4 that was approved to proceed to the CD stage in the 49th ISO/IEC JTC 1/SC 27 Mexico meeting. In this paper, we analyze unlinkability of the YZWB10 scheme [15]. In particular, we show that a (malicious) server in the YZWB10 scheme can specify which user actually sent the login request to the server. Unlike Yang et al.,'s claim, the YZWB10 scheme [15] does not provide unlinkability against server.

An anonymous password-authenticated key exchange (PAKE) protocol is designed to provide both password-only authentication and client anonymity against a semi-honest server, who honestly follows the protocol. In INDOCRYPT2008, Yang and Zhang [26] proposed a new anonymous PAKE (NAPAKE) protocol and its threshold (D-NAPAKE) which they claimed to be secure against insider attacks. In this paper, we first show that the D-NAPAKE protocol [26] is completely insecure against insider attacks unlike their claim. Specifically, only one legitimate client can freely impersonate any subgroup of clients (the threshold t > 1) to the server. After giving a security model that captures insider attacks, we propose a threshold anonymous PAKE (called, TAP+) protocol which provides security against insider attacks. Moreover, we prove that the TAP+ protocol has semantic security of session keys against active attacks as well as insider attacks under the computational Diffie-Hellman problem, and provides client anonymity against a semi-honest server, who honestly follows the protocol. Finally, several discussions are followed: 1) We also show another threshold anonymous PAKE protocol by applying our RATIONALE to the non-threshold anonymous PAKE (VEAP) protocol [23]; and 2) We give the efficiency comparison, security consideration and implementation issue of the TAP+ protocol.

In this paper, we propose a leakage-resilient and proactive authenticated key exchange (called LRP-AKE) protocol for credential services which provides not only a higher level of security against leakage of stored secrets but also secrecy of private key with respect to the involving server. And we show that the LRP-AKE protocol is provably secure in the random oracle model with the reduction to the computational Diffie-Hellman problem. In addition, we discuss about some possible applications of the LRP-AKE protocol.

In [31], Shin et al. proposed a Leakage-Resilient and Proactive Authenticated Key Exchange (LRP-AKE) protocol for credential services which provides not only a higher level of security against leakage of stored secrets but also secrecy of private key with respect to the involving server. In this paper, we discuss a problem in the security proof of the LRP-AKE protocol, and then propose a modified LRP-AKE protocol that has a simple and effective measure to the problem. Also, we formally prove its AKE security and mutual authentication for the entire modified LRP-AKE protocol. In addition, we describe several extensions of the (modified) LRP-AKE protocol including 1) synchronization issue between the client and server's stored secrets; 2) randomized ID for the provision of client's privacy; and 3) a solution to preventing server compromise-impersonation attacks. Finally, we evaluate the performance overhead of the LRP-AKE protocol and show its test vectors. From the performance evaluation, we can confirm that the LRP-AKE protocol has almost the same efficiency as the (plain) Diffie-Hellman protocol that does not provide authentication at all.

Let us consider a situation where someone wants to encrypt his/her will on an existing blockchain, e.g. Bitcoin, and allow an encrypted will to be decryptable only if designated members work together. At a first glance, such a property seems to be easily provided by using conventional threshold encryption. However, this idea cannot be straightforwardly implemented since key pairs for an encryption mechanism is additionally required. In this paper, we propose a new threshold encryption scheme in which key pairs for ECDSA that are already used in the Bitcoin protocol can be directly used as they are. Namely, a unique key pair can be simultaneously used for both ECDSA and our threshold encryption scheme without losing security. Furthermore, we implemented our scheme on the Bitcoin regtest network, and show that it is fairly practical. For example, the execution time of the encryption algorithm Enc (resp., the threshold decryption algorithm Dec) is 0.2sec. (resp., 0.3sec.), and the total time is just only 3sec. including all the cryptographic processes and network communications for a typical parameter setting. Also, we discuss several applications of our threshold encryption scheme in detail: Claiming priority of intellectual property, sealed-bid auction, lottery, and coin tossing service.

An anonymous password-authenticated key exchange (anonymous PAKE) protocol is designed to provide both password-only authentication and user anonymity against a semi-honest server, who follows the protocol honestly. Very recently, Yang and Zhang have proposed a new anonymous PAKE (NAPAKE) protocol that is claimed efficient compared to the previous constructions. In this paper, we propose a very-efficient anonymous PAKE (called, VEAP) protocol that provides the most efficiency among their kinds in terms of computation and communication costs. The VEAP protocol guarantees semantic security of session keys in the random oracle model under the chosen target CDH problem, and unconditional user anonymity against a semi-honest server. If the pre-computation is allowed, both the user and the server are required to compute only one modular exponentiation, respectively. Surprisingly, this is the same computation cost of the well-known Diffie-Hellman protocol that does not provide authentication at all. In addition, we extend the VEAP protocol in two ways: the first is designed to reduce the communication costs of the VEAP protocol and the second shows that stripping off anonymity parts from the VEAP protocol results in a new PAKE protocol.

Hidden Credential Retrieval (HCR) protocols are designed for access credentials management where users who remember short passwords can retrieve his/her various credentials (access keys and tokens) with the help of a remote storage server over insecure networks (e.g., the Internet). In this paper, we revisit two HCR protocols, both of which are based on blind signature schemes: one (we call it B-HCR) was proposed in ASIACCS 2009 and the other (we call it MRS-HCR) was in WISA 2010. In particular, we show that the B-HCR protocol is insecure against an outside attacker who impersonates server S. Specifically, the attacker can find out the user's password pw with off-line dictionary attacks by eavesdropping the communications between the user and a third-party online service provider. Also, we show that the MRS-HCR protocol does not work correctly itself. In other words, user U can not retrieve the plaintext Msg (i.e., credentials) even if he/she has a knowledge of the password.

Both mutual authentication and generation of session keys can be accomplished by an authenticated key exchange (AKE) protocol. Let us consider the following situation: (1) a client, who communicates with many different servers, remembers only one password and has insecure devices (e.g., mobile phones or PDAs) with very-restricted computing power and built-in memory capacity; (2) the counterpart servers have enormous computing power, but they are not perfectly secure against various attacks (e.g., virus or hackers); (3) neither PKI (Public Key Infrastructures) nor TRM (Tamper-Resistant Modules) is available. The main goal of this paper is to provide security against the leakage of stored secrets as well as to attain high efficiency on client's side. For those, we propose an efficient and leakage-resilient RSA-based AKE (RSA-AKE) protocol suitable for the above situation whose authenticity is based on password and another secret. In the extended model where an adversary is given access to the stored secret of client, we prove that its security of the RSA-AKE protocol is reduced tightly to the RSA one-wayness in the random oracle model. We also show that the RSA-AKE protocol guarantees several security properties (e.g., security of password, multiple sever scenario with only one password, perfect forward secrecy and anonymity). To our best knowledge, the RSA-AKE protocol is the most efficient, in terms of both computation costs of client and communication costs, over the previous AKE protocols of their kind (using password and RSA).

AONT (All-or-Nothing Transform) is a kind of (n, n)-threshold secret sharing scheme that distributes a message m into a set of n shares such that the message m can be reconstructed if and only if n shares are collected. At CRYPTO 2000, Desai proposed a simple and faster AONT based on the CTR mode of encryption (called CTRT) and proved its security in the ideal cipher model. Though AES-128, whose key length k = 128 and block length l = 128, can be used in CTRT as a block cipher, AES-256 and AES-192 cannot be used due to its intrinsic restriction of k ≤ l. In this paper, we propose an extended CTRT (for short, XCTRT) suitable for AES-256. By thoroughly evaluating all the tricky cases, we prove that XCTRT is secure in the ideal cipher model under the same CTRT security definition. Also, we discuss the security result of XCTRT in concrete parameter settings. For more flexibility of key length, we propose a variant of XCTRT dealing with l

A purpose of password-based anonymous authentication schemes is to provide not only password-based authentication but also user anonymity. In [19], Yang et al., proposed a password-based anonymous authentication scheme (we call it YZWB10 scheme) using the password-protected credentials. In this paper, we discuss user anonymity of the YZWB10 scheme [19] against a third-party attacker, who is much weaker than a malicious server. First, we show that a third-party attacker in the YZWB10 scheme can specify which user actually sent the login request to the server. This attack also indicates that the attacker can link different login requests to be sent later by the same user. Second, we give an effective countermeasure to this attack which does not require any security for storing users' password-protected credentials.

An augmented PAKE (Password-Authenticated Key Exchange) protocol provides password-only authentication in the presence of an attacker, establishment of session keys between the involving parties, and extra protection for server compromise (i.e., exposure of password verification data). Among many augmented PAKE protocols, AMP variants (AMP2 [16] and AMP+ [15]) have been standardized in IEEE 1363.2 [9] and ISO/IEC 11770-4 [10]. In this paper, we thoroughly investigate APKAS-AMP (based on AMP2 [16]) and KAM3 (based on AMP+ [15]) which require several validity checks on the values, received and computed by the parties, when using a secure prime. After showing some attacks on APKAS-AMP and KAM3, we suggest new sanity checks that are clear and sufficient to prevent an attacker from doing these attacks.

In the literature, many cryptosystems have been proposed to be secure under the Strong Diffie-Hellman (SDH) and related problems. For example, there is a cryptosystem that is based on the SDH/related problem or allows the Diffie-Hellman oracle. If the cryptosystem employs general domain parameters, this leads to a significant security loss caused by Cheon's algorithm [14], [15]. However, all elliptic curve domain parameters explicitly recommended in the standards (e.g., ANSI X9.62/63 [1], [2], FIPS PUB 186-4 [43], SEC 2 [50], [51]) are susceptible to Cheon's algorithm [14], [15]. In this paper, we first prove that (q-1)(q+1) is always divisible by 24 for any prime order q>3. Based on this result and depending on small divisors d1,d2≤(log q)2, we classify primes q>3, such that both (q-1)/d1 and (q+1)/d2 are primes, into Perfect, Semiperfect, SEC1v2 and Acceptable. Then, we describe algorithmic procedures and show their simulation results of secure elliptic curve domain parameters over prime/character 2 finite fields resistant to Cheon's algorithm [14], [15]. Also, several examples of the secure elliptic curve domain parameters (including Perfect or Semiperfect prime q) are followed.

In [2], Choi et al. proposed an identity-based password-authenticated key exchange (iPAKE) protocol using the Boneh-Franklin IBE scheme, and its generic construction (UKAM-PiE) that was standardized in ISO/IEC 11770-4/AMD 1. In this paper, we show that the iPAKE and UKAM-PiE protocols are insecure against passive/active attacks by a malicious PKG (Private Key Generator) where the malicious PKG can find out all clients' passwords by just eavesdropping on the communications, and the PKG can share a session key with any client by impersonating the server. Then, we propose a strengthened PAKE (for short, SPAIBE) protocol with IBE, which prevents such a malicious PKG's passive/active attacks. Also, we formally prove the security of the SPAIBE protocol in the random oracle model and compare relevant PAKE protocols in terms of efficiency, number of passes, and security against a malicious PKG.

Authenticated Key Establishment (AKE) protocols enable two entities, say a client (or a user) and a server, to share common session keys in an authentic way. In this paper, we review the previous AKE protocols, all of which turn out to be insecure, under the following realistic assumptions: (1) High-entropy secrets that should be stored on devices may leak out due to accidents such as bugs or mis-configureations of the system; (2) The size of human-memorable secret, i.e. password, is short enough to memorize, but large enough to avoid on-line exhaustive search; (3) TRM (Tamper-Resistant Modules) used to store secrets are not perfectly free from bugs and mis-configurations; (4) A client remembers only one password, even if he/she communicates with several different servers. Then, we propose a simple leakage-resilient AKE protocol (cf.[41]) which is described as follows: the client keeps one password in mind and stores one secret value on devices, both of which are used to establish an authenticated session key with the server. The advantages of leakage-resilient AKEs to the previous AKEs are that the former is secure against active adversaries under the above-mentioned assumptions and has immunity to the leakage of stored secrets from a client and a server (or servers), respectively. In addition, the advantage of the proposed protocol to is the reduction of memory size of the client's secrets. And we extend our protocol to be possible for updating secret values registered in server(s) or password remembered by a client. Some applications and the formal security proof in the standard model of our protocol are also provided.