22:
140:
80:
53:
455:(improperly?) to ECC implementing a trapdoor function, and my intuitive (but wrong?) sense that that must be true, unless 'trapdoor function' has a more esoteric definition than is 'commonly understood' -- in which case this article needs to explain that distinction more simply and clearly. Cheers.
432:
The article states "However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie-Hellman problem (CDH) and/or its decisional variant are used." I am not aware of any trapdoor permutation that can be constructed using CDH. Of
293:
Another candidate trapdoor permutation is squaring mod n, taken over the domain of quadratic residues mod n, where n is a Blum integer (i.e., the product of two primes that are both 3 mod 4). The public information is simply n, which allows one to compute f(x) = x^2 mod n. The secret information is
201:
Merkle proposed a one way function (trapdoor type) about '77 which turned out to not be a one way function after all, trapdoor or not. Adi Shamir found a way of reversing it (on an Apple II, no less) in almost no time. It was one of the knapsack group, which more or less explains why problems in this
262:
be reversed. Take a work of
Shakespeare and replace every letter with "X". Now take your result, and using only it, recover the original work. Cryptographic hashes are an example of a one way function. Any binary object can be hashed, but you cannot recover the original object from just a hash,
236:
The distinction is indeed somewhat informal, if not jargon. The problem is that the field of interest (usually crypto or something similar) has few proofs (of existence or any other sort) prompting/requiring the use of rigorous language. Crypto is an odd field in that few engineering disciplines are
205:
So, some one-way functions are known which have trapdoors (some of which are provably so in some sense -- ie the one-time pad algorithm), some one-way functions are known which are non-reversible in current practice (sufficienty large interger factorization) and thus may have no trapdoors, and some
197:
Take (p)(n) = m. If m is large enough, it will be impossible (in practice) to recover p or n. If p and n were prime, their values would be unique, but still unavailable in practice. On the other hand, if a one-way function has a trapdoor (to continue the example or something similar to it, consider
454:
Hi. The article seems to my far-from-expert reading to imply (state?) that
Elliptic Curve 'crypto stuff' isn't a 'proper' trapdoor function (because something about discrete logarithms). That's a wishy-washy sentence because it's not clear to me. I'm confused because many sites refer
193:
Perhaps not much ordinary usage, but considerable in theory and practice. Let's say we find a function which can be computed in one way only. Some of the large class of NP algorithms can be used as a starting point. More simple, we can just consider large integer multiplication.
240:
I like the idea of an article on one-way functions and in such an article the trapdoor subset would naturally be discussed. The problem is that I can't even begin to put one together given my limited range of maths expertise. Perhaps you could have a go at an initial dish?
289:
A candidate example of a trapdoor function (though "permutation" is more accurate than "function") is RSA, where (n,e) allows one to compute the function f(x)=x^e mod n, and the trapdoor is d = e^{-1} mod phi(n) which allows one to compute f^{-1}(y) = y^d mod n.
433:
course, one can use it to construct the DH encryption scheme, but that is not a trapdoor permutation (technically, the difference is that an encryption scheme may be randomized while a trapdoor permutation must be deterministic).
294:
the factorization of n, which can be used to find all four square roots of any y mod n. Exactly one of these square roots is itself a square, and this can also be found using the factorization of n.
130:
309:
There is no mathematical definition here, though there is a good intuitive definition. Not being strictly a cryptographer, I'd be more comfortable if someone else offered one. Any ideas guys?
286:
known to be trapdoor functions, and probably aren't. There is no known way to efficiently compute discrete logs, and there is no (known) single "trapdoor" which will help you factor integers.
255:
A trapdoor function is what's talked about on this page. It's easy to multiply two huge primes together, and takes a very long time to do the reverse. But it is possible to do the reverse.
237:
required to produce designs which can withstand attack by intelligent malevolent
Opposition, and furthermore using methods and techniques not now known (at least publicly) to anyone.
217:
Yes. If I take it correctly, it says these are 'jargon' rather than very rigorous terms; and that in this case it matters. So perhaps all three topics belong in an article like
422:
493:
154:
363:
498:
488:
483:
120:
503:
478:
96:
149:
63:
264:
456:
87:
58:
33:
218:
172:
268:
21:
460:
424:. A party randomly selects i and likewise obtains f_i. f_i is the trapdoor function, i is the trapdoor.
297:
These two are really the best-known and only tested candidate trapdoor permutations of which I'm aware. --
310:
226:
198:
RSA) then only those who have been told about the trapdoor (ie, who have the key) can recover p and n.
186:
39:
368:
95:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
298:
324:
176:
180:
440:
472:
92:
436:
464:
444:
313:
272:
139:
206:
which used to be thought to be one-way functions are known to not be so.
242:
210:
79:
52:
428:
Diffie-Hellman problem does not give rise to trapdoor permutation
321:
Let F be a family of one-way functions, indexed by I such that
15:
138:
282:
Hey all, "discrete log" and "prime factorization" are
450:
Elliptic Curve / logarithm stuff confusing to layfolk
371:
327:
278:
Corrections needed about candidate trapdoor functions
91:, a collaborative effort to improve the coverage of
416:
357:
202:group aren't being investigated much any more.
8:
263:even if you have infinite computing power.
175:? What precisely is the difference between
19:
47:
494:High-importance Computer science articles
396:
370:
326:
49:
499:WikiProject Computer science articles
489:Start-Class Computer science articles
484:High-importance Cryptography articles
7:
85:This article is within the scope of
365:may be easily computed, as well as
38:It is of interest to the following
318:Here is what I have come up with:
105:Knowledge:WikiProject Cryptography
14:
504:WikiProject Cryptography articles
479:Start-Class Cryptography articles
108:Template:WikiProject Cryptography
78:
51:
20:
417:{\displaystyle g'(i)=f^{-1}(i)}
219:one way functions and trapdoors
125:This article has been rated as
411:
405:
386:
380:
352:
346:
337:
331:
273:17:18, 10 September 2019 (UTC)
1:
147:This article is supported by
99:and see a list of open tasks.
445:13:44, 5 February 2008 (UTC)
183:? I feel we should be told.
150:WikiProject Computer science
520:
465:11:41, 14 July 2016 (UTC)
358:{\displaystyle g(i)=f(i)}
314:20:50, 10 July 2007 (UTC)
301:02:59, 17 Nov 2004 (UTC)
173:trapdoor one way function
146:
124:
73:
46:
258:A true one way function
213:15:38, 5 Apr 2004 (UTC)
189:17:58, 4 Apr 2004 (UTC)
171:Anyone able to sort out
88:WikiProject Cryptography
252:Fifteen years later...
245:20:09, 8 Apr 2004 (UTC)
229:16:47, 5 Apr 2004 (UTC)
418:
359:
143:
28:This article is rated
419:
360:
142:
111:Cryptography articles
369:
325:
221:, dishing the dirt.
414:
355:
144:
34:content assessment
209:Does this help?
177:trapdoor function
169:
168:
165:
164:
161:
160:
511:
423:
421:
420:
415:
404:
403:
379:
364:
362:
361:
356:
227:Charles Matthews
187:Charles Matthews
181:one way function
131:importance scale
113:
112:
109:
106:
103:
82:
75:
74:
69:
66:
64:Computer science
55:
48:
31:
25:
24:
16:
519:
518:
514:
513:
512:
510:
509:
508:
469:
468:
452:
437:Dominique Unruh
430:
392:
372:
367:
366:
323:
322:
307:
280:
155:High-importance
127:High-importance
110:
107:
104:
101:
100:
68:High‑importance
67:
61:
32:on Knowledge's
29:
12:
11:
5:
517:
515:
507:
506:
501:
496:
491:
486:
481:
471:
470:
451:
448:
429:
426:
413:
410:
407:
402:
399:
395:
391:
388:
385:
382:
378:
375:
354:
351:
348:
345:
342:
339:
336:
333:
330:
311:71.194.163.223
306:
303:
279:
276:
265:192.189.128.13
250:
249:
248:
247:
246:
238:
231:
230:
223:
222:
191:
167:
166:
163:
162:
159:
158:
145:
135:
134:
123:
117:
116:
114:
97:the discussion
83:
71:
70:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
516:
505:
502:
500:
497:
495:
492:
490:
487:
485:
482:
480:
477:
476:
474:
467:
466:
462:
458:
449:
447:
446:
442:
438:
434:
427:
425:
408:
400:
397:
393:
389:
383:
376:
373:
349:
343:
340:
334:
328:
319:
316:
315:
312:
304:
302:
300:
299:Chris Peikert
295:
291:
287:
285:
277:
275:
274:
270:
266:
261:
256:
253:
244:
239:
235:
234:
233:
232:
228:
225:
224:
220:
216:
215:
214:
212:
207:
203:
199:
195:
190:
188:
184:
182:
178:
174:
156:
153:(assessed as
152:
151:
141:
137:
136:
132:
128:
122:
119:
118:
115:
98:
94:
90:
89:
84:
81:
77:
76:
72:
65:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
457:92.27.136.85
453:
435:
431:
320:
317:
308:
296:
292:
288:
283:
281:
259:
257:
254:
251:
208:
204:
200:
196:
192:
185:
170:
148:
126:
102:Cryptography
93:Cryptography
86:
59:Cryptography
40:WikiProjects
305:Definition?
30:Start-class
473:Categories
129:on the
260:CANNOT
36:scale.
461:talk
441:talk
269:talk
179:and
121:High
284:not
475::
463:)
443:)
398:−
271:)
243:ww
211:ww
157:).
62::
459:(
439:(
412:)
409:i
406:(
401:1
394:f
390:=
387:)
384:i
381:(
377:′
374:g
353:)
350:i
347:(
344:f
341:=
338:)
335:i
332:(
329:g
267:(
133:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
