Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
0answers
38 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 ...
4
votes
1answer
54 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 ...
3
votes
1answer
68 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 ...
1
vote
3answers
119 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 ...
3
votes
0answers
63 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 ...
1
vote
1answer
94 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$ ...
1
vote
0answers
23 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 ...
0
votes
0answers
89 views

How trapdoor key exposure affects security of trapdoor-based simulatable NIZKs?

I wonder if revealing a trapdoor key would help the verifier to distinguish real and fake proofs in NIZKs that are based on substituting the challenge with the result of a chameleon hash. I don't ...
5
votes
0answers
117 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 ...
-2
votes
2answers
401 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 ...
1
vote
1answer
296 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 ...
0
votes
1answer
181 views

Matrix Trapdoor AB+BA

I believe I'm probably not the first person to think of using this as a trapdoor. Let $R$ be a square matrix ring, and $S$ a commutative subgroup of its multiplicative monoid. Let $P \in R$ ...
2
votes
3answers
444 views

What's the difference between trapdoor and encryption?

Trapdoor is a function taking as input $x$ and givings us output $y$ where it is hard to convert $y\rightarrow x $ back without knowing a secret $s$. I think that $y$ is an encryption of $x$ under a ...
1
vote
0answers
216 views

Deterministic Signing

A signature scheme has three algorithms (Kgen, Sign, Ver), Kgen is necessarily randomized and Ver is ususally determinstic. Show that it is without loss of generality to restrict the signing algorithm ...
5
votes
1answer
130 views

Can elliptic curve point common factors be detected?

Consider the two EC points $X=abG$ and $Y=bG$. Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 ...
5
votes
2answers
139 views

EC: How to prevent discovery of base point after commutative operation

If I have a scalar $x$ and point $B$, then I can compute $X = f(x,B)$ If the function $f$ is point multiplication, i.e. $f(x,B) = x \cdot B$, then $B$ can be determined if $X$ and $x$ are known. ...
5
votes
2answers
726 views

Trapdoor and RSA (Schneier)

Disclaimer: I'm new to cryptography. Background: From Applied Cryptography (Bruce Schneier), page 30 of 2nd edition A trapdoor one-way function is a special type of one-way function, one with a ...
4
votes
1answer
80 views

Is there any more asymetric-time permutation than x^3 (mod p)?

I've been using "asymetric-time bijective functions (or permutations)" for several practical uses. I've applied them to solve problems in software-attestation and proof of unique blockchain storage. ...
8
votes
2answers
354 views

Would a Rubik's cube be a trapdoor function?

It's easy to scramble a Rubik's cube but it is hard to solve, unless you know the algorithms for solving it. This makes it a trapdoor function, correct?
2
votes
1answer
680 views

Ring signatures in ECC

Are ring signatures possible with elliptic curves? If so how. The original paper by Rivest, Shamir, Tauman seems to require an invertible trapdoor function. But I've only seen algorithms for secret ...
4
votes
2answers
328 views

Discrete logarithm over prime modulo: small input, large exponent, larger prime

I am considering using modular exponentiation as a one-way hash function. More specifically, here is the scenario. 1) Input ($m$): the input messages are small (16-bit) 2) Exponent ($e$): the ...
3
votes
0answers
126 views

How to recover $e$ from $f_A(e) = Ae \mod q$ when knowing trapdoor

I have a silly question, but I don't know a solution, so I need to question. Assume, with a algorithm $TrapGen(1^\lambda)$, it generates $A\in\mathbb{Z}_q^{n\times m}$ with a basis $B \in\mathbb{Z}_q^...
1
vote
2answers
132 views

Applying Trapdoor Function directly to plaintext

Suppose we have a secure trapdoor function defined on (G, F, F^-1) where G is a randomized algorithm outputs a key pair (pk, sk). Why would this trapdoor function become insecure if we apply F ...
3
votes
1answer
304 views

Trapdoors for lattices

I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding): For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\...
1
vote
0answers
46 views

What constitutes a “description of B” for probabilistic encryption as defined in Cryptology 6.3.4?

On page 21 of the Rivest's Cryptology chapter, he defines a trapdoor predicate as a boolean function for which it is easy to choose an x such that ...
1
vote
0answers
66 views

1-1 trapdoor function mapping the set of $n$-bit numbers to themselves

I am looking for a trapdoor one-to-one function $f : \{0,1\}^n \rightarrow \{0,1\}^n$ (that is, mapping the set of $n$ bit numbers 1-1 onto itself [any $n$ is OK]). I was considering the use of ...
0
votes
3answers
314 views

Question on RSA trapdoor permutation

You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources: ...
5
votes
2answers
103 views

What does it mean that $BW_N$ is a permutation over the squares mod N?

Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am ...
1
vote
1answer
422 views

what is an injective trapdoor function?

The answer to this question at Crypto.SE is clear about what a trapdoor function is, but what makes a trapdoor function "injective"?
5
votes
2answers
13k views

What is the meaning of “trapdoor” in cryptography?

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions: What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
3
votes
1answer
2k views

What's the difference between Trapdoor Functions and Encryption Functions?

From Wikipedia: A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without ...