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
1
vote
1
answer
60
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
0
answers
45
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()$...
- 720
3
votes
1
answer
110
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 ...
- 197
1
vote
1
answer
68
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 ...
- 197
1
vote
1
answer
125
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
0
votes
0
answers
43
views
PKC (non Diffie-Hellman) from Graph Isomorphism
A Diffie Hellman style approach is proposed in https://mathoverflow.net/questions/408757/diffie-hellman-cryptography-based-on-graph-isomorphism but is broken easily.
Two graphs are isomorphic iff ...
- 908
3
votes
1
answer
207
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
4
votes
1
answer
115
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
...
- 390
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 ...
- 11
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 ...
2
votes
1
answer
1k
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
1
answer
84
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$...
- 11
1
vote
0
answers
69
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
3
votes
1
answer
197
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
3
votes
1
answer
230
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 $...
- 300
1
vote
1
answer
239
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.
...
- 113
3
votes
0
answers
448
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:...
- 141k
3
votes
1
answer
166
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-...
- 461
0
votes
1
answer
47
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 ...
2
votes
1
answer
167
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 $\...
- 23
1
vote
0
answers
69
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,213
0
votes
2
answers
120
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
4
votes
1
answer
319
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 ...
5
votes
0
answers
582
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 ...
- 48.5k
5
votes
1
answer
106
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^...
- 1,137
3
votes
1
answer
100
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 ...
2
votes
0
answers
135
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² ...
- 141k
0
votes
1
answer
589
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 ...
- 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 (...
- 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\...
3
votes
1
answer
316
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 ...
- 340
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?
- 1,605
0
votes
1
answer
118
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.).
...
- 113
1
vote
1
answer
394
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$...
- 21
2
votes
1
answer
332
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 ...
- 145
0
votes
0
answers
58
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?
- 81
3
votes
1
answer
210
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 ...
- 898
1
vote
0
answers
52
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 ...
- 567
2
votes
1
answer
147
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 ...
- 1,243
3
votes
1
answer
684
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 ...
- 932
4
votes
1
answer
250
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 ...
- 737
6
votes
1
answer
201
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 ...
- 506
4
votes
1
answer
331
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 ...
- 506
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 ...
- 315
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 ...
- 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$ ...
- 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 ...
- 404
6
votes
0
answers
426
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 ...
- 773
-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 ...
- 23
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 ...
- 13