23

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 ...


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

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 ...


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

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

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 the ...


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 ...


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

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

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

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

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

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

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

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

Your suggested formalization is not quite right. Also your notation isn't consistent with Schneier's. Schneier calls the hash function $f$, the input $x$ and the trapdoor $y$. The hash value of $x$ is the image $f(x)$ of $x$ under $f$. In general it is very difficult to compute $x$ just from $f(x)$. There is an efficiently computable function $g$, however, ...


2

One approach is suggested by the ideas introduced by this paper. I'll spell them out for you: The verifier selects two large safe primes $p, q$ (that is, primes where $(p-1)/2$ and $(q-1)/2$ are also prime), the value $n = p \times q$, an integer $z$, and a quadratic residue ($\bmod n$) $a$. The challenge (the "hard direction") is, given the values $n, z$ ...


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 ...


2

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 ...


2

So, does this mean AES doesn't have nothing-up-my-sleeve property? That is correct in a sense, the design of the s-box is formulaic. It is generated using finite field inversion, an affine transform, and xor of a constant (0x63). It can be described as a simple equation. The other parts of round transformation also have a very simple description, the most ...


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