TVP

# Dan Boneh密码学笔记14

Part 1 Elliptic curve cryptography

Elliptic curves.

–Over the reals.

–Geometric and algebraic.

–Over finite fields, GF(p).

Part 2 ECC based crypto version

The ECDLP Problem:

-Getting a group.

-Order.

Diffie-Hellman Key Exchange.

Elliptic Curve Diffie-Hellman Key Exchange

Elliptic Curve El-Gamal.

Part3 Bilinear Pairing

Motivating the use of bilinear pairings.

Bilinear pairing

Security problems

Part4 Identity based Encryption

Part 1 Elliptic curve cryptography

Elliptic curves.

–Over the reals.

–Geometric and algebraic.

–Over finite fields, GF(p).

We have seen some problems, DLP, CDHP, DDHP which are considered hard. Some of these problems are over Abelian fields or groups.

We have looked at fields GF(p) where the elements of the field are simply integers, and the operations are modular. But these are not the only domains we can use. Miller and Koblitz, independently, suggested the use of elliptic curves for constructing public-key cryptosystems.

We can take an Elliptic curve over a field, GF(p), or GF(p^m). We are effectively restricting solutions to an equation to elements of a particular field. The problems like DLP are not necessarily hard in those fields, so we need to be a little careful.

Relative key sizes: For similar security

Elliptic curves over the reals

To get to an Abelian group we need a commutative binary operation.

This addition can be defined geometrically, making use of intersections and mirror images. The addition can, alternately, be represented algebraically. The point at infinity acts as the identity.

Let P1 and P2 be elements of E. We can calculate P1+P2 geometrically by drawing a line through P1 and P2 and recording the point on interception of the curve. The reflection across the x axis and onto the elliptic curve E is the solution P1+P2.

How does infinity act as the identity? “A vertical line” hits the opposite side and reflects back.

Elliptic curves over GF(p)

The reals are an infinite field. In cryptography, the finite fields are more frequently used. We can consider elliptic curves where the operations are all carried out with the elements being elements of some field, and operations being “modular”.

x只需要从0算到11-1（p-1）即可。

Part 2 ECC based crypto version

The ECDLP Problem:

-Getting a group.

-Order.

Diffie-Hellman Key Exchange.

Elliptic Curve Diffie-Hellman Key Exchange

Elliptic Curve El-Gamal.

The ECDLP Problem椭圆曲线离散对数问题

The most common hard problem that underlies the use of public key elliptic curve cryptosystems is the Elliptic Curve Discrete Logarithm Problem.

Let E be the set of points of our elliptic curve defined over the field GF(p).

The collection of points and the operation of addition, as defined earlier, form a group which we could denote E(GF(p)).

In this group the common operation is “scalar multiplication”.

Notice that we have a group not a field.

Scalar multiplication is not an additional binary operation, rather is an extension of the addition rule.

We write scalar multiplication, of a point P, by an integer k as kP, and define it as P+P+…+P with k copies of P in the sum.

We can now define the Elliptic Curve Discrete Logarithm Problem:

Given two points in E, P1 and P2, find k: P1=kP2.

Order … group and element …

Diffie-Hellman Key Exchange

The first public key system.

Security is based on the difficulty of computing discrete logarithm.

Actually security it is based on the computational Diffie-Hellman problem.

System Setup：

A finite field Zp, where p is prime. A primitive element g ∈ Zp. p and g are public.

EC Diffie-Hellman key exchange

EC El-Gamal

Part3 Bilinear Pairing

Motivating the use of bilinear pairings.

Bilinear pairing

Security problems

Motivating the use of bilinear pairings.

for example

Bilinear pairings

Weil Pairing

Tate Pairing

Security for pairing over EC

Security depends on the hardness of one of a number of computational or decisional problems.

We have already seen the Elliptic Curve Discrete Log Problem (ECDLP).

We will now briefly look at the Bilinear Diffie-Hellman problem (BDHP).

BDHP，给定以下这个四元组，在不知道abc的情况下计算出e是困难的。

And, in the standard relationship manner, the corresponding BDH assumption is that there is no efficient algorithm to solve the BDHP with non-negligible probability.

CDH and DDH

CDH: 给定P in G，xP和yP，计算xyP

DDH: 给定P in G，xP，yP和Q = zP，请确定z = xy。

DDH in pairing

Part4 Identity based Encryption（IBE）

This is a special type of public key cryptography. The idea is to simplify the management, distribution etc. of public keys. In traditional public key cryptography the key itself is a (fairly) random string managed within a public key infrastructure. Certificates are used to move trust from the key to a trusted entity, often a certificate authority. The certificate ties an identity and public-key (and corresponding secret private key) to each other. But their management is complicated.

In identity based cryptography the idea (Shamir 1984) is to have an identity taking the role of identity and public key.The certificate trust is replaced through the use of a trusted authority which generates a private key for a user.

The role of the TA

The TA issues private keys, and there may be many private keys associated with the same public key, which is just the identity.

-The identity, and therefore the public key, exists before the private key.

-However, the issue of the private key can be restricted in a time dependent manner, or on the basis of access control.

-Bob can encrypt a message for Alice@uow.edu.au (an identity for Alice) which Alice can only decrypt if she receives the private decryption key from the TA, which will only happen if she produces appropriate evidence as to who she is.

TA发布私钥，并且可能有许多与同一公钥关联的私钥，而这仅仅是身份。

Bob可以为Alice@uow.edu.au（Alice的身份）加密一条消息，只有当她从TA收到私有解密密钥时，该消息才可以解密，只有当她提供有关其身份的适当证据时，才会发生该消息。

The private key of the TA, and thus it’s responsibilities and rights, can be distributed to distribute trust.

The private key of an individual is established as a function of the master-key and the public key for that individual (or identity), which was generated earlier.

private-key=F(master-key,public-key).

TA的私钥及其职责和权利可以分发以分发信任。

ID-Based Crypto in practice

Originally only identity based signatures were known. In 2001 the first efficient and “secure” identity based encryption scheme was proposed (Sakai, Ohgishi, Kasahara). This was followed shortly after by Boneh-Franklin’s security model for identity based encryption, and a provably secure scheme. This was roughly the same scheme as Sakai et al. IND-ID-CPA secure, but transformable to IND-ID-CCA secure. The identity based encryption schemes rely primarily on bilinear pairings.

K输出给Alice的私钥dID。对应的公钥是这个ID。

E是Bob使用Alice的公钥ID加密消息m。pp是公开参数。

D是Alice使用私钥dID解密密文。

Boneh-Franklin IBE

dID=sH1(ID)

s和t可以这么跳。

Security of IBE

0 条评论

• ### Dan Boneh密码学笔记7

1.Active attacks on CPA-secure encryption

• ### Dan Boneh密码学笔记2

实际上我的学习时间得在四个小时才够，而且得是脑子清醒的四个小时。这还是刚开始简单的流密码......感觉也就听懂了90%，真正消化完......尤其那些安全性的...

• ### Dan Boneh密码学笔记9

TTP发送给Alice用Alice密钥加密的信息，包括”这个共享密钥是AB之间的“和Kab。

• ### Dan Boneh密码学笔记5

⇒ attacker cannot produce a valid tag for a newmessage

• ### Dan Boneh密码学笔记8

3.Deterministic Encryption Constructions:SIV and wide PRP

• ### Dan Boneh密码学笔记6

这个定理：如果底层MAC是安全的，且H是抗碰撞的，那么这个组合可以计算长信息的MAC，得到的MAC也是安全的。

• ### Dan Boneh密码学笔记15

Boneh, D., & Franklin, M. (2001, August). Identity-based encryption from the Wei...

• ### Dan Boneh密码学笔记10

更新本节用了三天。最近开学事情有点多，学习上有点不知道先学哪个。要学的东西太多了，区块链安全的15篇论文、以太坊的课程、密码学课程（进度10/13）、UC安全框...

• ### Dan Boneh密码学笔记1

https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/

• ### Dan Boneh密码学笔记13

Boneh的课程更新到12章就没了，好像明年会继续更新，第一次像追剧一样追一门课。可太刺激了。

• ### Dan Boneh密码学笔记4

4.modes of operation: many time key (CBC)

• ### Dan Boneh密码学笔记12

12.Public key encryption from Diffie-Hellman

• ### Dan Boneh密码学笔记11

11.Public Key Encryption from trapdoor permutations

• ### Pairings in Cryptography

Dan Boneh密码学笔记14这篇part3介绍了bilinear pairing。

• ### 密码学安全归约6 Simulation and Solution

密码学安全归约1 Algorithm and Security Model Definitions

• ### Random oracles(2)

上面这篇笔记引用自Fuchun Guo, Willy Susilo, Yi Mu 《Introduction to security reduction》介绍了...

10元无门槛代金券