I have almost the same problem, but I want to find entities that contain at least the list passed in:
My relationship is Car has many Parts but Part has no reference to Car
Car 1:
  - Moonroof
  - Spoiler
  - Leather Seats
Car 2:
  - Leather Seats
Car 3:
  - Moonroof
  - Leather Seats
If I pass in {Moonroof, Leather Seats} I want the list to contain Car 1 and Car 3 because they both satisfy the minimal requirements.
Car Entity
Code:
@Entity
@Inheritance(strategy=InheritanceType.JOINED)
public class Car extends AbstractEntity 
{
      @OneToMany(fetch=FetchType.EAGER)
      private List<Part> parts = new ArrayList<Part> ();
}
The Part entity is just a basic entity with model num, etc.  AbstractEntity has the id and uid values.
Currently, if I add criteria like this: (searchCriteria is the current search criteria built on Car.class, and it already has DISTINCT_ROOT_ENTITY on car):
Code:
DetachedCriteria sc = searchCriteria.createCriteria("parts");
Junction junc = Restrictions.conjunction();
for (Part p : selectedParts)
{
   junc.add(Restrictions.idEq(p.getId()));
}
sc.add(junc);
When i run that as a 
conjuntion() if i select Moonroof, I get all Cars that have a Moonroof, but if I select Moonroof and Leather Seats, I get no entries.  When I set it up as a 
disjunction() and I select Moonroof and Leather Seats, I get all Cars that have a Moonroof, Leather Seats, or both.
When i run this code, the Executable Criteria looks like this:
Code:
Executable Criteria: CriteriaImpl(org.groupid.site.entities.car.Car:this[Subcriteria(parts:)][model=org.groupid.site.entities.car.Model@3c0e12d9, (id = 4 and id = 54)])
But that Criteria is inherently flawed because no one row in the Car_Part table would have both an id of 4 and 54.