Abstrakt. Motiverade av representationen av biometriska och multimedia objekt, anser vi problemet med att dölja bullriga punktuppsättningar med hjälp av en säker skiss. En punktuppsättning X består av s punkter från en d-dimensionell diskret domän [0, N −1] d. Under tillåtna ljud, för varje punkt x1,.. x d X, varje xi kan störas av ett värde på högst δ. Dessutom, som mest t punkter i X kan ersättas med andra punkter i [0, N − 1] d. Med tanke på en original X, vill vi beräkna en säker skiss P. En känd metod konstruerar skissen genom att lägga till en uppsättning slumpmässiga punkter R, och beskrivningen av (X  på R) fungerar som en del av skissen. Men beroendena bland de slumpmässiga punkter är svåra att analysera, och det finns ingen känd icke-trivial bunden på entropi förlust. I detta dokument ger vi först en allmän metod för att generera R och visar att entropiförlusten av (X  på R) är som mest s(d log  till + d + 0.443), där  till = 2δ + 1. Vi ger därefter förbättrade system för d = 1, och specialfall för d = 2. Sådana förbättringar uppnås genom föravrundning, och noggrann uppdelning av domänerna i celler. Det är möjligt att göra vår skiss kort, och undvika att använda slumpmässighet under konstruktion. Vi ger också en metod i d = 1 för att visa att, med hjälp av storleken på R som säkerhetsåtgärden skulle vara vilseledande.
Säkra skissscheman för punktuppsättningar i Ref motiveras av den typiska likhetsmått som används för fingeravtryck, där varje mall består av en uppsättning punkter i 2-D-utrymme och likhetsmåttet inte definierar ett metriska utrymme.
Hiding secret points amidst chaff
{'venue': 'in Eurocrypt', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}