My father-in-law had been raised as a Jew. His 1938 Hungarian passport said "Paul Kemeny, Protestant," though. So he lived, joined the LDS people, and died without any relatives knowing much about his family. Later we would learn that he had sworn his Jewish relatives to keep silence about his background.
In fact, when Hitler came into Budapest, he required all individuals to gather original documents back three generations, which Paul's sister Erzsebeth did. His other sisters, cousins and friends died during WW II; so we had only one contact in Hungary.
Because of the promise to keep silent, we did not make any headway until we began praying about the wording of the letters we wrote to her. In time, she miraculously got her family's 3-generations of original documents to the Hungarian embassy in Washington, D.C., along with 17 pages of a typed manuscript detailing events of their lives. Thank goodness that we started this research as newlywed's or we would have been unable to communicate even with this one elderly lady.
Once my daughter, Suzanne Riddle, got information from this aunt and from the single LDS microfilm covering only 20 years in our ancestors' birthplace, she started using her Internet capabilities. From a chat room and from some other leads, she was able to communicate by email with some other Hungarian researchers. ["Hungarian S.I.G." from www.jewishgen is really helpful for focusing on one geographical area.
She located a digitized record of survivors in Budapest, some notes that had been compiled in about 1950. Searching that website helped her find a sister-in-law who had gone to live with the aunt and other ancestors. Knowing where they lived after the War helped her identify which of the many people with that surname actually was the correct relative.
Some of the former Soviet satellite countries, however, have started restricting access to some original records in the past couple of years, she said.
I listened to a speaker from the US National Archives in Maryland / Washington DC. He said that in his department, on any given day, he will hear more people speaking in German than in English. These German citizens say that the records in the National Archives are more complete than the records in Germany. Turns out that the US required the Germans to turn over all their records having to do with the War and they were "sealed" by treaty for 50 years. In the 1990's people began coming to the Nat'l Archives to research these German microfilmed records of forced labor camps, deaths (including cause), and military advancement requests. [No doubt you heard that a Nazi could not get married or get a promotion unless he had turned in an Aryan pedigree chart going back 5-7 generations.]
Of course, many records are missing [for example, in Lithuania, both during WW I and during WW II, some executions were carried out without record-keeping -- masses of people were shot and then buried in a mass grave.] So then it's time to get creative. Warren Blatt has written a comprehensive study on how to determine the town of origin -- see https://www.jewishgen.org/ / FAQ / #10.
Sometimes if you cannot go back, try "going sideways" -- Find the obituary of your dad's sister; since you don't know anything about your dad's father. Maybe that obituary names the town of her birth, back in the old country. Here is another "sideways" approach: try to find the guild hall or church where your immigrant socialized or was married. Sometimes they have kept a detailed history. Sometimes the local library has archived records. These days cemeteries have almost all started compiling records in an online database. See which other friends and relatives were buried near your ancestor.
As a final "sideways approach", select an ancestor with an uncommon surname, enter it in the search box on https://www.rootsweb.com/. If an unknown distant cousin has already researched some of this line, you can get her contact info and write her an email; or look up her phone number and call her. [Messages can be posted for free on the Rootsweb Message Boards.] This website is especially useful for early US colonial settlements and early LDS Pioneer groups.