A ciphertext-Only Attack on Polly Two Rainer Steinwandt



Yüklə 382 Kb.
tarix30.10.2018
ölçüsü382 Kb.
#76707


A Ciphertext-Only Attack on Polly Two

  • Rainer Steinwandt


Polly Cracker

  • Conceptual public key encryption scheme introduced by Fellows and Koblitz (‘94)

  • Basic idea over Fq[x]:=Fq[x1,…,xn] :

    • Public key: finite basis of ideal I ≤Fq[x]
    • Secret key: common root ξV(I)
    • Encrypting mFq: choose representative of m+I
    • Decrypting cFq[x]: evaluate c at ξ
  • Can we get an encryption scheme out of this?



Security of Polly Cracker

  • Polly Cracker by definition homomorphic  we can’t expect IND-CCA

  • (S., Geiselmann: CCA easily reveals ξ)

  • IND-CPA has not been achieved so far:

  • no security proofs for encryption, various successful attacks, e.g.,

    • intelligent linear algebra (Lenstra)
    • differential attack (Hofheinz, S.)
    • improved diff. attack (Levy-dit-Vehel, Perret)
  • Can we obtain an efficient heuristic scheme?



A Proposal Resistant to Lin. Alg.

  • Levy-dit-Vehel, Perret ‘04:

  • “Reasonably efficient” Polly Cracker system based on 3-SAT:

  • elaborate key generation

  • encryption procedure designed to resist intelligent linear algebra attack,

  • … but the authors note that

  • “the attack … and the improvement we have described… apply to our system too.”



Polly Two

  • Ly (‘02) proposes a new related scheme:

  • Domain parameters: g1,…,gtFq[x] s.t. kernel of φ: Fq[y]  Fq[x]

  • yi  gi

  • can be computed easily (syzygies of the gi)

  • Public key: sparse generators of I ≤ Fq[y]

  • Secret key: ξFqn with (gi(ξ))iV(I) and

  • (g1 ∙…∙gt)(ξ)≠0



Polly Two (cntd.)

  • Encrypting mFq with public basis {f1,…,fs}:

  • Fix random hi:= αi∙yηi with monomials in

  • c’’:=Σhifi

  • getting canceled.

  • 2. For each monomial of c’’ find a ker(φ)-element canceling it. In

  • c’:=c’’+r (with rker(φ))

  • none of c’’ ‘s monomials should occur.

  • 3. Choose monomial yκ in c’ to get ciphertext

  • c:=(c’+m∙yκ, κ)

  • Decryption: evaluate at g(ξ) & divide by g(ξ)κ



Design Rationale

  • sparse high-degree public polynomials impede direct Gröbner basis computation

  • (cf. ENROOT)

  • addition of ker(φ)-element hampers linear algebra attack

  • message expansion more or less acceptable

  • promising proposal to dodge known attacks

  • … is “the list” complete?  Grassl, S. ‘04: low-degree elements in radical of public ideal allow to solve 1st challenge



“Challenge #2”

  • Domain param.: 11 quadratic binomials over F223

  • Public basis: 4 trinomials, total deg. 128,

  • 11 indeterminates

  • Ciphertext c: 126 terms, total deg. 256

  • (indermediate ciphertext c’’: ≤6 terms)

  • Goal of attack: reconstruct encryption step

  • no recovery of secret (or equivalent) key



Recovering the ker(φ)-Part

  • All terms of the ker(φ)-elements canceling

  • terms in Σhifi should occur in c up to

  • – the canceled term

  • (- a term involving yκ )

  • omit yκ –term from ciphertext c

  • &

  • identify terms of the ≤6 ker(φ)-elements

  • How can we find the terms of a syzygy?



Choice of ker(φ)-Polynomials

  • Likely construction for ker(φ)-elements used in encryption: multiply low-degree syzygy with a term α∙yη

  • fix a term β∙yσ of yκ –free ciphertext ĉ and compute multiset

  • {gcd(yσ, yπ): yπ≠yσ a monomial in ĉ}

  • high multiplicity (say >10) yields yη-candidate

  • Challenge: 137 candidates for yη … only 22 after removing multiples



Finding the Terms of a Syzygy

  • Given a yη-candidate, we can find the terms

  • {β∙yσ : β∙yσ is a term of ĉ divisible by yη}.

  • … summing (almost) all of them up should yield “a ker(φ)-element up to one term”.

  • How can we check whether a polynomial is a “syzygy up to one term”?



Validating an “Almost Syzygy” r

  • … in principle: evaluate r at g(x) &

  • check whether r(g1(x),…,gt(x)) is

  • (up to a const.) a power product of the gi

  • … in practice: specialize some xj’s to

  • constants before trial division.

  • In this way we find the missing term, too

  • (& can validate through repeated evaluation).



… Indeed It Works

  • Applying the idea to the challenge:

  • Candidate term sets have ≈20 terms &

  • adding one of these sets up yields 1st syzygy

  • subtract syzygy from ĉ & iterate

  • Five syzygies can be found easily, leaving us

  • with a simplified ĉ consisting of 27 terms.



Recovering the Secret Terms hi

  • Tempting: Apply “differential attack” of

  • Hofheinz and S. to simplified ĉ

  • yields only one term h2

  • … but a simple approach turns out to suffice:

  • Remaining public key polynomials contain term with only two multiples in simplified ĉ.

  • recovery of all secret terms hi



… Getting the Plaintext

  • Subtracting Σhifi + found ker(φ)-part from the ciphertext, yields (short) polynomial that up to the term -m∙yκ is a syzygy.

  • Complete missing term as before to get m.

  • Plaintext underlying the example: 308834



Conclusion?

  • Ample evidence that present form of

  • Polly Two not cryptographically secure.

  • Do we want Polly Two+ with a longer list […, linear algebra, differential attack, small degree in radical, this attack]?

  • Need the assumptions underlying the encryption algorithm to be clarified?



Stronger Attacks?

  • Design of encryption algorithm:

  • hide c’’=Σhifi (by adding a syzygy)

  • This attack: “Playing with terms” reveals c’’

  • Better approaches, e.g.,interpolation?

  • c’’: sparse multivariate polynomial over Fq

  • #terms in c’’ can be guessed

  • bounding tdeg(c’’) not implausible



Sparse Interpolation?

  • Evaluation of c’’+m∙yκ:

  • possible on the variety parameterized by

  • the domain parameters g1,…,gt.

  • Question:

  • Under which assumptions is this kind of

  • interpolation problem feasible?



Yüklə 382 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə