TEAM LinG

58 Jan Camenisch and Anna Lysyanskaya

a signature scheme with efficient protocols, similar to the one we describe in

Sections 3 and 4 can be obtained based on their assumptions as well.

2 Preliminaries

We use notation introduced by Micali [31] (also called the GMR notation), and

also notation introduced by Camenisch and Stadler [12]. Here we review it briefly;

the complete description can be found in the full version [CL04] of this paper.

If A is an algorithm, and be a Boolean function, then by

we denote the event that after was generated by running A on input

By we denote a Turing machine that makes queries to an oracle O. By

we denote the contents of the query tape once A

terminates, with oracle O and input

A function is negligible if for every positive polynomial and for

sufficiently large

Camenisch and Stadler [12] introduced notation for various proofs of knowl-

edge of discrete logarithms and proofs of the validity of statements about discrete

logarithms. For instance,

denotes a “zero-knowledge Proof of Knowledge of integers and such that

and holds, where where and are

elements of some groups and The convention

is that Greek letters denote quantities the knowledge of which is being proved,

while all other parameters are known to the verifier. We will sometimes apply

the Fiat-Shamir heuristic to turn such a proof into a signature on a message

which we will denote as, e.g.,

We also use the standard definition of a digital signature scheme [26].

2.1 Number-Theoretic Preliminaries

We now describe some number-theoretic preliminaries. Suppose that we have

a setup algorithm Setup that, on input the security parameter outputs the

setup for and two groups of prime order that have a

non-degenerate efficiently computable bilinear map More precisely: We assume

that associated with each group element, there is a unique binary string that

represents it. (For example, if then an element of G can be represented

as an integer between 1 and Following prior work (for example, Boneh

and Franklin [6]), is a function, such that

(Bilinear) For all for all

(Non-degenerate) There exists some such that where

1 is the identity of G.

(Efficient) There exists an efficient algorithm for computing

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 59

We write: It is easy to see, from the first two

properties, and from the fact that G and G are both of the same prime order

is a generator of G.

that whenever is a generator of

Such groups, based on the Weil and Tate pairings over elliptic curves (see

Silverman [37]), have been extensively relied upon in cryptographic literature

over the past few years (cf. [27,6,7,24] to name a few results).

Further, we make the following assumption about the groups G and G.

Assumption 21 (LRSW Assumption) Suppose that is a group cho-

sen by the setup algorithm Setup. Let Let

be an oracle that, on input a value outputs a triple

for a randomly chosen Then for all probabilistic polynomial time adversaries

defined as follows is a negligible function:

where Q is the set of queries that made to

This assumption was introduced by Lysyanskaya et al. [30], and considered

for groups that are not known to admit an efficient bilinear map. It was also

shown, in the same paper, that this assumption holds for generic groups. It is

not hard to see that the proof carries over to generic groups G and G with a

bilinear map between them.

3 Three Signature Schemes

First, we present a simple signature scheme (Scheme A) and prove it secure under

the LRSW assumption. Then, we modify this scheme to get signature schemes

that lend themselves more easily to the design of efficient protocols for issuing

a signature on a committed value and proving knowledge of a signature on a

committed value. The first generalization will allow to sign such that the signa-

ture produced is independent of the message (Scheme B), which we generalize

further into a scheme that allows to sign blocks of messages (Scheme C).

Schemes A and B are, in fact, special cases of Scheme C. So we really propose

just one new signature scheme, namely Scheme C. Schemes A and B are just

steps that simplify our presentation by making it more modular.

3.1 Scheme A: A Simple Signature Scheme

The signature scheme consists of the following algorithms:

Key generation. The key generation algorithm runs the Setup algorithm in

order to generate It then chooses and and

sets where and

TEAM LinG

60 Jan Camenisch and Anna Lysyanskaya

Signature. On input message secret key and public key

choose a random and output the signature

Verification. On input message and purported

signature check that the following verification equations hold.

Theorem 1. Signature Scheme A described above is correct and secure under

the LRSW assumption.

Proof. We first show correctness. The first verification equation holds as

and the second one holds because

We now show security. Without loss of generality, let

Consider the adversary interacting with the signer and outputting a valid

signature on some message that he did not query for. It is clear that the

signer acts the same way as the oracle defined in the LRSW assumption.

Therefore, in order to prove security, we must show that the forgery

that passes the verification equations, must be of the form and (**)

Let So, we wish to show that and that

Prom the first verification equation and the bilinearity of we get that

As g is a generator of G, we can take the logarithm base g on both sides, and

obtain which gives us (*) as desired.

From the second verification equation, using the above, and, again, the fact

that g is a generator:

3.2 Scheme B: Where Signature Is Independent of the Message

For constructing anonymous credentials, we need a signature scheme where the

signature itself is distributed in a way that is information-theoretically indepen-

dent of the message being signed. In essence, what is being signed should be

an information-theoretically secure commitment (Pedersen commitment) of the

message. Thus, we modify Scheme A and obtain Scheme B as follows:

Key generation. Run the Setup algorithm to generate Choose

Let and Set

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 61

Signature. On input message secret key and public key

do:

Choose a random

Let

Let

Let

Output

Verification. On input message and pur-

ported signature check the following:

1. A was formed correctly:

2. and B were formed correctly: and

3. was formed correctly:

Note that the values are information-theoretically inde-

pendent of if is chosen randomly. This will become crucial when using this

signature scheme in the context of an anonymous credential system.

Theorem 2. Signature Scheme B described above is correct and secure under

the LRSW assumption.

The full proof of this theorem is found in the full version [CL04] of this paper.

Here we give a sketch. Correctness follows by inspection. To show security, we

consider two types of forgery. Type 1 forgery is on some message such

that for all previously queried we have Type 2 forgery

is when this is not the case.

The existence of Type-1 forger contradicts the LRSW assumption by reduc-

tion from Signature Scheme A. On input a public key

for Scheme A, our reduction forms a public key

for Scheme B by choosing and setting It then runs the forger

on input and answers signature queries of the form by transforming

them into queries for the signature oracle for Scheme A.

It is easy to see that a Type 1 forgery on constitutes a successful forgery

for the message in Scheme A.

The existence of Type-2 forger contradicts the discrete logarithm assumption

(and therefore the LRSW assumption). The reduction takes as input

and sets up the public key for the signature scheme by choosing X and

Y. It then runs the forger, answers all the signature queries (since it generated

X and Y itself) and obtains a Type-2 forgery, namely such that

for some This immediately gives the discrete logarithm of Z

to the base

3.3 Scheme C: For Blocks of Messages

Scheme B allows us to generate a signature on in such a way that the signature

itself reveals no information about Namely, one can choose a random and

sign using Scheme B. In general, however, there is no reason that we should

limit ourselves to pairs when signing. In fact, the construction of Scheme

TEAM LinG

62 Jan Camenisch and Anna Lysyanskaya

B can be generalized to obtain Scheme C which can sign tuples

i.e., blocks of messages.

Scheme C consists of the following algorithms:

Key generation. Run the Setup algorithm to generate Choose

0 and for Let and, for

Set

Signature. On input message secret key

and public key do:

Choose a random

Let for

Let

Let

Output

Verification. On input message

and purported signature check the following:

1. were formed correctly:

2. and were formed correctly: and

3. was formed correctly:

The proof that this scheme is secure and correct is deferred to Corollary 1.

4 Anonymous Credential System

and Group Signature Scheme

Following Camenisch and Lysyanskaya [10,29], in order to construct an anony-

mous credential system, it is sufficient to exhibit a commitment scheme, a sig-

nature scheme, and efficient protocols for (1) proving equality of two committed

values; (2) getting a signature on a committed value (without revealing this value

to the signer); and (3) proving knowledge of a signature on a committed value.

We provide all these tools in this section.

Constructing a group signatures scheme or identity escrow scheme addition-

ally requires an encryption scheme that is secure against adaptively chosen ci-

phertext attacks and a protocol that a committed value is contained in a cipher-

text (cf. [12,3,11]). Camenisch and Shoup provide an encryption scheme and

such a protocol [11]. However, in our case we could also use the Cramer-Shoup

encryption scheme [18], provided that the order of the group over which encryp-

tion is carried out is the same as the order of the group over which our signature

scheme is constructed. This will allow for a more efficient proof that a ciphertext

contains information to identify a group member and thus a more efficient group

signatures/identity escrow scheme. We will describe the details of this in §4.4.

The reason that our new signature schemes are particularly suitable for the

credential scheme application, is the fact that, given one signature on a given

message, it is easy to generate another one. Consider Signature Scheme A. From

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 63

a signature on message it is very easy to compute a different

signature on the same message just choose a random and

let This alone is, of course, not sufficient, but this already

shows the way in which the pieces of our credential scheme will fall into place.

4.1 The Relevant Commitment Scheme

Recall the Pedersen commitment scheme [33]: given a group G of prime order

with generators and a commitment to is formed by choosing

a random and setting the commitment This commitment

scheme is information-theoretically hiding, and is binding under the discrete

logarithm assumption, which is implied by the LRSW assumption. Moreover,

there exist in the literature efficient protocols for proving knowledge and equality

of committed values (see, for example, [16,36,8,15]).

4.2 Obtaining a Signature on a Committed Value

When Information-Theoretic Hiding Is Not Needed. Consider the signing algo-

rithm for Scheme A. Note that, if the input to the signer is instead of

the algorithm will still work: on input output and

To maintain security of the signature scheme, however,

the user must prove knowledge of to the signer.

As we will discuss in more detail in §4.4, this leads to a natural application

to constructing group signatures: in order to join a group, a new member will

choose a secret give to the group manager, prove knowledge of and

obtain the membership certificate formed as above.

However, note here that the input to the signer, the value does not

unconditionally hide the value Thus, if the user wishes to become a member

in more than one group using the same secret (as is the case if we want to build

an anonymous credential system), the two group managers can discover that they

are talking to the same user. This is easy to see if both group managers use the

same generator for G, because in that case, the user will give to both of

them. But this is true even if one group manager uses while the other uses

recall that in groups with bilinear pairings, the decisional Diffie-Hellman problem

is easy, and so and can be correlated:

This is why we need Schemes B and C instead of Scheme A. However, we

note that for group signatures, Scheme A is sufficient. In the sequel, we will give

the description of the protocol for Scheme C, together with a proof of security.

Because Scheme A is a special case of Scheme C (in Scheme A, the

security of the protocols for A is implied by that for C.

Signing an Information-Theoretically Hidden Message. Signature Schemes B

and C are ideally suited for obtaining a signature on a committed value.

Consider Signature Scheme B. Note that to generate a valid signature, the

signer need not know Instead, it is sufficient that the signer know

The values are not a function of “ so the signer need

TEAM LinG

64 Jan Camenisch and Anna Lysyanskaya

not know to generate them. Suppose that the signer generates them as

follows: choose and let Choose A, and B as prescribed

by the signing algorithm. Finally, the signer can compute as

This will be correct, because:

More generally, in Signature Scheme C, all the signer needs is the value

He can then compute as prescribed,

and let as above.

We do not know how to prove such a method for signing secure under the

LRSW assumption: the difference from the usual method is that here, the ad-

versary may win by asking a signature query for M for which he does not know

the representation in terms of and Z.

Thus, in order to obtain a signature on a committed value, the protocol needs

to be amended by having a recipient of the signature prove that he knows the

representation of M in bases and Z.

Let us give the protocol in detail now. We give the protocol for Signature

Scheme C, the ones for Signature Schemes A and B follow from this as they are

special cases of Signature Scheme C.

Obtaining a Signature C on a Committed Value. Suppose that

is a commitment to a set of messages whose signature the

user wishes to obtain. Then the user and the signer run the following protocol:

Common Input. The public key and a com-

mitment M.

User™s Input. Values such that

Signer™s Input. Signing key

Protocol. First, the user gives a zero-knowledge proof of knowledge of the open-

ing of the commitment:

Next, the signer computes as described above, namely:

For let Then set and for let

The user outputs the signature

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 65

Theorem 3. The protocol above is a secure two-party computation of a signa-

ture on a discrete-logarithm representation of M under the signer™s public key.

Proof. (Sketch) From the signer™s point of view, this protocol is as secure as

when the user submits his signature queries in the clear. This is because of the

proof of knowledge: there exists an extractor that can discover the value of the

message being signed, and ask it of the signer in the clear.

From the user™s point of view, as the only place where the user™s secret input

is used is the zero-knowledge proof of knowledge of these values,

the only thing that the signer finds out about the message is

the input value M. Note that if is distributed uniformly at random, then

M information-theoretically hides the values

4.3 Proving Knowledge of a Signature

We first present a protocol to prove knowledge of a signature that works for

Scheme A. We then explain why the protocol does not generalize to Scheme B

(and thus also Scheme C), show how Scheme C needs to be extended to fix this

problem, and obtain Scheme D. We then give a proof of security of Scheme D and

a zero-knowledge protocol for proving knowledge of a signature under Scheme

D. We note that the protocol to sign a committed (secret) message also works

for Scheme D.

The following protocol is a zero-knowledge proof of knowledge of a signed

message for Scheme A.

Common input. The public key

Prover™s input. The message and signature

Protocol. The prover does the following:

1. Compute a blinded version of his signature Choose random

and blind the signature to form

Send to the verifier.

2. Let the and be as follows:

The Prover and Verifier compute these values (locally) and then carry

out the following zero-knowledge proof protocol:

The Verifier accepts if it accepts the proof above and

Theorem 4. The protocol above is a zero knowledge proof of knowledge of a

signature on a message under Signature Scheme A.

Proof. First, we prove the zero-knowledge property. The values that the verifier

receives from the prover in Step 1 are independent of the actual signature: and

TEAM LinG

66 Jan Camenisch and Anna Lysyanskaya

are just random values satisfying and is random in G because

for a randomly chosen Therefore, consider the following simulator S:

Choose random and and set Then is

distributed correctly, and so Step 1 is simulated correctly. Then, because in

Step 2, the Prover and Verifier execute a zero-knowledge proof, it follows that

there exists a simulator for this step; just run It is easy to see that S

constructed this way is the zero-knowledge simulator for this protocol.

Next, let us prove that this protocol is a proof of knowledge. That is to say, we

must exhibit a knowledge extractor algorithm E that, given access to a Prover

such that the Verifier™s acceptance probability is non-negligible, outputs a value

such that is a valid signature. Suppose that we are given such a prover.

The extractor proceeds as follows: first, it runs the extractor for the proof of

knowledge protocol of Step 2. As a result, it obtains the values such

that Then:

And therefore the triple satisfies the verification equation (1) and

hence is a signature on the message so our extractor outputs

Let us now try to adapt this protocol for Signature Scheme C. There is one

subtlety that arises here: The zero-knowledge simulator needs to be able to come

up with something that looks like a blinded signature (let us call it simulated

signature), even though the simulator is not given any signature. In Signature

Scheme A this turned out not to be a problem: the simulator simply picked a

random and set and Here, this is not going to work, because,

in addition to and the simulated signature needs to include the values

and Now, forming is not a problem: But how do we compute

without knowing or

To that end, we may augment the public key for signature scheme C to

include a signature on some dummy message, so that the simulator will be given

some valid signature that includes the correctly formed tuple

and then, in order to obtain the simulated signature, the simulator will pick a

random and let and

An even better solution, in terms of reducing the size of the public key, is

actually to include the values in the public key, instead of the signature

on the dummy message. It is easy to see that this has no effect on the security

of the signature scheme.

Let us now give this new, augmented signature scheme, and prove it secure.

Signature Scheme D. This signature scheme is the same as Signature Scheme

C, except that the public key also includes the values

Key generation. Run the Setup algorithm to generate Choose

and for Let

and, for and Set

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 67

The signature and verification algorithm are identical to the ones of Scheme C.

Theorem 5. Signature Scheme D is correct and secure under the LRSW as-

sumption.

The detailed proof of this theorem is given in the full version of this paper.

The main idea of the proof of security is that the proof for Scheme B generalizes

to the case when we have several

As a forger for Scheme C is also a forger for Scheme D, we have:

Corollary 1. Signature Scheme C is correct and secure under the LRSW as-

sumption.

The full description of the protocol and proof of security follow.

Common input. The public key

Prover™s input. The block of messages and signature

Protocol. The prover does the following:

1. Compute a blinded version of his signature Choose random

Form as follows:

Further, blind to obtain a value that it is distributed independently

of everything else:

Send to the verifier.

2. Let and be as follows:

The Prover and Verifier compute these values (locally) and then carry

out the following zero-knowledge proof protocol:

The Verifier accepts if it accepts the proof above and (a) were

formed correctly: and (b) and were formed

correctly: and

Theorem 6. The protocol above is a zero knowledge proof of knowledge of a

signature on a block of messages under Signature Scheme D.

The proof of this theorem follows the proof of Theorem 4 and is provided in the

full version of this paper.

TEAM LinG

68 Jan Camenisch and Anna Lysyanskaya

4.4 An Efficient Group Signature Scheme Secure

under the LSWR-Assumption

We now present the first efficient group signature (and identity escrow) scheme

whose security relies solely on assumptions related to the discrete logarithm

problem (in the random oracle model). In contrast, all previous efficient schemes

rely on the strong RSA assumption plus the decisional Diffie-Hellman assump-

tion.

Recall that a group signatures scheme allows members of a group to sign

anonymously on the group™s behalf. In case of disputes, there exists a trusted

third party called revocation manager who will be able to open a signature and

reveal the identity of the signer. A group signature scheme consists of five proce-

dures: (1) a key generation procedure that produces the public key of the group

(and also some keys for the group and revocation manager), (2) a join protocol

for a member to get admitted by the group manager, (3) a sign algorithm for an

admitted member to sign a message, (4) a verification algorithm to check group

signatures for validity with respect to the group™s public key, and (5) an opening

algorithm that allows the revocation manager to reveal the identity of a signer.

A group signature scheme is secure if only the revocation manager can reveal

the identity of the signer (anonymity) and if the revocation manager can do this

for all valid signatures (traceability) [3].

Our construction follows the approach introduced by Camenisch and Stadler

[12]: A member gets a certificate on a membership public key from the group

manager when she joins the group. When she wants to sign on behalf of the

group, she encrypts her membership public key under the encryption key of the

party who will later be able to open group signatures (revocation manager) and

then proves that she possesses a certificate on the encrypted membership public

key and that she knows its secret key. To make this proof a signature, one usually

applies the Fiat-Shamir heuristic to this proof [21].

The public key of the group manager is the public key of our Scheme A, i.e.,

and his secret key is and

The public key of the revocation manager is the public key of the Cramer-Shoup

encryption scheme [18] in the group i.e., with

and where are the

1

revocation manager™s secret key . Finally, let be a collision

resistant hash function (modeled as a random oracle in the proof of security).

The join protocol is as follows. The future group member chooses her mem-

bership secret key sets sends P authentically to the group

manager, and proves to the group manager the knowledge of The group

manager replies with a Scheme A signature on the message committed

by P, i.e., computes and where

1

The Cramer-Shoup cryptosystem is secure under the decisional Diffie-Hellman

(DDH) assumption. Therefore, we cannot use it over group G, because the exis-

tence of a bilinear map implies that the DDH problem is tractable. Thus, we use the

CS cryptosystem in group G instead.

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 69

The group manager stores together with P and the identity of the

new group member.

To sign a message on behalf of the group, the user computes

and a blinded version of the certificate by choosing random and

Next, she encrypts P under

computing

the revocation manager™s public key i.e., she chooses computes

and Then she computes the

following proof-signature (cf. §2):

where and A group signature consists

of and is valid if is a valid SPK as defined above

and if holds.

To open such a group signature, the revocation managers needs to decrypt

to obtain P which identifies the group member.

It is not hard to see that, in the random oracle model, this is a secure group

signatures scheme under the LRSW and the decisional Diffie-Hellman assump-

tion in G. Let us give a proof sketch for security under the Bellare et al. [3]

definition. If an adversary can break anonymity, then one can break the encryp-

tion scheme as are random values and is derived from an honest-verifier

zero-knowledge proof. If an adversary can produce a signature that cannot be

opened, i.e., linked to a registered member by the revocation manager, then one

can use rewinding to extract a forged signature and break the signature scheme

(cf. analysis of the protocol to prove knowledge of a signatures in §4.3). If used as

an identity escrow scheme (i.e., if is not a proof-signature but a real protocol

between a group member and a verifier), the security proof need not to assume

random oracles.

The scheme just described can be extended in several ways. For instance,

we could use Scheme D instead of Scheme A and include the user™s identity

id directly into her membership key P, e.g., That is, in the join

protocol, the user would send (and prove knowledge of and the

group manager would then compute P as to ensure that indeed id is contained in

P. Then, instead of encrypting P, one could use the Camenisch-Shoup encryption

scheme [11] to directly encrypt the identity as one of the discrete logarithms the

knowledge of which is proven when proving knowledge of a signature.

5 Constructions Based on the BBS Group Signature

Recently and independently of this work, Boneh, Boyen and Shacham [5] pre-

sented a group signature scheme secure under the strong Diffie-Hellman and the

Linear assumptions. They showed that, under these assumptions in groups with

bilinear pairings, it is hard, on input to sample tuples of the form

TEAM LinG

Jan Camenisch and Anna Lysyanskaya

70

where (in other words, even given a polynomial

number of such samples. In their group signature scheme, such a tuple is a

user™s group membership certificate, while is the public key of the group.

At the heart of their construction are (1) a zero-knowledge proof of knowledge

of such a tuple; and (2) a scheme for encrypting They prove the resulting

construction secure under a slightly weaker variant of the Bellare, Micciancio,

and Warinschi [3] definition of security.

Boneh, Boyen, and Shacham also modify their main group signature scheme

to achieve exculpability, as follows. The public key of the group is augmented

by an additional value it is now The membership certificate of a

group member is such that This membership certificate

is created via a protocol in which the group manager only learns the value

but not the value The unforgeability of membership certificates in this

modified scheme can be derived from that of their main scheme. They achieve

exculpability because a proof of knowledge of a membership certificate requires

the knowledge of the value

Note that this latter signature scheme gives rise to the equivalent of our

Signature Scheme A, but under a different assumption. Namely, the membership

certificate is a signature on the value Just as in our Scheme A, a group

member obtains his group membership certificate in such a way that the group

manager learns the value but not the value itself.

Not surprisingly, this signature scheme can be extended to the equivalent of

our Schemes B and C using techniques similar to the ones described above. As

a result, we can obtain signature schemes with efficient protocols based on the

BBS signature. Let us give a sketch for the equivalent for Scheme C. A public key

would be A signature on a block of messages

consists of values such that In order to obtain a signature

on a committed block of messages, a user will have to supply the signer with

the value and prove knowledge of its representation in the bases

If is chosen at random, then Y information-theoretically hides

The signer will then generate the signature. A proof of knowledge

of a signature on a committed value can be obtained by appropriate modifications

to the BBS group signature protocol.

Acknowledgments

We thank Dan Boneh, Xavier Boyen and Hovav Shacham for making their paper

[5] available to us as we were preparing the final version of this paper. We

also thank the anonymous referees for helpful comments. Anna Lysyanskaya is

supported by NSF Career grant CNS-0347661.

References

1 G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably

1.

secure coalition-resistant group signature scheme. In CRYPTO 2000, vol. 1880 of

LNCS, pp. 255“270. Springer Verlag, 2000.

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 71

2. G. Ateniese and B. de Medeiros. Efficient group signatures without trapdoors. In

ASIACRYPT 2003, vol. 2894 of LNCS, pp. 246“268. Springer Verlag, 2003.

3. M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures:

Formal definition, simplified requirements and a construction based on general

assumptions. In Eurocrypt 2003, vol. 2656 of LNCS, pp. 614“629, 2003.

4. D. Boneh and X. Boyen. Short signatures without random oracles. In EURO-

CRYPT 2004. Springer Verlag, 2004.

5. D. Boneh, X. Boyen, and H. Shacham. Short group signatures using strong diffie

hellman. In CRYPTO 2004. Springer Verlag, 2004.

6. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. In

CRYPTO 2001, vol. 2139 of LNCS, pp. 213“229. Springer Verlag, 2001.

7. D. Boneh and A. Silverberg. Applications of multilinear forms to cryptography. In

Topics in Algebraic and Noncommutative Geometry, Contemporary Mathematics,

vol. 324, pp. 71“90. American Mathematical Society, 2003.

8. S. Brands. Rapid demonstration of linear relations connected by boolean operators.

In EUROCRYPT ™97, vol. 1233 of LNCS, pp. 318“333. Springer Verlag, 1997.

9. J. Camenisch and A. Lysyanskaya. Efficient non-transferable anonymous multi-

show credential system with optional anonymity revocation. In EUROCRYPT

2001, vol. 2045 of LNCS, pp. 93“118. Springer Verlag, 2001.

10. J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In

Security in communication networks, vol. 2576 of LNCS, pp. 268“289, 2002.

[CL04] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous

credentials from bilinear maps. http://eprint.iacr.org, 2004.

11. J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of

discrete logarithms. In CRYPTO 2003, LNCS, pp. 126“144. Springer Verlag, 2003.

12. J. Camenisch and M. Stadler. Efficient group signature schemes for large groups.

In CRYPTO ™97, vol. 1296 of LNCS, pp. 410“424. Springer Verlag, 1997.

13. R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited.

In Proc. 30th Annual ACM STOC, pp. 209“218, 1998.

14. D. Chaum. Security without identification: Transaction systems to make big

brother obsolete. Communications of the ACM, 28(10):1030“1044, Oct. 1985.

15. D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demon-

strating possession of discrete logarithms and some generalizations. In EURO-

CRYPT ™87, vol. 304 of LNCS, pp. 127“141. Springer-Verlag, 1988.

16. D. Chaum and T. P. Pedersen. Wallet databases with observers. In CRYPTO ™92,

vol. 740 of LNCS, pp. 89“105. Springer-Verlag, 1993.

17. D. Chaum and E. van Heyst. Group signatures. In EUROCRYPT ™91, vol. 547 of

LNCS, pp. 257“265. Springer-Verlag, 1991.

18. R. Cramer and V. Shoup. A practical public key cryptosystem provably secure

against adaptive chosen ciphertext attack. In CRYPTO ™98, vol. 1642 of LNCS,

pp. 13“25, Berlin, 1998. Springer Verlag.

19. R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption.

In Proc. 6th ACM CCS, pp. 46“52. ACM press, nov 1999.

20. W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. on

Information Theory, IT-22(6):644“654, Nov. 1976.

21. A. Fiat and A. Shamir. How to prove yourself: Practical solution to identification

and signature problems. In CRYPTO ™86, vol. 263 of LNCS, pp. 186“194, 1987.

22. M. Fischlin. The Cramer-Shoup strong-RSA signature scheme revisited. In Public

Key Cryptography - PKC 2003, vol. 2567 of LNCS. Springer-Verlag, 2002.

23. R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the

random oracle. In EUROCRYPT ™99, vol. 1592 of LNCS, pp. 123“139, 1999.

TEAM LinG

Jan Camenisch and Anna Lysyanskaya

72

24. C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In ASIACRYPT

2002, vol. 2501 of LNCS, pp. 548“566. Springer Verlag, 2002.

25. S. Goldwasser and Y. T. Kalai. On the (in)security of the Fiat-Shamir paradigm.

In Proc. 44th IEEE FOCS, pp. 102“115. IEEE Computer Society Press, 2003.

26. S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against

adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281“308,

Apr. 1988.

27. A. Joux. A one-round protocol for tripartite Diffie-Hellman. In Proceedings of the

ANTS-IV conference, vol. 1838 of LNCS, pp. 385“394. Springer-Verlag, 2000.

28. J. Kilian and E. Petrank. Identity escrow. In CRYPTO ™98, vol. 1642 of LNCS,

pp. 169“185, Berlin, 1998. Springer Verlag.

29. A. Lysyanskaya. Signature Schemes and Applications to Cryptographic Protocol

Design. PhD thesis, Massachusetts Institute of Technology, Cambridge, Mas-

sachusetts, Sept. 2002.

30. A. Lysyanskaya, R. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In Selected

Areas in Cryptography, vol. 1758 of LNCS. Springer Verlag, 1999.

31. S. Micali. 6.875: Introduction to cryptography. MIT course taught in Fall 1997.

32. M. Naor and M. Yung. Universal one-way hash functions and their cryptographic

applications. In Proc. 21st Annual ACM STOC, pp. 33“43, 1989. ACM.

33. T. P. Pedersen. Non-interactive and information“theoretic secure verifiable secret

sharing. In CRYPTO ™91, vol. 576 of LNCS, pp. 129“140. Springer Verlag, 1992.

34. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures

and public-key cryptosystems. Communications of the ACM, 21(2):120“126, 1978.

35. J. Rompel. One-way functions are necessary and sufficient for secure signatures. In

Proc. 22nd Annual ACM STOC, pp. 387“394, Baltimore, Maryland, 1990. ACM.

36. C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology,

4(3):239“252, 1991.

37. J. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, 1986.

38. E. Verheul. Self-blindable credential certificates from the weil pairing. In ASI-

ACRYPT 2001, vol. 2248 of LNCS, pp. 533“551. Springer Verlag, 2001.

TEAM LinG

Complete Classification

of Bilinear Hard-Core Functions

Thomas Holenstein, Ueli Maurer, and Johan Sjödin

Department of Computer Science,

Swiss Federal Institute of Technology (ETH),

Zürich, Switzerland

{thomahol,maurer,sjoedin}@inf.ethz.ch

Abstract. Let be a one-way function. A function

is called a hard-core function for if, when given

for a (secret) drawn uniformly from it is computationally

infeasible to distinguish from a uniformly random string. A

(randomized) function is a general hard-

core function if it is hard-core for every one-way function

where the second input to is a uniform random string

Hard-core functions are a crucial tool in cryptography, in particular

for the construction of pseudo-random generators and pseudo-random

functions from any one-way function.

The first general hard-core predicate, proposed by Goldreich and Levin,

and several subsequently proposed hard-core functions, are bilinear func-

tions in the two arguments and In this paper we introduce a param-

eter of bilinear functions called expo-

nential rank loss, and prove that it characterizes exactly whether or not

is a general hard-core function. The security proofs for the previously

proposed bilinear hard-core functions follow as simple consequences. Our

results are obtained by extending the class of list-decodable codes and by

generalizing Hast™s list-decoding algorithm from the Reed-Muller code to

general codes.

Keywords: List-decoding, hard-core functions, Goldreich-Levin predi-

cate.

1 Introduction

Blum and Micali [BM84] showed a hard-core predicate1 for the exponentiation

function modulo a prime, which is widely conjectured to be one-way (except

for special primes). They also showed how to construct a pseudo-random gen-

erator based on it. Hard-core predicates are also known for some other specific

(conjectured) one-way functions.

In a seminal paper [GL89], Goldreich and Levin proved that for any one-

way function the XOR of a random subset of the bits

1

The term predicate is used throughout to denote a function with range {0,1}.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 73“91, 2004.

© International Association for Cryptologic Research 2004

TEAM LinG

74 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

of the input constitutes a hard-core predicate. This function is randomized

(because of the choice of a random subset), and it is easy to see that any general

hard-core function must be randomized. An alternative view is to interpret the

randomizing input of the hard-core function as an extra input and output of a

modified one-way function defined by

2

which now has a deterministic hard-core function . The Goldreich-Levin

hard-core function is simply the inner product of and which is a bilinear

function

Any such bilinear map is characterized by a binary matrix M, where

For the Goldreich-Levin predicate, M is simply the identity

matrix.

One can show (see [Lub96]) that independent Goldreich-Levin

predicates are jointly hard-core, i.e., they form a hard-core function

An important issue is to reduce the required amount of

randomness in a hard-core function. A construction presented in [GL89] (see

also [Go101]) requires only instead of mn random bits for an hard-

core function. Goldreich, Rubinfeld, and Sudan [GRS00] reduced the number of

random bits down to as for the Goldreich-Levin function which produces only

one (rather than bits. While some of the proofs of these results as they appear

in the literature are non-trivial, they will all follow as simple consequences of

our main theorem.

More generally, one can consider bilinear functions for vector spaces over

any finite field i.e., functions We are interested in

characterizing which of these functions are general hard-core functions. This

characterization turns out to be given by a quite simple parameter of such a

bilinear function. The characterization is complete in the sense that when the

parameter is below a certain threshold, then the function is hard-core, and other-

wise there exist one-way functions (under some reasonable complexity-theoretic

assumption) such that is not a hard-core function for

Let us discuss this parameter. For any linear function the

function is a bilinear function which can be characterized

by an matrix over The parameter of interest, which we call exponential

rank loss, is defined as the expected value of the exponentially weighted rank of

this matrix, when averaged over all non-zero functions

The main technical part of [GL89] consists in showing that an error-correcting

code has certain list-decoding properties, i.e., that it is possible to find a list of

all codewords in a Hamming ball of a certain size. In this paper we show how

to list-decode a larger class of codes. The stated characterization of hard-core

functions will then follow.

An application of one-way functions and hard-core predicates are pseudoran-

dom generators. It is easy to obtain a pseudorandom generator from any one-way

2

Yao™s method (implicit in [Yao82]) of using several copies of a one-way function and

computing the XOR of some of the inputs can also be seen in the same light.

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 75

permutation by iterating and after each iteration extracting a (the same)

hard-core predicate. It is much more complicated and less efficient to use any

one-way function (see [HILL99]).

The security of a cryptographic scheme that uses a pseudo-random generator

is proven by showing that an algorithm breaking the scheme could distinguish

the pseudo-randomness from real randomness. Hast [Has03] showed that in many

cryptographic applications, breaking the scheme is actually stronger than just

distinguishing the randomness from pseudorandomness with small probability,

in the sense that if an algorithm is given a pseudo-random or random input and

it breaks the scheme, then it is almost certain that the input was pseudo-random

rather than random. Hast then shows that this leads to an improved security

analysis for many constructions. The main technical tool is an extension of the

list-decoding algorithm to the case where erasures in the codewords are allowed.

We use this extension, and furthermore generalize Hast™s result by giving list-

decoding algorithms that are able to handle erasures for more general codes.

Section 2 introduces the notation and discusses bilinear functions and list-

decoding, the main technical tool of the paper. Previous work is also summarized

in this section. In Section 3, we analyze a special case of bilinear functions,

namely these for which all matrices mentioned above (i.e., for all non-zero linear

functions) have full rank. This special case already suffices to prove previous

results in the literature. We generalize the algorithm in Section 4 such that it

works with any bilinear code, where the running time and the produced list will

grow linearly with the exponential rank loss of the code. In Section 5 we discuss

the application to characterizing hard-core functions.

2 Preliminaries

We use calligraphic letters to denote sets. Capital letters denote random variables

over the corresponding sets; and lowercase letters denote specific values of these

random variables, i.e., values in the sets.

The notation is used to denote a function from the domain

to the range Sometimes, functions take additional randomness (i.e., for every

input the function only specifies a probability distribution over In

this case we write a notation which also will be used to denote

randomized algorithms with domain and range If an algorithm has access

to a randomized function, we use the term oracle for the randomized function.

2.1 Bilinear Functions

Let be the finite field with elements and let be the

vector space of over As a special case, we identify {0,1}

with GF(2), and the bitstrings of length with the vector

space over GF(2).

A linear function can be specified by a vector such that

We use to denote the set of all linear functions

TEAM LinG

76 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

Furthermore, 0 will denote the zero function and we use

for the set of all linear functions excluding 0.

A bilinear map can be specified by a matrix

such that The rank of a bilinear map is just the rank of this

matrix. A bilinear function is a function where every entry

in the output vector is specified by a bilinear map. Note that for any function

the concatenation is a bilinear map. If L is a uniformly chosen

random linear function from the exponential rank loss is defined as

We say that a bilinear function is full-rank, if for every

(in which case

2.2 List-Decoding

The main tool in the construction of hard-core functions is the notion of a list-

decodable code. Such a code has the property that, given a noisy codeword, it

is possible to find a list of all codewords which have a certain agreement with

the noisy codeword.

Consider a code given as a function Note that the input

to the function (usually the message) is an element of while the output (the

codeword) is a over The Hamming distance of two words of is

the number of coordinates in which the words differ. List-decoding is the task

of finding for a given all the values for which has a Hamming

distance from that is smaller than some predefined bound. This is in contrast

to usual error-correcting, where one aims to find the one codeword which is

closest to the received word. The most ambitious task is to list-decode close to

the noise barrier: given any one wants to find all values for which

has a Hamming distance of at most from a given word. Since a

random word has expected distance from any codeword, this is clearly

the best one can expect to achieve.

Instead of considering the function one can equivalently consider a

function such that is the value of at the

position. More generally we consider functions for any

domain Analogous, we assume that we have oracle access to the noisy word

to be decoded: instead of reading the complete word it will be convenient to

assume that an oracle on input returns the symbol at position

This allows us to list-decode in sublinear time, i.e., without looking at every

position of the word, which in turn allows the codewords to be exponentially

large. The oracle is stateless, but may be randomized and is not required to

return the same symbol if queried twice with the same input. The agreement of

an oracle with a codeword is then expressed as where the

probability is over the choices of Y and the randomness of the oracle.

Additionally, we allow erasures in the word which will be denoted by Thus,

the oracle is a randomized function The rate of such an

oracle is the probability that a symbol in is returned,

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 77

For a fixed word the advantage of is defined as

This motivates the following definition:

Definition 1 (List-decodable code).3 The function is

with oracle calls and list size if there exists an oracle algorithm

with running time which, after at most oracle calls to an

oracle with rate at least generates a set of size at most

such that for every with the set

satisfies

2.3 Hard-Core Functions

Informally, a one-way function is a function which is easy to evaluate but hard

to invert.

Definition 2 (One-way function). An efficiently computable function fam-

ily with is a one-way function if for

every probabilistic polynomial time (in algorithm A the inverting probability

is negligible.

A hard-core function can intuitively extract

bits from the input of a one-way function such that these bits look random,

even given We can distinguish (strong) hard-core functions, where the

output is indistinguishable from a random string of length (which we denote

by and weak hard-core functions, where the output of the function is hard

to predict.

Definition 3 (Strong hard-core function). An efficiently computable family

of functions, with is a

(strong) hard-core function if, for every one way function

and every probabilistic polynomial time algorithm A, the distinguishing advantage

given by is negligible

in

Definition 4 (Weak hard-core function). An efficiently computable family

with of functions is a

weak hard-core function if, for every one-way function

and every probabilistic polynomial time algorithm A, the advantage of A in guess-

ing on input and defined as is

negligible in

3

We require the list-decoding algorithm to work in time Note that

in some cases, will be superpolynomial in the input size and

TEAM LinG

78 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

In general, weak hard-core functions are easier to construct than strong ones.

However, we will see that for small outputs the notions are equivalent.

As shown in [Sud00], any list-decodable code

as defined above yields a weak hard-core function. To prove this, one assumes for

the sake of contradiction that an algorithm B is given which on input and

for some non-negligible4

predicts with probability higher than

After arguing that B needs to have a reasonable success probability for a sig-

nificant subset of the possible values for one then uses B as the oracle in the

list-decoding algorithm. The resulting list, which is small, then contains with

non-negligible probability, and one can find a preimage of by applying to

all values in the list.

In such a reduction, the running time of the resulting algorithm is dominated

by the running time of B. Thus, one is interested in the exact number of oracle

calls, while the exponent in the running time of the (polynomial) algorithm

is of minor importance. In this application, the second input (from

corresponds to a random string. As randomness is an expensive resource, one

wants to be as small as possible. We show how to achieve for any

2.4 Previous Work

The fundamental result on bilinear list-decodable codes implicitly appears in

[GL89], stating that the Reed-Muller code of first order, defined as

has an algorithm which efficiently

list-decodes it up to an error rate of for any

The standard proof used today was found independently by Levin and Rack-

off and is given in [Gol0l] (see also [Lev87]). In [Has03], Hast introduces the

extension of list-decoding algorithms for oracles with erasures. The existence of

the resulting algorithm is asserted in the following theorem:

Theorem 5 (Goldreich-Levin, cf. [Has03]). For any the function

is with list size

and oracle calls. The list-decoding algorithm needs as input.

This theorem is slightly stronger than the original version in [Has03], where

an additional factor appears in the number of oracle calls and the list size.

The version as stated here can be obtained by applying a trick that appears in

[Gol0l, Section 2.5.2.4]5.

It is natural to generalize this theorem to vector spaces over any finite field.

For this, the best known result is given in [GRS00].

Theorem 6. For any the function

is with list size and oracle

calls. The list-decoding algorithm needs as input.

4

We use non-negligible to denote a function which is not negligible.

5

Basically, one uses a linear, asymptotically optimal error-correcting code to find

instead of finding the bits one by one.

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 79

The algorithm which is used to prove Theorem 6 is similar to the original

algorithm given in [GL89]. The exponents in are rather high, so

we refrain from stating them explicitly.

N¤slund shows in [N¤s95] that for any one-way function a hard-core

predicate can be obtained if one interprets as a value in and outputs

any bit of for randomly chosen and a result which also follows from

the characterization in this paper. Furthermore, he proves that for randomly

chosen and prime the least significant bit of is a hard-core

predicate. More generally, in [N¤s96] he shows that all bits of are

hard-core.

In a different line of research, in [STV01] Sudan et al. give very strong list-

decodable codes which are not bilinear, based on Reed-Muller codes. These codes

can also be used to obtain hard-core functions for any one-way function.

In [AGS03], Akavia et al. show that list-decoding can also be used to prove

specific hard-core results. For example, they give a proof based on list-decodable

codes that the least significant bit of RSA is hard-core (which was first shown

in [ACGS88]).

3 Full-Rank Bilinear Functions

The main technical goal of this paper is to give a list-decoding procedure for

any bilinear function In this section, we will first consider

a simple, but very general subset of bilinear functions, namely full-rank bilinear

functions (i.e., for every We show that these functions

have very good list-decoding algorithms.

In a second step we will construct full-rank bilinear functions

which are optimal in the sense that for fixed the dimension is made as

small as possible, while for every value is possible. This allows us

to give a very large class of strong hard-core functions.

3.1 List-Decoding of Full-Rank Functions

In this section, we give a list-decoding algorithm for every full-rank bilinear

function In particular, for the case we will show

that there exists a list-decoding algorithm for which is as strong as the one

guaranteed in Theorem 5.

Theorem 7. Let be a full rank bilinear function.

For any the function is with list size

and oracle calls. The list-decoding algorithm needs as input.

For general finite fields, analogously to Theorem 6, the following holds.

Theorem 8. Let be a full-rank bilinear function. For any

the function is with list size

and oracle calls. The list-decoding algorithm needs as input.

TEAM LinG

80 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

To prove Theorems 7 and 8, we describe an algorithm which, on access to an

oracle with rate outputs a list of all which satisfy

to an oracle with the same rate and related

For this purpose we convert

advantage, but for a different code. Namely, will have advantage on

for any which satisfies (1), i.e.,

Applying Theorems 5 and 6, respectively, then yields the result.

In the following, let L be a uniform random function from i.e., L is a

random variable taking as values functions from We show that if a value

then

returned by the oracle is better than a random guess for is

as well. To see why this holds, we first

better than a random guess for

equals for two distinct values and

compute the probability that

this probability is close to

Lemma 9. For any distinct

Proof. First note that for

some If is chosen uniformly at random from all functions in (not

excluding 0), then and since for every we can

write

which implies the lemma.

Now we can estimate the probability that equals for two random

variables and Later, will be and a guess of an oracle

for

Lemma 10. Let be a random variable over and a random

variable over If, for any

then

Proof. Obviously, if we also have for every

Using Lemma 9 we obtain

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 81

Next, we translate a uniform query into a uniform pair

such that We will be able to use this by giving to the

oracle which predicts and then apply to get a prediction for

Since is uniform we will know the advantage of the oracle in predicting

and since is uniform, we can apply Lemma 10.

Lemma 11. Let be a full-rank bilinear function. There

exists an efficiently computable random mapping which,

for a uniformly chosen input outputs a uniform random pair such that

for every

Proof. The algorithm implementing first chooses an uniformly at

random. For a fixed let M be the matrix for which note

that As a second step, the algorithm chooses as a uniform

random solution of and returns the pair For every fixed if is

uniformly distributed; the vector will be uniformly distributed. Furthermore,

The next lemma proves the claimed conversion; i.e., given an oracle which

predicts we implement an oracle which predicts For this, on input

the algorithm first gets a pair using Lemma 11. Then, it queries the given

oracle with applies to the output and returns the result.

Lemma 12. Let be a full-rank bilinear function. There is

an efficient oracle algorithm A such that for any every and any

oracle which satisfies

algorithm satisfies

and Algorithm A makes one oracle call to

Proof. Given a uniformly chosen the algorithm first evaluates the function

as guaranteed by Lemma 11, to get a uniform pair with

It then queries the oracle with In case the answer is not it returns

otherwise it returns

Let be fixed such that

Lemma 10 implies that

Since is uniformly distributed this together with con-

cludes the proof.

TEAM LinG

82 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

Lemma 12 can be seen as a reduction of a code to another one, in the sense

that given a noisy codeword of one code we can generate a noisy codeword of a

related code such that the Hamming distances to codewords are related in some

sense. The proofs of Theorems 7 and 8 are now obvious.

Proof (of Theorems 7 and 8). Use Lemma 12, and apply Theorems 5 and 6,

respectively.

3.2 Construction of Full-Rank Functions

As mentioned before, a list-decodable code can be used to obtain a hard-core

function, which means that a family of full-rank bilinear functions can be used

as a hard-core function. This is stated in the following proposition (a more exact

version will be given in Theorem 25, Section 5).

Proposition 13. Any efficiently computable family of full-rank bilinear func-

tions where and is a

strong hard-core function.

The proposition implies that in order to give a hard-core function it is suf-

ficient to construct a full-rank bilinear function family. In this section, we will

present constructions which appear in the literature as hard-core functions, and

show that they satisfy for every

As usual in the context of hard-core functions, we will explain the construc-

tions for vector spaces over {0,1}. However, all constructions immediately gen-

eralize to vector spaces over any finite field.

Recall that any bilinear function can be de-

scribed by a sequence of matrices over GF(2) as

It follows that for every there exists a non-empty sub-

set such that the function can be written as

In order to get a full-rank bilinear function it is therefore sufficient to give

matrices which satisfy

Example 14. In [Lub96] it is shown that independent inner product

bits give a hard-core function. This function is

defined by matrices such that consists of all zeros, except that

from column to ni it contains a identity matrix. Here it is

obvious that (2) is satisfied.

Example 15. In order to keep the dimension small, one can obtain a full-rank

bilinear function with the construction

given in [Gol01] and [GL89]. There, is a matrix of size which

contains only zeros with the exception of an identity matrix starting at

column Again, it is obvious that (2) holds.

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 83

Note that since cannot be larger than for any it is necessary

to have If is small enough this is indeed sufficient:

Theorem 16. Let vector spaces and over {0, 1} be given.

If and then there exists a full-rank bilinear function

Proof. We first note that it is sufficient to give a full-rank bilinear function

for every since one can first obtain a bilinear

function by ignoring some of the output coordinates,

and in a second step one can get a full-rank bilinear function

by setting some of the inputs to the first arguments to zero.

To construct a full-rank bilinear function we

observe that the finite field is a vector space over {0,1} of dimension

and for every the map is linear. Let be a basis

of and let be the matrix which describes the linear mapping in

this basis. Since for any the matrix describes the linear mapping

for some non-zero this map is invertible and thus has rank

The bilinear function used in this proof is strongly related to the hard-core

function given at the end of [GRS00], and indeed the function given there also

satisfies the rank condition needed for Theorem 86.

4 General Bilinear Functions

In this section we give a list-decoding algorithm for every (possibly non full-

rank) bilinear function. Using the same technique as in Section 3.1 we prove the

following analogue of Theorem 7 (recall that

Theorem 17. Let be any bilinear function. After

a preprocessing phase taking time the function is

with list size and an expected number of oracle

as input.

calls. The algorithm needs

Note that is the expected number of queries. For general finite fields

Theorem 18 holds.

Theorem 18. Let be any bilinear function over After

a preprocessing phase taking time the function is

with list size and an expected number of

oracle calls. The list-decoding algorithm needs as input.

6

The functions are not identical, but if one considers the “cube” given by stacking

the matrices for different linear maps then the functions are obtained from each

other by a rotation of this cube. It is possible to show that for any two cubes which

are obtained by rotation from each other, the corresponding function satisfies the

full-rank condition if and only if the same holds for the other cube.

TEAM LinG

84 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

As before we prove these theorems by converting a given oracle which on

input predicts to an oracle which on input predicts We use

Lemma 10 again (and thus Lemma 9), but we modify Lemmas 11 and 12.

A problem is that for some it may be impossible to choose a pair

with for every This will force our reduction to return on

input since there is no way to get a reasonable guess for from Further-

more, the pair must be uniformly distributed which makes the conversion

return more often. We get the following generalization of Lemma 11:

Lemma 19. Let be a bilinear function. There exists an

efficiently computable mapping which, on uniformly

distributed input outputs with probability and otherwise a uniform

random pair satisfying for all The algorithm uses a

precomputation with time complexity

Proof. First, as a precomputation, for every the algorithm calculates

and stores it in such a way that later it is possible to efficiently

draw an element with probability where

After the precomputation, on input the algorithm chooses according to

this probability distribution and obtains the matrix M with

If the system is solvable, it chooses a solution uniformly at random

and returns otherwise it returns

Note that the precomputation can obviously be done in time

and every returned pair satisfies

For a fixed and uniformly chosen the probability that there exists a

such that is Furthermore, conditioned on the

event that the system above is solvable, every vector has the same probability.

This implies that the probability that a fixed pair is returned is

which is independent of the pair Summing over all possible pairs we

get

We point out that the probability of not returning cannot be made any

higher. To see why, first note that a pair can only be the answer for one

specific input Furthermore, there are possible pairs which can

only be output for implying that every pair can occur with probability at

most

Along the same line of reasoning as in Section 3, we can now prove the

generalized version of Lemma 12.

Lemma 20. Let be a bilinear function. There is an efficient

oracle algorithm A such that for any every and any oracle

which satisfies

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 85

algorithm satisfies

and The algorithm makes one query

to with probability It uses a preprocessing phase with time complexity

Proof. The preprocessing is the one needed for of Lemma 19. On input

the algorithm first uses to obtain either a pair or In the second

case, the algorithm returns and does not make an oracle query; this happens

with probability If a pair is returned, the algorithm makes one

query If the algorithm returns otherwise it returns

We fix and such that Lemma 10

implies that Conditioned on

the event that A makes a query to the pair is uniformly distributed

and satisfies Also, when A does not make a query to it

returns This implies

Finally, we see that A does not return if both of Lemma 19 and do not

return which happens with probability

Using this conversion, the proofs of Theorems 17 and 18 are now straightforward.

Proof (of Theorems 17 and 18). Use Lemma 20 and apply Theorems 5 and 6,

respectively.

5 Implications for Hard-Core Functions

The results of the previous sections have implications in cryptography, namely

for one-way functions. In particular, under a reasonable complexity-theoretic

assumption the results allow us to classify basically every bilinear function family

according to whether it is a strong hard-core

function or not.

We formulate our results in the context of uniform algorithms, but they

immediately generalize to a non-uniform context.

5.1 Weak vs. Strong Hard-Core Functions

In general, it is easier to construct weak hard-core functions than to construct

strong ones. For example the identity function is a weak hard-core

function for any one-way function (predicting given is the same as

inverting but not a strong hard-core function (given it is easy to distin-

guish from a random value).

TEAM LinG

86 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

For small output values the two notions are equivalent: every weak hard-core

function for is also a strong one. This

follows from the fact that any distinguisher for such a function can be converted

to a predictor. More concretely, assume that an oracle has advantage in

distinguishing from a random value. It is well known that one can get a

predictor with advantage from (see for example [Lub96]). The following

lemma improves this fact by following the idea of Hast that, in cryptographic

applications, a distinguisher often comes from an algorithm which tries to break

a scheme; if it succeeds then it is almost certain that the input was not random.

This can be used to obtain a predictor with lower rate but higher advantage. In

the following lemma we use this idea since the probability that a distinguisher

answers 1 on random input can be very small. By replacing with a uniform

random output one obtains the well-known version mentioned above.

Lemma 21. There exists a randomized oracle algorithm A such that for any

oracle with

and defined by

algorithm A queries once and outputs a value from such that

and

Proof. Algorithm A chooses a uniform random value It then queries

and outputs if the oracle outputs 1. Otherwise, it outputs

The probability that A outputs is The probability that A outputs

is and thus the probability that A outputs conditioned on the

event that it does not output is

As a corollary we obtain the following result:

Corollary 22. Let be a weak hard-core function

and Then, is a strong hard-core function.

Proof. Assume that is not a strong hard-core function. Then, there exists an

algorithm A which on input can distinguish from a uniform

random string with non-negligible advantage According to Lemma 21 we can

use this algorithm to obtain an algorithm which predicts the same string with

success probability at least and thus is not a weak hard-core function.

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 87

5.2 List-Decodable Codes and Weak Hard-Core Functions

Every list-decodable code can be used as a weak hard-core function. The idea to

prove this is to assume that the function is not a weak hard-core function, and

to use the algorithm A which predicts given and together with

the list-decoding algorithm to find a list which contains with probability at

least Applying to each element of the list and comparing the input we are

guaranteed to find a preimage of with high probability.

In our case, we would like to use the algorithm guaranteed in Theorem 17.

This algorithm requires to know the product and works as long as the correct

value is at least as large as the value given to the algorithm.

Note that the value of is fixed during a run of algorithm A. Consequently

such an algorithm can only be successful if the rate and advantage for

a fixed is large enough. However, typically only the rate and advantage

averaged over all is guaranteed to have a certain value. In order to show that

this is sufficient we first prove that In the following lemma, it is

useful to think of Z as an indicator variable which is 1 if the predictor guesses

correctly; 0 on a wrong guess and if the predictor refuses to produce a guess.

The random variable X corresponds to the value of

Lemma 23. Let X be a uniformly distributed random variable over and let Z

be some random variable in Let and

Fix any constant and let and

Then,

Proof. First we observe that Furthermore we have

and thus To show that

we note that this is equivalent to

which follows directly from the Cauchy-Schwarz inequality.

TEAM LinG

88 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

We now show how to use the list-decoding algorithm to invert a function

The following lemma is usually used when is a one-way function,

and in which case it states that is a weak hard-core function.

Lemma 24. Let be any efficiently computable function

family. Let be any efficiently computable bilinear

function with There exists an oracle algorithm A such that for any

which satisfies

and algorithm is

running in time and satisfies

while making an expected number of oracle calls to Algorithm A

needs as an input.

If is a full-rank bilinear function, the term in the running time

can be omitted.

Proof. For any fixed let and

Using Lemma 23 we obtain

Since for any we can apply Markov™s inequality

to obtain A run of the algorithm guaranteed in Theo-

rem 17 with input thus gives a set of size at most containing

with probability at least of ora-

while doing an expected number

cle calls. Applying to each and testing if it is correct yields the claimed

result.

5.3 Bilinear Hard-Core Functions

Lemma 21 converts a distinguisher to a predictor, while Lemma 24 uses a pre-

dictor to invert a function. Combining these two lemmas gives the following

theorem:

Theorem 25. Let be any efficiently computable function.

Let be any efficiently computable bilinear function

with There exists an oracle algorithm A such that for and

any which satisfies

algorithm A satisfies

and makes an expected number of

TEAM LinG

Complete Classification of Bilinear Hard-Core Functions 89

oracle queries to Algorithm A runs in time and

needs as input.

Proof. Combine Lemma 21 with Lemma 24.

This theorem implies that any bilinear function

with and can be used as a hard-core function.

Corollary 26. Let be a bilinear function with

and Then is a strong hard-core function.

Proof. Assume otherwise and use Theorem 25 to arrive at a contradiction.

5.4 Bilinear Functions not Suitable as Hard-Core Functions

In this section we also consider bilinear functions

for which or One can show that

implies the existence of a function which is infinitely often smaller

than Analogously, implies the existence of a function which

is strictly superpolynomial (i.e., and infinitely often smaller

than We say that a hard-core function is regular if or a

polynomial time computable function as above exists; and or a

polynomial time computable as above exists.

We show that any regular bilinear function not satisfying the conditions of

Corollary 26 is not a hard-core function if some reasonable complexity-theoretic