query/table design help

I have a table
permissions
with the fields (party_id integer, permission varchar, key_name varchar,
key_value integer)
for which I need to a query to see if a person has permission to carry out a
particular action.
The query looks like:
SELECT 1
FROM permissions
WHERE   party_id in (4, 7, 11, 26)
    AND
        permission = 'permission8'
        AND
        ((key_name = 'keyname8' AND key_value = 223) OR
         (key_name = 'keyname1' AND key_value = 123) OR
         (key_name = 'keyname5' AND key_value = 212) OR
         (key_name = 'keyname7' AND key_value = 523) OR
         (key_name = 'keyname0' AND key_value = 123) OR
         (key_name = 'keyname10' AND key_value = 400));

would a permissions(party_id, permission) index work best here?
or should I index all 4 columns?

Also,
Another alternative is to combine the key_name and key_value fields into a
varchar
field key (e. g. 'keyname8=223'), in which case the equilalent query would
just check
1 field 6 times instead of having 6 ANDstatements.

I expect the table to have about 1 million rows at the most, and I need this
query to run as fast
as possible since it will be run many, many times.
So, from a design standpoint, what is the the best way to go, should I have
two fields key_name, and key_value,
or just one field key. And how should I index this table best.  I guess the
fundamental question here is, is it faster
to check a varchar(60) field for equality, or to check two check an integer
and then a varchar(30). Or does having
one varchar field replace an integer and a varchar field, allow for some
nice optimization not practical otherwise (i.e a 3-column index).

I'd greatly appreciate any insight into this matter.
-Ara Anjargolian