Cipher Maps: 범주 이론과 Oblivious Computing의 만남

Source: Dev.to

소개

암호화된 데이터에 대해 대수적 구조를 유지하면서 연산을 할 수 있다면 어떨까요?
비싼 동형 암호화를 사용하는 대신, 다음을 통합하는 원칙적인 수학적 프레임워크를 통해 가능합니다:

• 옵리비어스 컴퓨팅
• 베르누이 타입 (통계적 근사)
• 범주론적 추상화

저의 최근 연구인 cipher maps와 algebraic cipher types는 바로 이 아이디어를 탐구합니다.

핵심 아이디어: Cipher Functors

A cipher functor cA lifts a monoid

[ (S,\ *,\ e) ]

into a cipher monoid

[ (cA(S),\ \oplus,\ \hat e) ]

Latent space (real monoid)   : (S, *, e)
          ↓ cA (cipher functor)
Cipher space (encrypted)    : (cA(S), ⊕, ê)

핵심 속성

These properties give us a type system for oblivious computing: instead of ad‑hoc encryption schemes, we obtain principled constructions that preserve algebraic structure.

Why This Matters

• Formal privacy guarantees are baked into the type.
• Error bounds are derived from Bernoulli‑type theory.
• Composable abstractions let us build complex oblivious pipelines from verified components.

예시

(링크: Algebraic Cipher Types, Cipher Maps)

통합 프레임워크

The paper unifies three major threads:

1. Algebraic cipher types – categorical foundations → 대수적 암호 유형 – 범주론적 기초
2. Bernoulli types – statistical approximation theory → 베르누이 유형 – 통계적 근사 이론
3. Oblivious function approximation – practical algorithms → 무관심 함수 근사 – 실용적인 알고리즘

Cipher Maps as Morphisms

• Objects – cipher types (encrypted/oblivious data structures) → 객체 – 암호 유형 (암호화된/무관심 데이터 구조)
• Morphisms – functions that preserve both algebraic structure and statistical properties → 사상 – 대수적 구조와 통계적 특성을 모두 보존하는 함수

Composition of morphisms yields principled ways to build complex oblivious computations while tracking error propagation. → 사상의 합성은 오류 전파를 추적하면서 복잡한 무관심 연산을 구축하는 원칙적인 방법을 제공합니다.

핵심 기여: Oblivious Bernoulli Maps

An Oblivious Bernoulli map is a function

[ f : cA(S) \to cA(T) ]

that:

• 암호화/은폐된 입력에서 동작한다
• 암호화/은폐된 출력을 생성한다
• 베르누이‑유형 이론에 기반한 증명 가능한 오류 경계를 가진다
• 암호 함자에서 유도된 범주 구조를 보존한다

Practical Result

1. 일반 함수 f : S → T 로 시작한다.
2. 이를 암호 맵 cA(f) : cA(S) → cA(T) 로 올린다.
3. 자동 프라이버시 보장과 형식적인 오류 경계를 얻는다.
4. 오류 전파를 추적하면서 여러 암호 맵을 합성한다.

왜 추상 수학인가?

이러한 추상화가 없으면, 새로운 은폐 알고리즘마다 맞춤형 보안 증명이 필요합니다.

Concrete Instantiation: Cipher‑Trapdoor‑Sets

cipher‑trapdoor‑sets 논문은 구체적인 예시를 제시한다:

• Base monoid – 멱집합 ((\mathcal{P}(U), \cup, \varnothing))
• Cipher functor – 해시 기반 베르누이 맵

Result: Hash‑Based Oblivious Sets (HBOS), 즉 다음을 갖춘 Bloom 필터:

• 형식적인 프라이버시 의미론
• 합성 오류 경계
• 타입‑안전 집합 연산 (합집합, 교집합 등)

Applications in the Wild

• 데이터베이스 연산자 – 접근 패턴을 숨기는 오블리비어스 데이터에 대한 조인, 프로젝션, 셀렉트
• 집계 쿼리 – 적절한 모노이드로 승격된 SUM, COUNT, AVG
• 그라디언트 집계 – 오블리비어스 타입을 사용하면 신뢰할 수 있는 집계자 없이도 차등 프라이버시를 구현 가능
• 스트리밍 분석 – 스트리밍 모노이드에 대한 암호 매핑은 상수 메모리, 검증 가능한 프라이빗 파이프라인을 제공

구현 스케치 (C++)

// Pseudocode sketch
template <typename T>
class CipherFunctor {
public:
    using Cipher = ObliviousBernoulli;

    // Lift a clear value into the cipher domain
    Cipher lift(const T& value);

    // Approximate inverse (decrypt/approximate)
    T approximate_inverse(const Cipher& cipher) const;

    // Monoidal operation on ciphertexts
    Cipher combine(const Cipher& a, const Cipher& b) const;
};

현대 템플릿 메타프로그래밍으로 구현되어, 설계는 제로 비용 추상을 목표로 합니다.

Research Directions

전망

우리는 전환점에 서 있습니다:

• 프라이버시 규제는 오블리비어스 컴퓨팅을 요구합니다.
• 규모는 근사 알고리즘으로 우리를 이끕니다.
• 복잡성은 구성적 추상화를 필요로 합니다.

Cipher maps는 이러한 시스템을 올바르게 구축하기 위한 수학적 기반을 제공합니다—“즉석 암호 + 희망”을 원칙적인 구성, 자동 프라이버시, 그리고 구성적 보안으로 전환합니다.

Related Papers

• Algebraic Cipher Types
• Cipher Maps: Unified Framework
• Hash‑Based Oblivious Sets
• Bernoulli Types Series
• Encrypted Search with Oblivious Types

(All links to be added.)

Privacy‑preserving systems with formal guarantees