. 3
( 19)


show that the scheme of Boneh, Boeyn and Shacham can be extended so that
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
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
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

Signature Schemes and Anonymous Credentials from Bilinear Maps 61

Signature. On input message secret key and public key
Choose a random
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
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
Signature. On input message secret key
and public key do:
Choose a random
Let for
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
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
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

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
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

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-

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-
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.
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-
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
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
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.

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
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
Jan Camenisch and Anna Lysyanskaya

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.

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.

1 G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably
secure coalition-resistant group signature scheme. In CRYPTO 2000, vol. 1880 of
LNCS, pp. 255“270. Springer Verlag, 2000.

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.

Jan Camenisch and Anna Lysyanskaya

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.

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

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-

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
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
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

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
Any such bilinear map is characterized by a binary matrix M, where
For the Goldreich-Levin predicate, M is simply the identity
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
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.

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
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,
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

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
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
We require the list-decoding algorithm to work in time Note that
in some cases, will be superpolynomial in the input size and

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]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.
We use non-negligible to denote a function which is not negligible.
Basically, one uses a linear, asymptotically optimal error-correcting code to find
instead of finding the bits one by one.

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
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.
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
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

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
Lemma 10. Let be a random variable over and a random
variable over If, for any


Proof. Obviously, if we also have for every
Using Lemma 9 we obtain

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.
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,

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.
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.
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.

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
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
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

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,

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).
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


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.

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

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.
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

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 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

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


. 3
( 19)