Abstrakt. Ett protokoll om nollkunskap ger bevisligen säker enhetsautentisering baserad på ett svårt beräkningsproblem. Bland många system som föreslagits sedan 1984, de mest praktiska förlitar sig på factoring och diskret logg, men ändå är de praktiska system som bygger på NP-hårda problem. Bland dem, problemet SD avkodning linjära koder är trots omkring 30 års forskningsinsatser, fortfarande exponentiellt. Vi studerar ett mer allmänt problem som kallas MinRank som generaliserar SD och innehåller även andra välkända svåra problem. MinRank används också i kryptoanalys av flera offentliga nyckelkryptosystem såsom birationssystem (Crypto'93), HFE (Crypto'99), GPT cryptosystem (Eurocrypt'91), TTM (Asiacrypt'2000) och Chens autentiseringssystem (1996). Vi föreslår ett nytt Zero-kunskapssystem baserat på MinRank. Vi bevisar att det är Zero-kunskap genom Black-box simulering. En motståndare som kan bedra för en given MinRank instans kan antingen lösa det, eller kan beräkna en kollision på en given hash funktion. MinRank är ett av de mest effektiva systemen baserat på NP-fullständiga problem. Det kan användas för att i Zero-kunskap bevisa en lösning på alla problem som beskrivs av multivariata ekvationer. Vi presenterar också en version med en offentlig nyckel som delas av några användare, som tillåter anonyma gruppsignaturer (även känt som. ringsignaturer).
Courtois Ref konstruerar ett ringsignatursystem baserat på ett protokoll för MinRank-problemet.
Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MiniRank
{'venue': 'ADVANCES IN CRYPTOLOGY – ASIACRYPT 2001, VOLUME 2248 OF LECTURE NOTES IN COMPUTER SCIENCE', 'journal': None, 'mag_field_of_study': ['Computer Science']}