25

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. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. ...


11

It might be a viable example for explaining the concept of a trapdoor function to a layman without a computer science or math background. But from a CS standpoint this is only half-true. For a low number of n where n is the number of rotate-operations performed on the cube, it is true that finding a solution for the cube is more computationally expensive ...


8

Typically, trapdoor functions are used in asymmetric cryptography. For instance, if you have a RSA public key $(n,e)$, it is easy to compute a cipher text $c = Pad(m)^e\mod n$, but hard to get back to $Pad(m)$ from $c$ even if you have the public key. In order to easily reverse the operation you need the corresponding private key $d = e^{-1}\mod\phi(n)$. The ...


6

A trapdoor function doesn't have the security requirements of an encryption function. If you directly use a trapdoor for encryption you open yourself up to related key attacks, known plaintext attacks, malleability attacks and a whole host of other attacks. Trapdoor functions are used as a single piece of a larger encryption function that handles all these ...


6

No: the parameter $m$ and the size $B$ of the coefficients of $(s,e)$ would not be the same in both scenarios. In the first (LWE decryption) the matrix $A$ is high and narrow, which makes the function `strongly injective', and decoding is possible. Most images do not have preimages, i.e., only a small fraction of $y$ are decodable, those corresponding to ...


5

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 and the size of the finite field? (Actually, you mean the size of the group) Technically, the answer is "yes, it is easy to determine that". The easiest subcase is if $G$ (and hence $X$ and $Y$) belong to ...


5

A rubik's cube is an NP problem. It is difficult to find a solution to the problem but it is very easy to verify correctness of the solution, by just rotating the cube and checking that all sides have matching colours. Yes, there is a widely known solution for the 3 * 3 * 3 rubik's cube. You can solve it in 20 moves because you have memorised the solution. ...


5

Definition of trapdoor function from Wikipedia; A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". The reverse trapdoor function is just the reverse usage of it. Normally, for encryption, we want the encryption easy but ...


4

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means? You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set. Basically, this map is a permutation if ...


4

The most direct use of a trapdoor one-way function is to create asymmetric cryptosystems such as Public Key Encryption (PKE), Key Encapsulation Mechanisms (KEM), and Digital Signatures. An analogy A trapdoor one-way function is like a lock box that is supplied to the user in an opened configuration. Any user may place an item inside the box, then close the ...


4

If the adversary is a classical algorithm, then the answer to your question is not known. But if the adversary is a quantum algorithm that can query the oracle in superposition, then the answer is yes: by making queries to the oracle on certain (efficiently produceable) quantum states, it can recover a Type-I trapdoor for $A$. For classical algorithms, the ...


4

It is a major open research question whether such a scheme exists, and how to construct one (see, for example, Open Problem 9.10). Of course, we do have schemes like (hashed) ElGamal, which are based on the conjectured hardness of the (computational or decisional) Diffie-Hellman problem. But it is unknown whether either of these problems is equivalent to the ...


3

No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation). The two citations are only distantly related. In particular, the "one-way hash" in ...


3

No, the mathematical problem that is used for Diffie-Hellman is the Diffie-Hellman problem or DHP which is different from the trapdoor function that is behind RSA. One way functions are for instance cryptographically secure hash functions.


3

It is computationally infeasible to find $R$ (or any other short matrix that satisfies the relation) because solving $A R = V \pmod{q}$ for uniformly random $A, V$ is the SIS problem (in its inhomogeneous version). SIS is provably as hard as solving worst-case approximation problems on lattices. (Also, for the parameters considered in the paper, $[\bar{A} \...


3

Your reasoning is flawed. Producing a cipher text for a given key from plaintext without the key is no easier than the reverse for symmetric ciphers. Without the key k, producing ciphertext $Enc_k(x)$ is every bit as hard as $Dec_k(x)$ for many ciphers it is the same operation entirely (e.g anything in CTR mode). And even for common block ciphers there is ...


3

If you have a (standard) commitment scheme $C$ and zero-knowledge proofs of knowledge (both exist from LWE -- in fact, both exist from one-way functions), then you necessarily have equivocal commitments. Here is a straightforward equivocal commitment $C_e$: committing with $C_e$ is just committing with $C$, and opening a commitment is done by revealing the ...


3

For the context of this answer I will assume that that the author meant to say doubly enhanced TDP, since that's the only path I can currently think of. (See Definition 7) Constructing CCA secure encryption The relevant construction is due to Dolev, Dwork, and Naor. It is based on a CPA secure public key encryption scheme, a one-time signature scheme and a ...


2

It means that it maps quadratic residues $\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ to quadratic residues. A quadratic residue is a number $x$ such that $x = y^2 \pmod N$ where $N=pq$. A trapdoor means that once you know the factorization of $N$ it is easy to break quadratic residuocity problem. $p=q=3 \pmod 4$ because you choose 'safe' primes $p,q$ such that ...


2

As far as we know, both one-way and pseudorandom permutations do not help us to get public key encryption schemes. The way we obtain these is by using trapdoor functions (also known as trapdoor permutations). These are keyed collections with the following property: there are two keys for each function: one to compute it in the forward direction and one to ...


2

From the paper, $f$ is a pseudo-random function that produces a result of $s$ bits. You can think of the master key as a vector of $r$ values each $s$ bits long and for pedagogical purposes I'm sure the trapdoor for $w$ could be thought of as the result of hashing the concatenation of each key value $k$ with the word $w$.


2

My own answer would be: 2048, 2048, and still 2048 bits. Why ? Because: 2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers. There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. ...


2

Trapdoor functions only provide one-wayness. This means, that if one uses a trapdoor function to encrypt this may leak large parts of the plaintext. Suppose I have a trapdoor function $F(pk,m)$ for say n-bit messages $m$. I can now define an adapted trapdoor function working on $2n$ bit messages as $F'(pk,m_1||m_2) = m_1 || F(pk,m_2)$ This is still a ...


2

As suggested, here is a hopefully entry-level precis of the paper linked in the comment above. A Discrete Logarithm based asymmetric key system lacks a true trapdoor function - you can't compute a pre-image for an arbitrary image. Instead, a Schnorr signature relies on a slightly weaker condition. A generalized Schnorr signature can be considered to have ...


2

All generality, no—that's pretty much guaranteed to be too broad of a question here. Here's a specific example. Let $S$ be a finite set $F$ a public trapdoor permutation of $S$ with secret inverse $F^{-1}$, and $H\colon S \to \{0,1\}^{256}$ a uniform random function. For a member of the public to send a message $m$ to the possessor of $F^{-1}$, they can: ...


2

How difficult is it to find $b$? If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps. If $u$ is specified explicitly in the public key or the ...


2

Trapdoor functions are a special kind of one-way function, where it is possible to calculate the reverse function with the knowledge of some secret value, which is called the trapdoor. If a trapdoor function is also a permutation (bijective, from a set to itself), then it's called a trapdoor permutation. When considering encryption, we need an encryption ...


Only top voted, non community-wiki answers of a minimum length are eligible