Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Advanced Cryptography Reading Assignment Lattice-Based Cryptanalysis

    Uploaded by

    MarioKundit
    This document provides reading assignments on the topic of lattice-based cryptanalysis. It outlines three main sections for students to study: 1) Current records for solving lattice challenges and how to use the Sage mathematics software to perform lattice reduction. 2) Cryptanalysis of a knapsack-based hash function by using LLL lattice reduction to find collisions. Students are asked to implement an attack. 3) Studying the Boneh-Durfee paper on lattice attacks against RSA and implementing one of the attacks in Sage. Experimental results should be analyzed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Advanced Cryptography Reading Assignment Lattice-Based Cryptanalysis

    Uploaded by

    MarioKundit
    61 views3 pages
    This document provides reading assignments on the topic of lattice-based cryptanalysis. It outlines three main sections for students to study: 1) Current records for solving lattice challenges and how to use the Sage mathematics software to perform lattice reduction. 2) Cryptanalysis of a knapsack-based hash function by using LLL lattice reduction to find collisions. Students are asked to implement an attack. 3) Studying the Boneh-Durfee paper on lattice attacks against RSA and implementing one of the attacks in Sage. Experimental results should be analyzed.

    Original Description:

    lijepe latice cvijeca

    Original Title

    Lattices

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides reading assignments on the topic of lattice-based cryptanalysis. It outlines three main sections for students to study: 1) Current records for solving lattice challenges and how to use the Sage mathematics software to perform lattice reduction. 2) Cryptanalysis of a knapsack-based hash function by using LLL lattice reduction to find collisions. Students are asked to implement an attack. 3) Studying the Boneh-Durfee paper on lattice attacks against RSA and implementing one of the attacks in Sage. Experimental results should be analyzed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    61 views3 pages

    Advanced Cryptography Reading Assignment Lattice-Based Cryptanalysis

    Uploaded by

    MarioKundit
    This document provides reading assignments on the topic of lattice-based cryptanalysis. It outlines three main sections for students to study: 1) Current records for solving lattice challenges and how to use the Sage mathematics software to perform lattice reduction. 2) Cryptanalysis of a knapsack-based hash function by using LLL lattice reduction to find collisions. Students are asked to implement an attack. 3) Studying the Boneh-Durfee paper on lattice attacks against RSA and implementing one of the attacks in Sage. Experimental results should be analyzed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Advanced Cryptography Reading Assignment

    Lattice-based Cryptanalysis
    Christophe Petit
    University of Oxford
    January 14, 2016
    The purpose of the following questions is to develop your knowledge and critical
    thinking on particular topics related to lattice-based cryptanalysis. You are required to read the papers cited below and to prepare a 40 min group presentation
    answering all questions. The presentation will be interrupted by discussions to
    check your understanding of the material covered. You are encouraged to split
    the work between you, but everybody must have a good understanding of the whole
    content. Your understanding of this material will be assessed in the mini-project.
    The presentation will take place in Week 5, Friday, 10am.

    1
    1.1

    Lattice reduction in practice


    Current records

    Browse http://www.latticechallenge.org/. What are the largest size of


    lattice challenges that can be solved? Are ideal lattices easier to solve? What
    is the gap between solving exact SVP and approximate SVP? What sort of
    algorithms have been used for the records?

    1.2

    Lattice reduction with Sage

    In Sage, lattices are stored as matrices, where the row vectors of a matrix
    generate the lattice. You can generate random matrices with the function
    random matrix and apply LLL on them with the function LLL.
    Apply the LLL algorithm on random matrices, varying the sizes of the random matrices and the parameter in LLL. Study the impact of these parameters
    on the shortest vector found and on the running time of LLL. Can you explain
    your observations from the theory?

    Cryptanalysis of a knapsack-based hash function

    The following Sage code implements a knapsack-based hash function. The first
    program Parameters(n,mu) generates params used for hashing values from
    {0, 1}n . Larger values of mu increase the output length of the hash function.
    The second program KnapsackHash(A,x) computes the hash of x.
    d e f Parameters ( n ,mu ) :
    A = list ();
    f o r i in range (0 , n ) :
    A. append ( r a n d i n t ( 0 , 2 mu1))
    r e t u r n [ v e c t o r (A) , n ,mu]
    d e f KnapsackHash ( params , x ) :
    A = params [ 0 ]
    n = params [ 1 ]
    mu = params [ 2 ]
    k = c e i l ( l o g ( n , 2 ) ) +mu
    i f n != l e n ( x ) :
    r e t u r n The i n p u t v e c t o r s a r e not t h e same l e n g t h !
    z = 0;
    f o r i in range (0 , len ( x ) ) :
    z = z + A[ i ] x [ i ] ;
    z = z . bits ()
    while len ( z ) < k :
    z . append ( 0 )
    return z
    1. Write a program which takes the output of Parameters and finds a collision on the resulting hash function using the LLL algorithm.
    2. Test your program on params = Parameters(n,mu) for (n, mu) = (10, 10), (20, 20), (40, 40).
    What are the largest values of (n, mu) for which your program finds a collision?

    Lattice attacks on RSA

    Study Boneh-Durfees paper [1] and describe one of their attacks. Implement the
    attack in Sage. Study the performances of your implementation experimentally
    and compare them with the theoretical predictions.

    References
    [1] Dan Boneh and Glenn Durfee. Cryptanalysis of RSA with private key d
    less than N 0.292 . In Jacques Stern, editor, Advances in Cryptology - EU2

    ROCRYPT 99, International Conference on the Theory and Application


    of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 111.
    Springer, 1999.
    [2] Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps
    from ideal lattices. In EUROCRYPT, pages 117, 2013.

    You might also like