On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.)
We consider the following problem: Let s be a n-bit string with m ones and n-m zeros. Denote by CEt(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of Cet(*), when the minimum is taken over all n-bit strings which consists of m ones...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149066 |
| _version_ | 1826198445385318400 |
|---|---|
| author | Goldreich, Oded |
| author_facet | Goldreich, Oded |
| author_sort | Goldreich, Oded |
| collection | MIT |
| description | We consider the following problem: Let s be a n-bit string with m ones and n-m zeros. Denote by CEt(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of Cet(*), when the minimum is taken over all n-bit strings which consists of m ones and n-m zeros? We prove a (reasonably) tight lower bound for this combinatorial problem. Implications, on the cryptographic secruity of the least significant bit of a message encrypted by the RSA scheme, follow. E.g. under the assumption that the RSA is unbreakable; there exist no probabilistic polynomial-time algorithm which guesses the least significant bit of a message (correctly) with probability at least 0.725, when given the encryption of the message using the RSA. This is the best result known concerning the security of RSA's least significant bit. |
| first_indexed | 2024-09-23T11:05:04Z |
| id | mit-1721.1/149066 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:05:04Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490662023-03-30T03:56:33Z On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) Goldreich, Oded We consider the following problem: Let s be a n-bit string with m ones and n-m zeros. Denote by CEt(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of Cet(*), when the minimum is taken over all n-bit strings which consists of m ones and n-m zeros? We prove a (reasonably) tight lower bound for this combinatorial problem. Implications, on the cryptographic secruity of the least significant bit of a message encrypted by the RSA scheme, follow. E.g. under the assumption that the RSA is unbreakable; there exist no probabilistic polynomial-time algorithm which guesses the least significant bit of a message (correctly) with probability at least 0.725, when given the encryption of the message using the RSA. This is the best result known concerning the security of RSA's least significant bit. 2023-03-29T14:24:18Z 2023-03-29T14:24:18Z 1984-03 https://hdl.handle.net/1721.1/149066 MIT-LCS-TM-256 application/pdf |
| spellingShingle | Goldreich, Oded On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title | On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title_full | On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title_fullStr | On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title_full_unstemmed | On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title_short | On the Numbers of Close-and-equal Pairs of Bits in a String (with Implications on the Security of RSA'S L.S.B.) |
| title_sort | on the numbers of close and equal pairs of bits in a string with implications on the security of rsa s l s b |
| url | https://hdl.handle.net/1721.1/149066 |
| work_keys_str_mv | AT goldreichoded onthenumbersofcloseandequalpairsofbitsinastringwithimplicationsonthesecurityofrsaslsb |