Elliptic curve cryptography | Computational hardness assumptions | Pairing-based cryptography

XDH assumption

The external Diffie–Hellman (XDH) assumption is a computational hardness assumption used in elliptic curve cryptography. The XDH assumption holds that there exist certain subgroups of elliptic curves which have useful properties for cryptography. Specifically, XDH implies the existence of two distinct groups with the following properties: 1. * The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in and . 2. * There exists an efficiently computable bilinear map (pairing) . 3. * The decisional Diffie–Hellman problem (DDH) is intractable in . The above formulation is referred to as asymmetric XDH. A stronger version of the assumption (symmetric XDH, or SXDH) holds if DDH is also intractable in . The XDH assumption is used in some pairing-based cryptographic protocols. In certain elliptic curve subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem. These groups, referred to as (GDH) groups, facilitate a variety of novel cryptographic protocols, including tri-partite key exchange, identity based encryption, and secret handshakes (to name a few). However, the ease of computing DDH within a GDH group can also be an obstacle when constructing cryptosystems; for example, it is not possible to use DDH-based cryptosystems such as ElGamal within a GDH group. Because the DDH assumption holds within at least one of a pair of XDH groups, these groups can be used to construct pairing-based protocols which allow for ElGamal-style encryption and other novel cryptographic techniques. In practice, it is believed that the XDH assumption may hold in certain subgroups of elliptic curves. This notion was first proposed by Scott (2002), and later by Boneh, Boyen and Shacham (2002) as a means to improve the efficiency of a signature scheme. The assumption was formally defined by Ballard, Green, de Medeiros and Monrose (2005), and full details of a proposed implementation were advanced in that work. Evidence for the validity of this assumption is the proof by Verheul (2001) and Galbraith and Rotger (2004) of the non-existence of in two specific elliptic curve subgroups which possess an efficiently computable pairing. As pairings and distortion maps are currently the only known means to solve the DDH problem in elliptic curve groups, it is believed that the DDH assumption therefore holds in these subgroups, while pairings are still feasible between elements in distinct groups. (Wikipedia).

Video thumbnail

Well Ordering and Induction: Part 2

This was recorded as supplemental material for Math 115AH at UCLA in the spring quarter of 2020. In this video, I discuss the "philosophical importance" of induction, and go over two proofs that use the Principle of Mathematical Induction and the Well-Ordering Principle, respectively.

From playlist Well Ordering and Induction

Video thumbnail

How to Find the X and Y Intercept of a Line ( Example 1 ) Intermediate Algebra , Lesson 60

This tutorial shows how to find the X intercept and Y intercept of a line. Once the X and Y intercepts of a line are found, they are used to sketch the line on the X Y coordinate system. Join this channel to get access to perks: https://www.youtube.com/channel/UCn2SbZWi4yTkmPUj5wnbfoA/joi

From playlist Intermediate Algebra

Video thumbnail

Introduction to Symmetry about the x-axis, y-axis, and the origin Using Points

This video introduces symmetry about the x-axis, y-axis, and the origin using points on the coordinate plane. Site: http://mathispower4u.com

From playlist Determining Odd and Even Functions

Video thumbnail

Giles Gardam: Solving semidecidable problems in group theory

Giles Gardam, University of Münster Abstract: Group theory is littered with undecidable problems. A classic example is the word problem: there are groups for which there exists no algorithm that can decide if a product of generators represents the trivial element or not. Many problems (th

From playlist SMRI Algebra and Geometry Online

Video thumbnail

What is the X Y Coordinate System , Intermediate Algebra , Lesson 55

This tutorial gives an introduction to the x y coordinate system, and demonstrates how to represent a point in this system. Join this channel to get access to perks: https://www.youtube.com/channel/UCn2SbZWi4yTkmPUj5wnbfoA/join :)

From playlist Intermediate Algebra

Video thumbnail

20 The identity element

Sets might contain an element that can be identified as an identity element under some binary operation. Performing the operation between the identity element and any arbitrary element in the set must result in the arbitrary element. An example is the identity element for the binary opera

From playlist Abstract algebra

Video thumbnail

Fundamentals of Mathematics - Lecture 26: Well-Definedness

course page: https://www.uvm.edu/~tdupuy/logic/Math52-Fall2017.html videography - Eric Melton, UVM

From playlist Fundamentals of Mathematics

Video thumbnail

Homomorphisms in abstract algebra

In this video we add some more definition to our toolbox before we go any further in our study into group theory and abstract algebra. The definition at hand is the homomorphism. A homomorphism is a function that maps the elements for one group to another whilst maintaining their structu

From playlist Abstract algebra

Video thumbnail

Gradient and Y-Intercept of a Straight Line Given its Equation

"Find the gradient or y-intercept of a straight line given its equation."

From playlist Algebra: Straight Line Graphs

Video thumbnail

Symmetry Introduction: x-axis, y-axis, the origin

This video produces symmetry about the x-axis, y-axis, and origin. It explains how to visually determine if a graph has symmetry and how to determine symmetry algebraically. Complete Library: http://mathispower4u.com Search by Topic: http://mathispower4u.wordpress.com

From playlist Graphing Functions (Algebra 1)

Video thumbnail

7. Reframing for Resolving Intractable Controversies

MIT 11.965 Reflective Practice: An Approach for Expanding Your Learning Frontiers, IAP 2007 View the complete course: http://ocw.mit.edu/11-965IAP07 Instructor: Ceasar McDowell, Claudia Canepa, Sebastiao Ferriera License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/te

From playlist MIT 11.965 Reflective Practice, IAP 2007

Video thumbnail

GoGaRuCo 2012 - Cruft and Technical Debt: A Long View

Cruft and Technical Debt: A Long View by: Yehuda Katz Cruft is inevitable. Whether you're working around a bug in Internet Explorer, Heroku or Ruby 1.8, our libraries and applications quickly diverge from the platonic ideal of software. In the short-term, there's no point in fretting. Rat

From playlist gogaruco 2012

Video thumbnail

Check Your ASSUMPTIONS for Parametric Hypothesis Tests (16-2)

All parametric statistical tests require that the population have certain characteristics. If the data do not meet those assumptions, then any conclusions drawn from the test may be wrong. Some assumptions can be addressed when designing your research and others can only be checked once yo

From playlist Assumptions, Significance, & Effect Size Wrap-Up (WK 16 - QBA 237)

Video thumbnail

Check Your Assumptions – The Test Assumptions of Statistical Testing (8-12)

You know what happens when you assume? If your assumptions are wrong, it prevents you from looking at the world accurately. Parametric inferential statistics are built on certain assumptions about the data. And if those assumptions are violated, the conclusions based on those assumptions a

From playlist WK8 Statistical Hypothesis Testing (NHST) - Online Statistics for the Flipped Classroom

Video thumbnail

Assumptions - Causal Inference

In this video, I introduce the most important assumptions in casual inference that we use in order to avoid mistakes such as presuming association and causation to be one and the same, among others: - Positivity - SUTVA - Large Sample Size - Double Blinded - No Measurement Error - Exchan

From playlist Causal Inference - The Science of Cause and Effect

Video thumbnail

Regularity of stable codimension 1 CMC varifolds - Neshan Wickramasekera

Variational Methods in Geometry Seminar Topic: Regularity of stable codimension 1 CMC varifolds Speaker: Neshan Wickramasekera Affiliation: University of Cambridge; Member, School of Mathematics Date: January 15, 2019 For more video please visit http://video.ias.edu

From playlist Variational Methods in Geometry

Video thumbnail

Logic 4: Natural Deduction with Logical Axioms — Tutorial 4/4

In this four-part series we explore propositional logic, Karnaugh maps, implications and fallacies, predicate logic, existential and universal quantifiers and finally natural deduction. Become a member: https://youtube.com/Bisqwit/join My links: Twitter: https://twitter.com/RealBisqwit L

From playlist Logic Tutorial

Video thumbnail

Bell inequalities and the profound implications of quantum mechanics

. Timestamps 00:00 Introduction 00:35 Toy model 04:32 Real experiments 08:10 Assumption 1 10:27 Assumption 2 18:36 Assumption 3 19:58 Conclusion The original paper by John Bell https://cds.cern.ch/record/111654/files/vol1p195-200_001.pdf Inspiration for using this state instead

From playlist Summer of Math Exposition 2 videos

Video thumbnail

PCP and Delegating Computation: A Love Story - Yael Tauman Kalai

Computer Science/Discrete Mathematics Seminar I Topic: PCP and Delegating Computation: A Love Story Speaker: Yael Tauman Kalai Affiliation: Microsoft Research Date: January 28, 2019 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Substitution and y = mx + b

Turn graphic data into algebraic equations.

From playlist Algebra: Linear Equations with One Variable

Related pages

Subgroup | Computational hardness assumption | Computational Diffie–Hellman assumption | Bilinear map | ElGamal encryption | Group (mathematics) | Pairing-based cryptography | Key exchange | Decisional Diffie–Hellman assumption