ในวิทยาการคอมพิวเตอร์เชิง ทฤษฎี และการเข้ารหัสลับ ฟังก์ชันกับดัก ( trapdoor function)คือฟังก์ชันที่คำนวณได้ง่ายในทิศทางหนึ่ง แต่คำนวณได้ยากในทิศทางตรงกันข้าม (การหาฟังก์ชันผกผัน ) โดยไม่มีข้อมูลพิเศษที่เรียกว่า "กับดัก" ฟังก์ชันกับดักเป็นกรณีพิเศษของฟังก์ชันทางเดียวและถูกใช้กันอย่างแพร่หลายใน การ เข้ารหัสลับแบบกุญแจสาธารณะ^{[ 2 ]}

ในทางคณิตศาสตร์ ถ้าfเป็นฟังก์ชันแบบกับดัก (trapdoor function) แล้วจะมีข้อมูลลับบางอย่างt อยู่ ซึ่งเมื่อกำหนดf ( x ) และtแล้ว จะสามารถคำนวณx ได้อย่างง่ายดาย ลองพิจารณาแม่กุญแจและกุญแจของมัน การเปลี่ยนแม่กุญแจจากเปิดเป็นปิดนั้นทำได้ง่ายมากโดยไม่ต้องใช้กุญแจ เพียงแค่ดันห่วงเข้าไปในกลไกของแม่กุญแจ แต่การเปิดแม่กุญแจให้ง่ายขึ้นนั้นจำเป็นต้องใช้กุญแจ ในที่นี้ กุญแจtคือกับดัก และแม่กุญแจคือฟังก์ชันแบบกับดัก

ตัวอย่างของกับดักทางคณิตศาสตร์อย่างง่ายคือ "6895601 เป็นผลคูณของจำนวนเฉพาะสองจำนวน จำนวนเหล่านั้นคืออะไร" วิธีแก้ ปัญหา แบบ "ลองผิดลองถูก" ทั่วไปคือการลองหาร 6895601 ด้วยจำนวนเฉพาะหลายๆ จำนวนจนกว่าจะพบคำตอบ อย่างไรก็ตาม หากบอกว่า 1931 เป็นหนึ่งในจำนวนเหล่านั้น เราสามารถหาคำตอบได้โดยการป้อน "6895601 ÷ 1931" ลงในเครื่องคิดเลขใดก็ได้ ตัวอย่างนี้ไม่ใช่ฟังก์ชันกับดักที่แข็งแกร่ง – คอมพิวเตอร์สมัยใหม่สามารถเดาคำตอบที่เป็นไปได้ทั้งหมดได้ภายในหนึ่งวินาที – แต่ปัญหาตัวอย่างนี้สามารถปรับปรุงได้โดย ใช้ผลคูณของจำนวนเฉพาะสองจำนวน ที่ ใหญ่กว่ามาก

ฟังก์ชันกับดัก (Trapdoor functions) เริ่มเป็นที่รู้จักอย่างแพร่หลายในด้านการเข้ารหัสลับในช่วงกลางทศวรรษ 1970 จากการตีพิมพ์ เทคนิค การเข้ารหัสแบบอสมมาตร (หรือแบบกุญแจสาธารณะ)โดยDiffie , HellmanและMerkleที่จริงแล้วDiffie & Hellman (1976)เป็นผู้บัญญัติศัพท์คำนี้ มีการเสนอคลาสของฟังก์ชันหลายประเภท และในไม่ช้าก็เห็นได้ชัดว่าการค้นหาฟังก์ชันกับดักนั้นยากกว่าที่คิดไว้ในตอนแรก ตัวอย่างเช่น ข้อเสนอแนะในยุคแรกคือการใช้แผนการที่อิงตามปัญหาผลรวมของเซตย่อยซึ่งในไม่ช้าก็พบว่าไม่เหมาะสม

ณ ปี 2004 ฟังก์ชันดักจับ (ตระกูลฟังก์ชัน) ที่เป็นที่รู้จักดีที่สุดคือ ตระกูลฟังก์ชัน RSAและRabinทั้งสองตระกูลเขียนในรูปการยกกำลังมอดูลจำนวนประกอบ และทั้งสองตระกูลมีความเกี่ยวข้องกับปัญหา การแยก ตัวประกอบ เฉพาะ

ฟังก์ชันที่เกี่ยวข้องกับความยากของปัญหาลอการิทึมแบบไม่ต่อเนื่อง (ไม่ว่าจะมอดูลกับจำนวนเฉพาะหรือในกลุ่มที่กำหนดบนเส้นโค้งวงรี ) ไม่ เป็น ที่รู้จักว่าเป็นฟังก์ชันกับดัก เนื่องจากไม่มีข้อมูล "กับดัก" ที่รู้จักเกี่ยวกับกลุ่มที่ช่วยให้สามารถคำนวณลอการิทึมแบบไม่ต่อเนื่องได้อย่างมีประสิทธิภาพ

ในทางด้านวิทยาการเข้ารหัสลับ คำว่า "กับดัก" (trapdoor) มีความหมายเฉพาะเจาะจงตามที่ได้กล่าวไว้ข้างต้น และไม่ควรสับสนกับคำว่า " ประตูหลัง" (backdoor ) (ซึ่งมักใช้สลับกัน ซึ่งไม่ถูกต้อง) ประตูหลังคือกลไกที่จงใจเพิ่มเข้าไปในอัลกอริธึมการเข้ารหัสลับ (เช่น อัลกอริธึมการสร้างคู่กุญแจ อัลกอริธึมการลงนามดิจิทัล ฯลฯ) หรือระบบปฏิบัติการ เป็นต้น ซึ่งอนุญาตให้บุคคลที่ไม่ได้รับอนุญาตหนึ่งคนหรือมากกว่านั้นสามารถหลีกเลี่ยงหรือบ่อนทำลายความปลอดภัยของระบบได้ในบางลักษณะ

ฟังก์ชันประตูกับดัก (Trapdoor function)คือชุดของฟังก์ชันทางเดียว { f _k  : D _k → R _k } ( k ∈ K ) ซึ่งK , D _k , R _k ทั้งหมด เป็นเซตย่อยของสตริงไบนารี {0, 1} ^*ที่ตรงตามเงื่อนไขต่อไปนี้:

• มี อัลกอริทึม การสุ่มตัวอย่าง แบบพหุนามเวลาเชิงความน่าจะเป็น (PPT) Gen st Gen(1 ⁿ ) = ( k , t _k ) โดยที่k ∈ K ∩ {0, 1} ⁿและt _k ∈ {0, 1} ^*เป็นไปตาม | t _k | < p ( n ) โดยที่pเป็นพหุนามบางตัว แต่ละt _kเรียกว่ากับดักประตูที่สอดคล้องกับkแต่ละกับดักประตูสามารถสุ่มตัวอย่างได้อย่างมีประสิทธิภาพ
• เมื่อกำหนดอินพุตkแล้ว ยังมีอัลกอริทึม PPT ที่ให้เอาต์พุตx ∈ D _k อีกด้วย กล่าวคือสามารถสุ่มตัวอย่างD _{k แต่ละตัวได้อย่างมีประสิทธิภาพ}
• สำหรับk ∈ K ใดๆ จะมีอัลกอริทึม PPT ที่คำนวณf _k ได้อย่างถูก ต้อง
• สำหรับk ∈ K ใดๆ จะมีอัลกอริทึม PPT A st สำหรับx ∈ D _k ใดๆ ให้y = A ( k , f _k ( x ), t _k ) แล้วเราจะได้f _k ( y ) = f _k ( x ) นั่นคือ เมื่อกำหนดกับดักแล้ว ก็สามารถผกผันได้ง่าย
• สำหรับk ∈ K ใดๆ โดยไม่มีกับดักt _kสำหรับอัลกอริทึม PPT ใดๆ ความน่าจะเป็นที่จะกลับf _k ได้อย่างถูกต้อง (กล่าวคือ เมื่อกำหนดf _k ( x ) แล้ว ให้หาภาพก่อนหน้าx'ที่f _k ( x' ) = f _k ( x )) นั้นมีน้อยมาก^{[ 3 ] [ 4 ] [ 5 ]}

ถ้าฟังก์ชันแต่ละฟังก์ชันในชุดข้างต้นเป็นการเรียงสับเปลี่ยนทางเดียว ชุดดังกล่าวก็เรียกว่าการเรียงสับเปลี่ยนแบบประตูกับดัก^{[ 6 ]}

ในสองตัวอย่างต่อไปนี้ เราจะถือว่าการแยกตัวประกอบของจำนวนประกอบขนาดใหญ่เป็นเรื่องยากเสมอ (ดูการแยกตัวประกอบจำนวนเต็ม )

ในตัวอย่างนี้ ตัวผกผันของโมดูลัส( ฟังก์ชันโทเทียนต์ของออยเลอร์ของ) คือกับดัก: ${\displaystyle d}$${\displaystyle e}$${\displaystyle \phi (n)}$${\displaystyle n}$

${\displaystyle f(x)=x^{e}\mod n.}$

ถ้า ทราบการแยกตัวประกอบของ ก็ สามารถคำนวณได้ ด้วยวิธีนี้สามารถคำนวณ อินเวอร์ส ของ ได้ จากนั้นเมื่อกำหนดก็สามารถหาได้ความยากของมันเป็นผลมาจากสมมติฐาน RSA ^{[ 7 ]}${\displaystyle n=pq}$${\displaystyle \phi (n)=(p-1)(q-1)}$${\displaystyle d}$${\displaystyle e}$${\displaystyle d=e^{-1}\mod {\phi (n)}}$${\displaystyle y=f(x)}$${\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}$

ให้z เป็นจำนวนประกอบขนาดใหญ่ที่ โดยที่และเป็นจำนวนเฉพาะขนาดใหญ่ที่และ ถูกเก็บเป็นความลับจากฝ่ายตรงข้าม ปัญหาคือการคำนวณเมื่อกำหนดให้ โดยที่ กับดัก คือการแยกตัวประกอบของด้วยกับดักนี้ คำตอบของzสามารถกำหนดได้เป็น โดยที่ดูทฤษฎีบทเศษเหลือของจีนสำหรับรายละเอียดเพิ่มเติม โปรดทราบว่าเมื่อกำหนดจำนวนเฉพาะและเราสามารถหาและได้ เงื่อนไขและรับประกันว่าคำตอบและสามารถกำหนดได้อย่างดี^{[ 8 ]}${\displaystyle n}$${\displaystyle n=pq}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$${\displaystyle z}$${\displaystyle a}$${\displaystyle a\equiv z^{2}{\pmod {n}}}$${\displaystyle n}$${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$${\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}$${\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}$${\displaystyle p\equiv 3{\pmod {4}}}$${\displaystyle q\equiv 3{\pmod {4}}}$${\displaystyle x}$${\displaystyle y}$

• ฟังก์ชันทางเดียว