10

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


7

The answer is that it's me and not you. There was a typo in the proof and indeed $x$ referred to here is $f^{-1}_\alpha(S(\alpha,r))$. I have made the change in the proof and updated the ePrint paper. Thank you for pointing out the typo.


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


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


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

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

Q: What reductions exist to known problems on Group Theory, if any? I would consider the factorization search problem to be a known problem in group theory. After all, the LU-decomposition and QR-decompositions of matrices are special cases of the factorization search problem. In group based cryptography, the decomposition problem is usually stated in the ...


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

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


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


4

Yes, this is relatively straightforward. First, it seems that Sage has this built-in (see the dual flag, although I didn't test it). I'll describe the "mathematical" way to proceed, as I think it is conceptually more useful. For a lattice with basis $B$, it is well-known (see theorem 2) that the dual has basis: $$D = B (B^t B)^{-1}$$ It follows ...


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

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

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


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

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


3

If I understand your quantifies (for any given irreducible $f(x)$, there does not exist such an algorithm), then it’s a stronger assumption and one that is unlikely to be true as $n$ grows. First, note that if we write $x_i$ for $g^{s_i}$ then the degree (at most) $n$ polynomial $\sum c_is^i$ gives $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ as easily calculable. ...


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

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

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

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


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