# Confidential Signatures and Deterministic Signcryption

 Cofidential Signatures and Deterministic Signcryption Authors Alexandr W.Dent, Marc Fischlin, Mark Manulis, Martijn Stam, Dominique Schr?oder Published 2011 г. Download [1]
Abstract. . Encrypt-and-sign, where one encrypts and signs a message in parallel, is usually not recommended for con dential message trans-mission as the signature may leak information about the message. This motivates our investigation of con dential signature schemes, which hide all information about (high-entropy) input messages. In this work we provide a formal treatment of con dentiality for such schemes. We give constructions meeting our notions, both in the random oracle model and the standard model. As part of this we show that full domain hash signatures achieve a weaker level of con dentiality than Fiat-Shamir sig-natures. We then examine the connection of con dential signatures to signcryption schemes. We give formal security models for deterministic signcryption schemes for high-entropy and low-entropy messages, and prove encrypt-and-sign to be secure for con dential signature schemes and high-entropy messages. Finally, we show that one can derandomize any signcryption scheme in our model and obtain a secure deterministic scheme.[1]

## Introduction

A common mistake amongst novice cryptographers is to assume that digital signature schemes provide some kind of con dentiality service to the message being signed. The (faulty) argument in support of this statement is (a) that all signature schemes are of the \hash-and-sign" variety, which apply a hash function to a message before applying any kind of keyed operation, and (b) that a one-way hash function will hide all partial information about a message. Both facets of this argument are incorrect. However, it does suggest that notions of con dentiality for signature schemes are an interesting avenue of research.[2]

The question of con dentiality of hash functions in signature schemes was previously considered by Canetti as \content-concealing signatures"; however the original treatment only serves to motivate the concept of perfect one-way hash functions . We provide a more formal treatment here. The question of entropic security has been considered by several other authors. Dodis and Smith studied entropic secure primitives requiring that no function leaks their input Russell and Wang consider the security of symmetric encryption

schemes based on high-entropy messages, and several authors have considered the security of asymmetric encryption schemes based on high-entropy messages However, we are the rst authors to consider the con dentiality of signatures and signcryption schemes in this scenario. [2] We believe that the concept of con dential signatures is intrinsically inter-esting and may prove to be useful in the construction of protocols in which two entities need to check that they are both aware of a particular message which

(a) contains some con dential information, such as a password, and (b) contains a high entropy component, such as a con dential nonce.[2]

De ning Con dential Signatures. Our rst contribution is to de ne con dential signatures. Our starting point are high-entropy messages (signatures for mes-sages with low entropy inevitably leak through the veri cation algorithm of the signature scheme). Our de nitions are based on previous e orts for determinis-tic public-key encryption , and yield three models for con dential signature schemes:

- Weak con dentiality means that no information is leaked to a passive adver-sary, except possibly for information related to the technical details of the signature scheme.

- Mezzo con dentiality means that no information is leaked to a passive ad-versary (in possession of the veri cation key). Note that this is in contrast to deterministic public-key encryption where information cannot be hidden in such circumstances. [3]

- Strong con dentiality means that no information is leaked to an active ad-versary (in possession of the veri cation key).

Our de nitions are general enough to cover probabilistic and deterministic sig-nature schemes, although we need an additional stipulation in the latter case, preventing the case where the leaked information is the unique signature itself.

Relation to Anonymous Signatures. There are similarities between con dential signatures and anonymous signatures . Anonymous signatures hide the identity of the signer of a high-entropy message, whereas con dential signatures hide all the information about the message itself. This is relationship between these two primitives is similar to the relationship between anonymous encryption and traditional public key encryption.

Constructing Con dential Signatures. We then show how to obtain con dential signatures. We rst introduce the related concept of con dential hash functions, akin to hiding hash functions. We prove that random oracles are con dential hash functions, as are perfectly one-way hash functions in a weaker form.

We then show that the use of weakly con dential hash functions in full do-main hash (FDH) signature schemes yields weakly con dential signatures. We show that FDH signature schemes and Fiat-Shamir signatures are con dential in the random oracle model. We also show that strongly secure con dential sig-natures can be obtained in the standard model via the use of a randomness extractor (provided the message entropy lies above some xed bound).

Applications to Signcryption. Secure message transmission is usually performed via the encrypt-then-sign paradigm, where the sender encrypts the message un-der the receiver's public encryption key and then signs the ciphertext with his own signing key. Signcryption schemes, introduced by , aim to gain e - ciency by combining the two operations. One consequence of previous security de nitions is that the encrypt-and-sign approach, where one encrypts the message and signs the message in parallel, does not provide a secure signcryption in general as the signature may reveal information about the message.[/itex].[4]

We introduce security notions for (possibly deterministic) signcryption schemes with high-entropy messages, along the lines of deterministic public-key encryp-tion and con dential signatures. In case of signcryption schemes, we can also give a low-entropy-message version and show that this de nition is strictly stronger than the de nitions for high-entropy messages. We show that the parallelizable encrypt-and-sign scheme is high-entropy con dential if the underlying encryption scheme is IND-CCA2 and the signature scheme is con dential (and determin-istic). We nally prove that we can derandomize any signcryption scheme to derive a secure deterministic scheme.[3]

Besides the fact that some of our results require the signcryption scheme to be deterministic, we also believe that deterministic signcryption schemes may be intrinsically more secure than many current schemes. The reason is that most of the current signcryption schemes are based on discrete-logarithm-based digital signature schemes which are highly sensitive to imperfect randomness .

In situations where we have been forced due to size constraints to omit a theorem's proof, the proof can be found in the full version of the paper.[5]

## Confidential Signature Schemes

We formalise the notion of a con dential signature in three ways and give con-structions. These con dentiality notions can be applied to either probabilistic or deterministic signature schemes.[6]

### Definition of Confidential Signature Schemes

A digital signature scheme is a tuple of e cient algorithms ${\displaystyle SS=(SS.Setup,SS.kg,SS.Sign,SS.Ver)}$. All algorithms (in this article) are probabilistic polynomial-time (PPT) in the security parameter k (which we assume clear from the con-text). The parameter generation algorithm produces a set of parameters common to all users ${\displaystyle \lambda _{(}ss){\xleftarrow {R}}SS.Setup(1^{k})}$; subsequently the key generation algorithm pro-duces a public/private key pair ${\displaystyle (pk,sk){\xleftarrow {R}}SS.Kg(\lambda _{(}ss))}$.The signing algorithm takes a message ${\displaystyle m\in {0,1}^{*}}$ and the private key, and outputs a signature ${\displaystyle \sigma {\xleftarrow {R}}SS.Sign(sk,m)}$.. The veri ca-tion algorithm takes as input a message, signature and public key, and outputs either a valid symbol > or an invalid symbol. This is written ${\displaystyle SS.Ver(pk,m,\sigma )}$.[7].

(1)

${\displaystyle Expt_{A}^{wSig-b}(k)}$

${\displaystyle \lambda _{ss}{\xleftarrow {R}}SS.Setup(1^{k})}$

${\displaystyle (pk,sk){\xleftarrow {r}}SS.Kg(\lambda _{ss})}$

${\displaystyle (m_{0},t_{0}){\xleftarrow {R}}A_{1}(\lambda _{ss})}$

${\displaystyle (m_{1},t_{1}){\xleftarrow {R}}A_{1}(\lambda _{ss})}$

${\displaystyle \sigma ^{*}{\xleftarrow {}}SS.Sign(sk,m_{b})}$

${\displaystyle t'{\xleftarrow {R}}A_{2}^{SS.Sign(sk,*)}(pk,\sigma )}$

If ${\displaystyle t'=t_{0}}$ then output ${\displaystyle 1}$

Else return ${\displaystyle 0}$

(2)

${\displaystyle Expt_{A}^{wSig-b}(k)}$

${\displaystyle \lambda _{ss}{\xleftarrow {R}}SS.Setup(1^{k})}$

${\displaystyle (pk,sk){\xleftarrow {r}}SS.Kg(\lambda _{ss})}$

${\displaystyle (m_{0},t_{0}){\xleftarrow {R}}A_{1}(pk)}$

${\displaystyle (m_{1},t_{1}){\xleftarrow {R}}A_{1}(pk)}$

${\displaystyle \sigma ^{*}{\xleftarrow {}}SS.Sign(sk,m_{b})}$

${\displaystyle t'{\xleftarrow {R}}A_{2}^{SS.Sign(sk,*)}(pk,\sigma )}$

If ${\displaystyle t'=t_{0}}$ then output ${\displaystyle 1}$

Else return ${\displaystyle 0}$

(3)

${\displaystyle Expt_{A}^{wSig-b}(k)}$

${\displaystyle \lambda _{ss}{\xleftarrow {R}}SS.Setup(1^{k})}$

${\displaystyle (pk,sk){\xleftarrow {r}}SS.Kg(\lambda _{ss})}$

${\displaystyle (m_{0},t_{0}){\xleftarrow {R}}A_{1}^{SS.Sign(sk,*)}(pk)}$

${\displaystyle (m_{1},t_{1}){\xleftarrow {R}}A_{1}^{SS.Sign(sk,*)}(pk)}$

${\displaystyle \sigma ^{*}{\xleftarrow {}}SS.Sign(sk,m_{b})}$

${\displaystyle t'{\xleftarrow {R}}A_{2}^{SS.Sign(sk,*)}(pk,\sigma )}$

If ${\displaystyle t'=t_{0}}$ then output ${\displaystyle 1}$

Else return ${\displaystyle 0}$[8]

Notions of con dentiality for (a) weakly con dential signature schemes; (b) mezzo con dential signature schemes; (c) strongly con dential signature schemes. The signing algorithm is applied to the message vector m component-wise.

The standard notion for signature security is that of unforgeability under chosen message attacks (see Appendix A.1 for formal de nitions). We present three con dentiality notions for a digital signature scheme | see Figure 1. These notions are split depending on the adversary's capabilities, which corresponds in a natural way to real-life scenarios where it may be possible to derive some information about a message from a signature which might be deemed practically useless, e.g., the value of the hash of the message, but leakage of which cannot be avoided.[5]

In the weak con dentiality model, the attacker should not be able to de-termine any information about the messages apart from that which can be ob-tained directly from the signature itself. Mezzo con dentiality models the sce-nario where the attacker is able to retrieve public keys of the users, but cannot interact directly with their communication network and obtain signatures of mes-sages. In the strong model, an active attacker should not be able to determine any information about the messages apart from the signature itself.[8]

For x from {w,m,s} the attacker A's advantage in the xSig game is de ned to be:

${\displaystyle Adv_{A}^{xSig}(k)=|Pr[Expt_{A}^{xSig-0}(k)=1]-Pr[Expt_{A}^{xSig-1}(k)=1]|}$

A signature scheme is weakly con dential (resp. mezzo con dential/strongly con-dential) if all ${\displaystyle PPT}$attackers ${\displaystyle A=(A1,A2)}$ have negligible advantage ${\displaystyle Adv_{A}^{xSig}(k)}$ in the wSig security game, subject to the following restraints:

For deterministic schemes we need the following additional constraint, ruling out trivial attacks:[7]

(1)

${\displaystyle SS.Kg'(\lambda _{ss}):}$

${\displaystyle r{\xleftarrow {R}}{0,1}^{k}}$

${\displaystyle (pk,sk){\xleftarrow {R}}SS.Kg(\lambda _{ss})}$

Return ${\displaystyle (pk||r,sk||r)}$

(2)

${\displaystyle SS.Sign'(sk||r,m):}$

If${\displaystyle m=m'||r}$

Return ${\displaystyle SS.Sign(sk,m)||m}$

Else

Return${\displaystyle SS.Sign(sk,m)}$

(3)

${\displaystyle SS.Ver'(pk||r,m,\sigma ):}$

If ${\displaystyle m=m'||r}$

Parse ${\displaystyle \sigma }$ as ${\displaystyle \sigma '||m}$

${\displaystyle \sigma {\xleftarrow {}}\sigma '}$

Return ${\displaystyle SS.Ver(pk,m,\sigma )}$

A signature scheme which is weakly con dential but not mezzo con dential.

The latter condition prevents an attacker against a deterministic scheme from \winning" by setting ${\displaystyle t{\xleftarrow {}}SS.Sign(sk,m)}$ | i.e., it prevents the attacker from \winning" the game simply by determining that the message m has the property that its unique signature is ${\displaystyle SS.Sign(sk,m)}$[9]

The notions of con dentiality are strictly increasing in strength. If SS is a weakly con dential signature schemes, then Figure 2 depicts a scheme which is weakly con dential but not mezzo con dential. Similarly, if SS is a mezzo con dential signature scheme, then Figure 3 shows a scheme which is mezzo con dential but not strongly con dential.

[6]


(1)

${\displaystyle SS.Kg'(\lambda _{ss}):}$

${\displaystyle (pk,sk){\xleftarrow {r}}SS.Kg(\lambda _{s}s)}$

${\displaystyle r{\xleftarrow {R}}{0,1}^{k}}$

${\displaystyle \sigma _{r}{\xleftarrow {}}SS.Sign(sk,0||r)}$

Return ${\displaystyle (pk,sk||r||\sigma _{r})}$

(2)

${\displaystyle SS.Sign'(sk||r||\sigma _{r},m):}$

If ${\displaystyle m=m'||r||\sigma _{r}}$

Set ${\displaystyle \sigma '{\xleftarrow {}}SS.Sign(sk,1||m)}$

Return ${\displaystyle \sigma =(\sigma ',m)}$

Else

Set ${\displaystyle \sigma {\xleftarrow {}}SS.Sign(sk,2||m)}$

Return ${\displaystyle \sigma =(\sigma ',r,\sigma _{r})}$

(3)

${\displaystyle SS.Ver'(pk,m,\sigma )}$

If ${\displaystyle \sigma =(\sigma ',m')}$

Parse ${\displaystyle m'}$ as ${\displaystyle m'=m''||r'||\sigma '_{r}}$

${\displaystyle SS.Ver(pk,1||m',\sigma ')=T,}$ and

${\displaystyle m=m'}$ , and

${\displaystyle SS.Ver(pk<0||r',\sigma '_{r})=T}$

If ${\displaystyle \sigma =(\sigma ',r',\sigma '_{r})}$

Return T iff

${\displaystyle SS.Ver(pk,2||m,\sigma ')=T}$ , and

${\displaystyle m!=m''||r'||\sigma '_{r}}$ for any m from {0,1}*,

and ${\displaystyle SS.Ver(pk,0||r',\sigma '_{r})=T}$

Else return T

A signature scheme which is mezzo con dential but not strongly con dential.

## Confidential Hash Functions and Signature Schemes

### Confidential Hash Functions

We recap the notion of a hiding hash function by Bellare et al., but call such functions con dential here. For our purposes, a hash function ${\displaystyle H=(H.Kg,H)}$ is a PPT pair of algorithms for key generation and hashing, respectively. We will identify the description output by the key generation algorithm H:Kg with the hash function H itself. The collision${\displaystyle Adv_{A}^{col}}$ of an attacker A against a hash function H is defined as[5]

${\displaystyle Adv_{H},A^{col(k)}=Pr[H(x;r)=H(x',r')and(x,r)!=(x',r'):(x,x',r,r'){\xleftarrow {R}}A(H);H{\xleftarrow {R}}H.Kg(1^{k})]}$

A hash function is weakly (resp. strongly) con dential if every PPT attacker A has negligible advantage in the corresponding game subject to the following restraints:

- Pattern preserving: there exist a length function l(k) and equality functions such that for all possible ${\displaystyle (x,t){\xleftarrow {R}}A_{1}(1^{k})}$ we have that ${\displaystyle |x|=l(k)}$.

- High entropy: the function ${\displaystyle \pi (k)=max_{xfrom{0,1}*}*Pr[xi=x:(x,t){\xleftarrow {R}}A_{1}(a)]}$ is negligible where the probability is only over A1's random tape. We de ne ${\displaystyle \mu (k)=-log_{2}\pi (k)}$to be the adversary's minimum entropy.

### Confidentiality of Random Oracles

For any adversary A = (A1; A2) where A1 outputs vectors of length${\displaystyle l(k)}$ and with min-entropy ${\displaystyle \mu (k)=-log\pi (k)}$, and where A2 makes at most ${\displaystyle q_{h}(k)}$ queries to the random oracle, we have

${\displaystyle Adv_{H,A}^{x}Hash(k)<=2*q_{h}(k)*l(k)*\pi (k)}$

for ${\displaystyle x}$from ${\displaystyle {w,s}}$where A is assumed to be hash-free (in the strong case).

As for constructions in the standard model, we note that perfectly one-way functions (POWs) provide a partial solution. POWs have been designed to hide all information about preimages, akin to our con dentiality notion. How-ever, all known constructions of POWs are only good for xed (sets of) input distributions where the distributions can depend only on the security parameter but not the hash function description. Furthermore, known POWs usually re-quire the conditional entropy of any xi to be high, given the other xj's. In light of this, any valued perfectly one-way function is a weakly con dential hash function. Hence, we can build such hash functions based, for example, on claw-free permutations or one-way permutations .[10]

### Full-Domain Hash Signatures

A full-domain hash (FDH) signature scheme FDH for deterministic hash function H is a signature scheme in which the signing algorithm computes a signature as ${\displaystyle \sigma =f(H(m))}$ for some secret function f, and the verification algorithm checks that ${\displaystyle g(\sigma )=H(m)}$ for some public function g.[11]

(1)

${\displaystyle FDH.Kg(\lambda _{ss}):}$

${\displaystyle (f,g){\xleftarrow {}}FDH.Kg'(\lambda _{ss})}$

${\displaystyle H{\xleftarrow {}}H.Kg(1^{k})}$

${\displaystyle (pk,sk)=((g,H),(f,H))}$

Return ${\displaystyle (pk,sk)}$

(2)

${\displaystyle FDH.Sign(sk,m):}$

Parse ${\displaystyle sk}$ as ${\displaystyle (f,H)}$

Return ${\displaystyle \sigma =f(H(m))}$

(3)

${\displaystyle FDH.Ver(pk,m,\sigma ):}$

Parse ${\displaystyle pk}$ as ${\displaystyle (g,h)}$

Return T if ${\displaystyle H(m)=g(\sigma )}$

Otherwise return T

### Weak Confidentiality of FDH

The FDH-signature for hash function H is weakly con dential if H is weakly con dential. More precisely, for any adversary A = (A1; A2) against the weak confidentiality of FDH, where A1 outputs ${\displaystyle l(k)}$ messages and A2 makes at most ${\displaystyle q_{s}(k)}$ signature queries, there exists an adversary B = (B1; B2) against the weak con dentiality of the hash function such that[7]

${\displaystyle Adv_{FDH,A}^{wSig}(k)\leq Adv_{H,B}^{wHash}(k)}$

where B1's running time is identical to the one of A1, and B2's running time is the one of A2 plus${\displaystyle Time_{FDH.Kg}(k)+(q_{s}+l(k))*Time_{FDH.Sign}(k)+O(k)}$.

The proof actually shows that the signature scheme remains con dential for an adversarially chosen key pair (f; g), i.e., confidentiality only relies on the confidentiality of the hash function. Moreover, by Proposition 1, we have that FDH-signature schemes are weakly con dential in the random oracle model.

Proof. Assume that FDH is not weakly con dential and that there exists an adversary A = (A1; A2) successfully breaking this property. Then we construct an adversary B = (B1; B2) against the weak con dentiality of the hash function as follows. Adversary B1 on input ${\displaystyle 1^{k}}$ runs A1 on input ${\displaystyle 1^{k}}$ and outputs this algorithm's answer ${\displaystyle (m,t)}$.[12]

Algorithm B2 receives as input a description H of the con dential hash func- tion and a vector h of hash values. B2 runs ${\displaystyle (f,g){\xleftarrow {}}FDH.Kg'(1^{k})}$, and computes signatures${\displaystyle \sigma *=f(h)}$. It invokes A2 on ${\displaystyle (1^{k},pk,\sigma *)}$ and answers each subsequent signature request for message m by computing ${\displaystyle \sigma =FDH.Sign(sk,m)}$. When A2 outputs t' algorithm B2 copies this output and stops.

It is easy to see that B's advantage attacking the con dentiality of the hash function is identical to A's advantage attacking the con dentiality of the FDH signature scheme.[11]

### Strongly Confidential Signatures in the ROM

Recall from the previous section that FDH signatures leak the hash value of a message. To prevent this, we make the hashing process probabilistic and compute ${\displaystyle (r,H(r,m))}$ for randomness r. Then A1 cannot predict the hash values of the challenge messages due to r (which becomes public only afterwards) and A2 cannot guess the hash values due to the entropy in the message m (even though r is then known). Our instantiation is shown in Figure 5.[13]

### Random Oracle Instantiation

If H is a hash function modeled as a random oracle, then the signature scheme SS0 is strongly con - dential. That is, for any attacker A = (A1; A2) against the strong con dentiality of the signature scheme SS0, where A1 outputs a vector of length${\displaystyle l(k)}$ and with ${\displaystyle SS=(SS.Setup,SS.Kg,SS.Sign,SS.Ver)}$ is a signature scheme. We define a new signature scheme SS’ as follows [14]

(1)

${\displaystyle SS.Kg'(\lambda _{ss}):}$

${\displaystyle (pk,sk){\xleftarrow {}}SS.Kg(\lambda _{ss})}$

${\displaystyle H{\xleftarrow {R}}H.Kg(1^{k})}$

${\displaystyle pk'{\xleftarrow {}}(pk,H);sk'{\xleftarrow {(}}sk,H)}$

Return ${\displaystyle (pk',sk')}$

(2)

${\displaystyle SS.Sign'(sk',m):}$

Parse ${\displaystyle sk'}$ as ${\displaystyle (sk,H)}$

${\displaystyle r{\xleftarrow {R}}{0,1}^{k}}$

${\displaystyle h{\xleftarrow {}}H(r,m)}$

${\displaystyle \sigma '{\xleftarrow {}}SS.Sign(sk,h)}$

${\displaystyle \sigma (\sigma ',r)}$

Return ${\displaystyle \sigma }$

(3)

${\displaystyle SS.Ver'(pk',m,\sigma )}$

Parse ${\displaystyle pk'}$ as ${\displaystyle (pk,H)}$

Parse ${\displaystyle \sigma }$ as ${\displaystyle (\sigma ',r)}$

Return ${\displaystyle SS.Ver(pk,H(r,m),\sigma ')}$

Construction of a strongly con dential signature scheme in the ROM

Min-entropy ${\displaystyle \mu (k)=-log\pi (k)}$, and where A2 asks at most qh oracle queries (signing queries and direct hash oracle queries), we have

${\displaystyle Adv_{SS',A}^{sSig}(k)\leq 2*q_{h}(k)*l(k)*(2^{-k}+\pi (k))}$

### Fiat-Shamir Signature Schemes

Our second instantiation is based upon the Fiat-Shamir paradigm that turns every (three-round) identi cation scheme into a signature scheme. An identification scheme (ID scheme) is defined by a triplet ${\displaystyle (G,S,R)}$, where G is a key generation algorithm and the sender S wishes to prove his identity to the re-ceiver R. More formally: ${\displaystyle G(1^{k})}$ is an eficient algorithm that outputs a key pair ${\displaystyle (ipk,isk)}$. ${\displaystyle (S(isk),R(ipk))}$ are interactive algorithms and it is required that ${\displaystyle Pr[(S(isk),R(ipk))=1]=1}$ (where the probability is taken over the coin tosses of S; R and G). A canonical ID scheme is a 3-round ID scheme in which is sent by the sender S, by the receiver R and consists of R's random coins, and is sent by the sender.[14]

In order to prove the con dentiality of this scheme, we need to assume that the commitment of the Fiat-Shamir scheme has non-trivial entropy. This can always be achieved by appending public randomness.

### Fiat-Shamir Instantiation

If H is a hash function modeled as a random oracle, then the Fiat-Shamir instantiation SS for non-trivial com-mitments is strongly con dential. More precisely, for any attacker A = (A1; A2) against the strong con dentiality of the signature scheme SS where A1 out-puts a message vector of length ${\displaystyle l(k)}$ with min-entropy ${\displaystyle \mu '(k)=-log\pi '(k)}$, has min-entropy ${\displaystyle \mu '(k)=-log\pi '(k)}$, and A2 asks at most ${\displaystyle q_{h}}$ oracle queries (signing queries and direct hash oracle queries), we have

${\displaystyle Adv_{SS'',A}^{sSig}(k)\leq 2*q_{h}(k)*l(k)*(\pi (k)+\pi '(k))}$

Suppose ${\displaystyle (G,S,R)}$ is a canonical identification scheme and H is a hash function family. We de ne the signature scheme SS’’=(SS.Setup’’, SS.Kg’’, SS.Sign’’, SS.Ver’’) as follows[15]

(1)

${\displaystyle SS.Kg''(\lambda _{ss}):}$

${\displaystyle (ipk,isk){\xleftarrow {}}G(\lambda _{ss})}$

${\displaystyle H{\xleftarrow {R}}H.Kg(1^{k})}$

${\displaystyle pk'{\xleftarrow {}}(ipk,H);sk'{\xleftarrow {(}}isk,H)}$

Return ${\displaystyle (pk',sk')}$

(2)

${\displaystyle SS.Sign''(sk',m):}$

Parse ${\displaystyle sk'}$ as ${\displaystyle (isk,H)}$

${\displaystyle r{\xleftarrow {R}}{0,1}^{k}}$

${\displaystyle \alpha {\xleftarrow {}}S(isk;r)}$

${\displaystyle \beta {\xleftarrow {}}H(\alpha ,m)}$

${\displaystyle \gamma {\xleftarrow {}}S(isk,\alpha ,\beta ,r)}$

${\displaystyle \sigma {\xleftarrow {}}(\alpha ,\beta ,\gamma )}$

Return ${\displaystyle \sigma }$

(3)

${\displaystyle SS.Ver''(pk',m,\sigma ):}$

Parse ${\displaystyle pk'}$ as ${\displaystyle (ipk,H)}$

Parse ${\displaystyle \sigma }$ as ${\displaystyle (\alpha ,\beta ,\gamma )}$

${\displaystyle \beta '{\xleftarrow {}}H(\alpha ,m)}$

Return 1 iff ${\displaystyle \beta =\beta '}$

and ${\displaystyle R(ipk,\alpha ,\beta ,\gamma )=1}$

The Fiat-Shamir paradigm that turns every ID scheme into a signature scheme.

### Strongly Confidential Signatures from Randomness Extraction

Our instantiation in the standard model relies on randomness extractors and is depicted in Figure 7. The main idea is to smooth the distribution of the message via an extractor, and to sign the almost uniform value h[15]

To ensure unforgeability we need to augment the extractor's extraction prop-erty by collision-resistance, imposing the requirement that the extractors be keyed and introducing dependency of the extractor's parameters on the security parameter k. For a survey about very e cient constructions of such collision-resistant extractors see .

In order to use extractors, we need a stronger assumption on the message distribution: we assume that the adversary A1 now outputs vectors of messages such that each message in the vector has min-entropy greater than some xed bound ${\displaystyle mu(k)}$ given the other messages. Observe that the collision-resistance re-quirement on the extractor implies that must be super-logarithmic. We say that the output has conditional min-entropy ${\displaystyle mu(k)}$.[16]

### Extractor Instantiation

If ${\displaystyle Ext(a,b,n,t,\epsilon )}$-extractor then the extractor instantiation of ${\displaystyle SS'''}$ is strongly con dential. More specifically, for any attacker A = (A1; A2) against the strong con dentiality of the signature scheme SS, where A1 outputs a vector of length ${\displaystyle l(k)}$ with conditional min-entropy ${\displaystyle \mu (k)\geq t(k)}$, we have

${\displaystyle Adv_{SS''',A}^{sSig}(k)\leq 2*l(k)*\epsilon (k)}$

Note that our construction of the randomness extractor operates on messages of a fixed length of ${\displaystyle a(k)}$ input bits, and the signature length depends on this Suppose ${\displaystyle SS=(SS.Setup,SS.Kg.SS.Sign,SS.Ver)}$ is a signature scheme. We define a new signature scheme SS as follows value ${\displaystyle a(k)}$. [17]

(1)

${\displaystyle SS.Kg'''(\lambda _{ss}):}$

${\displaystyle (pk,sk){\xleftarrow {}}SS.Kg(\lambda _{ss})}$

Choose an extractor Ext

${\displaystyle pk'{\xleftarrow {}}(pk,Ext)}$

${\displaystyle sk'{\xleftarrow {}}(sk,Ext)}$

Return ${\displaystyle (pk',sk')}$

(2)

${\displaystyle SS.Sign'''(sk',m):}$

Parse ${\displaystyle sk'}$ as ${\displaystyle (sk,Ext)}$

${\displaystyle r{\xleftarrow {R}}(0,1)^{b}}$

${\displaystyle h{\xleftarrow {}}Ext(m,r)}$

${\displaystyle \sigma '{\xleftarrow {}}SS.Sign(sk,h)}$

${\displaystyle \sigma {\xleftarrow {}}(\sigma ',r)}$

Return ${\displaystyle \sigma }$

(3)

${\displaystyle SS.Ver'''(pk',m,\sigma ):}$

Parse ${\displaystyle pk'}$ as ${\displaystyle (pk,Ext)}$

Parse ${\displaystyle \sigma }$ as ${\displaystyle (r,\sigma ')}$

Set ${\displaystyle h{\xleftarrow {}}Ext(m,r)}$

Return ${\displaystyle SS.Ver(pk,h,\sigma )}$

Construction of strongly con dential signature scheme based on randomness extractors.

To process larger messages we can first hash input messages with a collision-resistant hash function, before passing it to the extractor. In this case, some care must be taken to determine a correct bound for the entropy lost through the hash function computation.

## Deterministic Signcryption

Signcryption is a public-key primitive which aims to simultaneously provide mes-sage con dentiality and message integrity. Signcryption was introduced by Zheng and security models were independently introduced by An, Dodis and Ra-bin and by Baek, Steinfeld and Zheng . Similar to public-key encryption, achieving con dentiality in the formal security models requires that signcryp-tion is a randomised process; however, we may also consider the con dentiality of deterministic signcryption schemes on high-entropy message spaces. We will also see that a practical version of con dentiality may even be achieved by a deterministic signcryption scheme for low entropy message distributions.[16]

### Notions of Confidentiality for Signcryption Schemes

A signcryption scheme is a tuple of PPT algorithms [9] ${\displaystyle SC=(SS.Setup,SC.Kgs,SC.Kgr,SC.SignCrypt,SC.UnSignCrypt)}$. The setup algorithm generates public parameters ${\displaystyle \lambda _{sc}{\xleftarrow {R}}SC.Setup(1^{k})}$ common to all algorithms. We will generally assume that all algorithms take sc as an implicit input, even if it is not ex-plicitly stated. The sender key-generation algorithm generates a key pair for the sender ${\displaystyle (pk_{S},sk_{S}){\xleftarrow {R}}SC.Kg_{s}(\lambda _{sc})}$ and the receiver key-generation algorithm generates a key pair for a receiver ${\displaystyle (pk_{R},sk_{R}){\xleftarrow {R}}SC.Kg_{s}(\lambda _{sc})}$. The signcryp-tion algorithm takes as input a message m, the sender's private key ${\displaystyle sk_{s}}$, and the receiver's public key ${\displaystyle pk_{r}}$, and outputs a signcryption ciphertext C R SC:SignCrypt(skS; pkR; m). The unsigncryption algorithm takes as input a ciphertext C 2 C, the sender's public key ${\displaystyle pk_{s}}$, and the receiver's private key ${\displaystyle sk_{r}}$, and outputs either a message [14]${\displaystyle m{\xleftarrow {R}}SC.UnSignCrypt(pk_{R},sk_{R},C)}$ or an error symbol.

It is interesting to consider the basic attack on a deterministic signcryption scheme. In such an attack, the attacker picks two messages (m0; m1) and receives a signcryption C of the message mb. The attacker checks whether C is the signcryption of m0 by requesting the signcryption of m0 from the signcryption oracle. As in the case of public-key encryption, we may prevent this basic attack by using a high-entropy message space and so prevent the attacker being able to determine which message to query to the signcryption oracle. However, unlike the case of public-key encryption, we may also prevent this attacker by forbidding the attacker to query the signcryption oracle on m0 and m1. We can therefore di erentiate between the high-entropy case (in which the message distribution chosen by the attacker has high entropy) and the low-entropy case (in which the attacker is forbidden from querying the signcryption oracle on a challenge message)..[10]

We give de nitions for the high-entropy and low-entropy con dentiality in Figure 8. In both cases, i.e. for x from {h,l}, the attacker's advantage is defined as

${\displaystyle Adv_{SS,A}^{xSCR}(k)=|Pr[Expt_{A}^{xSCR-1}=1]-Pr[Expt_{A}^{xSCR-0}=1]|}$

A signcryption scheme is high-entropy con dential if every PPT attacker A has negligible advantage in the hSCR game subject to the following restrictions:[17]

- Strongly pattern preserving
- High entropy
- Signature free
- Non-trivial


A signcryption scheme is low-entropy con dential if every PPT attacker A has negligible advantage in the lSCR game subject to the restrictions that A never queries the encryption oracle, and A2 never queries the decryption oracle on (${\displaystyle (pk_{S}^{*},C*)}$[16]

Any deterministic signcryption scheme SC which is low-entropy con dential is also high-entropy con dential. In particular, for any adversary A against high-entropy con dentiality, making at most ${\displaystyle q_{s}(k)}$ signcryption queries and where A1 outputs ${\displaystyle l(k)}$ messages with min-entropy ${\displaystyle \mu (k)=-log\pi (k)}$, there exists an adversary A' such that

${\displaystyle Adv_{SC,A}^{hSCR}(k)\leq l(k)*Adv_{SC,A}^{lSCR}(k)+4*q_{s}(k)*l(k)*\pi (k)}$

where the running time of A' equals the time of A plus ${\displaystyle O(k)}$..[8]

(1)

${\displaystyle Expt_{A}^{hSCR-b}(k):}$

${\displaystyle \lambda _{sc}{\xleftarrow {R}}SC.Setup(1^{k})}$

${\displaystyle (pk_{s}^{*},sk_{s}^{*}){\xleftarrow {R}}SC.Kg_{a}(\lambda _{sc})}$

${\displaystyle (pk_{R}^{*},sk_{R}^{*}){\xleftarrow {R}}SC.Kg_{r}(\lambda _{sc})}$

${\displaystyle (m_{0},t_{0}){\xleftarrow {R}}A_{1}^{O}(\lambda _{sc},pk_{S}^{*},pk_{r}^{*})}$

${\displaystyle (m_{1},t_{1}){\xleftarrow {R}}A_{1}^{O}(\lambda _{sc},pk_{S}^{*},pk_{r}^{*})}$

${\displaystyle C*{\xleftarrow {}}SC.SignCrypt(\lambda _{sc},pk_{S}^{*},pk_{r}^{*},m_{b})}$

${\displaystyle t'{\xleftarrow {R}}A_{2}^{O}(\lambda _{sc},pk_{S}^{*},pk_{r}^{*},C*)}$

If ${\displaystyle t'=t_{0}}$ then output 1

Else return 0

(2)

${\displaystyle Expt_{A}^{hSCR-b}(k):}$

${\displaystyle \lambda _{sc}{\xleftarrow {R}}SC.Setup(1^{k})}$

${\displaystyle (pk_{s}^{*},sk_{s}^{*}){\xleftarrow {R}}SC.Kg_{a}(\lambda _{sc})}$

${\displaystyle (pk_{R}^{*},sk_{R}^{*}){\xleftarrow {R}}SC.Kg_{r}(\lambda _{sc})}$

${\displaystyle (m_{0},m_{1},w){\xleftarrow {R}}A_{1}^{O}(\lambda _{sc},pk_{s}^{*},pk_{R}^{*})}$

${\displaystyle C*{\xleftarrow {}}SC.SignCrypt(\lambda _{sc},pk_{S}^{*},pk_{r}^{*},m_{b})}$

${\displaystyle b'{\xleftarrow {R}}A_{2}^{O}(C*,w)}$

Output b'

The proof essentially shows that, since the challenge messages produced by a high-entropy attacker A1 have min-entropy ${\displaystyle \mu (k)}$, the probability that A2 queries the signcryption oracle on one of those messages is bounded by ${\displaystyle 4*q_{s}(k)*l(k)*\pi (k)}$. If this does not occur, then a low-entropy attacker can easily run a high-entropy attacker as a black-box subroutine. The proof holds for deterministic schemes only. We are not aware if the same is true for probabilistic schemes.[16]

We also have that the low-entropy con dentiality de nition is strictly stronger than the high-entropy con dentiality de nition. If SC is a high-entropy con den-tial signcryption scheme, then the signcryption scheme SC0 given in Figure 9 is high-entropy con dential signcryption scheme but not a low-entropy con dential signcryption scheme.

A signcryption scheme which is high-entropy secure but not low-entropy secure[15]

(1)

${\displaystyle SC.SignCrypt'(sk_{S},pk_{R},m):}$

${\displaystyle C{\xleftarrow {}}SC.SignCrypt(sk_{S},pk_{R},m)}$

if ${\displaystyle m=0^{k}}$

Return ${\displaystyle C||0}$

Else

Return ${\displaystyle C||1}$

### The Encrypt-and-Sign Signcryption Scheme

Initially, it may be thought that high-entropy con dentiality may be easily achieved through the combination of deterministic encryption and con dential signatures.

However, many of the classic composition theorems, such as encrypt-then-sign, fail to achieve high-entropy security even when instantiated with se-cure components.[10]

Тheorem 1
If the signature scheme is deterministic, strongly unforgeable, and strongly confidential, and the encryption scheme is IND-CCA2 secure, then the signcryption scheme is con dential in the high-entropy model. In particular, if there exists an attacker A against the high-entropy security of the signcryption scheme, then there exist attackers${\displaystyle A_{pke},A_{ss},A_{sunf}}$against the IND-CCA2 security of the encryption scheme, against the strong con dentiality of the signa-ture scheme, and against the strong unforgeability of the signature scheme, such that

${\displaystyle Adv_{E+S,A}^{hSCR}(k)\leq l(k)*Adv_{PKE,A_{pke}}^{sSig}(k)+Adv_{SS,A_{ss}}^{sSig}(k)+Adv_{SS,A_{sunf}}^{seuf-cma}(k)}$

, where the running times ${\displaystyle A_{pke},A_{ss},A_{sunf}}$ equal the one of A plus ${\displaystyle (q_{sc}(k)+l(k))*(Time_{SC.SignCrypt}(k)+Time_{SC.UnSignCrypt}(k))+O(k)}$

.
Proof
The security of this scheme can be proven in a manner similar to the encryp-tion/signature composition theorems proven by An.

### Derandomization

Goldreich presents a technique to turn any probabilistic signature scheme into a deterministic one. The idea is to include the secret key of a pseudoran-dom function (PRF:Kg; PRF) in the secret signing key and, when signing a message m, use the random coins r = PRF( ; m) in this process. Note that the resulting scheme now yields the same signature if run twice on the same message. A formal definition of a PRF can be found in Appendix A.

We show that Goldreich's idea applies to signcryption schemes as well, taking advantage of the fact that a signcryption scheme involves a secret signing key in which we can put the key of the pseudorandom function. Nonetheless, whereas a probabilistic signcryption scheme usually hides the fact that the same message has been encrypted twice, a derandomized version clearly leaks this information.[15]

For a signcryption scheme ${\displaystyle SC}$ the derandomized version ${\displaystyle SC^{P}RF}$ based on a pseudorandom function ${\displaystyle PRF}$ works according to Goldreich's strategy: [9]

(1)

${\displaystyle SC.Kg_{s}^{PRF}(\lambda _{sc}):}$

${\displaystyle (sk_{s},pk_{s}){\xleftarrow {}}SC.Kg_{s}(\lambda _{sc})}$

${\displaystyle k{\xleftarrow {}}PRF.Kg(1^{k})}$

${\displaystyle sk_{S}^{PRF}{\xleftarrow {}}(sk_{S},k);pk_{S}^{PRF}{\xleftarrow {}}pk_{s}}$

Return ${\displaystyle (sk_{S}^{PRF},pk_{S}^{PRF})}$

(2)

${\displaystyle SC.SignCrypt^{PRF}(sk_{S}^{PRF},pk_{R},m):}$

Parse ${\displaystyle sk_{S}^{PRF}}$ as ${\displaystyle (sk_{S},k)}$

${\displaystyle r{\xleftarrow {}}PRF(k,(pk_{R},m))}$

${\displaystyle C{\xleftarrow {}}SC.SignCrypt(sk_{S},pk_{R},m;r)}$

Return C

### Derandomized Signcryption

Let ${\displaystyle SC}$ be an unforgeable and high-entropy (resp. low-entropy) con dential signcryption scheme. Then the scheme ${\displaystyle SC^{P}RF}$ is a deterministic, unforgeable signcryption scheme which is high-entropy (resp. low-entropy) con dential. That is, for x from {l,h} and any adver-sary A = (A1; A2) against ${\displaystyle xSCR}$ con dentiality, there exist adversaries D and B = (B1; B2) such that[1]

${\displaystyle Adv_{SC^{P}RF,A}^{xSCR}(k)\leq 2*Adv_{D}^{PRF}(k)+Adv_{SC,B}^{xSCR}(k)+2*q_{sc}(k)*l(k)*\pi (k)}$

## Acknowledgements

The authors wish to thank the ECRYPT II MAYA work-ing group on the design and analysis of primitives and protocols for interesting preliminary discussions on this topic. The work described in this report has in part been supported by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 ECRYPT II. The informa-tion in this document is provided as is, and no warranty is given or implied that the information is t for any particular purpose. The user thereof uses the infor-mation at its sole risk and liability. Dominique and Marc were supported by the Emmy Noether grant Fi 940/2-1 of the German Research Foundation (DFG), and by CASED (www.cased.de).

## Referenses

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />
1. 18. N. A. Howgrave-Graham and N. P. Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, 23(3):283{290, 2001.
2. J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In L. Knudsen, editor, Advances in Cryptology – Eurocrypt 2002, volume 2332 of Lecture Notes in Computer Science, pages 83–107. Springer-Verlag, 2002.
3. 9. J.-S. Coron. On the exact security of full domain hash. In M. Bellare, editor,
4. J16. Marc Fischlin. Anonymous signatures made easy. In Public-Key Cryptography (PKC) 2007, volume 4450 of Lecture Notes in Computer Science, pages 31{42. Springer-Verlag, 2007.
5. 15. M. Fischlin. Pseudorandom function tribe ensembles based on one-way permuta-tions: Improvements and applications. In J. Stern, editor, Advances in Cryptology - Eurocrypt 1999, volume 1592 of Lecture Notes in Computer Science, pages 429{444. Springer-Verlag, 1999.
6. 13. D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography. SIAM Journal on Computing, 30(2):391{437, 2000...
7. J. Baek, R. Steinfeld, and Y. Zheng. Formal proofs for the security of signcryption. Journal of Cryptology, 20(2):203–235, 2007
8. 10. A. W. Dent, M. Fischlin, M. Manulis, M. Stam, and D. Schr•oder. Con dential signatures and deterministic signcryption. Available from http://eprint.iacr.org/2009/588, 2009.,
9. 12. Y. Dodis and A. Smith. Entropic security and the encryption of high entropy messages. In J. Kilian, editor, Theory of Cryptography { TCC 2005, volume 3378 of Lecture Notes in Computer Science, pages 556{577. Springer-Verlag, 2005..
10. 7. R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information. In B. Kaliski, editor, Advances in Cryptology – Crypto ’97, volume 1294 of Lecture Notes in Computer Science, pages 455–469. Springer-Verlag, 1997
11. R. Canetti, D. Micciancio, and O. Reingold. Perfectly one-way probabilistic hash functions. In Proc. 30th Symposium on the Theory of Computing – STOC 1998, pages 131–140. ACM, 1998.
12. M. Bellare, A. Boldyreva, and A. O’Neill. Deterministic and efficiently searchable encryption. In A. Menezes, editor, Advances in Cryptology – Crypto 2007, volume 4622 of Lecture Notes in Computer Science, pages 535–552. Springer-Verlag, 2007
13. M. Bellare, M. Fischlin, A. O’Neill, and T. Ristenpart. Deterministic encryption: Definitional equivalences and constructions without random oracles. In D. Wagner, editor, Advances in Cryptology – Crypto 2008, volume 5157 of Lecture Notes in Computer Science, pages 360–378. Springer-Verlag, 2008.
14. 14. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identi cation and signature problems. In A. Odlyzko, editor, Advances in Cryptology { Crypto '86, volume 263 of Lecture Notes in Computer Science, pages 186{194. Springer-Verlag, 1986
15. 6. A. Boldyreva, S. Fehr, and A. O’Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In D. Wagner, editor, Advances in Cryptology – Crypto 2008, volume 5157 of Lecture Notes in Computer Science, pages 335–359. Springer-Verlag, 2008.
16. 5. M. Bellare and P. Rogaway. The exact security of digital signatures — how to sign with RSA and Rabin. In U. Maurer, editor, Advances in Cryptology – Eurocrypt ’96, volume 1070 of Lecture Notes in Computer Science, pages 399–416. SpringerVerlag, 1996.
17. 17. O. Goldreich. Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In A. M. Odlyzko, editor, Proceedings on Advances in Cryptology { Crypto '86, volume 263 of Lecture Notes in Computer Science, pages 104{110. Springer-Verlag, 1987.