Preimage Sampleable Functions

Preimage sampleable functions are a primitive that is utilized in cryptographic constructions such as signature or identity-based encryption schemes. It is first, and foremost a trapdoored function \(f_a :D \to R\), that, with access to a trapdoor \(td\) generated as \((a, td) \gets Gen(1^\lambda)\) allows to sample preimages for \(r \in R\) under \(f_a\). Additionally, there exists an algorithm \(SampleD\), that samples elements in \(D\) with specific properties related to the presampling and \(f_a\). For more details, refer to the definition in the original paper GPV08.

We provide a trait that interfaces the functionality of a PSF. qFALL-tools also has explicit implementations of the trait that can be used in constructions.

The PSF Trait

The PSF trait consists of five algorithms trap_gen, samp_d, samp_p, check_domain, f_a. Here, f_a is the function evaluation and check_domain checks if an element is in the domain \(D\).

A PSF trait can be implemented for a specific struct as follows:

use qfall_tools::primitive::psf::PSF;
pub type Placeholder = bool;

pub struct ExamplePSF;

impl PSF for ExamplePSF {
    type A = Placeholder;
    type Trapdoor = Placeholder;
    type Domain = Placeholder;
    type Range = Placeholder;

    fn trap_gen(&self) -> (Self::A, Self::Trapdoor) {
        todo!()
    }

    fn samp_d(&self) -> Self::Domain {
        todo!()
    }

    fn samp_p(&self, a: &Self::A, r: &Self::Trapdoor, u: &Self::Range) -> Self::Domain {
        todo!()
    }

    fn f_a(&self, a: &Self::A, sigma: &Self::Domain) -> Self::Range {
        todo!()
    }

    fn check_domain(&self, sigma: &Self::Domain) -> bool {
        todo!()
    }
}

Using the PSF Trait

The PSF trait can be used to implement full-domain hash signatures very easily and generically.

use crate::crypto_tools::psf_definition::ExamplePSF;
use crate::crypto_tools::psf_definition::Placeholder;
use qfall_tools::primitive::psf::PSF;

pub struct ExampleUsingPSF {
    example_psf: ExamplePSF,
}

impl ExampleUsingPSF {
    fn kgen(&self) -> (Placeholder, Placeholder) {
        self.example_psf.trap_gen()
    }

    fn sign(&self, a: Placeholder, td: Placeholder, m: &str) -> Placeholder {
        // hash message into domain
        let t = todo!("Hash(m)");
        self.example_psf.samp_p(&a, &td, t)
    }

    fn verify(&self, a: Placeholder, m: &str, sig: Placeholder) -> bool {
        // hash message into domain
        let t: Placeholder = todo!("Hash(m)");
        self.example_psf.check_domain(&sig) && self.example_psf.f_a(&a, &sig) == t
    }
}

Originally, we had a completely generic implementation, where the signature uses a generic PSF. However, the type handling became too complicated, so we decided on an implementation, where the developer needs to provide the explicit types for the fixed implementations. However, the abstraction of the PSF behavior is still something we consider desirable for consistency.