International Journal of Cryptology Research X(Y): (20ZZ)

Survey and New Idea for Attribute-Based Identification Scheme
Secure against Reset Attacks
1

5

Ji-Jian Chin, 2Hiroaki Anada, 3Seiko Arita, 2,4Kouichi Sakurai, SweeHuay Heng and 1Raphael Phan

1

Faculty of Engineering, Multimedia University
Institute of Systems, Information Technologies and Nanotechnologies, Japan
3
Institute of Information Security, Japan.
4
Faculty of Information Science and Electrical Engineering, Kyushu University
5
Faculty of Information Science and Technology, Multimedia University
Email: 1jjchin@mmu.edu.my, 2anada@isit.or.jp
2

ABSTRACT
Identification schemes are a common one-way authentication technique for a user toprove himself securely to a verifier. However, it is known that identification schemes
based on the sigma-protocol are basically insecure against reset attacks. On the otherhand, attribute-based cryptography is a technique which allows for the secure
implementation of access policies within a cryptosystem. In this paper, we report on
the developments in the area of reset attacks for identification schemes as well as for
attribute-based identification schemes. Then we put together a new idea to constructattribute-based identification schemes secure against reset attacks.

SECTION 1: INTRODUCTION
An identification scheme is a cryptographic primitive that allows one
party, the prover, to prove himself convincingly to another party, the verifier,without revealing any knowledge about his private key. First proposed by
Fiat and Shamir (1983), this primitive is usually used to facilitate access
control to allow legitimate users to access resources upon being able to prove
themselves securely to a verifying mechanism.
Identification schemes are generally categorized into two-movechallenge-response and three-move sigma protocols. Two-move challengeresponse protocols basically revolve around the capability of the prover todecrypt a challenge ciphertext or sign a verifiable message, given that he has
a valid private key. However, in general, two-move protocols are more
expensive operationally.
For three-move sigma protocols the prover and verifier engage in athree-step canonical interaction every time a prover wishes to prove itself.
The prover begins by sending a commitment. The verifier follows by
selecting a random challenge from a predefined challenge set. Then theprover provides a response using a combination of his private key,

Ji-Jian Chin, Hiroaki Anada, Seiko Arita, Kouichi Sakurai, Swee-Huay Heng and Raphael Phan

commitment as well as the challenge. The verifier will then decide to accept
or reject a prover’s session based on the response.
Sigma-protocols have the following properties:i)
Completeness – provers with valid private keys should be given an“accept” except with negligible probability.
ii)Soundness – provers with invalid private keys should be given a
reject decision except with negligible probability.
iii)
Zero-knowledge – certain sigma protocols have a zero-knowledge
property, where the verifier upon completing the interaction with theprover learns nothing about the user’s private key. This is proven bya simulator that is able to produce a valid interaction transcript withor without a prover’s participation. However, since it is hard to provesecurity against concurrent-active attacks for protocols with zeroknowledge properties, sometimes the requirement is relaxed to justsatisfying a witness indistinguishability requirement (Fiege andShamir, 1990), where a verifier cannot distinguish between the twowitnesses used in the protocol.
1.1 Reset Attacks
While generally two-move challenge-response protocols are secureagainst reset attacks, unfortunately sigma protocols have an inherent
weakness against reset attacks, where an adversary is allowed to reset theprover to where he first sent the commitment. Then due to the soundness
property, with two different challenges, the adversary is able to extract auser’s private key from the different responses and challenges but using thesame commitment.
Reset attacks can be performed if an adversary has access to theverifying machine, for example a smart card reader that is able to tamper
with the internal state of the smart card. Thus the adversary with access tothis smart card reader will be able to extract an honest user’s private key if
the user interacts with it.
The reset attack was first addressed for identification schemes by
Bellare et al. (2001). In their seminal paper, they tackled the problem ofadversaries with the resetting capability and proposed several methods ofovercoming this problem. We provide a more comprehensive review of thesemethods in a later section of this paper.
The power of reset attacks can be seen by the following scenarios
given by Bellare et al. (2001), describing how a reset-attack can be mounted
practically. Firstly, if an adversary captures a prover device such as a smart
International Journal of Cryptology ResearchSurvey and New Idea for Reset Secure Attribute-Based Identification

card, the adversary can disconnect and reinsert the battery to reset the card’s
secret internal state to its initial state. This can be done multiple times.
Secondly if an adversary is able to crash the prover device, such as bycausing a stack/heap overflow, upon reinitializing the device will resume
computation after the crash, forcing the device to reset itself.
Thus, reset-secure identification schemes are desirable due to theexistence of these threats.
1.2 Identification Schemes without CertificatesIn traditional public key cryptography, certificates are required tobind a user to his public key, which could otherwise be replaced by amalicious party. These certificates are issued by certificate authorities, andinclude a wide-array of information ranging from the public key to validity
period. Any doubtful parties can verify that a user’s public key actuallybelongs to a particular user by checking the Certificate Authority’s digital
signature on the certificate.
The certificate management issue occurs when the users of thecryptosystem grow large and a large overhead is required to issue, validate,manage and revoke these certificates. To circumvent this issue, Adi Shamirfirst proposed identity-based cryptography (Shamir, 1984), where users canimplicitly certify themselves using a publicly known identity-string. Identitybased cryptography only kicked off in 2001 when Boneh and Franklin (2001)
proposed the first identity-based encryption scheme. In 2004, the first
identity-based identification schemes were proposed by Bellare et al. (2004)
and Kurosawa and Heng (2004) independently.
Since then, many identity-based identification schemes have been
proposed, but none of them are secure against reset attacks. The first
identity-based identification scheme that is secure against reset attacks was
first proposed by Thorncharoensri et al. (2009).
In addition to identity-based cryptography, other extensions for
identification schemes that operate without the requirement of certificateshave surfaced in the recent decade. Certificateless cryptography was
proposed by Alriyami and Paterson (2001) to resolve the key escrow issue,
where the central key generation center has access to every user’s private key.
In certificateless cryptography, the key generation center creates a partial
private key, which the user combines with his component of the private key
to create the full private key. Thus without the user’s component the key
generation center does not have complete access to the full private key. For
the identification primitive, certificateless identification was first defined andproposed by Dehkordi and Alimoradi (2013) and Chin et al. (2013)independently. However, subsequently Chin et al. (2014) pointed out flaws
International Journal of Cryptology Research

207

Ji-Jian Chin, Hiroaki Anada, Seiko Arita, Kouichi Sakurai, Swee-Huay Heng and Raphael Phanin Dehkordi and Alimoradi (2013)’s design, therefore it is insecure against
impersonation attacks.
Another new area of identification schemes without certificates is theattribute-based identification (ABID) scheme. Attribute-based identification
was introduced by Anada et al. (2013). In an ABID scheme, each entity has
credentials called attributes. An access policy is written as a boolean formulaover these attributes. Thus, a verifier can identify that a prover possesses acertain set of attributes that satisfies the verifier’s access policy. Hence,
ABID schemes can be considered as an expansion of the usual ID schemes.
In Anada et al. (2013)’s seminal paper, a two-move generic (and concrete)construction was presented. That is, by employing an attribute-based key
encapsulation mechanism (Sahai and Waters 2005, Waters 2011), a
challenge-and-response protocol was proposed. Their scheme was proven to
be secure against reset attacks. After their two-move construction, a threemove construction was presented by Anada et al. (2014a). This three-moveconstruction was captured as a canonical ABID scheme and it wastransformed into an attribute-based signature scheme by using the FiatShamir transform (Anada et al. 2014b).
In contrast to the earlier construction by Anada et al. (2013), thethree-move construction was based on the (traditional) sigma protocol(Cramer et al., 2001). Enhancing the technique of OR-proof (Damgard,2004), they succeeded to provide a three-move generic ABID scheme thatcan be concretely realized without pairings. Hence Anada et al. (2014a)’s
three-move protocol can be said to be more efficient than the two-moveprotocol (Anada et al., 2013). But their three-move protocol is not secureagainst reset attacks because its security is based on the Reset-Lemma(Bellare and Palacio, 2002). That is, under the condition that an adversary isallowed to reset an honest prover, the adversary can extract the prover’s
witness in polynomial-time.
1.3 Motivations and Contributions
Since its conception in 2004, identification schemes withoutcertificates have received much attention, particularly attribute-based
identification schemes. Secondly, the notion of reset attacks has not yet been
examined in depth, particularly with regards for identification schemes
without certificates.
In this paper, we introduce the reader to the security notions of resetsecure identification as well as attribute-based identification (ABID)
schemes. After that, we provide the first generic construction to modify athree-move attribute-based identification scheme to be secure against reset
attacks.
International Journal of Cryptology ResearchSurvey and New Idea for Reset Secure Attribute-Based Identification

It is worthwhile to note that the security against reset attacks
discussed in this paper is Concurrent-Reset-1 (CR1) security defined by
Bellare et al. (2001). CR1 security is, even if we ignore concurrency,
different from the security of resettable zero-knowledge and the security ofresettable soundness (see Arita 2012 for definitions).
The rest of the paper is organized as follows: In Section 2 we begin
by reviewing the definitions and security model of reset-secure identification
schemes and ABID schemes. In Section 3, we introduce the first genericconstruction to modify three-move ABID schemes to be reset-secure. We
conclude in Section 4 with some closing remarks.

SECTION 2: PRELIMINARIES AND DEFINITIONSIn this section, we review the formal definitions and security notions
for reset-secure identification schemes as well as ABID schemes.
2.1 Reset-Secure Identification Schemes
An identification scheme consists of three probabilistic polynomialtime algorithms: Keygen, Prover and Verifier.
Keygen takes in the security parameter 1௞ and generates apublic/private key pair for the user 〈, 〉.
Prover takes in the private key  while Verifier takes in the publickey . Together they run the sigma protocol as such:
1) Prover sends the commitment  .
2) Verifier selects and sends a random challenge from a set ofpredefined challenges.
3) Prover calculates his response  based on the challenge andreturns it to Verifier. Verifier will then choose to accept/rejectbased on the response given.
An adversary towards an identification scheme is an impersonator.
For normal identification schemes an impersonator can be a passive one,
where he only eavesdrops on conversations, or an active one where he canplay a cheating verifier to learn information by interacting with honest users
before attempting impersonation.
For reset-secure identification schemes, an additional concurrent
reset-attacker is defined. This attacker is more powerful than theconventional passive/active attacker and is able to run several instances ofthe prover interactions concurrently, interleaving executions and performing
reset actions on the prover states. Bellare et al. first formalized these two
types of concurrent reset attackers as CR1 and CR2 respectively.
International Journal of Cryptology Research

209

Ji-Jian Chin, Hiroaki Anada, Seiko Arita, Kouichi Sakurai, Swee-Huay Heng and Raphael Phan

For the CR1 attacker, the adversary may interact with the honestuser’s Prover algorithm as a verifier and in addition to identification queries,
be able to perform a reset action for the Prover algorithm to any state. Laterthe adversary performs the impersonation attempt.
For the CR2 attacker, the adversary may do all the actions described
for the CR1 attacker, but may attempt impersonation whenever it wishes to.
Therefore, the CR1 attacker is a special case of CR2 attacker.
We describe the security for the reset-secure identification scheme
using the following game played between a challenger  and animpersonator .
Keygen:  takes in the security parameter 1௞ , generates 〈, 〉 andpasses  to .
Phase 1:  is able to make the following queries:i)
Identification queries:  interacts as a cheating verifier with aprover simulated by  to learn information.
ii)
Reset queries:  resets the prover simulated by  to any statethat it wishes within the three-step sigma protocol.
Phase 2:  changes mode into a cheating prover trying to convince .
For CR2 impersonators,  can still continue to make any of the queries from
Phase 1.  wins if it manages to convince  to accept its interaction with
non-negligible probability.
We say an identification scheme is , ூ , ௥ ,  -secure underconcurrent reset attacks if any reset concurrent impersonator  that runs intime  , [ can impersonate] <  where  can make at most ூ
identification queries and ௥ reset queries.
Bellare et al. (2001) also proposed four techniques in order to secure
identification schemes that are constructed using the sigma protocol against
reset attackers, which are naturally insecure against reset attacks. We briefly
describe the four techniques here:
1) Stateless digital signatures: a prover can authenticate himself to a verifierby showing the capability of signing random documents the verifierchooses. Here the message becomes the challenge while the signature isused as the response. Statelessness is required so that the reset attacker
cannot reset the state of the signer. However, this is generally a twomove protocol.
2) Encryption schemes: a prover can authenticate himself to a verifier byshowing the capability to decrypt random ciphertexts the verifier chooses.
Here the ciphertext becomes the challenge while the message becomesthe response. However, reset-security requires that an encryption scheme
secure against chosen-ciphertext attacks be used.
International Journal of Cryptology ResearchSurvey and New Idea for Reset Secure Attribute-Based Identification

3) Trapdoor commitments: this technique uses a trapdoor commitment
scheme to ‘commit’ a verifier’s challenge. This commitment is used as
the generator for the prover’s salt using a pseudorandom function. One
can therefore verify that upon revealing the verifier’s challenge, the salt
can be regenerated in order to create the proper response for the verifier.
If the prover was reset, the regeneration of the salt would yield adifferent (and invalid) response.
4) Zero-knowledge proof of membership: a prover proves membership in a
hard language rather than proving that it has a witness for the language.
This is done by using a resettable zero-knowledge proof of language
membership, as defined by Canetti et al. (2000).
In this work, we utilize the third technique as a generic way toconstruct reset-secure ABID schemes.
2.2 ABID Schemes
Let  = {1, . . . , } be an attribute Universe. An access structure  ,which means an access policy, is defined as a subset of 2௎ \ . We only treat
monotone access structures.
An ABID scheme consists of four PPT algorithms: Setup, KeyGen,
Prover and Verifier.
Setup( ࢑ ,  ) → ( ,  ). Setup takes as input the security
parameter λ and the attribute universe U. It outputs a public key PK and amaster secret key MSK.
KeyGen(, ,  ) →ࡿ . A key-generation algorithm KeyGentakes as input the public key , the master secret key   and an attributeset . It outputs a secret key ௌ corresponding to .
Prover( , ࡿ ) and Verifier( ,  ). Prover and Verifier areinteractive algorithms. Prover takes as input the public key  and the secretkey ௌ . Here the secret key ௌ is given to Prover by an authority that runs
KeyGen( ,  , ). Verifier takes as input the public key  and an
attribute set . Prover is provided Verifier’s access structure by the firstround. Prover and Verifier interact with each other for some rounds. Then,
Verifier finally returns its decision bit . When = 1 it means that Verifier!""# Prover in the sense Prover has a secret key ௌ such that S satisfies. When = 0 it means that Verifier #$#" Prover.
We require correctness of an ABID scheme that for any 1௞ and , andif ∈ , then the probability of Verifier outputting an !""# will always
be true, namely
Pr[(,  ) ← #(1௞ , );International Journal of Cryptology Research211

Ji-Jian Chin, Hiroaki Anada, Seiko Arita, Kouichi Sakurai, Swee-Huay Heng and Raphael Phanௌ ← #%&#',  , ;
= 1] = 1.
← ⟨(, ௌ ), ((, )⟩ ∶SECTION 3: GENERIC CONSTRUCTION OF 3-MOVERESET-SECURE ABID SCHEME
In this section, we present a new and generic idea for modifying threemove ABID schemes to be secure against reset attacks. We utilize Bellare etal. (2001)’s third paradigm, which is to use a trapdoor commitment scheme,
and embed this scheme within the three-move ABID scheme. The resulting
scheme consists of four-moves.
The construction of the scheme is described in Table 1.

Table 1: Generic Construction of 3-move Reset-Secure ABID Scheme
Setup(࢑ , )→  ≔ ࡭࡮ࡵࡰ , ࢀࡰ࡯ , :Setup takes in the security parameter 1௞ and the space of the attribute universe  andoutputs the public key and master secret key 〈 = (஺஻ூ஽ , ்஽஼ ),  〉. However,the public key consists of two components, one for the ABID scheme ஺஻ூ஽ and theother for the trapdoor commitment scheme ்஽஼ .
KG(࡭࡮ࡵࡰ , , )→ ࡿ :Keygen KG takes in the public key for the ABID scheme, ஺஻ூ஽ , the master secret key  and the set of attributes and outputs the secret key ௌ corresponding to .
Prover(࡭࡮ࡵࡰ , ࢀࡰ࡯ , ࡿ ):Verifier(, ) ௏ ← +*஼ு஺ (1௞ )*்஽஼ெ்,஺
←*஼ெ் (்஽஼ ,  ௏ ; ஼ )஺஻ூ஽ ←  ) ௉ , * ,-----.
 ← +*஼ெ்  ௌ , ஺஻ூ஽ , ஼ெ்/-0஼ு஺ೇ ||ோ಴,-----.
IF*௏ி ்஽஼ , * , = !""#
THEN←+*ோௌ௉ ( ௌ ,  ,  ௏ ;ELSE  =⊥௏ || ஼ ோௌ௉/-0஺஻ூ஽ )

1#"← +*௏ி ஺஻ூ஽ , ,  , International Journal of Cryptology Research௏Survey and New Idea for Reset Secure Attribute-Based Identification

Prover and Verifier engage in the identification protocol as follows:
1) Upon receiving an initialization message from Prover, Verifier first generates acommitment * for his random challenge  ௏ using the trapdoor commitment
scheme’s commit algorithm *஼ெ் and sends it to Prover along with the accesspolicy .
2) Prover evaluates * and his own internal coins ௉ with a pseudorandomfunction  ) and generates the salt ஺஻ூ஽ . This salt is used to generate hiscommitment  and is sent to Verifier.
3) Verifier then sends his random challenge  ௏ and random coins ஼ to Prover.
4) The Prover uses the trapdoor commitment scheme’s public key ்஽஼ , the Verifier’s
trapdoor commitment * , as well as the newly received challenge  ௏ andrandom coins from the Verifier ஼ to reveal the commitment for verification.
5) If verification of the commitment is an !""# , Prover will then calculate theresponse  for the ABID scheme and send it to the Verifier. Otherwise it aborts.
6) Verifier then outputs the decision on whether to accept the Prover’s response or not.

Informally, the trapdoor commitment generated using a predetermined challenge by the Verifier serves to fix the commitment value tobe used by the Prover. Later on, when this pre-determined challenge isrevealed as the challenge from the Verifier, the Prover then verifies that it
was indeed the committed value by the Verifier before continuing with its
response. If the Prover is reset to the commitment state, it cannot continue
with a different challenge from the Verifier (which normally exposes the user
secret key) due to the fact that the trapdoor commitment verification stage
will fail.
The construction and provable security of a concrete scheme iscurrently a work-in-progress.
SECTION 4: CONCLUSION
In this paper, we provided a review of the security notions of resetsecure identification as well as ABID schemes. We also provided a brief
survey of all the work currently done in both reset-secure identification
schemes as well as attribute-based identification schemes. Then, we gave ageneric construction to modify three-move ABID schemes to be reset secure.
Future work would include providing detailed proof of security as well as aconcrete construction as a case study for the transformation work.

International Journal of Cryptology Research213

Ji-Jian Chin, Hiroaki Anada, Seiko Arita, Kouichi Sakurai, Swee-Huay Heng and Raphael PhanACKNOWLEDGEMENTS
This research is partially supported by Grants-in-Aid for Scientific Research(Research Project Number:25540004) by the Japan Society for the
Promotion of Science and The Fundamental Research Project Scheme(No.: FRGS/2/2013/ICT07/MMU/03/5) by the Ministry of Education of theGovernment of Malaysia.

REFERENCES
1. Amos Fiat, Adi Shamir: How to Prove Yourself: Practical Solutions to
Identification and Signature Problems. CRYPTO 1986: 186-194
2. Uriel Feige, Adi Shamir: Witness Indistinguishable and Witness Hiding
Protocols. STOC 1990: 416-426
3. Mihir Bellare, Marc Fischlin, Shafi Goldwasser, Silvio Micali:
Identification Protocols Secure against Reset Attacks. EUROCRYPT
2001: 495-511
4. Adi Shamir: Identity-Based Cryptosystems and Signature Schemes.
CRYPTO 1984: 47-53
5. Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the
Weil Pairing. CRYPTO 2001: 213-229
6. Mihir Bellare, Chanathip Namprempre, Gregory Neven: Security Proofs
for Identity-Based Identification and Signature Schemes. EUROCRYPT
2004: 268-286
7. Kaoru Kurosawa, Swee-Huay Heng: From Digital Signature to ID-based
Identification/Signature. Public Key Cryptography 2004: 248-261
8. Pairat Thorncharoensri, Willy Susilo, Yi Mu: Identity-Based
Identification Scheme Secure against Concurrent-Reset Attacks without
Random Oracles. WISA 2009: 94-108
9. Sattam S. Al-Riyami, Kenneth G. Paterson: Certificateless Public Key
Cryptography. ASIACRYPT 2003: 452-473
10. Massoud Hadian Dehkordi and Reza Alimoradi: CertificatelessIdentification Protocols from Super Singular Elliptic Curve. Security andCommunication Networks, 2013.
11. Ji-Jian Chin, Raphael C.-W. Phan, Rouzbeh Behnia, Swee-Huay Heng:
An Efficient and Provably Secure Certificateless Identification Scheme.
SECRYPT 2013: 371-378
International Journal of Cryptology ResearchSurvey and New Idea for Reset Secure Attribute-Based Identification

12. Ji-Jian Chin, Rouzbeh Behnia, Swee-Huay Heng, Raphael C-W. Phan:
Cryptanalysis of a Certificateless Identification Scheme. Security andCommunication Networks, 2014, 7, 4
13. Hiroaki Anada, Seiko Arita, Sari Handa, and Yousuke Iwabuchi:
Attribute-based Identification: Definitions and Efficient Constructions.
ACISP 2013, 168-186.
14. Hiroaki Anada, Seiko Arita, Kouichi Sakurai (a): Attribute-Based
Identification Schemes of Proofs of Knowledge. SCIS2014, 3E3-3.
15. Hiroaki Anada, Seiko Arita, Kouichi Sakurai (b): Attribute-Based
Signatures without Pairings via the Fiat-Shamir Paradigm. To appear in
ASIAPKC2014.
16. Amit Sahai and Brent Waters: Fuzzy Identity-based Encryption.
EUROCRYPT 2005, 457-473.
17. Brent Waters: Ciphertext-Policy Attribute-Based Encryption: An
Expressive, Efficient and Provably Secure Realization. PKC 2011, 53-70.
18. Ronald Cramer, Ivan Damgard, Jesper Buus Nielsen: Multiparty
computation from threshold homomorphic encryption. EUROCRYPT
2001, 280-300.
19. Ran Canetti, Shafi Goldwasser, Oded Goldriech and Silvio Micali:
Resettable zero-knowledge. Proceedings of the 32nd Annual Symposiumon the Theory of Computing, ACM 2000.
20. Seiko Arita: A Constant-Round Resettably-Sound Resettable ZeroKnowledge Argument in the BPK Model. IEICE Transactions 2012, 95-A
(8): pp. 1390-1401.

International Journal of Cryptology Research215