full version. On the Generic Construction of Identity-Based Signatures with Additional Prop
An extended abstract of this paper appears in Advances in Cryptology—ASIACRYPT’06, Lecture Notes in Computer Science Vol.??,Xuejia Lai ed.,Springer-Verlag,2006.This is the full version.
On the Generic Construction of Identity-Based Signatures with
Additional Properties
David Galindo1Javier Herranz2Eike Kiltz2
1Nijmegen Institute for Computing and Information Sciences,
The Netherlands
d.galindo@cs.ru.nl
http://www.cs.ru.nl/~dgalindo/
2CWI Amsterdam
The Netherlands
kiltz@cwi.nl,j.herranz@cwi.nl
https://www.wendangku.net/doc/cf5534830.html,,http://www.cwi.nl/~herranz/
Abstract
It has been demonstrated by Bellare,Neven,and Namprempre(Eurocrypt2004)that identity-based signature schemes can be constructed from any PKI-based signature scheme.
In this paper we consider the following natural extension:is there a generic construction of
“identity-based signature schemes with additional properties”(such as identity-based blind
signatures,veri?ably encrypted signatures,...)from PKI-based signature schemes with the
same properties?Our results show that this is possible for great number of properties includ-
ing proxy signatures;(partially)blind signatures;veri?ably encrypted signatures;undeniable
signatures;forward-secure signatures;(strongly)key insulated signatures;online/o?ine sig-
natures;threshold signatures;and(with some limitations)aggregate signatures.
Using well-known results for PKI-based schemes,we conclude that such identity-based signature schemes with additional properties can be constructed,enjoying some better prop-
erties than speci?c schemes proposed until know.In particular,our work implies the exis-
tence of identity-based signatures with additional properties that are provably secure in the
standard model,do not need bilinear pairings,or can be based on general assumptions.
Keywords:Signatures with Additional Properties,Identity-Based Cryptography.
Contents
1Introduction1
1.1Our Results (2)
1.2Organization of the Paper (3)
2De?nitions3
2.1Standard Signatures (3)
2.2Identity-Based Signatures (4)
3Generic Construction of Identity-based Signatures5
3.1Veri?ably Encrypted Signatures (6)
3.2(Partially)Blind Signatures (7)
3.3Undeniable Signatures (8)
3.4Forward-Secure Signatures (9)
3.5(Strongly)Key Insulated Signatures (9)
3.6Proxy Signatures (10)
3.7Online/O?ine Signatures (10)
3.8Threshold Signatures (11)
3.9Aggregate Signatures (11)
3.10Limitations and Extensions (12)
4Generic Construction of Identity-Based Blind Signatures12
4.1Blind Signature Schemes (13)
4.2Identity-Based Blind Signature Schemes (14)
4.3Constructing Identity-Based Blind Signature Schemes (15)
4.4Security Analysis (16)
Acknowledgments19
1Introduction
Digital signatures are one of the most fundamental concepts of modern cryptography.They provide authentication,integrity and non-repudiation to digital communications,which makes them the most used public key cryptographic tool in real applications.In order to satisfy the needs of some speci?c scenarios such as electronic commerce,cash,voting,or auctions,the original concept of digital signature has been extended and modi?ed in multiple ways,giving raise to many kinds of what we call“digital signatures with additional properties”,e.g.blind signatures,veri?ably encrypted signatures,and aggregated signatures.
Initially,all these extensions were introduced for the standard PKI-based framework,where each user generates a secret key and publishes the matching public key.In practice,digital certi?cates linking public keys with identities of users are needed to implement these systems, and this fact leads to some drawbacks in e?ciency and simplicity.For this reason,the alternative framework of identity-based cryptography was introduced by Shamir[47].The idea is that the public key of a user can be directly derived from his identity,and therefore digital certi?cates are avoidable.The user obtains his secret key by interacting with some trusted master entity.In his paper,Shamir already proposed an identity-based signature scheme.In contrast,the problem of designing an e?cient and secure identity-based encryption scheme remained open until[11,46].
From a theoretical point of view,results concerning identity-based encryption schemes are more challenging than those concerning identity-based signatures(IBS).In contrast to the identity-based encryption case it is folklore that a standard PKI-based signature scheme already implies an identity-based signature scheme by using the signature scheme twice:for generat-ing user secret keys and for the actual signing process.More precisely,the user secret key of an identity consists of a fresh PKI-based signing/veri?cation key and a certi?cate proving the validity of the signing key.The latter certi?cate is established by the master entity by signing (using the master signing key)the new veri?cation key together with the user’s identity.In the actual identity-based signing process the user employs this signing key to sign the message.The identity-based signature itself consists of this signature along with the certi?cate and the public veri?cation key.
The above idea was formalized by Bellare,Neven,and Namprempre in[6],where they propose a generic and secure construction of identity-based signature schemes from any secure PKI-based signature scheme.However,some speci?c identity-based signature schemes have been proposed and published,mostly employing bilinear pairings and random oracles,without arguing if the proposed schemes are more e?cient than the schemes resulting from the generic construction in[6].In fact,in many papers the authors do not mention the generic approach from[6]and in spite of Shamir’s work from more than two decades ago[47]it still seems to be a popular “opinion”among some researchers that the construction of identity-based signatures inherently relies on bilinear pairings.
Our observation is that the situation is quite similar when identity-based signature schemes with additional properties are considered.Intuitively such schemes may be obtained using the same generic approach as in the case of standard identity-based signatures combining a digital certi?cate and a PKI-based signature scheme with the desired additional property.To the best of our knowledge,this intuitive construction was never mentioned before,nor has a formal analysis been given up to now.Furthermore,speci?c identity-based signature schemes with additional properties keep being proposed and published without arguing which improvements they bring with respect to the possible generic certi?cate-based approach.Nearly all of these papers employ bilinear pairings and the security proofs are given in the random oracle model[8] (with its well-known limitations[14]).
1.1Our Results
In this work we formally revisit this intuitive idea outlined in the last https://www.wendangku.net/doc/cf5534830.html,ly,if S is a secure PKI-based signature scheme and PS is a PKI-based signature scheme with some additional property P,we pursue the question if for a certain property P the combination of those two signature schemes can lead to a secure IBS scheme IB PS enjoying the same additional property P.We can answer this question to the positive,giving generic constructions of signature schemes with the following properties:
?Proxy signatures(PS)
?(Partially)blind signatures(PBS/BS)
?Veri?ably encrypted signatures(VES)
?Undeniable signatures(US)
?Forward-secure signatures(FSS)
?Strong key insulated signatures(SKIS)
?Online/o?ine signatures(OOS)
?Threshold signatures(TS)
?Aggregate signatures(AS)1
Implications.By considering well-known results and constructions of PKI-based signatures PS with the required additional properties,we obtain identity-based schemes IB PS from weaker assumptions than previously known.A detailed overview of our results can be looked up in Table1on page6.To give a quick overview of our results,for nearly every property P listed above,we obtain(i)the?rst IB PS scheme secure in the standard model(i.e.,without random oracles);(ii)the?rst IB PS scheme built without using bilinear pairings;and(iii)the?rst IB PS based on“general assumptions”(e.g.on the sole assumption of one-way functions), answering the main foundational question with regard to these primitives.Our results therefore implicitly resolve many“open problems”in the area of identity-based signatures with additional properties.
Generic Constructions.For some properties P the construction of the scheme IB PS is the same as in[6]and a formal security statement can be proved following basically verbatim the proofs given in[6].But as the limitations of the generic approach indicate,this approach does not work in a black-box way for every possible property P.For some special properties the certi?cate-based generic construction sketched above has to be(non-trivially)adapted to?t the speci?c nature of the signature scheme.This is in particular the case for blind and undeniable signatures and hence in these cases we will lay out our constructions in more detail. Limitations.On the other hand the generic way of constructing identity-based signatures with additional properties is not sound for every property.In particular,it does not seem to be applicable when,in the PKI-based scheme PS,an additional public key di?erent from that of the signer has to be used in the protocol.This includes ring,designated veri?er,con?rmer, 1We stress that the length of our implied aggregated identity-based signatures is still depending linearly on the number of di?erent signers(optimally it is constant)and therefore our results concerning AS are not optimal.
nominative or chameleon signatures.For these kinds of signatures,therefore,it makes more
sense to consider speci?c constructions in the identity-based framework.
Discussion.We think that in some cases the constructions of identity-based signatures with additional properties implied by our results are at least as e?cient as most of the schemes
known before.However,because of the huge number of cases to be considered,we decided not
to include a detailed e?ciency analysis of our generic constructions.Note that,in order to
analyze the e?ciency of a particular identity-based scheme resulting from our construction,we
should?rst?x the framework:whether we admit the random oracle model,whether we allow the
use of bilinear pairings,etc.Then we should take the most e?cient suitable PKI-based scheme
and measure the e?ciency of the resulting identity-based one.Our point is rather that this
comparison should be up to the authors proposing new speci?c schemes:the schemes(explicitly
and implicitly)implied by our generic approach should be used as benchmarks relative to which
both,existing and new practical schemes measure their novelty and e?ciency.
We stress that we do not claim the completely novelty of our generic approaches to construct
identity-based signatures with additional properties.Similar to[6]we rather think that most of
these constructions can be considered as folklore and are known by many researchers.However,
the immense number of existing articles neglecting these constructions was our initial motivation
for writing this paper.We think that our results may also help better understanding IBS.To
obtain a practical IBS with some additional properties the“standard method”in most articles
is to start from a standard IBS and try to“add in”the desired additional property.Our results
propose that one should rather start from a standard signature scheme with the additional
property and try to make it identity-based.We hope that the latter approach may be used to
obtain more e?cient practical schemes.
1.2Organization of the Paper
In Section2we recall the basic de?nitions(protocols and security requirements)about signature
schemes,in both the PKI-based and the identity-based frameworks.Then we present our main
results in Section3:we list those additional properties P which can be preserved by a generic construction of identity-based signatures and present the transformations.We also discuss why
this approach does not seem to work for other additional properties.We do not include the
details of the constructions and the security analysis for each additional property.However,as
a representative example,we give in Section4the details concerning the(identity-based)blind
signature case.We stress that we have a formal proof for all other constructions.
2De?nitions
In this section we recall the well-known syntax and de?nition of(identity-based)signature
schemes.
2.1Standard Signatures
A standard signature scheme S=(S.KG,S.Sign,S.Vfy)consists of the following three(probabilis-tic polynomial-time)algorithms.The key generation algorithm S.KG takes as input a security parameter k and returns a secret key SK and a matching public key PK.We use the notation (SK,PK)←S.KG(1k)to refer to one execution of this protocol.The signing algorithm S.Sign inputs a message m and a secret key SK.The output is a signature sig SK(m).We denote an execution of this protocol as sig SK(m)←S.Sign(SK,m).The veri?cation algorithm S.Vfy
takes as input a message m,a signature sig=sig SK(m)and a public key PK.The output is1 if the signature is valid,or0otherwise.We use the notation{0,1}←S.Vfy(PK,m,sig)to refer to one execution of this algorithm.
Security.We will consider security against adaptively-chosen message attacks.For a formal de?nition one considers a forger F trying to attack the scheme.This situation is modeled by the following interactive game that F plays against a challenger.
First the challenger runs the key generation protocol(SK,PK)←S.KG(1k)and gives PK to F.The secret key SK is kept secret by the challenger.During its execution the forger F adaptively chooses messages m i,then the challenger runs sig i←S.Sign(SK,m i)and gives the resulting signatures to F.Eventually the adversary F outputs a forgery consisting of a pair (m,sig).There are two kinds of unforgeability,depending on the outputs which are considered as a successful attack by F.In the standard case,we say that F succeeds if sig is a valid forgery of message m(i.e.if1←S.Vfy(PK,m,sig))and if m=m i for all the messages m i that F queried the signature for during the attack.We de?ne the advantage of such a forger F as Adv forge
S,F(k)=Pr[F succeeds].For the notion of strong unforgeability we relax the second condition such that we require(m,sig)=(m i,sig i)for all the tuples(m i,sig i)that F
has obtained during the attack and de?ne Adv sforge
S,F(k)=Pr[F succeeds].A scheme is called (strongly)unforgeable if the respective advantage is a negligible function in k.
2.2Identity-Based Signatures
An identity-based signature scheme IB S=(IB S.KG,IB S.Extr,IB S.Sign,IB S.Vfy)consists of the following four(probabilistic polynomial-time)algorithms[15].The setup algorithm IB S.KG takes as input a security parameter k and returns,on the one hand,the system public parameters mpk and,on the other hand,the value master secret key msk,which is known only to the master entity.We note an execution of this protocol as(mpk,msk)←IB S.KG(1k).The key extraction algorithm IB S.Extr takes as inputs mpk,the master secret key msk and an identity id∈{0,1}?,and returns a secret key sk[id]for the user with this identity.We use notation sk[id]←IB S.Extr(msk,id)to refer to one execution of this protocol.The signing algorithm IB S.Sign inputs a user secret key sk[id],the public parameters mpk,an identity, and a message m.The output is a signature sig=sig msk(id,m).We denote an execution of this protocol as sig←IB S.Sign(mpk,id,sk[id],m).Finally,the veri?cation algorithm IB S.Vfy inputs mpk,a message m,an identity id and a signature sig;it outputs1if the signature is valid,and0otherwise.To refer to one execution of this protocol,we use notation {0,1}←IB S.Vfy(mpk,id,m,sig).
Security.To de?ne security of an identity-based signature scheme[15],one considers a forger F IB trying to attack the scheme.This situation is modelled by the following game,that F IB plays against a challenger.
Initially,the challenger runs the key generation protocol(msk,mpk)←IB S.KG(1k)and gives mpk to F IB.The secret key msk is kept secret by the challenger.During its execution the forger F IB is allowed to make two di?erent types of queries.The forger F IB may make a key extraction query for some identity id i.Then the challenger?rst checks if it has already established a user secret key for id i.If so,the old secret key is returned.Otherwise,it stores and returns a new user secret key by running sk[id i]←IB S.Extr(msk,id i).Furthermore,the forger F IB is allowed to make signature queries with respect to pairs of identities and messages (id i,m i).The challenger?rst calls its internal key extraction oracle to obtain a(a new or stored) user secret ket sk[id i].Using this user secret key the challenger runs sig i←IB S.Sign(sk[id i],m i)
and returns the resulting signature sig i to F IB.Eventually,the adversary F IB outputs a forgery (id,m,sig).We say that F IB succeeds if sig is a valid signature for id and message m(i.e.,if 1←IB S.Vfy(mpk,id,m,sig)),if id=id i for all id i that F IB has queried user secret keys for during the attack,and if(id,m)=(id i,m i)for all the tuples(id i,m i)that F IB has queries signatures for during the attack.
We de?ne the advantage of such a forger F IB as Adv forge
IB S,F IB(k)=Pr[F IB succeeds]and a scheme is called unforgeable if this advantage is a negligible function in k.
3Generic Construction of Identity-based Signatures
In this section we?rst outline the BNN generic transformation[6]from two standard signature schemes S,S into an identity-based signature scheme.Subsequently we study the question whether,for di?erent types of signature schemes PS with additional properties,we have a (similar)generic transformation that combines S with PS to obtain IB PS,where IB PS is an identity-based signature scheme with the same additional property as PS.
Let S=(S.KG,S.Sign,S.Vfy)and S =(S .KG,S .Sign,S .Vfy)be two(possibly equal)stan-dard signature schemes.The generic construction of an identity-based signature scheme IB S= (IB S.KG,IB S.Extr,IB S.Sign,IB S.Vfy),proposed in[6],is de?ned as follows.
Key Generation IB S.KG(1k):The key generation algorithm from the standard signature scheme S is run to obtain the master key-pair for the identity-based signature scheme IB S: (msk,mpk)←S.KG(1k).
IBS Key extraction IB S.Extr(msk,id i):The secret key of a user with identity id i is de?ned as
sk[id i]=(sig msk(id i||pk i),pk i,sk i),(1) where(pk i,sk i)is a random key-pair obtained by running S .KG(1k)and sig msk(id i||pk i)←S.Sign(msk,id i||pk i).Here the signature sig msk(id i||pk i)can be viewed as a“certi?cate”on the validity of pk i.
Identity-Based Sign IB S.Sign(mpk,id i,sk[id i],m):Given a user secret key for identity id i (cf.Eqn.(1))an identity-based signature for identity id i and message m is de?ned as
sig(id i,m)=(sig msk(id i||pk i),pk i,sig sk
i
(m)),(2)
where sig sk
i (m)=S .Sign(sk i,m)can be computed by the possessor of the user secret key
sk[id i]since sk i is contained in sk[id i].Signature sig msk(id i||pk i)included in Eqn.(2)certi?es the validity of pk i.
Verification IB S.Vfy(mpk,sig):For veri?cation of the identity-based signature the user checks if the?rst signature from Eqn.(2)is valid with respect to mpk and the“message”id||pk i(using the veri?cation protocol S.Vfy);and if the second signature is valid with respect to pk i and the message m(using the veri?cation protocol S .Vfy).
Bellare,Namprempre,and Neven[6]prove the following result:
Theorem3.1If S and S are both secure standard signature schemes then IB S is a secure identity-based signature scheme.
Let PS be a signature scheme with the property P.We extend the above construction to an IBS with additional properties IB PS in a straightforward way:as with signing/veri?cation, all functionality provided by PS is“lifted”to the identity-based case.That means that(analog
Signature type Existence of identity-based signature schemes with additional properties
BS§3.2 /
US§3.3 ?
FSS§3.4
SKIS§3.5
PS§3.6 §3.7
a against concurrent adversaries.
Table1:A summary of the practical implications of our results.Here“ ”means that a scheme was known before,a“ ”means that our construction gives the?rst such scheme,and a“?”means that no such scheme is known.
to IB S.Sign and IB S.Vfy)any protocol additionally provided by PS is executed using the cor-responding secret/public key pair(sk i,pk i)from the user secret key Eqn.(1).We will refer to the latter construction as the“generic construction of identity-based signatures with additional properties”or simply“generic construction”.
In the rest of this section we will demonstrate that this generic construction and variants of it can indeed be used for many signatures schemes with additional properties:proxy signa-tures(PS);(partially)blind signatures(BS);veri?able encrypted signatures(VES);undeniable signatures(US);forward-secure signatures(FSS);strongly key insulated signatures(SKIS);on-line/o?ine signatures(OOS);threshold signatures(TS);and aggregate signatures(AS).For most properties the generic construction can be applied without many di?culties and therefore we decided to only outline the functionality and to summarize the known results for the IBS with the additional property.For(partially)blind,undeniable,and aggregate signatures our constructions derive from the generic construction and therefore we provide additional details. Due to lack of space we are forced to present our results in a rather informal way.However,as a representative example we will provide a full formal treatment of the generic construction of identity-based blind signatures in Section4.We stress that we can treat the rest of our results at the same level of formality.
In Table1we summarize the practical impact of our results,i.e.we show what types IB PS of new identity-based signature schemes are implied by our general constructions.
3.1Veri?ably Encrypted Signatures
Veri?ably encrypted signature(VES)schemes can be seen as a special extension of the standard signature primitive.VES schemes enable a user Alice to create a signature encrypted using an adjudicator’s public key(the VES signature),and enable public veri?cation if the encrypted signature is valid.The adjudicator is a trusted third party,who can reveal the standard signa-ture when needed.VES schemes provide an e?cient way to enable fairness in many practical applications such as contract signing.
An e?cient VES scheme in the random oracle model based on pairings was given in[12],one in the standard model in[40].It was further noted in[40]that VES schemes can be constructed on general assumptions such as trapdoor one-way permutations.
Identity-based veri?ably encrypted signature(IB-VES)schemes were introduced in[29] where also a concrete.security model was proposed.In contrast to[29],here we only con-
sider a weaker(but still reasonable)model where the adjudicator has a?xed public key,i.e.it is not identity-based.
Compared to a standard signature a VES scheme has three additional algorithms:VES signing/veri?cation(with respect to an adjudicators public key),and adjudication.Here the adjudication algorithm inputs an adjudicators secret key and transforms a VES into a standard signature.For our generic construction VES signing and veri?cation can be lifted to the identity-based case in the same way as in the generic construction,i.e.in an IB-VES one replaces
sig sk
i (m)in Eqn.(2)with its VES counterpart obtained by running the VES signing algorithm
on sk i,m,and the adjudicator’s public key.IB-VES veri?cation checks the certi?cate and the VES using the standard VES veri?cation algorithm.Since we only consider a standard(non identity-based)adjudicator we note that there is no need to make the adjudication process identity-based.More formally we can prove the following theorem:
Theorem3.2If S is a secure standard signature scheme and PS is a secure veri?ably encrypted signature scheme then the generic construction gives a secure identity-based veri?ably encrypted signature scheme.
An pairing-based IB-VES scheme secure in the random oracle model was given in[29].We note that the IB-VES scheme from[19]does not have a formal security https://www.wendangku.net/doc/cf5534830.html,ing our generic construction we get an IB-VES scheme based on any trapdoor one-way function[40],and a more e?cient one using[12].
3.2(Partially)Blind Signatures
In blind signature(BS)schemes[16]a user can ask a signer to blindly sign a(secret)message m.At the end of the(interactive)signing process,the user obtains a valid signature on m,but the signer has no information about the message he has just signed.A formal security model of blind signatures was introduced in[33,44].Partially blind signature schemes are a variation of this concept,where the signer can include some common information in the blind signature, under some agreement with the?nal receiver of the signature.This concept was introduced in [1]and the security of such schemes was formalized in[2].
The?rst identity-based blind signature(IB-BS)schemes were proposed in[54,53].They employ bilinear pairings,but their security is not formally analyzed.Subsequent schemes were proposed in[21]but security is only provided in a weaker model(i.e.against sequential ad-versaries).We take the case of blind signatures to exemplify how our generic construction of identity-based signature schemes with additional properties works:in Section4we give all nec-essary formal de?nitions,our generic construction,and a formal security analysis.The case of partially blind signatures can be analyzed in a very similar way.Summing up,and quite informally,we will obtain the following general result(see Section4for details).
Theorem3.3If S is a strongly secure standard signature scheme and PS is a secure(partially) blind signature scheme then a secure identity-based(partially)blind signature scheme IB PS can be constructed.
Here the IB-BS scheme inherits the security properties of the BS scheme—if BS is secure against concurrent adversaries so is IB-BS.In particular,we obtain the?rst IB-BS scheme provably secure(in the standard model),against concurrent adversaries(by using the results from[13,43,26]),we obtain IB-BS schemes which do not employ bilinear pairings[7],and we obtain IB-BS schemes from any one-way trapdoor permutation[33,26].
3.3Undeniable Signatures
Undeniable signatures[18](US)are signature schemes in which testing for(in)validity of a sig-nature requires interaction with the signer.Undeniable signatures are used in applications where signed documents carry some private information about the signer and where it is considered to be an important privacy factor to limit the ability of veri?cation.
Following[23],an undeniable signature scheme US consists of four algorithms US=(US.KG, US.Sign,US.Conf,US.Disav),where US.Conf is a con?rmation and US.Disav is a disavowal pro-tocol,both being interactive algorithms run between a prover and a veri?er.The basic se-curity properties are(standard)unforgeability,non-transferability and simulatability.By non-transferability it is meant that no adversary should be able to convince any third party of the validity/invalidity of a given message/signature pair after having participated in the con?rmation and disavowal protocols.Intuitively this is captured by requiring the con?rmation and disavowal protocols to be“zero-knowledge”,such that no information is leaked besides(in)validity.With simulatability one wants to ensure that the strings representing signatures can not be recognized (i.e.,distinguished from a random string)by an attacker.This security property is ful?lled if there exists a signature simulator algorithm US.Sim,that on input of a public key and a message, outputs a simulated signature sig(m)which looks like a“real undeniable signature”to anyone who only knows public information and has access to con?rmation/disavowal oracles.
Extending the previous de?nition to the identity-based setting,an identity-based unde-niable signature(IB-US)scheme consists of a tuple of?ve algorithms IB US=(IB US.KG, IB US.Extr,IB US.Sign,IB US.Conf,IB US.Disav)where IB US.Conf and IB US.Disav are inter-active algorithms run between a prover and a veri?er.The basic security properties for an IB-US(unforgeability,non-transferability and simulatability),are de?ned by suitably adapting the standard US security notions to the identity-based scenario.
In particular,the identity-based simulatability property is de?ned in terms of the existence of an additional simulation algorithm IB US.Sim.On input of the system public parameters mpk, an identity id and a message m,IB US.Sim outputs a simulated signature sig(id,m),which is indistinguishable from a real signature for someone having access to con?rmation/disavowal oracles for the identity id.
We now sketch our generic construction of identity-based undeniable signatures.In contrast to the generic construction(cf.Eqn.(2))we de?ne the identity-based undeniable signature
IB US.Sign(sk[id i],m)as sig sk
i (m)(i.e.,the certi?cate sig msk(id i||pk i)and pk i are not included
in the signature).In the interactive identity-based con?rmation and disavowal protocols,the signer sends his certi?cate(sig msk(id i||pk i),pk i)to the veri?er such that the veri?er can be convinced about the link between the signature and id i||pk i.Then prover(using sk i)and veri?er(using pk i)engage in the standard US con?rmation/disavowal protocol.2 It remains to describe the identity-based simulation algorithm IB US.Sim in terms of the underlying algorithm US.Sim.We de?ne the output of IB US.Sim(mpk,id,m)as US.Sim(pk i,m), where(pk i,sk i)←US.KG(1k)is a fresh key pair generated by the simulator.Note that the simulator IB US.Sim does not input the user secret key sk[id]and therefore the public key pk i from the user secret key for id i(cf.Eqn.(1))is information theoretically hidden from it. However,an adversary against simulatability may learn this public key pk i from an execution of the con?rmation/disavowal protocol.It turns out that to ensure that our generic IB-US 2At this point it may be interesting to see why the generic construction would not be simulatable and therefore not secure.In our generic construction the signature also contains(sig msk(id i||pk i),pk i).Now,for building an identity-based signature simulator,one should be able to simulate the signatures sig msk(id i||pk i)based on the master public-key only,which is infeasible since the signature scheme S is assumed to be unforgeable.
construction satis?es the simulatability property it is su?cient to require the scheme US to be anonymous in the sense of[27].A scheme US is said to be anonymous if(roughly)for two randomly generated key pairs(pk0,sk0),(pk1,sk1)and a message m,it is infeasible to distinguish the two distributions US.Sign(sk0,m)and US.Sign(sk1,m).More formally,we can prove the following theorem:
Theorem3.4If S is a secure standard signature scheme and US is a secure anonymous un-deniable signature scheme then IB US as outlined above is a secure identity-based undeniable signature scheme.
As far as we know,only one IB-US has been previously presented in[39].This scheme uses bilinear pairings and it is proved secure in the random oracle model.We stress that the security model in[39]seems to be incomplete,as the authors do not consider simulatability.
In[27],an anonymous PKI-based US scheme based on the RSA primitive was proposed(the security proof uses the random oracle model).A di?erent anonymous US scheme,whose security is proved in the standard model,can be found in[37];it does not employ bilinear pairings,but the disavowal protocol is quite ine?https://www.wendangku.net/doc/cf5534830.html,ing these anonymous US schemes[27,37],we can obtain secure IB-US schemes in the random oracle model and also in the standard model,based on di?erent computational assumptions,which do not employ bilinear pairings.
3.4Forward-Secure Signatures
In a forward-secure signature(FSS)scheme the veri?cation key is?xed but the signing key is updated at regular intervals,in such a way that compromise of the signing key at a certain time period does not allow to forge signatures pertaining to any previous period.
History on FSS:FSS schemes were studied for the?rst time in[5],in order to mitigate the damage caused by key exposure without requiring redistribution of keys.Shortly after their introduction,a construction of FSS schemes from any signature scheme was proposed in[35]. In particular,this result implies that FSS schemes can be obtained from any one-way function.
To the best of our knowledge,the concept of identity-based forward-secure signature(IB-FSS)has not been previously considered in the literature.In a IB-FSS scheme,the identity id of the signer remains?xed,while the signing key sk[id]j is updated at regular intervals. Roughly speaking,the initial signing key sk[id]0is delivered to the user by the master entity, while the signing keys for the subsequent periods are generated by the user itself.Notice that this approach favorably compares with the usual way to defense against key exposure used in identity-based cryptography,in which the master entity issues new private keys sk[id||j]to the user with identity id at every time period j.The latter approach heavily relies on the master entity and increases the(costly)communication between the entity and the users.
Theorem3.5If S is a secure standard signature scheme and PS is a secure forward-secure signature scheme then the generic construction gives a secure identity-based forward-secure signature scheme IB PS.
As a consequence of this theorem IB-FSS can be constructed from any one-way function[35].
3.5(Strongly)Key Insulated Signatures
The concept of(strongly)key insulated signatures(SKIS)was introduced in[24]and is quite similar to the one of FSS.Without going into details we remark that the generic construction of identity-based SKIS is secure provided the underlying SKIS is secure.SKIS signatures can
be built from any one-way function[24],which implies our generic construction yields identity-based SKIS schemes from any one-way function.Previously,an identity-based SKIS using bilinear pairings and random oracles has been proposed in[55].
3.6Proxy Signatures
In proxy signature(PS)schemes,an original signer A delegates its signing capabilities to a proxy signer B,in such a way that B can sign(some speci?ed set of)messages on behalf of A.The recipient of the?nal message veri?es at the same time that B computed the signature and that A had delegated its signing capabilities to B.
The concept of proxy signatures was introduced in[42].The?rst formal analysis of the security of PKI-based proxy signatures was done in[9]where is was shown that a secure proxy signature scheme can be constructed from any secure digital signature scheme(and therefore, in particular,from any one-way function).In general,one looks for more e?cient constructions of(identity-based)proxy signature schemes than this generic constructions.Our generic con-struction to obtain an IB-PS from any PKI-based PS works in general,provided the public key of the proxy signer is not strictly needed in the delegation phase of the considered PKI-based PS(which is the case in general,where the public key is only used as an identi?er of the proxy, and so it can be replaced with the identity of the proxy in the constructed IB-PS).Summing up,we obtain the following result.
Theorem3.6If S is a secure standard signature scheme and PS is a secure proxy signa-ture scheme then the generic construction gives a secure identity-based proxy signature scheme IB PS.
History on IB-PS:The?rst IB-PS appeared in[53],but they lacked of a formal security analysis,since the?rst formal security model for IB-PS(which was adapted from the one in [9])came later,in[51].All these existing proposals of IB-PS employ bilinear pairings,and their security is proved in the random oracle model.With our certi?cate-based approach,we can easily obtain IB-PS which do not employ bilinear pairings and whose security can be proved in the standard model.Furthermore,based on[9]we obtain an IB-PS scheme based on any one-way function.
3.7Online/O?ine Signatures
In online/o?ine signatures signing is split into two phases:the o?ine and online phase.The idea is to shift the major computational overhead to the o?ine phase,whereas the online phase requires only a very low computational overhead.
Online/o?ine signatures were introduced in[25].They presented a general method for converting any signature scheme into an online/o?ine signature scheme which was later improved in[48].Using our generic construction we can make identity-based signing online/o?ine. Theorem3.7If S is a secure standard signature scheme and PS is a secure online/o?ine signature scheme then the generic construction gives a secure online/o?ine signature scheme IB PS.
We are only aware of one identity-based online/o?ine signature scheme[52]in the literature that is in the random oracle model and uses bilinear pairings.Applying the known generic construction[25]to our construction we get identity-based online/o?ine signature scheme based on one-way functions.
3.8Threshold Signatures
Threshold signatures(TS)are used whenever the ability to sign must be decentralized.The idea is to share the signing power(the master secret key)among a number of di?erent players, in such a way that signing is possible only when a su?ciently large enough number of honest players cooperate together.A PKI-based non-interactive threshold signature schemes in the standard model and without pairings has recently been proposed in[22].
Identity-Based Threshold Signatures(IB-TS)were introduced in[4],to be used in a context where the signing key sk[id]is shared by a collective of signers with a common identity id. Given any j-th share sk[id]j of the signing key it is possible to(non-interactively)create a j-th signature share sig(id,m)j,so that a full signature sig(id,m)is obtained by combining a su?ciently large fraction of correctly generated signature shares from di?erent(honest)players. More IB-TS schemes were proposed in[20].
In the following,an IB-TS construction based on our generic construction is outlined.The components are a signature scheme S and a threshold signature scheme TS.Let(msk,mpk)←S.KG(1k)be the master entity keys.For each identity id,the master entity executes the key generation algorithm for TS,obtaining a veri?cation key pk and a set of shares{sk1,...,sk n} of the matching secret key.Then,sk[id]j(i.e.the j-th share of the signing key sk[id])is de?ned as sk[id]j=(sig msk(id||pk),pk,sk j).In a similar fashion,sig(id,m)j(i.e.the j-th signature share for a message m by the j-th player holding the identity id)is de?ned as (sig msk(id||pk),pk,sig(m)j),where sig(m)j denotes the signature share on message m obtained by the j-th player when applying the signing protocol of the PKI-based threshold scheme TS. The full signature sig(id,m)is computed by combining signature shares sig(id,m)j(using the combining algorithm of TS with inputs shares sig(m)j).
Note that,if the signing phase of the PKI-based threshold signature scheme TS is non-interactive,we obtain a non-interactive identity-based threshold signature scheme(i.e.,compa-rable to that in[4]).
Theorem3.8If S is a secure standard signature scheme and PS is a secure threshold signature scheme then the generic construction gives a secure identity-based threshold signature scheme IB PS.
As a consequence of this theorem and the work[22],IB-TS schemes can be obtained from RSA or discrete-log based signatures,without resorting to random oracles.
3.9Aggregate Signatures
The idea of an aggregate signature scheme is to combine n signatures on n di?erent messages, signed by n(possibly di?erent)signers,in order to obtain a single aggregate signature which provides the same certainty than the n initial signatures.In the PKI-based scenario,an execution of such an aggregation mechanism can be represented as
Ag Sig←?Aggregate({(pk i,m i,sig sk
(m i)}1≤i≤n).
i
The main goal in the design of such protocols is that the length of Ag Sig be constant,inde-pendent of the number of messages and signers.Of course,to check correctness of an aggregate signature,the veri?er will also need the messages m i and the public keys pk i,but this is not taken into account when considering the length of Ag Sig.
The idea of aggregate signatures was introduced in[12],where a scheme with constant-length aggregate signatures is presented and analyzed,based on the signature scheme of[10].In the identity-based framework,the only proposal which achieves constant-length aggregation is that
of [28];however,this scheme only works in a more restrictive scenario where some interaction or sequentiality is needed among the signers of the messages which later will be aggregated (in the same direction as [41,40]for the PKI-based scenario).With respect to strict aggregate signatures (without any kind of interaction among the signers)in the identity-based setting,the most e?cient proposal is that in [30],which does not achieve constant-length aggregation:the length of the aggregate signature does not depend on the number of signed messages,but on the number of di?erent signers.
Using the approach of this work,we can achieve exactly the same level of partial aggregation for identity-based signatures.In e?ect,let us consider our generic construction,and let us as-sume that the employed PKI-based signature scheme S allows constant-length aggregation.The the input of the aggregation algorithm would be {(id i ,sig msk (id i ||pk i ),pk i ,m i ,sig sk i (m i )}1≤i ≤n ,where sig msk (id i ||pk i )and sig sk i (m i )are signatures resulting from scheme S ,and can therefore be aggregated into a PKI-based aggregate signature Ag Sig ,of constant-length.Then the ?nal identity-based aggregate signature would be
IB Ag Sig =(Ag Sig,pk 1,...,pk n ).
This aggregate signature,along with the n messages and the n identities,is su?cient to verify the correctness of the n signatures.Therefore,similar to [30],the length of the identity-based aggregate signature IB Ag Sig is linear with respect to the number of di?erent signers (and not with respect to the number of messages).
3.10Limitations and Extensions
Our generic approach to construct identity-based signature schemes with special properties does not work in situations where the signing procedure (in the corresponding PKI-based scheme)involves other public keys than the one from the signer,and interaction between the signer and the owners of these public keys is not mandatory.Our approach fails in this case because in the identity-based framework the signer only knows the identity of the other users,and needs some interaction with them in order to know the public key that they have received in the key extraction phase.
Some examples of signature schemes with special properties falling inside this group are:ring signatures [45,54];designated veri?er signatures [31,49];con?rmer signatures [17];chameleon signatures [36,3];and nominative signatures [50].
We are aware of the fact that the list of properties where the generic approach can be applied is not complete and it obviously can also be applied to other concepts (like one-time signatures [38],homomorphic signatures [32],etc.)as well.We also note that our generic construction can be extended to the case of hierarchical identity-based signatures (HIBS)using certi?cate-chains [34].Furthermore,combinations of di?erent additional properties are possible,e.g.it is possible to give a generic construction of identity-based threshold undeniable signatures based on the existence threshold undeniable signatures.
4Generic Construction of Identity-Based Blind Signatures
In this section we consider in more detail the generic construction in the case of blind signature schemes.We ?rst recall the basic de?nitions of PKI-based and identity-based blind signature schemes,then we explain and analyze our construction.
4.1Blind Signature Schemes
Blind signature schemes were introduced in[16]with electronic banking as?rst motivation. The intuitive idea is that a user asks some signer to blindly sign a(secret)message m.At the end of the process,the user obtains a valid signature on m from the signer,but the signer has no information about the message he has signed.More formally,a blind signature scheme BS=(BS.KG,BS.Sign,BS.Vfy)consists of the following(partially interactive)algorithms.
The key generation algorithm BS.KG takes as input a security parameter k and returns a secret key sk and a matching public key pk.We use notation(sk,pk)←BS.KG(1k)to refer to one execution of this protocol.The blind signing algorithm BS.Sign is an interactive protocol between a user U and a signer S with public key pk.The input for the user is Inp U= (m,pk)where m is the message he wants to be signed by the signer.The input Inp S of the signer is his secret key sk.In the end,the output Out S of the signer is’completed’or’not completed’,whereas the output Out U of the user is either’fail’or a signature sig=sig sk(m).We use notation(Out U,Out S)←BS.Sign(Inp U,Inp S)to refer to one execution of this interactive protocol.Finally,the veri?cation algorithm BS.Vfy is the same veri?cation protocol as in standard signature schemes.To refer to one execution of this protocol,we use notation{0,1}←BS.Vfy(m,sig).
Blindness.Intuitively,the blindness property captures the notion of a signer who tries to obtain some information about the messages he is signing for some user.Formally,this notion is de?ned by the following game that an adversary(signer)B plays against a challenger(who plays the role of a user).
First the adversary B runs the key generation protocol(sk,pk)←BS.KG(1k).Then the adversary B chooses two messages m0and m1and sends them to the challenger,along with the public key pk.The challenger chooses at random one bit b∈{0,1}and then the interactive sign-ing protocol is executed two times(possibly in a concurrent way),resulting in(Out U,b,Out S,b)←BS.Sign(Inp U,b,Inp S,b)and(Out U,1?b,Out S,1?b)←BS.Sign(Inp U,1?b,Inp S,1?b),where adversary B plays the role of the signer S,and the challenger plays the role of the user,with inputs Inp U,b=(pk,m b)and Inp U,1?b=(pk,m1?b).Finally,the adversary B outputs its guess b .Note that the adversary in the above security game is in the possession of the secret key sk.
We say that such an adversary B succeeds if b =b and de?ne its advantage in the above game as Adv blind
BS,B(k)=|Pr[b =b]?1/2|.A scheme BS has the blindness property if,for all PPT adversaries B,Adv blind
BS,B(k)is a negligible function(with respect to the security parameter k).If Adv blind
BS,B(k)is exactly0,for any(possibly computationally unbounded)adversary B,then the blindness of the scheme is unconditional.
Unforgeability.Unforgeability captures the intuitive requirement that a user obtains a valid signature from the signer only if they complete together an execution of the blind signature protocol.Among the di?erent(but equivalent)formal de?nitions of unforgeability for blind signature schemes(see,e.g.,[33,44]),we consider the one from[33],which is given by the following game that an adversary F(user or forger)plays against a challenger(signer).
First the challenger runs the key generation protocol(pk,sk)←BS.KG(1k)and gives pk to F,whereas the secret key sk is kept secret by the challenger.During its execution the forger F adaptively chooses messages m j,then the interactive signing protocol(Out U,Out S)←BS.Sign(Inp U,Inp S)is executed(possibly in a concurrent way),where the adversary F plays the role of the user U,with input Inp U=(pk,m j),and the challenger plays the role of the signer,with input the secret key sk.Let be the number of such queries that?nish with Out S=’completed’.Eventually the adversary F outputs a list of tuples{(m i,sig i)}1≤i≤ .
We say that F succeeds if < and1←BS.Vfy(pk,m i,sig i),for all i=1,..., .
We say that such an adversary F is an( , )-forger and de?ne its advantage as Adv forge
BS,F(k)= Pr[F succeeds].The scheme BS is unforgeable if Adv forge
BS,F(k)is a negligible function in k for all PPT( , )-forger F.
4.2Identity-Based Blind Signature Schemes
Analogously,an identity-based blind signature scheme IB BS=(IB BS.KG,IB BS.Extr,IB BS.Sign, IB BS.Vfy)consists of the following algorithms.
The setup algorithm IB BS.KG takes as input a security parameter k and returns,on the one hand,the master public key mpk and,on the other hand,the value master secret key msk,which is known only to the master entity.We note an execution of this protocol as (msk,mpk)←IB BS.KG(1k).The key extraction algorithm IB BS.Extr takes as inputs mpk, the master secret key msk and an identity id∈{0,1}?,and returns a secret key sk[id]for the user with this identity.We use notation sk[id]←IB BS.Extr(msk,id)to refer to one execution of this protocol.The blind signing algorithm IB BS.Sign is an interactive protocol between a user U and a signer with identity id.The common input for them is mpk.The input for the user is Inp U=(id,m)where m is the message he wants to be signed by id.The input Inp id of the signer is his secret key sk[id].In the end,the output Out id of the signer is ’completed’or’not completed’,whereas the output Out U of the user is either’fail’or a signature sig=sig msk(id,m).We use notation(Out U,Out id)←IB BS.Sign(mpk,Inp U,Inp id)to refer to one execution of this interactive protocol.Finally,the veri?cation algorithm IB BS.Vfy takes as input mpk,a message m,an identity id and a signature sig;it outputs1if the signature is valid with respect to the public key mpk and the identity id,and0otherwise.To refer to one execution of this protocol,we use notation{0,1}←IB BS.Vfy(mpk,id,m,sig).
An identity-based blind signature scheme must satisfy the requirements of correctness,blind-ness and unforgeability,that we now explain in detail.
Correctness.For any execution of the setup protocol(msk,mpk)←IB BS.KG(1k),the key extraction protocol sk[id]←IB BS.Extr(msk,id),and the interactive signing protocol (Out U,Out id)←IB BS.Sign(mpk,Inp U,Inp id),where Inp U=(id,m)and Inp id=sk[id],the following property must be satis?ed:
Out id= completed =? 1←IB BS.Vfy(mpk,id,m,Out U) .
Blindness.Blindness of an identity-based blind signature scheme is de?ned by a game played between a challenger and an adversary.This adversary B IB models the dishonest behavior of a signer who tries to distinguish which message(between two messages chosen by himself)is being signed in an interactive execution of the signing protocol with a user.The game is as follows.
First the challenger runs the setup protocol(msk,mpk)←IB BS.KG(1k)and gives mpk to B IB.The master secret key msk is kept secret by the challenger.The adversary B IB is allowed to query for secret keys of identities id i of his choice.The challenger runs sk[id i]←IB BS.Extr(msk,id i)and gives the resulting secret key sk[id i]to B IB.If the same identity is asked again,the same value sk[id i]must be returned by the challenger.At some point,the adversary B IB chooses an identity id?and two messages m0,m1,and sends these values to the challenger.The challenger chooses at random one bit b∈{0,1}and then the interactive signing protocol is executed twice(possibly in a concurrent way),resulting in(Out U,b,Out id?,b)←IB BS.Sign(Inp U,b,Inp id?,b)and(Out U,1?b,Out id?,1?b)←IB BS.Sign(Inp U,1?b,Inp id?,1?b),where
adversary B IB plays the role of the signer id?,and the challenger plays the role of the user,with inputs Inp U,b=(m b,id?)and Inp U,1?b=(m1?b,id?).Finally,the adversary B IB outputs its guess b .
We say that such an adversary B succeeds if b =b and de?ne its advantage in the above game as Adv ib-blind
IB BS,B IB(k)=|Pr[b =b]?1/2|.A scheme IB BS has the blindness property if,for all PPT adversaries B IB,Adv ib-blind
IB BS,B IB(k)is a negligible function(with respect to the security
parameter k).If Adv ib-blind
B IB
(k)is exactly0,for any(possibly computationally unbounded) adversary B IB,then the blindness of the scheme is unconditional.
Unforgeability.Our de?nition of unforgeability for identity-based blind signatures is adapted from the concept of( , )-unforgeability introduced in[33]for standard PKI-based blind sig-natures.A forger F IB against the unforgeability property of an identity-based blind signature scheme is de?ned by means of the following game that it plays against a challenger.
First of all,the challenger runs the setup protocol(msk,mpk)←IB BS.KG(1k)and gives mpk to F IB.The master secret key msk is kept secret by the challenger.Then the forger F IB can make two kinds of queries to the challenger.On the one hand,F IB can ask for the secret key of an identity id i of his choice;the challenger runs sk[id i]←IB BS.Extr(msk,id i) and gives the resulting user secret key sk[id i]to F IB.If an identity id i is asked twice,the challenger must returns the same secret key sk[id i].On the other hand,the forger F IB can ask for the execution of the blind signing protocol:F IB chooses pairs(id j,m j),then the challenger ?rst runs sk[id j]←IB BS.Extr(msk,id j)to get the secret key sk[id j]for this identity.After that,the interactive signing protocol(Out U,Out id)←IB BS.Sign(mpk,Inp U,Inp id)is executed (possibly in a concurrent way),where the adversary F IB plays the role of the user U,with input Inp U=(id j,m j),and the challenger plays the role of the signer id j,with input the secret key
sk[id j].Let be the number of such queries that?nish with Out id
j =’completed’.Eventually,
the adversary F IB?nally outputs a list of tuples{(id i,m i,sig i)}1≤i≤ .We say that F IB succeeds if:
? < ;
?1←IB BS.Vfy(mpk,id i,m i,sig i),for all i=1,..., ;
?the pairs(id i,m i)included in the output list are pairwise di?erent;and
?F IB did not ask a secret key query for any of the identities id i in the output list.
We say that such an adversary F IB is an( , )-forger and de?ne its advantage as Adv ib-forge
IB BS,F IB(k)= Pr[F IB succeeds].The scheme IB BS is unforgeable if Adv ib-forge
IB BS,F IB is a negligible function in k for all PPT( , )-forgers F IB.
4.3Constructing Identity-Based Blind Signature Schemes
Let S=(S.KG,S.Sign,S.Vfy)be a standard signature scheme and let BS=(BS.KG,BS.Sign,BS.Vfy) be a blind signature scheme.We construct an identity-based blind signature scheme IB BS= (IB BS.KG,IB BS.Sign,IB BS.Extr,IB BS.Vfy)as follows.
Setup IB BS.KG(1k):on input a security parameter k,the key generation protocol S.KG of S
is executed,resulting in(SK,PK)←S.KG(1k).The master public key is de?ned as mpk=PK, whereas the master secret key stored by the master entity is msk=SK.
Key extraction IB BS .Extr (msk ,id i ):when the user secret key sk [id i ]for some identity id i is requested,the master entity ?rst checks if it already has established a user secret key for id i .If so,the old secret key is returned.Otherwise it generates and stores a new user secret key as follows:it runs the key generation protocol of the blind signature scheme BS ,resulting in (sk i ,pk i )←BS .KG (1k ).Then it uses signature scheme S to sign the ”message”id i pk i ,that is,it executes sig msk (id i pk i )←S .Sign (msk ,id i pk i ).The resulting secret key,which is sent to the owner of the identity,is sk [id i ]=(sk i ,pk i ,sig msk (id i pk i )).The recipient can verify the obtained secret key by executing {0,1}←S .Vfy (mpk ,id i pk i ,sig msk (id i ||pk i ));if the output is 1,then the secret key is accepted.
Blind signature IB BS .Sign :the interactive protocol between a user U and a signer with identity id i consists of the following steps (recall that mpk is a common input for user and signer,the input of the user is (id i ,m )and the input of the signer is sk [id i ]).
https://www.wendangku.net/doc/cf5534830.html,er U sends the query (id i , blindsignature? )to the signer.
2.If the signer does not want to sign,the protocol ?nishes with Out U =’fail’and Out id i =’not completed’.Otherwise,the signer sends (pk i ,sig msk (id i ||pk i ))back to the user.
3.The user runs {0,1}←S .Vfy (mpk ,id i ||pk i ,sig msk (id i ||pk i )).If the output is 0,then the protocol ?nishes with Out U =’fail’and Out id i =’not completed’.
Otherwise,user and signer interact to run the blind signature protocol of BS ,result-ing in (Out U ,Out id i )←BS .Sign (Inp U ,Inp id i ),where Inp U =(pk i ,m )and Inp id i =sk i .If Out U =’fail’,then it consists of a standard signature sig sk i (m )on m under secret key sk i .The ?nal output for the user is in this case Out U =sig (id i ,m i )=(sig msk (id i ||pk i ),pk i ,sig sk i (m )),which is de?ned to be the identity-based signature on message m coming from identity id i .
Veri?cation IB BS .Vfy (mpk ,id i ,m,sig (id i ,m i )):given as input a message m ,an identity id i and an identity-based signature sig (id i ,m i )that is parsed as (sig msk (id i ||pk i ),pk i ,sig sk i (m )),the veri?cation protocol works as follows.The two veri?cation protocols,of schemes S and BS ,are executed:{0,1}←S .Vfy (mpk ,id i ||pk i ,sig msk (id i ||pk i ))and {0,1}←BS .Vfy (pk i ,m,sig sk i (m )).If both outputs are 1,then the ?nal output of this protocol is also 1.Otherwise,the output is 0.
4.4Security Analysis
In this section we prove that the identity-based blind signature scheme IB BS constructed in the previous section satis?es the three required security properties.It is very easy to check correctness of the protocol.Let us prove in detail that blindness and unforgeability also hold,assuming that the schemes S and BS employed as primitives are secure.
Theorem 4.1Assume the signature scheme S is strongly unforgeable and the blind signature scheme BS is blind.Then the identity-based blind signature scheme IB BS constructed in Section 4.3is blind.
Proof:To prove this result,we show that if there exists a successful adversary B IB against the blindness of the scheme IB BS ,then there exists either a successful forger F against the
signature scheme S or a successful adversary B against the blindness of the blind signature scheme BS.In particular we show that
Adv ib-blind
BS,B(k)+Adv sforge
IB BS,B IB(k)≤Adv blind
S,F(k).
We now construct F and B.
Setup.Forger F receives as initial input some public key PK for the standard signature scheme S.Then we initialize the adversary B IB by providing it with mpk=PK.
Secret key queries.Adversary B IB is allowed to make secret key queries for identities id i of its choice.To answer this query,we run the key generation protocol of the blind signature scheme BS to obtain(sk i,pk i)←BS.KG(1k).Then we send the query m i=id i pk i to the signing oracle associated to the forger F,and obtain as answer a valid signature sig i with respect to scheme S and public key PK=mpk.Then we send to B IB the consistent answer sk[id i]=(sk i,pk i,sig i).We store all this information in some table.If the same identity is asked twice by B IB,then the same secret key is given as answer.
Challenge.At some point,B IB will output some challenge identity id?and two messages m0,m1.Without loss of generality we can assume that B IB had already asked for the secret key of this identity(otherwise,we generate it now and send it to B IB),obtaining sk[id?]=(sk?,pk?,sig?).Then we start constructing an adversary B against the blindness of the blind signature scheme BS,by sending public key pk?and messages m0,m1to the corresponding challenger.
Now we must execute twice the interactive blind signature protocol with B IB,where B IB acts as a signer and we act as the user.For both executions,we?rst send(id?, blindsignature? ) to B IB.As answers,we will obtain(pk(0)?,sig(0)?)and(pk(1)?,sig(1)?)from B IB,where sig(j)?
is a valid signature on id? pk(j)?,for both j=0,1.
If(pk(j)?,sig(j)?)=(pk?,sig?)for either j=0of j=1,then F outputs sig(j)?as a valid forgery on the message id?||pk(j)?for the signature scheme S.This is a valid forgery against signature scheme S,because these signatures were not obtained during the attack.
Therefore,in this case we would have a successful forger F against S,contradicting the hypothesis in the statement of the theorem which claims that S is strongly unforgeable.
From now on we assume that we have(pk(j)?,sig(j)?)=(pk?,sig?)for both j=0,1and the two?rst steps in the two executions of the interactive signing protocol are identical.Then we run the two execution of the blind signing protocol of scheme BS,playing the role of the signer:we obtain from B IB the information that we must send to the challenger(user) of BS,and this challenger sends back to us the information that we must provide to B IB.
This challenger of BS is the one who chooses the bit b∈{0,1}.
At the end,the adversary B IB outputs its guess b .B outputs the same bit b as its guess in the blindness game against the blind signature scheme BS.
Since the two?rst steps in the two executions of the interactive signing protocol of IB BS run between B IB and us are identical,we have that distinguishing between the two executions of
IB BS.Sign is equivalent to distinguishing between the two executions of BS.Sign.
Summing up,if B IB succeeds in breaking the blindness of IB BS.Sign,then we can construct an algorithm which breaks the blindness of BS.Sign,with exactly the same success probability.
We stress that the signature scheme S really has to be strongly unforgeable.Otherwise an signer can break blindness by using di?erent versions of sk[id i]in di?erent signing sessions and later use this information to trace the user.
Theorem4.2Assume the standard signature scheme S is unforgeable and the blind signa-ture scheme BS is unforgeable.Then the identity-based blind signature scheme IB BS from Section4.3is unforgeable.
Proof:The proof of Theorem4.2is similar to the one of Theorem4.1.We prove that if there exists a successful adversary F IB against the unforgeability of the scheme IB BS,then there exists either a successful forger F against the unforgeability of the signature scheme S or a successful adversary F against the unforgeability of the blind signature scheme BS.In particular,we show that
Adv forge
IB BS,F IB(k)≤q·(Adv forge
BS,F (k)+Adv forge
S,F(k)),
where q is an upper bound for the total number of di?erent identities appearing in F IB’s queries during the security experiment.
Let us assume F IB is an( , )-forger for some value (polynomial in k)and let us construct from it F and F ,where at least one of them is successful.
Setup.Forger F receives as initial input some public key PK for the signature scheme S.
Then we initialize adversary F by providing it with mpk=PK.Then the adversary
F IB is allowed to make two di?erent kinds of queries,secret key queries for identities id i
and blind signature queries for pairs(id j,m j).First of all,we choose at random some integer i?∈{1,2,...,q}(recall that q is an upper bound for the total number of di?erent identities appearing in F IB’s queries).We also start constructing an adversary F against the unforgeability of the blind signature scheme BS,receiving from the corresponding challenger some public key pk?.
Queries.Each time a new identity id i appears in some of the queries made by F IB,where the indices refer to the order of appearance(id1is the?rst identity that appears in some F IB’s queries,and so on),we act as follows:
?If i=i?,then we run the key generation protocol of the blind signature scheme BS
to obtain(sk i,pk i)←BS.KG(1k).Then we send the query m i=id i pk i to the
signing oracle associated to the forger F,and we obtain as answer a valid signature
sig i with respect to the scheme S and public key mpk=PK.
?For i?-th identity,we send the query m i
?=id i
?
pk?to the signing oracle associated
to the forger F,and we obtain as answer a valid signature sig i
?
.
Now we are ready to answer F IB’s queries.If F IB asks for the secret key of id i
?,we abort.
Otherwise,if F IB asks for the secret key of id i,with i=i?,then we send back the correct secret key sk[id i]=(pk i,sig i,sk i).
With respect to blind signature queries(id j,m j),if id j=id i
?,we can perfectly simulate
a running of the blind signing protocol because we know the secret key sk[id j]for this
signer.Otherwise,if id j=id i
?,then the?rst message(id i
?
, blindsignature? )comes from
the adversary(acting as a user).We answer by sending back to F IB the values(pk?,sig i
?
).
黄自艺术歌曲钢琴伴奏及艺术成就
【摘要】黄自先生是我国杰出的音乐家，他以艺术歌曲的创作最为代表。而黄自先生特别强调了钢琴伴奏对于艺术歌曲组成的重要性。本文是以黄自先生创作的具有爱国主义和人道主义的艺术歌曲《天伦歌》为研究对象，通过对作品分析，归纳钢琴伴奏的弹奏方法与特点，并总结黄自先生的艺术成就与贡献。 【关键词】艺术歌曲；和声；伴奏织体；弹奏技巧 一、黄自艺术歌曲《天伦歌》的分析 （一）《天伦歌》的人文及创作背景。黄自的艺术歌曲《天伦歌》是一首具有教育意义和人道主义精神的作品。同时，它也具有民族性的特点。这首作品是根据联华公司的影片《天伦》而创作的主题曲，也是我国近代音乐史上第一首为电影谱写的艺术歌曲。作品创作于我国政治动荡、经济不稳定的30年代，这个时期，这种文化思潮冲击着我国各个领域，连音乐艺术领域也未幸免――以《毛毛雨》为代表的黄色歌曲流传广泛，对人民大众，尤其是青少年的不良影响极其深刻，黄自为此担忧，创作了大量艺术修养和文化水平较高的艺术歌曲。《天伦歌》就是在这样的历史背景下创作的，作品以孤儿失去亲人的苦痛为起点，发展到人民的发愤图强，最后升华到博爱、奋起的民族志向，对青少年的爱国主义教育有着重要的影响。 （二）《天伦歌》曲式与和声。《天伦歌》是并列三部曲式，为a+b+c，最后扩充并达到全曲的高潮。作品中引子和coda所使用的音乐材料相同，前后呼应，合头合尾。这首艺术歌曲结构规整，乐句进行的较为清晰，所使用的节拍韵律符合歌词的特点，如三连音紧密连接，为突出歌词中号召的力量等。 和声上，充分体现了中西方作曲技法融合的创作特性。使用了很多七和弦。其中，一部分是西方的和声，一部分是将我国传统的五声调式中的五个音纵向的结合，构成五声性和弦。与前两首作品相比，《天伦歌》的民族性因素增强，这也与它本身的歌词内容和要弘扬的爱国主义精神相对应。 （三）《天伦歌》的伴奏织体分析。《天伦歌》的前奏使用了a段进唱的旋律发展而来的，具有五声调性特点，增添了民族性的色彩。在作品的第10小节转调入近关系调，调性的转换使歌曲增添抒情的情绪。这时的伴奏加强和弦力度，采用切分节奏，节拍重音突出，与a段形成强弱的明显对比，突出悲壮情绪。 c段的伴奏采用进行曲的风格，右手以和弦为主，表现铿锵有力的进行。右手为上行进行，把全曲推向最高潮。左手仍以柱式和弦为主，保持节奏稳定。在作品的扩展乐段，左手的节拍低音上行与右手的八度和弦与音程对应，推动音乐朝向宏伟、壮丽的方向进行。coda 处，与引子材料相同，首尾呼应。 二、《天伦歌》实践研究 《天伦歌》是具有很强民族性因素的作品。所谓民族性，体现在所使用的五声性和声、传统歌词韵律以及歌曲段落发展等方面上。 作品的整个发展过程可以用伤感――悲壮――兴奋――宏达四个过程来表述。在钢琴伴奏弹奏的时候，要以演唱者的歌唱状态为中心，选择合适的伴奏音量、音色和音质来配合，做到对演唱者的演唱同步，并起到连接、补充、修饰等辅助作用。 作品分为三段，即a+b+c+扩充段落。第一段以五声音阶的进行为主，表现儿童失去父母的悲伤和痛苦，前奏进入时要弹奏的使用稍凄楚的音色，左手低音重复进行，在弹奏完第一个低音后，要迅速的找到下一个跨音区的音符；右手弹奏的要有棱角，在前奏结束的时候第四小节的t方向的延音处，要给演唱者留有准备。演唱者进入后，左手整体的踏板使用的要连贯。随着作品发展，伴奏与旋律声部出现轮唱的形式，要弹奏的流动性强，稍突出一些。后以mf力度出现的具有转调性质的琶音奏法，要弹奏的如流水般连贯。在重复段落，即“小
我国艺术歌曲钢琴伴奏-精
我国艺术歌曲钢琴伴奏-精 2020-12-12 【关键字】传统、作风、整体、现代、快速、统一、发展、建立、了解、研究、特点、突出、关键、内涵、情绪、力量、地位、需要、氛围、重点、需求、特色、作用、结构、关系、增强、塑造、借鉴、把握、形成、丰富、满足、帮助、发挥、提高、内心 【摘要】艺术歌曲中，伴奏、旋律、诗歌三者是不可分割的重 要因素，它们三个共同构成一个统一体，伴奏声部与声乐演唱处于 同样的重要地位。形成了人声与器乐的巧妙的结合，即钢琴和歌唱 的二重奏。钢琴部分的音乐使歌曲紧密的联系起来，组成形象变化 丰富而且不中断的套曲，把音乐表达的淋漓尽致。 【关键词】艺术歌曲；钢琴伴奏；中国艺术歌曲 艺术歌曲中，钢琴伴奏不是简单、辅助的衬托，而是根据音乐 作品的内容为表现音乐形象的需要来进行创作的重要部分。准确了 解钢琴伴奏与艺术歌曲之间的关系,深层次地了解其钢琴伴奏的风 格特点,能帮助我们更为准确地把握钢琴伴奏在艺术歌曲中的作用 和地位，从而在演奏实践中为歌曲的演唱起到更好的烘托作用。 一、中国艺术歌曲与钢琴伴奏 “中西结合”是中国艺术歌曲中钢琴伴奏的主要特征之一，作 曲家们将西洋作曲技法同中国的传统文化相结合，从开始的借鉴古 典乐派和浪漫主义时期的创作风格，到尝试接近民族乐派及印象主 义乐派的风格，在融入中国风格的钢琴伴奏写作，都是对中国艺术 歌曲中钢琴写作技法的进一步尝试和提高。也为后来的艺术歌曲写 作提供了更多宝贵的经验，在长期发展中，我国艺术歌曲的钢琴伴 奏也逐渐呈现出多姿多彩的音乐风格和特色。中国艺术歌曲的钢琴
写作中，不可忽略的是钢琴伴奏织体的作用，因此作曲家们通常都以丰富的伴奏织体来烘托歌曲的意境，铺垫音乐背景，增强音乐感染力。和声织体，复调织体都在许多作品中使用，较为常见的是综合织体。这些不同的伴奏织体的歌曲，极大限度的发挥了钢琴的艺术表现力，起到了渲染歌曲氛围，揭示内心情感，塑造歌曲背景的重要作用。钢琴伴奏成为整体乐思不可缺少的部分。优秀的钢琴伴奏织体，对发掘歌曲内涵，表现音乐形象，构架诗词与音乐之间的桥梁等方面具有很大的意义。在不断发展和探索中，也将许多伴奏织体使用得非常娴熟精确。 二、青主艺术歌曲《我住长江头》中钢琴伴奏的特点 《我住长江头》原词模仿民歌风格，抒写一个女子怀念其爱人的深情。青主以清新悠远的音乐体现了原词的意境，而又别有寄寓。歌调悠长，但有别于民间的山歌小曲；句尾经常出现下行或向上的拖腔，听起来更接近于吟哦古诗的意味，却又比吟诗更具激情。钢琴伴奏以江水般流动的音型贯穿全曲，衬托着气息宽广的歌唱，象征着绵绵不断的情思。由于运用了自然调式的旋律与和声，显得自由舒畅，富于浪漫气息，并具有民族风味。最有新意的是，歌曲突破了“卜算子”词牌双调上、下两阕一般应取平行反复结构的惯例，而把下阕单独反复了三次，并且一次比一次激动，最后在全曲的高音区以ff结束。这样的处理突出了思念之情的真切和执著，并具有单纯的情歌所没有的昂奋力量。这是因为作者当年是大革命的参加者，正被反动派通缉，才不得不以破格的音乐处理，假借古代的