Question $6.$ Since that didn't work, let's try the next smallest vector by

extracting the second row of the LLL$-$reduced NTRU matrix. Run

$v=L*row(1)$

$f2=R(list(v[0$:$N]))$

$g2=R(list(v[N$:$2**N]))$

Confirm that $Rq(f2)**h$ and $Rq(g2)$ are the same polynomial, then use these

this key to decrypt Alice's message e $2$ to Bob.

def T$($d$1,$d$2,$N$)$:

$"""$

Returns a random ternary polynomial in ZZ$[$z$]$ with:

d$1$ coefficients that equal $+1$

d$2$ coefficients that equal $-1$

$"""$

if d$1+$ d$2>$ N:

raise$($ValueError$,"$d$1+$ d$2$ cannot exceed N$")$

R$.=$ PolynomialRing$($ZZ$)$

S $=$ Set$($range$($N$+1))$

pos $=$ S$.$subsets$($size$=$d$1).$random$\_$element$()$

S$2=$ S $-$ pos

neg $=$ S$2.$subsets$($size$=$d$2).$random$\_$element$()$

v $=[0$ for i in range$($N$+1)]$

for i in pos:

v$[$i$]=1$

for i in neg:

v$[$i$]=-1$

return R$($v$)$

def centerlift$($f$)$:

R$.=$ PolynomialRing$($ZZ$)$

P $=$ f$.$parent$().$base$\_$ring$().$cardinality$()$

return R$([$ mod$($t$,$ P$).$lift$\_$centered$()$ for t in f$])$

def encode$($s$)$:

$"""$

Encode the message ASCII string s as a polynomial m$($x$)$ in R$\_$p$.$

Uses environment variables p and N$.$

$"""$

s $=$ str$($s$)$

k $=$ N$*$log$($p$,128)$

if len$($s$)>=$ k:

raise$($ValueError$,$ "String too long. Max length in R$\_$p is $"+$ str$($floor$($k$)))$

t $=$ sum$($ord$($s$[$i$])*128^$i for i in range$($len$($s$)))$

return Rp$($t$.$digits$($base$=$p$))$

def decode$($m$)$:

$"""$

Decode the polynomial m$($x$)$ in R$\_$p$.$

$"""$

mc $=$ list$($m$)$

# Remember, mc$[$i$]$ belongs to GF$($p$).$ Lift to integers!

c $=$ sum$($Integer$($mc$[$i$])*$p$^$i for i in range$($len$($mc$)))$

v $=\text{'}\text{'}.$join$([$ chr$($x$)$ for x in Integer$($c$).$digits$($base$=128)])$

return v

def circulantmatrix$($a$)$:

$"""$

Returns the matrix whose ROWS are the rotations of the vector a:

$($ a$[0]$ a$[1]...$ a$[$n$-1])$

$($ a$[$n$-1]$ a$[0]...$ a$[$n$-2])$

$(......)$

$($ a$[1]$ a$[2]...$ a$[0])$

$"""$

n $=$ len$($a$)$

R $=$ range$($n$)$

return matrix$([[$ a$[($j$-$k$)\%$ n $]$ for j in R $]$ for k in R $])$

def NTRUmatrix$($h$)$:

$"""$

Returns the NTRU lattice matrix associated to the public key

$($N$,$p$,$q$,$d$)$ and h$($y$)$ in R$\_$q$,$ in row form.

This matrix is$,$ in ROW form, the $2$N x $2$N block matrix:

$($ I H $)$

$(0$ qI $)$

where H is the circulant matrix generated by the coefficients of h

as a vector.

$"""$

hv $=$ list$($centerlift$($h$))$

H $=$ circulantmatrix$($hv$)$

I $=$ identity$\_$matrix$($ZZ$,$ N$)$

O $=$ zero$\_$matrix$($ZZ$,$ N$)$

return block$\_$matrix$([[$I$,$ H$],[$O$,$ q$*$I$]])$

### End of functions block ###

###################################################

#################### PROBLEMS $2$ onwards ####################

#################### Alice's public key ####################

p $=723829$

q $=414165413$

N $=151$

d $=30$

R$.=$ PolynomialRing$($ZZ$)$

Sp$.=$ PolynomialRing$($GF$($p$))$

Rp$.=$ Sp$.$quotient$($Y$^$N $-1)$

Sq$.=$ PolynomialRing$($GF$($q$))$

Rq$.=$ Sq$.$quotient$($Z$^$N $-1)$

h $=292154189*$z$^150+301473751*$z$^149+7992279*$z$^148+256274577*$z$^147+138291792*$z$^146+213244800*$z$^145+66018664*$z$^144+216541653*$z$^143+365219395*$z$^142+82857950*$z$^141+128660538*$z$^140+293420876*$z$^139+73203043*$z$^138+260799189*$z$^137+359907246*$z$^136+349417304*$z$^135+102642608*$z$^134+118603125*$z$^133+409669254*$z$^132+94999973*$z$^131+11465625*$z$^130+228101539*$z$^129+109606852*$z$^128+83282299*$z$^127+398988836*$z$^126+42736600*$z$^125+48009769*$z$^124+188832192*$z$^123+75400492*$z$^122+238286103*$z$^121+27338506*$z$^120+21309908*$z$^119+109080944*$z$^118+75580822*$z$^117+370783439*$z$^116+64338600*$z$^115+140857785*$z$^114+197109864*$z$^113+239817418*$z$^112+384329482*$z$^111+329530957*$z$^110+77994009*$z$^109+2901367$

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

MATHEMATICS FOR MACHINE LEARNING Marc Peter Deisenroth A. Aldo Faisal Cheng Soon Ong Contents Foreword 1 Part I Mathematical Foundations 9 1 Introduction and Motivation 11 1.1 Finding Words for...

Q:

Python and most Python libraries are free to download or use, though many users use Python through a paid service. Paid services help IT organizations manage the risks associated with the use of...

Q:

Jupiter Notebook We have covered some of the limitations of single layer neural networks in class, but they are still powerful learning systems that provide a good way to begin learning about how to...

Q:

Conduct an internet search to find an organization that lists its mission and vision statement on its website. What do the mission and vision statements communicate? How might the organization use...

Q:

i got 7 questions in the assignment in the PDF file on P16-17 They are all about the case story The total of the words are 1500 words without any format QUEENSLAND UNIVERSITY OF TECHNOLOGY QUT...

Q:

Accuracy in Matlab and Condition Number For most systems of linear equations, we can get an answer with enough accuracy fast enough in a number of different ways, and we don't even bother with trying...

Q:

BLC Inc. is a medium-sized manufacturing company based in the UK. The company operates mainly in the London area and is based in Peterborough. At a recent board meeting, the company decided to expand...

Q:

its a matlab assignment Question 3. Matrix Addition and Matrix-Vector Multiplication Generate vectors u and v and matrices A and B by typing...

Q:

The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...

Q:

from the following podcast pick one of the podcasts and briefly provide some thoughts on it in the context of the topic of leadership. PODCAST Support for this podcast and the following message comes...

Q:

You are buying a car. No Better Deals will give you $500 off the list price on a $10,000 car. a. You can get the same car from Best Deals if you pay $4,000 down and the rest at the end of two years....

Q:

Suppose that there is a 3%per year chance that the firms asset value can jump to zero. Assume that the firm issues 5-year zero-coupon debt with a promised payment of $110. Using the Merton jump...

Q:

Identify which of the following statements is true. Question content area bottom Part 1 A. A partnership cannot have an NOL carryback or carryforward. B. A partnership cannot make charitable...

Q:

.The graph of a quadratic function passes through (1,7) and has a vertex at (4, 16). Find the equation of the parabola. Write it in vertex form y = a(xh) + k. Type a response

Previous Question Next Question