Encryption, trapdoor generation and pattern detection methods and devices

A method implemented by a device and comprising:

• encryption method implemented by a device in an encryption system defining a public key, to obtain a cipher by encryption of data including at least u elementary characters m[i], the public key pk including:
• elements gc,i for any integer i between 1 and an integer u, the elements gc,i being of the form g{circumflex over ( )}(ac,i) where ac,i is an integer between 0 and an integer p-1 and g a generator of a group G of order p;
• elements hk, for any integer k between 1 and an integer t, the elements hk being of the form g{circumflex over ( )}(1/bk) where bk is an integer between 0 and p-1;
• the generator g;
• a description of the group G;
• and
• a description of a function H with a value in a finite set,
• said method including:
• selecting an integer a between 0 and p-1;
• calculating for any integer k between 1 and t, a value Ek=H(hk{circumflex over ( )}(a));
• calculating for any integer i between 1 and u, a value Ci equal to gm[i],i{circumflex over ( )}a;
• and
• obtaining the cipher, said cipher consisting of the elements {Ek, Ci}.

A method implemented by a device and comprising:

• detecting, in an encryption system, a pattern in a cipher obtained by encryption of data, said pattern comprising elementary characters w[1], . . . w[v] comprised in an alphabet supplemented by a special character that can replace any character of said alphabet, the detecting comprising:
• obtaining a trapdoor associated with said pattern;
• calculating an element Q=C1{circumflex over ( )}r1* . . . *Cv{circumflex over ( )}rv with ri=0 if w[i] is said special character and ri=r otherwise;
• calculating a value D equal to Q{circumflex over ( )}(1/T), where T is an element of said trapdoor;
• calculating a value H(D) where H is a function H with a value in a finite set;
• calculating that the data include said pattern if H(D) is equal to Es, where s is an integer comprised in said trapdoor.

A device for detecting, in an encryption system, presence of a pattern in a cipher obtained by encryption of data, said pattern comprising elementary characters w[1], . . . w[v] comprised in an alphabet supplemented by a special character that can replace any character of said alphabet, the device comprising:

• at least one processor;
• and
• at least one non-transitory computer readable medium comprising instructions stored thereon which when executed by the at least one processor configure the device to detect the presence of the cipher, the detecting comprising:
• obtaining a trapdoor associated with said pattern;
• calculating an element Q=C1{circumflex over ( )}r1* . . . *Cv{circumflex over ( )}rv with ri=0 if w[i] is said special character and ri=r otherwise;
• calculating a value D equal to Q{circumflex over ( )}(1/T), where T is an element of said trapdoor;
• calculating a value H(D) where H is a function H with a value in a finite set;
• detecting that the data include said pattern if H(D) is equal to Es, where s is an integer comprised in said trapdoor.