비밀공유 기반 SQL 스타일 조인은 안전한 협력적 데이터 분석의 핵심 구성요소인데, 실제로는 중복 키로 인한 일대다(Join-OM)·다대다(Join-MM) 관계가 자주 발생해 일치하는 모든 행 쌍을 비은닉적으로 구체화해야 한다. 기존 프로토콜은 확장된 더 큰 입력에 대해 비은닉 정렬을 수행하거나, 로그 라운드가 추가되는 여러 집계 트리에 의존하는 식으로 비용이 컸다. 이 논문은 반정직 설정에서 Join-OM과 Join-MM을 위한 고효율 프로토콜을 제시하는데, 핵심 기여는 확장된 입력을 처음부터 비은닉 정렬하는 대신 원본 입력만 정렬한 뒤 확장 후의 정렬 순서를 유도하는 상수 라운드 프로토콜인 '비은닉 정렬 확장(OSE)'이다. Join-OM에서는 OSE가 기존 최신 프로토콜(Asharov 등, CCS 2023)의 입력 확장으로 인한 중복 정렬 오버헤드를 제거하며, Join-MM에서는 OSE와 지역적 선형 연산을 결합해 집계 트리 없는 프로토콜을 얻는다. 실험 결과 기존 프로토콜 대비 실행 시간과 통신 비용을 Join-OM에서 약 27%, Join-MM에서 약 65% 줄였다.

• •중복 키로 인한 일대다·다대다 조인을 위한 새 프로토콜 OSE(비은닉 정렬 확장) 제시
• •확장된 입력 전체를 정렬하지 않고 원본만 정렬 후 확장 후 순서를 유도하는 상수 라운드 기법
• •Join-MM에서는 OSE와 지역 선형 연산을 결합해 집계 트리 없는 프로토콜 구현
• •기존 프로토콜 대비 실행시간·통신비용을 Join-OM 약 27%, Join-MM 약 65% 절감