[cap-talk] Implementing a crypto brand: What are the security requirements?

[David Wagner]

David Hopwood writes:
>Yes. The corresponding cryptographic property is "recipient-hiding
>encryption", where a ciphertext does not leak information about which
>public key was used to encrypt it.

Interesting.  Do you have any argument why the "recipient-hiding"
property is important for sealers and unsealers?  In particular,
if you give me a Box, and I can figure out which Sealer you used
to generate the Box, why is that a problem?  It seems fine if Boxes
happen to reveal the Sealer that was used to generate them.  This
is just knowledge.

>Of course the scheme must also be secure in other senses usually required
>of a public-key encryption scheme.

Thank you for pointing out that sealers and unsealers should be
thought of by analogy to public-key encryption.  In my last email,
I claimed that an analogy to public-key signatures; I'm chagrined to
say that was ill-considered and best forgotten.

Indistinguishability under adaptive chosen ciphertext attack does
seem like the right concept.  Here is a translation of that definition,
in terms of sealers and Unsealers.  Introduce a new interface:
    public interface Sealer2<T> {
        Box<T> seal2(T value0, T value1);
    }
The attacker is a function with the signature
    public boolean adversary(Sealer2<T> s, Unsealer<T> u);
Consider the following code:
    final Brand<T> br = keyspace.bear(...);
    final boolean b = new SecureRandom().nextBoolean();
    final Set<Box<T>> = new HashSet<Box<T>>();
    Sealer2<T> s2 = new Sealer2<T>() {
        public Box<T> seal(T value0, T value1) {
            Box<T> box = br.sealer.seal(b ? value1 : value0);
            set.add(box);
            return box;
        }
    }
    final boolean[] legal = new boolean[1] { true };
    Unsealer<T> u = new Unsealer<T>() {
        public String getLabel() { return br.unsealer.getLabel(); }
        public T unseal(Box<T> box) {
            if (box == null || set.contains(box))
                legal[0] = false;
            return br.unsealer.unseal(box);
        }
        
    }
    boolean guess = adversary(s2, u);
    return legal[0] && b == guess;
The desired security property is that no matter how you implement
adversary(), the chances that this code returns true is no more than
1/2 + epsilon, where epsilon is some very small number that depends
upon the total running time of the adversary.

(The above assumes that all Boxes returned by the sealer under
consideration have a trustworthy equals() and hashCode().)