본 연구에서는 암호문에 노이즈를 추가하는 새로운 설계 사상에 기반하는 대칭키 암호 알고리즘 Rubato를 제안하였으며, 이렇게 설계된 암호화 방식이 근사 연산을 지원하는 동형 암호-대칭키 암호 하이브리드 구조에서 뛰어난 효율성을 제공한다는 것을 보였다.

동형암호는 암호문 상의 계산을 가능하게 하는 암호화 방식이다. 이를 사용하여 개인정보의 유출 없이 개인에게 맞춤형 서비스를 제공할 수 있고, 금융/의료 등 민감한 분야에서도 데이터 분석을 할 수 있다. 그러나 동형암호는 효율성 측면에서 두 가지 단점이 있다. 첫번째 단점은 느린 암호화 속도이다. 현재 가장 많이 쓰이는 인증 암호화 알고리즘 중 하나인 AES-GCM과 비교할 경우 동형암호가 수천 배 가량 느리다. 동형암호가 많은 양의 데이터를 한 번에 처리함에도 불구하고 이 정도의 차이가 난다. 두 번째 단점은 암호문의 크기가 크다는 점이다. 동형암호의 암호문 크기는 차후 연산 가능량에 비례하기 때문에 단순히 비교하긴 어렵지만, 평문에 비해 10배에서 1000배까지 암호문 확장이 일어난다.

전호화(transciphering)는 위에 서술된 동형암호의 단점을 해결하기 위해 제안된 해결책이다. 전호화란 대칭키 암호로 암호화된 대칭키 암호문을 동형암호문으로 변환하는 방법이다. 데이터를 암호화된 상태로 단순히 저장할 때에는 암호화가 빠르고 암호문의 크기가 작은 대칭키 암호화를 이용하고, 이후 암호문의 계산이 필요할 때는 전호화를 통해 동형암호문으로 변환하여 계산하는 방식이다. 이때 쓰이는 대칭키 암호는 동형암호화된 상태로 계산되기 때문에, 동형암호에서 효율적으로 계산되어야 한다. 이런 대칭키 암호를 동형암호향 대칭키 암호(HE-friendly cipher)라고 한다.

동형암호는 곱셈이 덧셈보다 더 무겁기 때문에, 기존 동형암호향 대칭키 암호 연구는 곱셈을 줄이는 방향으로 발전해왔다. 하지만 대칭키 암호의 안전성을 위해 일정 개수 이상의 곱셈이 필요했기 때문에, 효율성 발전에 한계가 있었다. 이주영 교수 연구팀은 이런 문제를 해결하기 위해 적은 라운드의 대칭키 암호에 노이즈를 더하는 방식을 사용한 새로운 동형 암호향 대칭키 암호 Rubato를 제안하였다. Rubato는 여러 번의 라운드에 걸쳐 생성된 키스트림에 노이즈와 메시지를 더하는 방식으로 암호화한다. 이 방식을 통해 안전성을 잃지 않으면서도 곱셈의 개수를 획기적으로 줄일 수 있었다. 이러한 성과를 인정받아 본 논문은 최우수 암호 학회 Eurocrypt 2022에 채택되었다.

Rubato의 라운드 함수는 다음과 같다