이 논문은 Classic McEliece 공개키에 대해 일반 디코딩보다 저렴한 최초의 구별자를 제시한 GIJS 연구를 확장해, 그 구별자가 이미 계산하는 대규모 희소 선형대수 안에 비밀키 정보가 담겨 있음을 보이고 이를 추출하는 두 가지 방법을 제안한다. 첫 번째는 구별자가 계산하는 다항식의 그래디언트를 이용해 각 열에서 공개 코드의 어떤 부분코드가 생성되는지 증명하고 선형대수로 키를 복원하는 방법이며, 두 번째는 GIJS의 키 복원 방식을 확장해 단 한 번의 실행으로 전체 서포트를 읽어내는 방법이다. 실행 비용을 약 20비트 낮춰 NIST 5개 후보 파라미터 세트 기준 키 복원 비용을 2^94~2^102 비트 연산으로(정보집합 디코딩의 2^151~2^287에 비해) 크게 낮췄으며, 미해결이던 TII McEliece 챌린지 인스턴스 253의 비밀키를 각 700 코어시간의 계산 두 번으로 복원해냈다.

• •GIJS 구별자의 희소 선형대수 계산 안에 비밀키 정보가 담겨 있음을 증명하고 추출법 2가지 제안
• •실행 비용을 약 20비트 절감, NIST 5개 파라미터 세트 기준 키복원 비용을 2^94~2^102 비트연산으로 감소
• •정보집합 디코딩(2^151~2^287) 대비 훨씬 저렴하나 메모리 비용 반영 시 2^110~2^128
• •미해결이던 TII McEliece 챌린지 인스턴스 253을 700 코어시간 계산 2회로 실제 복원