# Questions tagged [trapdoor]

A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently.

73 questions
Filter by
Sorted by
Tagged with
30 views

What would be the analogue of the gadget matrix in the ring setting? Would it be the same matrix? Do the trapdoor algorithms work exactly the same way? Thanks
• 27
1 vote
62 views

### Can I generalize trapdoor information to trapdoor functions for one-way function?

We know that, for one-way function $y=f(x)$, it's hard to compute $x=f^{-1}(y)$, but there exists an efficient algorithm $A(y,t)=f^{-1}(x)$ once we know the trapdoor information $t$. I'm wondering, ...
• 41
1 vote
46 views

### "tunable" trapdoor function

We know that a trapdoor function $f()$ is easy to compute in its original direction $y=f(x)$ while finding its inverse $x=f^{-1}(y)$ requires a secret information: without that trapdoor inverting $f()$...
• 730
113 views

### Trapdoor Quality for Lattice Crypto

In these two papers the authors mention the "quality" of a trapdoor [GPV] https://eprint.iacr.org/2007/432 [MP] https://eprint.iacr.org/2011/501 But the best detail on this matter I could ...
1 vote
69 views

### Sigma parameter from Trapdoors for Lattices

In the document Trapdoors for Lattices, section 5.4 Gaussian Sampling, they introduce the parameter $\sqrt{\Sigma_{\bf G}}$, which is related to the lattice $\Lambda^\perp(\bf G)$. They use it as a ...
1 vote
135 views

### Post-quantum secure trapdoor function

I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
• 21
210 views

### How is the Unix / PostgreSQL crypt function a trapdoor function?

I am looking at this in the context of password hashing in PostgreSQL, specifically, the crypt function of the pgcrypto ...
• 133
124 views

### "Shifting" a dual-Regev keypair away from a trapdoored instance

This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality: $\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair ...
• 430
1 vote
54 views

### Why the output of G-lattice sampling is spherical in the paper GM18?

In the paper GM18, they say that the sampling algorithm, SampleG, is shown in Figure 2. It takes as input a modulus $q$, an integer variance $s$, a coset $u$ of $\Lambda^{\perp}(g^T )$, and outputs a ...
89 views

### Cryptographic functions as feature map/kernel function?

Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario. I was not able to ...
2k views

### Where is the definition of one-way trap-door function used in public key cryptography

This is a rather simple question but I've been unable to find a proper answer for this online. When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to ...
1 vote
86 views

### Type 1 Trapdoor Sampling in LWE

In the BGN-like LWE cryptosystem, section $2.2$, we sample a $m \times m$ trapdoor matrix $T$ that is full rank such that $TA = 0 \pmod q$. Suppose that $q$ is prime so we are in a finite field: if $T$...
1 vote
88 views

### Example of enhanced trapdoor perrmutation (Enhanced TDP)

I am currently reading about Trapdoor Permutations (TDP). While I can totally understand and think of examples of TDP. I cannot think of any examples of Enhanced TDP. The definition of both TDP and ...
• 962
208 views

### Trapdoor recovery from lattice-based preimage sampling

[GPV] and [MP] (references below) give constructions of the trapdoor function defined by $$f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x,$$ where $\mathbf A \in \mathbb Z_q^{n \times m}$ is ...
• 845
264 views

• 23
1 vote
71 views

### Why is a hash function required for building Public Key Encryption from a Trap Door Function

This is from Dan Boneh's Coursera Lectures - Week 6 - Constructions. https://www.coursera.org/learn/crypto/lecture/nTRhL/constructions Here he picks a random x from X. And then Hashes X to get the ...
• 2,245
121 views

### Proof that a particular algorithm has been used

I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular ...
• 179
326 views

### Are there any public-key encryption schemes based on DLog?

There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the ...
595 views

### RSA like trapdoor permutations in Discrete logarithm

In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a ...
• 49k
111 views

• 43
1 vote
87 views

• 516
345 views

### Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
• 516
1 vote
182 views

### Could ANY cipher serve as the foundation for a public key cryptosystem?

My reasoning goes like this: In principle, any trapdoor function can serve as the foundation for an asymmetric encryption scheme. All ciphers are trapdoor functions, since it's easier to encrypt ...
• 315
143 views

### If trapdoor OWF exists then f is a trapdoor OWF, is there such a construction?

Is there a known construction of f, such that given that a trapdoor OWF exists then f is a trapdoor OWF, so we can construct inefficient cryptomania, ala Levin's construction for minicrypt in "The ...
• 233
1 vote
184 views

### What is it known about the hardness of the factorization search problem in non-commutative crypto?

The factorization search is an interesting problem in non-commutative crypto that can be defined as: Given an element $c$ of a group $G$, two subgroups $A,B \leqslant G$. Find two elements $a\in A$ ...
• 898
1 vote
57 views

### Extending the basis

Suppose I have $A \in \mathbb{Z}_q^{n \times m},A_1 \in \mathbb{Z}_q^{n \times m},A_2 \in \mathbb{Z}_q^{n \times m}$. I am following the $\textbf{ExtBasis}$ algorithm of this (Page No. 13). I ...
• 404
436 views

### Relation between Claw-free permutation and Trapdoor

Can someone explain the two definitions in relation to each other? Is a claw-free permutation a permutation without a trapdoor? For your convenience, here's the definition of a "claw-free ...
4k views

### How is a trapdoor used in cryptography?

Given a trapdoor function, is there a way to explain in all generality how it will be used in a cryptographic system in a simple way? I am writing a project for high school and I am looking for a way ...
• 23
1 vote