Back

View the solution

### Puzzle Preparation

## See puzzle details on Github

Puzzle link
### Puzzle Hints

### Puzzle Winners

## niooss-ledger

## Konstantce

## bkomuves

### Puzzle Solution

29th November

19:00 UTC

Built by: Applied Cryptography Group @ Stanford

With great power comes great responsibility.

View the solution

To give you a better chance of solving this puzzle, we suggest that you look through some relevant background materials.

1. Try using the Bls12Cheon::pairing functionality to calculate the following pairing values:
e(P, Q), e(τP, Q), e(τ^{d_1} P, τ^{d_2} Q) ∈ F_{p^k}. Can you apply Cheon’s attack to these values?

2. Look at the algorithm described on pages 4-5 of Cheon’s paper, and apply
this algorithm to the three values from Hint #1 to find τ in time O(√(q/d)).

3. Since we know the lower and upper bounds on k_0, the m in the BSGS algorithm
to kind k_0 can be smaller than expected - it can be be sqrt(B - A)

01

Puzzle completed

Score

1000

02

Puzzle completed

Score

988.8

03

Puzzle completed

Score

900

You can see all of the scores for this puzzle in the spreadsheet here.

The winner of the puzzle write up was submitted by niooss-ledger. You can view the solution and puzzle write up here. The background material required to solve the puzzle is also covered in the write up.