Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
30 views

Gadget Matrix Ring Setting

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
woah's user avatar
  • 27
1 vote
1 answer
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, ...
Marc_12's user avatar
  • 41
1 vote
0 answers
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()$...
baro77's user avatar
  • 730
3 votes
1 answer
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 ...
Cristian Baeza's user avatar
1 vote
1 answer
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 ...
Cristian Baeza's user avatar
1 vote
1 answer
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.
Mjf T's user avatar
  • 21
3 votes
1 answer
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 ...
ahron's user avatar
  • 133
4 votes
1 answer
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 ...
rozbb's user avatar
  • 430
1 vote
1 answer
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 ...
jackson deng's user avatar
0 votes
0 answers
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 ...
Omar Shehab's user avatar
2 votes
1 answer
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 ...
Crypto Newbie's user avatar
1 vote
1 answer
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$...
pizzamath's user avatar
1 vote
0 answers
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 ...
tur11ng's user avatar
  • 962
3 votes
1 answer
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 ...
Myath's user avatar
  • 845
3 votes
1 answer
264 views

Strong Diffie Hellman in bilinear groups

The $n$-strong Diffie Hellman assumption state that given the subset $\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$ in a cyclic group $\mathbb{G}$ of prime order $p$, a PPT algorithm cannot output $...
Mathdropout's user avatar
1 vote
1 answer
244 views

Lattice in Sage: Generate matrix A from a basis S such that AS = 0 (mod q)

In Sage, there is a function: gen_lattice() that can generate a basis $$S \in \mathbb{Z}^{m \times m}_q $$ of a lattice $$\Lambda^\bot_q(A)$$, where $$A \in \mathbb{Z}^{n \times m}_q$$ is a random. ...
Zi-Yuan Liu's user avatar
3 votes
0 answers
460 views

Security of Full Domain Hash (or not quite full)

Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway:...
fgrieu's user avatar
  • 142k
3 votes
1 answer
171 views

Understanding Lindell's proof of (semi-honest) oblivous transfer

In Lindell's tutorial "How to simulate it" [2016/046], section 4.3, he gives a semi-honest protocol for oblivious transfer, based on enhanced trapdoor permutations and a corresponding hard-...
Sebastian's user avatar
  • 461
0 votes
1 answer
48 views

Trapdoor committement using ring lattices involving three parties

Assume there are three parties say A, B, C. A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B. B has to prove to C that he possesses commitment $c(m)$. There is no interaction ...
user3322017's user avatar
2 votes
1 answer
171 views

Computational LWE-Trapdoor without tag

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$ in paragraph $\...
kibuff's user avatar
  • 23
1 vote
0 answers
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 ...
user93353's user avatar
  • 2,245
0 votes
2 answers
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 ...
gurghet's user avatar
  • 179
4 votes
1 answer
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 ...
Keshav Srinivasan's user avatar
5 votes
0 answers
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 ...
kelalaka's user avatar
  • 49k
5 votes
1 answer
111 views

Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501. To summarize, assume we have a matrix $G$ where, on input $b$, we can efficiently find $(s,e)$ such that $s^...
Sam Jaques's user avatar
  • 1,202
3 votes
1 answer
102 views

Computational trapdoor where the problem is tractable for both parties but easier for one

Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other. But what if one party merely has a big ...
Richard Flarinson's user avatar
2 votes
0 answers
137 views

One-Way Trapdoor Permutation more secure than RSA at same width?

The classical One-Way Trapdoor Permutation is RSA. The permutation that it implements on a set of $n$ elements¹ is invertible by an adversary knowing only the public key with work $w$ conjecturally² ...
fgrieu's user avatar
  • 142k
0 votes
1 answer
607 views

Are all public-key encryption protocols based on one-way functions? [duplicate]

Are there any public-key cryptography protocols which don't rely on one-way (or trapdoor) functions? RSA and Diffie-Hellman cryptographic protocols both rely on one-way functions (prime factorization ...
vlovic's user avatar
  • 1
4 votes
1 answer
100 views

Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?

Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf Suppose a PPT adversary is given the LWE trapdoor function in the picture: $g_{A^\top} (s,e) = A^\top s + e = b (...
Biu's user avatar
  • 43
1 vote
1 answer
87 views

How decode works in CCA1 scheme based on MP12 construction?

In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have: $S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\...
Eduardo Morais's user avatar
3 votes
1 answer
327 views

AES S-box and Nothing Up My Sleeve

Cryptographic primitives should have nothing-up-my-sleeve property to prove their designers don't have an advantage in using them versus the general public. For example, Blowfish is using binary ...
Paul Miller's user avatar
1 vote
0 answers
35 views

What is the high level idea why trapdoor is used for digital signature?

What is the high level idea why trapdoor is used for digital signature? Are there any digital signature schemes without trapdoor?
mallea's user avatar
  • 1,635
0 votes
1 answer
121 views

Trapdoors for Lattices: CCA-secure encryption

In Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller, Micciancio and Peikert proposed a CCA-secure encryption. However, I am confused about the step in decryption algorithm (p.36 Lemma 6.2.). ...
Zi-Yuan Liu's user avatar
1 vote
1 answer
410 views

Can a One way function also be its inverse?

This is from my homework: Prove that if there exists a one-way function, then there exists a one-way function f such that $f(0^n ) = 0^n$ for every $n$. Note that now for infinitely many values $y$...
Viraj Kamat's user avatar
2 votes
1 answer
340 views

What is Reverse Trapdoor Function?

In wikipedia on Digital_signature: but rather, the message to be signed is first hashed to produce a short digest, that is then padded to larger width comparable to N, then signed with the ...
Alex Martian's user avatar
0 votes
0 answers
59 views

How to verify a root of high degree polynomials?

If I want to verify a root of a polynomial that has degree $n$, I must to compute the $x^n, x^{n-1}...x, 1$.It seems to be inefficient. Is there any method to do this without computing many power?
BorisWang's user avatar
3 votes
1 answer
212 views

What can be said about the self-power map on groups based on DLP?

Introduction I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
kub0x's user avatar
  • 898
1 vote
0 answers
53 views

Gennaro multi trapdoor commitment scheme

In the Scheme Based on the SDH Assumption (page 11 of the paper https://link.springer.com/content/pdf/10.1007%2F978-3-540-28628-8_14.pdf), how does the commitment get revealed with the master trapdoor ...
Fiono's user avatar
  • 567
2 votes
1 answer
150 views

If TDP exist then CCA-secure PKES exist?

My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following: If trapdoor permutations exist then CCA-secure public key ...
user1868607's user avatar
  • 1,243
3 votes
1 answer
717 views

trapdoor commitment from lattice-based assumptions?

I'm wondering that is there any equivocal commitment scheme (i.e., trapdoor commitment) can be constructed from lattice-based assumptions? I know there are a lot of commitment schemes from lattices as ...
CryptoLover's user avatar
4 votes
1 answer
256 views

Is there an information theoretic equivalent of a trap door collision free function?

Warning: Possibly ill-posed question. I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it ...
user1936752's user avatar
6 votes
1 answer
205 views

Hash and sign via trapdoors for lattices

Both the papers GPV'08 and MP'11 present trapdoors for lattices that allow to recover $s\in\mathbb{Z}_q^n$ and the error vector $e\in\mathbb{Z}_q^m$ when given $y=As+e$, for $A\in\mathbb{Z}_q^{m\times ...
P.B.'s user avatar
  • 516
4 votes
1 answer
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 ...
P.B.'s user avatar
  • 516
1 vote
3 answers
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 ...
Meler Lawler's user avatar
4 votes
0 answers
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 ...
Ilk's user avatar
  • 233
1 vote
1 answer
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$ ...
kub0x's user avatar
  • 898
1 vote
0 answers
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 ...
chelsea's user avatar
  • 404
6 votes
0 answers
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 ...
graphtheory92's user avatar
-1 votes
2 answers
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 ...
pangloss's user avatar
1 vote
1 answer
2k views

Is Diffie Hellman key exchange based on one-way function or trapdoor function?

I have a question for my information security lab, which I am not able to find online. As the title says, is Diffie Hellman key exchange based on a one-way or a trapdoor function? In case of RSA I ...
0x00's user avatar
  • 13